1

To protect passwords a website uses a hashing function before storing the password (This is just an example of a very simple hash function):

f(x) = x mod 10

Passwords are hashed before they are stored in the database and then when a user logs in the password input field is hashed and compared with the one in the database.

If the user's password is 17, then 17 mod 10 = 7 is what is stored in the database. If the user types in 17 when logging in then it will hash to 7 and work correctly. However, couldn't 27, 37, 47 ... wouldn't there be lots of passwords also hash to 7 so they would correctly authenticate?

Melkor
  • 1,285
  • 2
  • 10
  • 12

1 Answers1

3

All hash functions - except perfect hash functions - have collisions, because hashing normally maps a larger set of inputs to a smaller set of outputs.

That being said, mod 10 is an awful function for hashing passwords as the amount of collisions are unacceptable in practice.

Apart from that, it is also unacceptable because it is too fast, and because it is incredibly easy to find a matching input (because you can just use the hash as password, it will always match). You can also not really reduce collisions by increasing the divisor. If you would eg set it to 1000, all input less than 1000 wouldn't actually change.

This is a nice example that not all hash functions are acceptable as cryptographic hash functions.

Cryptographic hash functions need to be preimage resistance, second preimage resistance, and collision resistance.

mod is none of those:

  • Pre-image resistance: Given a hash h, it should be difficult to find any password p such that h = h(p). It's not. p = h will always work.
  • Second pre-image resistance: Given a password p1, it should be difficult to find another password p2 such that h(p1) = h(p2). It's not. p2 = p1 + divisor will work.
  • Collision resistance: It should be difficult to find two passwords p1 and p2 such that h(p1) = h(p2). It's obviously not, given the two previous points.

For acceptable functions, see How to securely hash passwords?.

tim
  • 29,018
  • 7
  • 95
  • 119