March 29, 2007

Breaking SuperFastHash

Filed under: Hashing,Programming,Security — floodyberry @ 3:31 am
Tags: ,

After the problems SuperFastHash had in Hash Algorithm Attacks, I decided to try and break it completely, i.e. generate collisions algorithmically instead of brute forcing them. The attempt was more successful than I had anticipated, although Paul is obviously aware of the weak mixing in the final bits as evidenced by his comment in the source code, “Force ‘avalanching’ of final 127 bits”. My favorite collisions encountered would have to be “10/4 < 3”, “10/5 = 2”, and “10/6 > 1”, which have the property of hashing to the same value while being mathematically correct!

As I was writing this, I came up with a way to attack Bob Jenkins’ lookup3 as well. Unlike SuperFastHash, the lookup3 attack is due to the way the input bytes are being read in and does not indicate a deficiency in the mixing itself. If you are using lookup3 with hash tables, the core function will still be quite safe; it will only need to be modified if you are using it to generate unique 64bit identifiers and the input data could be altered for a malicious purpose.

With that said, let’s look at the attacks:



March 7, 2007

When Bad Hashing Means Good Caching

Filed under: Hashing,Programming — floodyberry @ 1:54 pm

I was testing various string hashing algorithms on chained hash tables, primarily to look at the bucket distribution and number of key comparisons with both prime and power of 2 sized tables. Each table node was set up to remember it’s full hash value so bucket collisions would only drop to a key comparison on a true key collision. I initially wasn’t concerned with run times, but I tacked on a timer anyway so I could get a quick metric on how collisions and distribution were affecting performance and wound up running in to a rather odd situation. (more…)

Blog at