Feeds

Crypto attack puts digital sig hash on collision course

SHA-1, your time is near

HP ProLiant Gen8: Integrated lifecycle automation

Cryptographers have found new chinks in a widely-used digital-signature algorithm that have serious consequences for applications that sign email, validate websites, and carry out dozens of other online authentication functions.

The researchers, from Macquarie University in Sydney, Australia, found a way to break the SHA-1 algorithm in significantly fewer tries than previously required. Although the hash function was previously believed to withstand attempts numbering 263, the researchers have been able to whittle that down to 252, a number that puts practical attacks well within grasp of well-funded organizations.

Secure hashing algorithms are designed to reduce text or digital files to a unique series of letters and numbers that is often compared to the document's signature. The findings, which were published Wednesday here (PDF), mean it's easier to create what cryptographers call collisions in SHA-1, in which two different sources share the same the same output.

"I'm expecting that we'll start seeing SHA-1 collisions before the end of the year, if not sooner," said Paul Kocher, president and chief scientist at Cryptography Research, a San Francisco-based consultancy. "For applications that fail because of collisions, you need to be really worried."

Indeed, it was collisions in the now-disgraced MD5 algorithm that allowed independent researchers last year to poke holes in the internet's digital certificate system by forging counterfeit credentials needed to impersonate websites that rely on the security measure. The discovery sent certificate authorities such as VeriSign's RapidSSL scrambling to change the way they issue SSL, or secure sockets layer, certificates.

Other hashes, including SHA-0 and MD4, have also been demonstrated to be weak enough to generate collisions using relatively modest means. With the latest findings, that list is steadily growing.

"Now, SHA-1 has some of the same problems that MD5 has had creeping up on it for a while," Kocher said.

The 160-bit output of SHA-1 should in theory allow hashes to withstand 280 operations without generating a collision. That number came down to 269 and later to 263 as researchers discovered ways to exploit weaknesses in the algorithm. But until now, only the most elite government organizations had the computing power to do that.

Cryptographers have long recognized that advances in computing power and research into weaknesses of various hashing algorithms jeopardize the reliability of digital signatures. Last year, the National Institute of Standards and Technology commenced an open competition to create a new algorithm. The winning entry should be one that is able to withstand attack and able to generate hashes quickly and without consuming too many computer resources. It will offer hashes with as many as 512 bits, enough to (at least theoretically) withstand 2256 attempts to create a collision.

The new attack technique combines what's known as a non-linear differential path with a boomerang attack. It decreases the cost of a collision attack by a factor of more than 2,000 compared with previous methods. The paper has not yet been peer reviewed.

The method works only for collisions, in which an attacker is able to control both messages that are hashed. SHA-1 is still believed to resist what's known as pre-image attacks, in which an attacker tries to create one message that generates the same hash value as a pre-determined message. ®

The Essential Guide to IT Transformation

More from The Register

next story
Brit celebs' homes VANISH from Google's Street View
Tony Blair's digs now a Tone-y Blur
German government orders local CIA station chief to pack his bags
Sour Krauts arrest second local in domestic spy ring probe
Doctor Who season eight scripts leak online
BBC asks fans to EXTERMINATE copies before they materialise
Snowden leaks latest: NSA, FBI g-men spied on Muslim-American chiefs
US Navy veteran? Lawmaker? Academic? You're all POTENTIAL TERRORISTS
LibreSSL crypto library leaps from OpenBSD to Linux, OS X, more
First cross-platform version of cleaned-up OpenSSL fork
UK's emergency data slurp: IT giants panicked over 'legal uncertainty'
PM says rushed-through DRIP law will 'plug holes' in existing legislation
Russian MP fears US Secret Service cuffed his son for Snowden swap
Seleznev Jnr is 'prolific trafficker in stolen credit card data', it is alleged
Teensy card skimmers found in gullets of ATMs
Hi-tech fraudsters treading more softly, but gas still yielding bang for buck
Adobe Flash: The most INSECURE program on a UK user's PC
XML a weak spot, but nothing's as dire as Adobe player
prev story

Whitepapers

Designing a Defense for Mobile Applications
Learn about the various considerations for defending mobile applications - from the application architecture itself to the myriad testing technologies.
Consolidation: The Foundation for IT Business Transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.
The Power of One Brief: Top reasons to choose HP BladeSystem
Download this brochure to find five ways HP BladeSystem can optimize your business with the power of one.
Securing Web Applications Made Simple and Scalable
Learn how automated security testing can provide a simple and scalable way to protect your web applications.
Top 8 considerations to enable and simplify mobility
In this whitepaper learn how to successfully add mobile capabilities simply and cost effectively.