Researchers have found the most popular cryptographic hash function to be far weaker than they originally thought.
DetailsSHA-1 is a hash function that's fast and easy to implement. And until recently, the industry also believed it conformed to the two critical factors required of a secure hash function. First, it must be truly one-way, and second, it must produce a different result every time it's applied, known in cryptography as being "collision-free".
SHA-1 is widely deployed because users believed it provided a certain level of security. As with all cryptographic algorithms, you can expect that someone will eventually break it, but researchers believed it would take a tremendous amount of time and/or computing power to do so. They thought the only way to crack SHA-1 would be by using brute force decryption, a very time-consuming process.
However, researchers in China and at Princeton University have shown that SHA-1 is not collision-free and that it's possible to create an algorithm, which means someone can break it far more quickly than previously thought --approximately 2,000 times faster.
Users choose crypto algorithms based on ease-of-use, efficiency, and how long they can expect it to keep data secure. For example, if you have information that only needs to remain protected for 20 to 50 years, then an algorithm that takes an average of 100 years to break is plenty good enough.
But there is always the danger that someone will discover a way to break it more quickly, reducing the expected 100-year protection to 20-day protection or so (2,000 times faster.) While a hacker or competitor may balk at planning a 100-year campaign to read your secrets, he or she may find that a couple of weeks is a good investment.
Of course, this calculation also involves computer power; having a 100X faster computer (or using 100 computers) makes the job 100 times faster, and we expect computers to get faster with time. But computing power isn't free, so the time analogy still holds.
You can read a brief outline of the researchers' results in this MIT document. While the document doesn't provide detailed directions to actually exploit the new technique, researchers are currently preparing a longer paper. The same techniques apply to weaker versions of SHA and perhaps to stronger versions as well.
The security firm RSA Laboratories has posted comments on this discovery and the need to change SHA-1. Meanwhile, rumours about this, or perhaps another similar discovery, surfaced as far back as August 2004, as published on the Freedom to Tinker Web site.
Applicability
SHA-1 is widely deployed.
Risk level - Serious
While definitely serious, it's not of immediate concern.
Mitigating factors
Although SHA-1 is now far weaker, it still remains pretty strong. Panic isn't necessary, but advance planning is.
Final word
You may find this a pretty obscure item to qualify for the lead in this column, but I want to remind you that many security downloads (such as those from Apple) carry verification based on SHA-1. Any time researchers discover a widely deployed cryptographic algorithm to be weaker than originally thought, it sends ripples through the security community. And this discovery proved that SHA-1 isn't just weaker than originally thought—it's thousands of times weaker.
Perhaps the scariest aspect of this finding is that researchers widely viewed SHA-1 as highly secure, and years of study had failed to locate any significant vulnerability. That should give great pause to people relying on other more secure algorithms.
Also watch for …
- Apple has finally acknowledged that a Java problem acknowledged and fixed by Sun in November 2004 also affects OS X. A patch is available from Apple. Secunia.com rates this as an extremely critical vulnerability because it can allow an attacker to take complete control of vulnerable systems.
- Microsoft's IM program, MSN Messenger, has a vulnerability that led the company to force users to upgrade their program. Unfortunately, it apparently doesn't matter whether you actually use IM; I keep receiving pop-up demands that I upgrade IM immediately. This is getting very annoying, and it's probably annoying a lot of your users as well.
- The big virus news last week was the email purporting to come from the FBI. I don't know just how dumb someone has to be to think the FBI is emailing him or her personally, but anyone who did certainly wouldn't work for me by next week. What I'm wondering is whether the FBI will really take this seriously and charge the instigator, if they find him or her, with impersonating a federal officer.
- TurboTaxing? A News.com story reports that, just in time for tax season, Intuit TurboTax users are experiencing a lot of problems with the popular tax program, this time apparently due to conflicts with security tools, which could lead users to disable security features as a workaround. This problem gets worse every year, and it's becoming intolerable. I've been complaining about similar problems for years, but Intuit has never responded to my requests for information. Perhaps this year's mounting problems will finally end the company's anti-consumer stand.
- David Jeansonne has admitted to spreading MSN TV malware, which triggers calls that could flood 911 emergency response switchboards. And yet, for these two federal felonies, he only faces a maximum of 10 years in a federal prison.
- Gartner Research has labelled Microsoft's decision to make Internet Explorer 7.0 only available for XP users irresponsible.
- Police arrested Anthony Greco, suspected of trying to extort money from MySpace.com, last week when he flew to Los Angeles offering to sell his spim technique to the networking service. Similar to spam, spim targets IM users. This is the first spim-related arrest.
- Finally, if you've been living in a cave, you may not know that ChoicePoint, an information broker that almost certainly has lots of information about American citizens, recently suffered a critical security breach. People have already begun reporting identity theft problems.
