Schneier on Security
A blog covering security and security technology.
« "Clear" Registered Traveller Program |
| RFID Tattoos »
January 22, 2007
Slashdot is reporting on this article claiming that SHA-1 has been cracked.
The reality is more complicated.
Posted on January 22, 2007 at 12:07 PM
• 25 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
FWIW, I believe the Epoch Times is run by the Falun Gong. I don't know whether their news coverage has an agenda as a result, but it's worth knowing.
Why is this news? Not you Bruce, but /. and "first post!!!1!"ers? Most of us have read the reports and positions.
It's sad, really. /. has really declined in quality of content over the years.
Er, no. Not it really hasn't declined. Slashdot quality is about the same as it was in 2000. I think you're just remembering through rosy glasses.
Bruce, what every came out of the "hash function workshop" that occured a year or two ago? You mentioned some new directions being taken (rather than the traditional "wide block cipher" approach), but I haven't really seen much news lately.
Of course, I rely on your blog for all my crypto-related news; I'm sure if I monitored CiteSeer or other academic resources I would be more informed.
"Bruce, what every came out of the 'hash function workshop' that occured a year or two ago?"
NIST is going to have a competition for a hash function to replace SHA-1. It'll be a slow process, but that's a good thing.
Forgive me if I'm wrong here, but...
If I recall correctly, SHA-1 is a 128-bit digest. This means that there are 2^128 possible hash values, and that for any given data of length N bits, there are on average (N / 2^128) possible values that will give the same hash value.
The article mentions that the "crack" reduced the time required to about 1/2000 of what it was previously. That's roughly a factor of 2^11. Therefore, instead of needing to try 2^128 values to find a hash collision, it's now possible with only 2^117 values.
That's still 1.66 x 10^35 combinations. If a single computer could try 1 million combinations per second, it would take 5.3 million million million years to find a collision.
Also, I've just done a search on the New Scientist article, and nothing comes up by that name. The closest I could find is an article from December 2005. If this is old news, why have the Epoch Times only written about it now? Slow news day?
Crack is the wrong word to use...she has created a way to create collisions with less combinations than would be required for brute force.
I don't know why Epoch Times even did a write up about it so late...if I remember correctly, this was released like early 2006 or something. Whenever it was..it is old. This was one of the reaons why NIST was holding a Hash workshop....to move past SHA altogether.
The government now uses SHA-256 or SHA-512...so faster cracking in SHA-1 isn't really a big deal..or am I just crazy?
> Crack is the wrong word to use...she has created a way to create
> collisions with less combinations than would be required for brute force.
That's "cracked" or "broken" as far as cryptanalysis is concerned, right?
Now, as far as the average slashdotter is concerned, "cracked" probably means "able to be unencrypted by mortal humans", but this is a terminology/domain problem, not really a misuse of the term.
SHA-1 is actually a 160-bit digest.
Jamie, as SHA-1 is a 160-bit digest, meet-in-the-middle attacks reduce its computational complexity to 2^80, but still, your point is well taken. Reducing its complexity to 2^63 is not going to compromise data integrity for mere mortals any time soon. For the NSA? Maybe. I'm sure they're using longer, SHA-2 hashes.
Guys, this may be a bit "offtopic", but i just want to know, where there is any "Legal problems" in using SHA-256 or SHA-512 algorithm for a commercial application.
i have read some where that there is a legal complication (NIST) saying that commercial application should not use a key length of 512 for AES Algorithm.
so just want to confirm this.
to the point, SHA-1 being cracked, whats next, bulk of the applications world wide uses SHA-1, which was considered secured.
> i have read some where that there is a legal complication (NIST) saying that commercial application should not use a key length of 512 for AES Algorithm.
This may be true, since AES does not seem to support 512 bit keys.
>> This may be true, since AES does not seem to support 512 bit keys.
i know AES supports 128 bits, 192 bits and 256 bits Key size.. yaa may not support 512.
but is there any legal complications against using key size greater than 128 bit :)
While Xiaoyun Wang does bring a possible attack vector out of the theoretical world and into the reach of real world, the media and others really need to put this into scope.
She found a weakness in SHA-1, but the chances of this being used in an attack are very small.
Software makers and the general public should be more worried about other attacks. SE attacks, SQL injection attack, buffer overflows, etc.
If a possible weakness in SHA-1 is your only security issue, then you are dreaming.
I think George Ou sums it up pretty well in his ZDNet article (http://blogs.zdnet.com/Ou/?p=409)
“Just because a hash collision is found doesn't necessarily mean hackers can start exploiting this. Not only does it still requires a massive amount of computing fire power to find a single hash collision but more importantly; finding a hash collision doesn't necessarily mean that a hacker has something useful….. The science of finger print forensics or even genetic DNA matching is far less reliable than SHA-1 hashing but perfectly legitimate in the courts.��?
The Epoch Times prints some seemingly neutral stories in order to build up street cred as a "real newspaper" rather than a Falun Gong mouthpiece. Which is how a Falun Gong supporter got invited as a reporter to a press conference at the White House with Chinese president Hu Jintao in attendance. (Or maybe not street cred, but plausible deniability. There were a lot of weird things that went on at the Hu visit, and Bush may have been deliberately snubbing him.)
@Technocrat: Chinese newspapers are well-known for doing assemblage articles on slow news days. There was one case where a paper paraphrased an article in the Onion, not realizing that it was a joke paper.
Have there been any improvements on the attacks on SHA-1 since 2005?
In particular with respect to preimage attack?
Bruce, you should have chosen a slightly different title like "2005 attack on SHA-1 gets new media attention" -- which would still be over-rated, IMHO, but anyway more appropriate as to the urgency of the message.
I got quite a chill when reading the headline via RSS...
regarding the SHA-512 off topic question: What does the size of the SHA output have to do with AES encryption key sizes?
>> @funkyj regarding the SHA-512 off topic question: What does the size of the SHA output have to do with AES encryption key sizes?
it has nothing to do with AES Key size. i was just curious about knowing any kind of legal complications in using of both algorithms with higher key size :)
a. @Arun, there is no legal complication with the use of long keys. The NSA once limited the use of long keys, but has given up this war long ago. As mentioned by Hen, Rijndael (aka AES) supports only 128,192 and 256 bit keys, as was required by the NIST, and they are more than enough unless you manage to build a quantum computer.
b. That's what happens when people think they understand something which they don't, and cryptography is a HARD topic. Xiaoyun Wang has shown more than a year ago how to find collisions in MD-4, MD-5 and SHA-1 in small amount of computations (for MD-4 she doesn't even need a computer). Clearly, for any future application, SHA-256 or a new hash function which will be selected by NIST should be used, but existing applications using MD-5 or SHA-1 are still secure, as finding a different source for given hashed data is still infeasible.
Thanks friend for the information. i knew about the objection raised by NIST against usage of AES 256 bit key size.
thanks for giving the information that its perfectly alright for us to use it in commercial applications as well.
Any ideas or papers on standard ways to truncate hash output and the security implications? I've seen recommendations to just cut the first bits out of the digest, but XORing looks better to me.
return x[1:64] xor x[65:128] xor x[129:192] xor x[193:256]
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.