A better way to store password hashes? (2012)

opine.me

7 pointslclemente3 comments

> To brute force even a single user’s password, the attacker would have to search the entire Hashes table after each iteration.

The attacker can use a bloom filter to avoid this.

Interesting, could you give a quick explanation how this could work?

Bloom filter:

A quick way to do a probabilistic check of if an element is in a set.

Setup: Take the hash of each element in the set, bitwise-or them together.

Lookup: Take the hash of the element you wish to lookup. If any of the bits that are on in this hash are off in the Bloom filter, you know that the element is not in the set. Otherwise, the element is probably in the set, but could be a false positive.

By choosing the length of the hash and the hash function, you end up with ~10 bits/element for a 95% success rate.

As most of the password hashes will be misses, this is an ideal situation. The only time you actually need to do the slow lookup is when a password is a hit.

Reply on news.ycombinator.com