Crypto collisions cause denial of service in major hashes

Denial of service vulnerabilities have been found in hashes underpinning host of web applications including those offered by Google, Microsoft, Yahoo and those based on Java among scores of others.

The attacks target weaknesses in the hash algorithms that permit multiple hash collisions to take place. This can quickly overload any application using a vulnerable hash algorithm.

The popular MurmurHash algorithm was found vulnerable to the attacks, along with a hash used by Python, Google's CityHash and likely Microsoft's .Net Marvin32 hash which appeared not to be “built with security in mind”, according to the research trio behind the work.

Problems occurred when hash algorithms did not evenly distribute strings causing link lists to become long and making hash tables slow.

“Some applications, practically every string that you hash has some fixed first byte which means you'll have all of those strings piling up on a certain link list, no matter how many [lists] you have,” researcher Daniel Bernstein said.

Strong algorithms like 256bit SHA-3 was very slow (which is contrary to the goal of hash tables) and did not prevent hash collisions because attackers need only work with the size of hash tables. Randomisation was also proven insufficient as was the use of more complex data structures which served to slow down the computation process.

“You can have the world's most amazing hash function [but] reduce it to the size of the hash table and suddenly the attacker can find collisions by trying a million inputs, of which one has a value of say zero … after reasonable computation, the attacker has piled up thousands of string with a hash value of zero,” he says.

“The question isn't where are hashes used, it is where aren't they used – just about every real-world application has them somewhere.”

The researchers reported the flaws to Ruby on Rails and Oracle for Java after testing the respective platforms in August and September last year. Rails pounced on the flaw but Oracle has yet to fix the vulnerability.

The response from Oracle, Rails developer Martin Bosslet says, was the “sound of them not giving a f**k”.

But fixing the flaw was not as simple as applying a form of patch or including randomisation into the hash algorithms; Rather the researchers point to their own ground-up built hash as the most effective solution.

SipHash 2.4, a 128 bit algorithm, was researchers boasted as fast as the vulnerable but speedy hashes yet more secure than cumbersome but rugged SHA-3. They explained SipHash had a more specific security focus that was different from SHA-3, and was 10 times faster.

It completely blocked the attacks, however a group of university students were already working to break it.

The hash has been adopted by the likes of Mozilla, OpenDNS, Perl 5, Rust, and Rails.

The work builds on previous research by the trio into hash flooding against programming languages including Perl and the Squid webcache presented at the conference a year earlier. Perl responded by secretly randomising its hash function which improved the situation but did not remove the possibility for attack.

Read more technical information about SipHash (pdf), details about the attacks, and a proof of concept attack code against Rails.

Copyright © SC Magazine, Australia