Birthday attacks and hashed passwords
Posted: Tue Jan 23, 2007 5:29 pm
Could someone please explain to me how birthday attacks have anything to do with hashed passwords?
The birthday attack states that the probability that, in a pool of randomly selected values, there are two values are the same is much higher than most people expect. However, we have no previous knowledge of what these two values are, or what the collision will be. We just know that there's a high chance that there will be one.
However, from the perspective of someone who has a hash and wants to find the password it was generated from, the birthday attack doesn't apply: you already have one half of the pair, whereas a birthday attack requires that you have no preconceptions on the concept. Attacks that let you take the hash and find the message are called preimage attacks, and are mostly non-existent right now.
Thus, while from a cryptography/encryption standpoint the collisions that MD5 and SHA1 have are fairly worrying, they are irrelevant with regards to password obfuscation, and although in the future we may find out that there are indeed preimage attacks against these, with a hearty helping of salt (preferably binary and long) to ward off rainbow tables they are just as secure as SHA-256.
Hmm...
The birthday attack states that the probability that, in a pool of randomly selected values, there are two values are the same is much higher than most people expect. However, we have no previous knowledge of what these two values are, or what the collision will be. We just know that there's a high chance that there will be one.
However, from the perspective of someone who has a hash and wants to find the password it was generated from, the birthday attack doesn't apply: you already have one half of the pair, whereas a birthday attack requires that you have no preconceptions on the concept. Attacks that let you take the hash and find the message are called preimage attacks, and are mostly non-existent right now.
Thus, while from a cryptography/encryption standpoint the collisions that MD5 and SHA1 have are fairly worrying, they are irrelevant with regards to password obfuscation, and although in the future we may find out that there are indeed preimage attacks against these, with a hearty helping of salt (preferably binary and long) to ward off rainbow tables they are just as secure as SHA-256.
Hmm...