Feeds

Crypto researchers break SHA-1

It's official

  • alert
  • submit to reddit

Website security in corporate America

Long rumored and now official, the popular SHA-1 hashing algorithm has been attacked successfully by researchers in China and the US. A collision has been discovered in the full version in 269 hash operations, making it just possible to mount a successful brute-force attack with the most powerful machines available today.

This is by no means a disaster in practical terms, as the amount of computational power and mathematical insight needed to perform a successful attack is still great. But SHA-1 has been demonstrated not to be beyond the reach of current supercomputers, as had previously been believed, or at least hoped. Theoretically, 280 operations should be necessary to find a collision.

By using reduced-round versions of the algorithm, and the team's technique, it was possible to attack SHA-1 in fewer than 233 operations. Using the same technique, the full SHA-0 could be attacked in 239 operations.

SHA-1 is regarded as more secure than MD5, in which collisions were found last year by some of the people who reported the recent discovery. Also last year, collisions were found in SHA-0 by a French team.

The researchers in the latest effort, Xiaoyun Wang and Hongbo Yu from Shandong University and Yiqun Lisa Yin from Princeton University, have released a paper briefly outlining their findings. The technical details will be released in the near future. Wang and Yu were part of the team that discovered the weakness in MD5.

Hashing is a one-way cryptographic function. It differs from encryption in that the original input creating the hash should not be recoverable under any circumstances, whereas in encryption, the original input is meant to be recovered, albeit under tightly controlled circumstances. Hashing is used in many applications, from passwords and other authentication schemes, to digital signatures and certificates, to creating checksums used to validate files.

Ideally, no two inputs would create the same hash. However, in the real world this inevitably happens, and when it does, it's called a collision. Finding a collision is a matter of brute-force hashing until two different inputs are found to create the same output. This could, with considerable effort, be used to forge certificates and signatures.

Still, in practical terms, things are not as bad as they might seem. Collisions are irrelevant in a number of crypto implementations, and in those where they are relevant, the trick is to keep them ahead of the practical computing resources required to find them. The chief consequence of these discoveries is that there is now a degree of uncertainty about whether a digital signature, say, is authentic, because it is not impossible for a duplicate to be created. But it's also not likely to happen, either, at least with current technology. Indeed, collisions notwithstanding, the algorithm remains the strongest element of most crypto implementations. It would be wise to approach any encryption or hashing scheme as a fine boost in security that can never be trusted one hundred per cent. Which is exactly how every security scheme should be approached.

The US National Institute of Standards and Technology (NIST) has recently begun recommending that government phase out SHA-1 in favor of SHA-256 and SHA-512.

NIST security technology group manager William Burr was recently quoted in Federal Computer Week saying that, "SHA-1 is not broken, and there is not much reason to suspect that it will be soon."

NIST had been recommending that SHA-1 be phased out by 2010. It looks as if that date will have to be tweaked just a bit. ®

Related stories

Number crunching boffins unearth crypto flaws

Is SSL safe?

Crypto attack against SSL outlined

Weak crypto casts shadow over ecommerce

109-bit Elliptic Curve Cryptography knocked over with brute force

US.gov plans DES's retirement

Protecting users from Firesheep and other Sidejacking attacks with SSL

More from The Register

next story
Home Depot: 56 million bank cards pwned by malware in our tills
That's about 50 per cent bigger than the Target tills mega-hack
Hackers pop Brazil newspaper to root home routers
Step One: try default passwords. Step Two: Repeat Step One until success
UK.gov lobs another fistful of change at SME infosec nightmares
Senior Lib Dem in 'trying to be relevant' shocker. It's only taxpayers' money, after all
Critical Adobe Reader and Acrobat patches FINALLY make it out
Eight vulns healed, including XSS and DoS paths
Spies would need SUPER POWERS to tap undersea cables
Why mess with armoured 10kV cables when land-based, and legal, snoop tools are easier?
TOR users become FBI's No.1 hacking target after legal power grab
Be afeared, me hearties, these scoundrels be spying our signals
Blood-crazed Microsoft axes Trustworthy Computing Group
Security be not a dirty word, me Satya. But crevice, bigod...
Snowden, Dotcom, throw bombs into NZ election campaign
Claim of tapped undersea cable refuted by Kiwi PM as Kim claims extradition plot
prev story

Whitepapers

Secure remote control for conventional and virtual desktops
Balancing user privacy and privileged access, in accordance with compliance frameworks and legislation. Evaluating any potential remote control choice.
WIN a very cool portable ZX Spectrum
Win a one-off portable Spectrum built by legendary hardware hacker Ben Heck
Storage capacity and performance optimization at Mizuno USA
Mizuno USA turn to Tegile storage technology to solve both their SAN and backup issues.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?
The next step in data security
With recent increased privacy concerns and computers becoming more powerful, the chance of hackers being able to crack smaller-sized RSA keys increases.