Skip to main content
replaced http://security.stackexchange.com/ with https://security.stackexchange.com/
Source Link

What you're talking about is known as the pigeonhole principle - if you have n possible passwords and a hash function with m possible outputs, where n > m, there will always be some input values which produce the same output hashes.

The question then becomes: does this matter? With a hash output space of 2160 possible values, an accidental collision has a probability of about 6.842×10-49. Not a whole lot. This gets more interesting when you look into birthday attacks, because the probabilities get much higher, but it's still generally considered infeasible to find 160-bit collisions using naive methods such as brute-force.

In reality, a smart attacker is more likely to focus upon vulnerabilities within the hash function which reduce the necessary computation in order to find a collision. But, in the arena of password storage, this should mostly be moot - passwords are easy to crack if you only hash them with SHA1, because GPUs can brute-force at a rate of billions of hashes per second due to their massively parallel nature.

If you want to store passwords safely, don't use a hash. Use a key-derivation algorithm designed for password storage, such as PBKDF2 or bcrypt. You should also take a look at a related answera related answer I wrote about salted hashes, which goes into the history of how we progressed from hashes, to salted hashes, onto modern KDFs, and the rationales behind each defense and attack step.

What you're talking about is known as the pigeonhole principle - if you have n possible passwords and a hash function with m possible outputs, where n > m, there will always be some input values which produce the same output hashes.

The question then becomes: does this matter? With a hash output space of 2160 possible values, an accidental collision has a probability of about 6.842×10-49. Not a whole lot. This gets more interesting when you look into birthday attacks, because the probabilities get much higher, but it's still generally considered infeasible to find 160-bit collisions using naive methods such as brute-force.

In reality, a smart attacker is more likely to focus upon vulnerabilities within the hash function which reduce the necessary computation in order to find a collision. But, in the arena of password storage, this should mostly be moot - passwords are easy to crack if you only hash them with SHA1, because GPUs can brute-force at a rate of billions of hashes per second due to their massively parallel nature.

If you want to store passwords safely, don't use a hash. Use a key-derivation algorithm designed for password storage, such as PBKDF2 or bcrypt. You should also take a look at a related answer I wrote about salted hashes, which goes into the history of how we progressed from hashes, to salted hashes, onto modern KDFs, and the rationales behind each defense and attack step.

What you're talking about is known as the pigeonhole principle - if you have n possible passwords and a hash function with m possible outputs, where n > m, there will always be some input values which produce the same output hashes.

The question then becomes: does this matter? With a hash output space of 2160 possible values, an accidental collision has a probability of about 6.842×10-49. Not a whole lot. This gets more interesting when you look into birthday attacks, because the probabilities get much higher, but it's still generally considered infeasible to find 160-bit collisions using naive methods such as brute-force.

In reality, a smart attacker is more likely to focus upon vulnerabilities within the hash function which reduce the necessary computation in order to find a collision. But, in the arena of password storage, this should mostly be moot - passwords are easy to crack if you only hash them with SHA1, because GPUs can brute-force at a rate of billions of hashes per second due to their massively parallel nature.

If you want to store passwords safely, don't use a hash. Use a key-derivation algorithm designed for password storage, such as PBKDF2 or bcrypt. You should also take a look at a related answer I wrote about salted hashes, which goes into the history of how we progressed from hashes, to salted hashes, onto modern KDFs, and the rationales behind each defense and attack step.

Source Link
Polynomial
  • 135.8k
  • 44
  • 309
  • 383

What you're talking about is known as the pigeonhole principle - if you have n possible passwords and a hash function with m possible outputs, where n > m, there will always be some input values which produce the same output hashes.

The question then becomes: does this matter? With a hash output space of 2160 possible values, an accidental collision has a probability of about 6.842×10-49. Not a whole lot. This gets more interesting when you look into birthday attacks, because the probabilities get much higher, but it's still generally considered infeasible to find 160-bit collisions using naive methods such as brute-force.

In reality, a smart attacker is more likely to focus upon vulnerabilities within the hash function which reduce the necessary computation in order to find a collision. But, in the arena of password storage, this should mostly be moot - passwords are easy to crack if you only hash them with SHA1, because GPUs can brute-force at a rate of billions of hashes per second due to their massively parallel nature.

If you want to store passwords safely, don't use a hash. Use a key-derivation algorithm designed for password storage, such as PBKDF2 or bcrypt. You should also take a look at a related answer I wrote about salted hashes, which goes into the history of how we progressed from hashes, to salted hashes, onto modern KDFs, and the rationales behind each defense and attack step.