undefined | Better HN

0 pointsStavrosK15y ago0 comments

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.

0 comments

2 comments · 1 top-level

Xk15y ago· 1 in thread

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.

StavrosKOP15y ago

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.

j / k navigate · click thread line to collapse