Andrew

After my previous post on When Bad Hashing Means Good Caching, I got to thinking about Crosby/Wallach's Denial of Service via Algorithmic Complexity Attacks paper and wondered if any of the algorithms I was looking at were susceptible to induced collisions. While I had never done this before and didn't expect much success, the results were a little surprising.

Method

The basic method I used is the one as described by Crosby and Wallach:

The hash functions used by typical programs for their hash tables are generally not cryptographically strong functions like MD5 or SHA-1. Instead, they tend to be functions with 32 bits of internal state, designed primarily for speed. Because this state is limited, we need only find inputs such that the internal state after hashing is the same as the initial state.

Consider a hash function with the initial state of 0. Imagine we can find generators, or inputs k1,k2, ... ki such that 0 = Hash(k1) = Hash(k2) = ... = Hash(ki). Then the concatenation of any number of these generators in any combination and any order also hashes to 0. So, k1k2 also hashes to 0, as will k1k1 or k2k1k3k2. Thus, by finding three inputs k1, k2, k3 via exhaustive search and concatenating them combinatorially, we can generate a large number of collisions without requiring any additional searching. The number of possible collisions is bounded only by the maximum length to which we are willing to allow concatenated generators to grow.

I adapted this general idea into the following series of steps:

Step 1 - Quick Duplicates

Run through a couple hundred iterations of your test space and choose a few hashes to hopefully duplicate. Then re-run through the test space and watch for the selected hashes; weak algorithms should crack on this step without even needing to permute the duplicates you find.

Step 2 - Permute and Concatenate Duplicates

If you are not finding abundant duplicates with brute force iterations, keep going until you find at least ~20 or so duplicates for 2-3 hashes, then do a cheap permutation and concatenation of each set of keys as described by Crosby and Wallach. If the hash algorithm is weak, the keys may still generate substantial collisions and even provide full collisions without needing to match up initial states.

Step3 - Generating Proper Duplicates for Varied Initial States

To get full collisions with more complicated algorithms, some trickery is needed. This is because you can only ensure a string will generate a specific hash from a specific starting value. Consider the general form of a hash function

function Hash( string, initial value ) {
	hash = initial value
	foreach( string as item ) {
		hash <-> item
	}
	possible finalizer
	return ( hash )
}

Ignoring the finalizer:

Hash(x, A) = B
Hash(y, A) = B
Hash(z, A) = B
Hash(xy) = Hash(x,A) <-> Hash(y,B)
Hash(xz) = Hash(x,A) <-> Hash(z,B)

We have only guaranteed that y and z hash to B when initialized with A, not B! We can not be sure they will even collide with the new initial hash value B. To get around this, we need to:

• Comment out any finalizers. We are only concerned with duplicates within the innerloop
• Generate duplicates keys for the initial hash state A. If the hash is initialized with the length of the input string, we will need to include the length of our target permuted string as well, e.g. using 24 if we are going to permute three 8 character strings.
• Once we have enough duplicates for initial state A, set the initial state to the hash of our duplicate keys and find another set of keys. Rinse and repeat
• Permute and concatenate the generated keys in order.

Hash(x, A) = B
Hash(y, A) = B
Hash(z, B) = C

Hash(xz) = Hash(x,A) <-> Hash(z,B) = C
Hash(yz) = Hash(y,A) <-> Hash(z,B) = C

Results

Target Keyspace

To keep things simple and to be fair to the algorithms only intended for string hashing, I did my testing with lowercase alpha characters, i.e. 'a' - 'z'. Initial key length is 8 characters and the attack key length is a multiple of 8 depending on how many concatenations are performed. When fewer duplicates are found, more concatenations may be needed to generate enough collisions to be statistically interesting.

Algorithms

hash31

for ( i = 0; i < length; ++i )
	hash = ( ( 31 * hash ) + key[i] );

Bruteforcing the keyspace wasn't enough to find enough duplicates in Step 1, but concatenating the duplicates in Step 2 resulted in full collisions. This one was actually took more work to attack than I had figured.

DooM III

for ( i = 0; i < length; ++i )
	hash += ( key[i] * (119 + i) );

I had already known the algorithm was weak from previous testing (it turns useless for large table sizes), but it's efficacy to produce collisions was still amazing. Step 1 was enough to find many duplicates, and concatenating and permuting them in Step 2 also resulted in full key collisions.

Difficulty in attack: Effortless

STLPort 4.6.2.

for ( i = 0; i < length; ++i )
	hash = ( ( 5 * hash ) + key[i] );

Same story as DooM III, effortless collisions and successful permutation.

Difficulty in attack: Effortless

Tribes/Torque

for ( i = 0; i < length; ++i ) {
	uint c = ( tolower( key[ i ] ) );
	hash += hash;
	hash ^= ( c * c );
}

