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
Frugality as a service: the Amazon story
Behind the scenes, Amazon Web Services is one lean machine.
 
Negotiating with the cloud email megavendors
[Blog post] Lessons from Woolworths’ mammoth migration.
 
Qld govt to move up to 149k staff onto Office 365
Australia's largest deployment, outside of the universities.
 
 
Sign up to receive iTnews email bulletins
   FOLLOW US...

Latest VideosSee all videos »

The great data centre opportunity on Australia's doorstep
The great data centre opportunity on Australia's doorstep
Scott Noteboom, CEO of LitBit speaking at The Australian Data Centre Strategy Summit 2014 in the Gold Coast, Queensland, Australia. http://bit.ly/1qpxVfV Scott Noteboom is a data centre engineer who led builds for Apple and Yahoo in the earliest days of the cloud, and who now eyes Asia as the next big opportunity. Read more: http://www.itnews.com.au/News/372482,how-do-we-serve-three-billion-new-internet-users.aspx#ixzz2yNLmMG5C
Interview: Karl Maftoum, CIO, ACMA
Interview: Karl Maftoum, CIO, ACMA
To COTS or not to COTS? iTnews asks Karl Maftoum, CIO of the ACMA, at the CIO Strategy Summit.
Susan Sly: What is the Role of the CIO?
Susan Sly: What is the Role of the CIO?
AEMO chief information officer Susan Sly calls for more collaboration among Australia's technology leaders at the CIO Strategy Summit.
Meet the 2014 Finance CIO of the Year
Meet the 2014 Finance CIO of the Year
Credit Union Australia's David Gee awarded Finance CIO of the Year at the iTnews Benchmark Awards.
Meet the 2014 Retail CIO of the Year
Meet the 2014 Retail CIO of the Year
Damon Rees named Retail CIO of the Year at the iTnews Benchmark Awards for his work at Woolworths.
Robyn Elliott named the 2014 Utilities CIO of the Year
Robyn Elliott named the 2014 Utilities CIO of the Year
Acting Foxtel CIO David Marks accepts an iTnews Benchmark Award on behalf of Robyn Elliott.
Meet the 2014 Industrial CIO of the Year
Meet the 2014 Industrial CIO of the Year
Sanjay Mehta named Industrial CIO of the Year at the iTnews Benchmark Awards for his work at ConocoPhillips.
Meet the 2014 Healthcare CIO of the Year
Meet the 2014 Healthcare CIO of the Year
Greg Wells named Healthcare CIO of the Year at the iTnews Benchmark Awards for his work at NSW Health.
Meet the 2014 Education CIO of the Year
Meet the 2014 Education CIO of the Year
William Confalonieri named Healthcare CIO of the Year at the iTnews Benchmark Awards for his work at Deakin University.
Meet the 2014 Government CIO of the Year
Meet the 2014 Government CIO of the Year
David Johnson named Government CIO of the Year at the iTnews Benchmark Awards for his work at the Queensland Police Service.
Q and A: Coalition Broadband Policy
Q and A: Coalition Broadband Policy
Malcolm Turnbull and Tony Abbott discuss the Coalition's broadband policy with the press.
AFP scalps hacker 'leader' inside Australia's IT ranks.
AFP scalps hacker 'leader' inside Australia's IT ranks.
The Australian Federal Police have arrested a Sydney-based IT security professional for hacking a government website.
NBN Petition Delivered To Turnbull's Office
NBN Petition Delivered To Turnbull's Office
UTS CIO: IT teams of the future
UTS CIO: IT teams of the future
UTS CIO Chrissy Burns talks data.
New UTS Building: the IT within
New UTS Building: the IT within
The IT behind tomorrow's universities.
iTnews' NBN Panel
iTnews' NBN Panel
Is your enterprise NBN-ready?
Introducing iTnews Labs
Introducing iTnews Labs
See a timelapse of the iTnews labs being unboxed, set up and switched on! iTnews will produce independent testing of the latest enterprise software to hit the market after installing a purpose-built test lab in Sydney. Watch the installation of two DL380p servers, two HP StoreVirtual 4330 storage arrays and two HP ProCurve 2920 switches.
The True Cost of BYOD
The True Cost of BYOD
iTnews' Brett Winterford gives attendees of the first 'Touch Tomorrow' event in Brisbane a brief look at his research into enterprise mobility. What are the use cases and how can they be quantified? What price should you expect to pay for securing mobile access to corporate applications? What's coming around the corner?
Ghost clouds
Ghost clouds
ACMA chair Chris Chapman says there is uncertainty over whether certain classes of cloud service providers are caught by regulations.
Was the Snowden leak inevitable?
Was the Snowden leak inevitable?
Privacy experts David Vaile (UNSW Cyberspace Law and Policy Centre) and Craig Scroggie (CEO, NextDC) claim they were not surprised by the Snowden leaks about the NSA's PRISM program.
Latest Comments
Polls
Which bank is most likely to suffer an RBS-style meltdown?





   |   View results
ANZ
  21%
 
Bankwest
  9%
 
CommBank
  11%
 
National Australia Bank
  17%
 
Suncorp
  24%
 
Westpac
  19%
TOTAL VOTES: 1426

Vote