Limitations of Hashing

Don’t Hash Secrets (via). Informative, accessible article that sketches the limitations of hashing, even with a salt.

I’d like to add a few annotations:

An attacker can build up a huge dictionary of hashed passwords just once, and, when he breaks into your web site, check the hashes against this pre-built dictionary.

This set of pre-computed passwords is often referred to as a rainbow table. As the article stated, salting complicates such an attack.

But it’s going to be darn hard for you to find any other document, big or small, that hashes to the same 30 characters.

[…]

In fact, you can try something that should be easier: rather than find another document that hashes specifically to those 30 characters that represent your baby, you can go looking for any two documents that happen to hash to the same thing (collide). And you won’t find any such pair. Promised. We call that “collision resistance”.

More specifically, the first paragraph refers to weak collision resistance, and the second refers to strong collision resistance. If a hash function has the property of strong collision resistance, this implies that it also has weak collision resistance, but not the other way around. In some (most?) applications, including storing passwords, weak collision resistance is sufficient. So it’s worth thinking twice before throwing out your favorite hash function (SHA1) if (when) someone breaks strong collision resistance on it.