However, in Tribes the key is treated as signed so the multiplication is signed as well, and in Torque, the multiplication is replaced with a pre-generated lookup that truncates the upper 24 bits of the result and indexes the lookup table with a signed byte in the hash loop, i.e. any byte over 0x7f will actually use negative indices. The version attacked was the buggy Torque version, although any version is easy to attack.

As with the other weaker algorithms, duplicates were easy to generate with or without permutation.

Difficulty in attack: Effortless

SuperFastHash

Paul Hsieh's SuperFastHash was one of the hashes I was looking forward to having a crack at. I knew it was quite good as a general purpose hash, but I hadn't seen anything as to whether or not it could be easily attacked.

Unfortunately, it went downhill right off the bat. There were high concentrations of colliding hashes during Step 1, usually 50-60 for a particular hash in a tight group of keys. This "group" also seemed to repeat every 8 characters or so for the most significant digit, i.e. a group at axxxxxxx, a group at ixxxxxxx, and a group at qxxxxxxx.

The good news is that SuperFastHash was resistant to permuting and concatenating keys in Step 2. I could still get collisions and slow down the hash table, sometimes quite noticeably, but overall the chain lengths tended to stay around 10 to 30 links per active bucket.

The bad news is that the Step 3 method of generating successive collisions with adjusted initial hash values was very easy due to SuperFastHash's collision clustering problem. It took no time at all to get 3 sets of collisions and to permute and concatenate them into a deadly key set for SuperFastHash.

If anybody knows David Malone, tell him he was right!

Difficulty in attack: Easy after identifying the need for Step 3

FNV

The Fowler/Noll/Vo hash is a generally well performing hash based on multiplication by a prime number. Unlike SuperFastHash, duplicates are not clustered with FNV and are rather painful to find, requiring quite a lot of brute force iterating. The differences end there though, as, like SuperFastHash, FNV exhibits only mild collisions at Step 2 and full collisions at Step 3.

Since FNV took so long to generate duplicates, I did it in the following way:

• Generate ~10 duplicates with hash A using the default hash B
• Generate ~10 duplicates with hash B using A as the default hash

This way I can permute

Set1 ( A to B ) | Set2 ( B to A ) | Set3 ( A to B )

..and so on without needing to generate more duplicates. The only downside is the key gets a little large, but you can still generate huge amounts of keys with relatively little searching.

Difficulty in attack: Medium, somewhat time consuming

lookup3

Bob Jenkins' lookup3 hash laughed politely when I tried to knock it around. It can find duplicates (slowly) with 8 character keys, but concatenating keys does absolutely nothing due to it's 96bit internal state.

Conclusions

Crosby and Wallach presented a few remedies to this type of a attack:

• Use another data structure with guaranteed worst-case performance, such as a self-balancing binary tree. A Judy Tree is another interesting alternative, offering sorted and sequential access as well as competitive performance to a hash table without being susceptible to algorithmic complexity attacks.
• Generate a random value to use as the initial hash value, i.e. keying the hash table. Crosby and Wallach reported that even MD5 and SHA-1 were susceptible to brute-forcing collisions in the lower 19 bits of a hash value when unkeyed.
• Addendum to the previous item: It's true! Masking with 0x0007ffff, I managed to find 2.7 SHA-1 collisions a second (497 total), and even got twenty-three pairs of 32bit collisions out of it. That's ~53 hours to compute all the collisions in the 512k bucket space. Changing just a single bit of the initial SHA-1 key dropped the distribution back to completely random.
• Use a Universal Hashing algorithm. Crosby started work on a Universal Hashing library, but unfortunately doesn't seem to have updated it since 2003.

One thing they didn't mention is expanding your algorithm to use more than 32bits of internal state. Combining this with keyed hash values should solve both permuted collisions and brute forcing collisions for a subsection of the bitspace. Although if you're determined to stick with hash tables, modifying a flawed algorithm wouldn't make much sense when the general purpose algorithm with the best distribution is also close to the quickest and strongest, and easily adapted to keyed initial values: lookup3.

Download

You may download a slightly modified version of Paul Hsieh's htest which comes equipped with demonstration files for each attacked hash algorithm.

readme.txt:

A collection of colliding keysets for various string hashing algorithms.
Keyset size is limited to provide a smaller download, not due to
computational complexity. Test Harness used is Paul Hsieh's htest.

Run testcollisions.bat under windows to see the results, or figure
out how to convert it to something lunixy if you don't have windows.

Algorithm         Number of fully colliding keys
------------------------------------------------
DooM3                                  4096 keys
FNV                                   16384 keys
hash31                                 1024 keys
SuperFastHash                         16384 keys
STLPort 4.6.2                          4096 keys
Torque                                 4096 keys

The original htest may be found at
http://www.azillionmonkeys.com/qed/htest.zip