Comment by Xk | Hacker News Reader

Comment by Xk | Hacker News Reader

Parent Full thread

Imagine you have two hash functions F and G, both mapping from the domain of integers to integers mod 2^128. Imagine they are perfect in that if you hash all the integers up to some large N, each hash is expected to recorded exactly the same number of times (probabilistically).

Now clearly if I hash a password F(P) and another password F(Q) there is a 1 in 2^128 chance they collide.

Now imagine we do G(F(P)) and G(F(Q)). We first have the chance of 1 in 2^128 that F(P) == F(Q) which implies G(F(P)) == G(F(Q)). However, that is not all!

We now have a new 1 in 2^128 chance that G(F(P)) == G(F(Q)). So we have (about) a 1 in 2^127 chance that the passwords will collide.

But, none of this really matters. Collisions aren't what you worry about with password hashes.

I see what you mean, and I agree that it doesn't matter, but it's an interesting exercise anyway.

I disagree that there's a 2^128 chance that they will collide. Trivially, I can show you a hash that will never collide for up to some N, and that is F(P) = P mod 2^128. This will never collide unless P is more than 128 bits long.

My rationale, above, was that SHA constrains the space to 128 bits. Therefore, for different SHA hashes (ones that haven't already collided), the probability that bcrypt will collide might be smaller (or zero, as in my example above).

In reality it doesn't work like that, I know, but in theory you can't be sure that the probabilities of collision will add (or, well, multiply) up.

Point taken, it's probably true that the probability that G(F(P)) == G(F(Q)) given F(P) != F(Q) is less than 1 in 2^128. But it's probably also true that it's greater than 0.

Clearly it's impossible to be less than zero. So no matter what you do, Defining H(X) to be G(F(X)) will have strictly more collisions than F(X).

The reason I would argue it's greater than zero is that if a function H existed such that H(X) will never collide for X less than 2^128, it would probably have some cryptographic weakness.

Hmm, you're right indeed, since they're additive. I should have said that the second layer is less likely to collide than the first, not than both combined.

Reply on news.ycombinator.com