Hacker News Reader

Comment by whoami_nr | Hacker News Reader

I am not an expert on password hashing but I was wondering why can't the websites hash their passwords twice using two different hash algorithms. That way when the hashes are exposed, the attackers have to go through two algorithms. Is the time complexity increase only marginal that people don't do this ?

View on HN

https://link.springer.com/chapter/10.1007%2F978-3-540-28628-...

https://link.springer.com/content/pdf/10.1007%2F978-3-540-28...

Abstract:

"In this paper, we study the existence of multicollisions in iterated hash functions. We show that finding multicollisions, i.e. r-tuples of messages that all hash to the same value, is not much harder than finding ordinary collisions, i.e. pairs of messages, even for extremely large values of r. More precisely, the ratio of the complexities of the attacks is approximately equal to the logarithm of r. Then, using large multicollisions as a tool, we solve a long standing open problem and prove that concatenating the results of several iterated hash functions in order to build a larger one does not yield a secure construction. We also discuss the potential impact of our attack on several published schemes. Quite surprisingly, for subtle reasons, the schemes we study happen to be immune to our attack."

Shouldn't the reduction is input space for the subsequent hash functions actually make it easier to find collisions ? Or is finding collisions not closely related to input space ?

The paper is a bit above my level of understanding and I tried making sense of how the cryptanalysis is done to no avail.

In that paper they're concatenating two hash outputs which obviously (right?) only makes it easier to reverse the hash - the attacker need only pick whichever hash he can work with quicker, and find the preimage for that. Given the fact that password entropy is much lower than hash entropy, the preimage thus found is almost certainly the original password, not a collision - rendering solving the other hash preimage moot.

If you want to force the attack to go through two hashes, you'd use functions sequentially (e.g. F(G(input)), not F(input)+G(input)), which the paper at least initially doesn't talk about. I didn't read the whole thing, mind you...

Note that password-stretchers like bcrypt/PBkdf2 use only fairly small extensions to this idea, so clearly in general the construction isn't known to be flawed.

There's no actual need for two algorithms -- you can just hash them with the same algorithm twice. This is essentially what PBKDF2 does, hashing the password a configurable number (thousands) of times. It's a little more complicated than that, but that's why you should not just use a hash, but a KDF like PBKDF, scrypt, bcrypt -- they'll do what you're suggesting and more. They are exactly designed to make it a bunch of work for an attacker to guess-and-check your passwords.

Instead of the added complexity of implementing multiple hash algorithms, if you're using something like bcrypt or PBKDF2 you can just increase the work-factor which makes the attacker (or indeed your application) do more work to calculate the hash.

There's a risk, depending on your usecase and traffic levels that if you crank work factors too high, you can impact the users perception of your performance (e.g. a login operation might appear slow)

Which is actually better in terms of time required to brute force(as in which takes longer) ? Two different fast algorithms with moderate work factors or one algorithm with a pretty high work factor ?

well AFAIK you can keep cranking the work factor as high as you like, so realistically one algorithm with a high work factor is likely to be better as it's a simpler thing to implement and has no drawbacks in terms of security.

I think that's more security through obscurity rather than difficulty.

Once the attacker figures out what the 2 hashing algorithms are, the scenario basically becomes the same as cracking hashes of 1 algorithm of increased difficulty (through number of passes)

So, like the other answer implied, the increased complexity of maintaining 2 algorithms might not be worth the obscurity trade-off in the end.

However, I am not a security professional either, so perhaps my opinion is not comprehensive enough.

I'm not sure how modern hashes fare in this regard, but one issue is that hashing a hash reduces your input space from all possible passwords to all possible hashes of the first hasher.

In my experience, it wouldn't be a reduction. I.e. most passwords are shorter than most hashes.

Technically, it does actually. Suppose we use SHA-256 as first hashing algorithm, the input space for the second is effectively reduced to the 256 bits of output from the first which is much smaller compared to the input space of the first algorithm.

38 characters of ASCII gibberish (all 95 printable characters) gives you less than 2^256 possible passwords, and pretty much nobody uses a password with more entropy than that.

The problem is that you aren't just dealing with "any output from the first hashing algo", since passwords are going into that algo in the first place. A hashing algo can't add entropy, but collisions can reduce it.

An undetected I/O error is vastly more likely than even one accidental SHA-256 collision among billions of passwords. It's not quite literally impossible but I'd bet my car I never see it happen.

Reply on news.ycombinator.com