Crypto collisions cause denial of service in major hashes

Powered by SC Magazine
 

Researchers poke holes in Murmurhash, CityHash, and others.

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


Crypto collisions cause denial of service in major hashes
 
 
 
Top Stories
Photos: Global Switch opens Sydney East data centre
First stage opened, to some fanfare.
 
ATO releases long-awaited Bitcoin guidance
Everyday investors escape the tax man.
 
Why the Weather Bureau’s new supercomputer is a 'gamechanger'
IT transformation starts to reap results.
 
 
Sign up to receive iTnews email bulletins
   FOLLOW US...
Latest Comments
Polls
Which is the most prevalent cyber attack method your organisation faces?




   |   View results
Phishing and social engineering
  68%
 
Advanced persistent threats
  3%
 
Unpatched or unsupported software vulnerabilities
  12%
 
Denial of service attacks
  7%
 
Insider threats
  11%
TOTAL VOTES: 482

Vote