An encryption standard widely used in digitally signing documents and programs has a flaw in it that could allow for the creation of forgeries, sources said Wednesday.
Researchers: Digital encryption standard flawed
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
Wrong, wrong, wrong. SHA-1 is not used for encryption.
It’s used for hashing, which is a totally different matter.
Still a significant find, though not nearly in the same way.
All they did was find a more mathematically efficient method to brute force the hashes, but all is not lost.
CNET states:
The break of the full SHA-1 algorithm reduces the complexity of producing a “collision”–or matching hash value–by a factor of about 2,000. If cluster of computers could handle 1 million hash values every second, it would still take about 19 million years to find two different documents whose digital fingerprints match.
This is significant in that SHA-1 has now known flow, which may be extended further. But in itself…
This attack reduces 2^80 ops needed to find a collision to 2^69. Now… brute-forcing MD5 required 2^64!
There are a lot of other limitations on how the attack can be used as well. For example, in order to take advantage of the improved time-to-collision, the attacker has to have complete control of both files being hashed. Hence an attacker can only really “forge” his own data. There are still creative ways to spin a dangerous attack out of that, but it ups the ante quite a bit.
—–BEGIN PGP SIGNED MESSAGE—–
Hash: SHA1
SHA-1 hashing is still an important part of crypto systems. See above (I hope it wraps the
same as the preview).
And this is significant. As I recall, this is the same team that not so long ago broke MD5,
proposed this weakness in SHA-1, and made MD4 so trivial to break you could do it with a
paper and pencil. The sky isn’t falling yet, but don’t think of SHA-1 as still being 99.95% as
strong as it used to be.
—–BEGIN PGP SIGNATURE—–
Version: GnuPG v1.2.6 (GNU/Linux)
iD8DBQFCFDHOQuxzIuKcNh8RAjBbAJ9PUG/K3e2J0Qa7goAxA1ghPFfxIgCeOUa2
2NQ830m4i/S8zVWsmmkjLIk=
=xfeX
—–END PGP SIGNATURE—–
<cough> How come nobody seems to have a copy of the actual paper (beside the authors) ?
This is a WAG, but hopefully will give you an estimate of how long it would take to generate a dataset capable of causing a SHA-1 hash collision with an alternate dataset.
The distributed.net project brute forced an RC5 64bit key over many years, however:
… at our peak rate we could expect to exhaust the
keyspace in 790 days. Our peak rate of 270,147,024
kkeys/sec is equivalent to 32,504 800MHz Apple PowerBook
G4 laptops or 45,998 2GHz AMD Athlon XP machines or (to
use some rc5-56 numbers) nearly a half million Pentium Pro
200s.
Assuming SHA-1 is on the same level of complexity as this, you would need 46,000 Athlon 2.0 Ghz cracking for 69 years – or ~ 3.2 million Athlon 2.0 Ghz’s cracking for one year. Feel free to chop these numbers into a fraction, 1/luck. if you’ve got average luck you’ll only have to search 1/2 of the space before colliding.
I heard the paper was circulating in China, but I don’t know if it has yet been translated to english.
The academic world does not equate to the same free flow of information as the Internet does. This is due in part to history and also to the peer system used. The article will most likley be posted in a peer review journal. This is pay to view to people outside the academic system. But you could go to your local University Library, and probably pull the journal off the shelf to read it, if they subscribe to it. It will eventually appear on the Internet due to the its subject nature though. I would assume it would be posted to either a computing or mathematics journal.
After studying one of the authors websites. It seems she last published in a Chinese Cryptographic Conference in 2002, china-pub made a publication of the papers submitted to that conference. It seems likley that the results might be in CHINACRYPT 2005.
http://www.freedom-to-tinker.com/archives/000661.html
the title of the story is really confusing …
“Researchers: Digital encryption standard flawed”
as the well known DES cipher is short for
Digital Encryption Standard … and have nothing to do with sha-1 which himself is not an encryption cipher but a hash as previously noted …
anyway, thank you for your great osnews website !