I know that say given a md5/sha1 of a value, that reducing it from X bits (ie 128) to say Y bits (ie 64 bits) increases the possibility of birthday attacks since information has been lost. Is there any easy to use tool/formula/table that will say what the probability of a "correct" guess will be when that length reduction occurs (compared to its original guess probability)?
A:
Well, since every extra bit in the hash provides double the number of possible hashes, every time you shorten the hash by a bit, there are only half as many possible hashes and thus the chances of guessing that random number is doubled.
128 bits = 2^128 possibilities
thus
64 bits = 2^64
so by cutting it in half, you get
2^64 / 2^128 percent
less possibilities
erjiang
2009-08-06 18:01:17
I don't think that md5 or sha1 guarantee an equal amount of entropy (randomness) for any subset of the hash. If this is the case, the uniform probability distribution won't apply.
Dana the Sane
2009-08-06 18:23:52
I would have to agree, but to avoid people doing this kind of cutting seems like there should be a brain-dead table that says how bad it gets when you try (with various algorithms)
JH
2009-08-06 21:16:17
Update: Upon re-examining md5, it's apparent that each 32-bit section is calculated separately. If you really wanted to cut down a 128-bit MD5 hash, best do it every 2 or 4 bits. Of course, best not do it at all if you need security.
erjiang
2009-08-07 14:14:13
+1
A:
Crypto is hard. I would recommend against trying to do this sort of thing. It's like cooking pufferfish: Best left to experts.
So just use the full length hash. And since MD5 is broken and SHA-1 is starting to show cracks, you shouldn't use either in new applications. SHA-2 is probably your best bet right now.
Jason Creighton
2009-08-06 18:29:21
I agree that its hard, but without making it easy for "normal" people to understand the consequences of doing this, then it will continue to occur. I know there are consequences, but to convince others that u can't really just cut half the bits and expect half the "quality" of the original.
JH
2009-08-06 21:15:02
+1
A:
I would definitely recommend against reducing the bit count of hash. There are too many issues at stake here. Firstly, how would you decide which bits to drop?
Secondly, it would be hard to predict how the dropping of those bits would affect the distribution of outputs in the new "shortened" hash function. A (well-designed) hash function is meant to distribute inputs evenly across the whole of the output space, not a subset of it.
By dropping half the bits you are effectively taking a subset of the original hash function, which might not have nearly the desirably properties of a properly-designed hash function, and may lead to further weaknesses.
Peter
2009-08-06 18:35:12
But without quantifying what the effect is it will be hard to convince people they shouldn't do it.
JH
2009-08-06 21:18:04