Just when you thought you had it all secured, it turns out that the encryption method, regarded most safe and created by the NSA, is broken. Not just now, but about a year ago.
A chinese mathematician, Xiaoyun Wang, uses collision search to break SHA-0, SHA-1 and MD5, which she successfully did. [Edit nov-2007: About the whole world refers to the link I used as well, but it's invalid; I believe this is the correct one, if not, browse this for all publications]
Hashes
What Xiaoyun ('Little Cloud') Wang and her associates Yiqun Lisa Yin, and Hongbo Yu did, was looking into the hash-algorithms. These are mathematical formulas, that, when applied to a file, create a stream of a couple of hundred bits (a string), that is characteristic for the file the algorithm was applied to. In fact, it's some sort of fingerprint: changing one bit in the file causes the hash to change, too. That is why hashes allow you to determine whether files have been tampered with: send the file/document, send the hash. Compute the hash at the receiver's end, and check whether the hashes match.
In order to facilitate this, a hashing algorith must forfill certain prerequisites:
Collisions
What Wang does, is looking for collisions. And she found them. For the MD5 as well as for the SHA1 hashing algorithms. MD5 is old (developed in 1991), and supposedly not used very much anymore. It is, however, remarkably often found.
Xiaoyun Wang detects collisions by looking carefully at the original data when it is being hashed. She develops a feeling for that data, and thus "feels" when collisions might occur. All in all, she reduces the original 2^80 combinations, via a subset (reduction to 2^64) to 2^39 possible sequences. Breakable in about a day, on a fast PC.
The standing ovation when this was presented at Eurocrypt, was deserved, I'd say! As well as the best paper award. Nice detail about the Eurocrypt site: their certificate is untrusted...
Soon after the publication, German mathematicians tried sign a PDF document and a Postscript file with a forged digital signature.
Panic
A Dutch researcher, De Weger, created a forged certificate, based on signatures, provided by Wang. Two different certificates had the same hash value, even though only one was genuine.
Wang went on, and announced to have broken SHA1 as well. That caused a bit of a stir, as it is often used hashing method for securing HTTP traffic, the Secure Socket Layer, or SSL.
She was not granted a visum to speak in the USA about her work. Now, who's an austrich here? Getting typical for the US, it seems, this kind of reaction.
[edit feb 2017: Google and CWI hacked SHA-1 160 bits. "Again?, you would say]
Hier is een link naar een Nederlands artikel over haar. Uitleg over botsingen.
A chinese mathematician, Xiaoyun Wang, uses collision search to break SHA-0, SHA-1 and MD5, which she successfully did. [Edit nov-2007: About the whole world refers to the link I used as well, but it's invalid; I believe this is the correct one, if not, browse this for all publications]
Hashes
What Xiaoyun ('Little Cloud') Wang and her associates Yiqun Lisa Yin, and Hongbo Yu did, was looking into the hash-algorithms. These are mathematical formulas, that, when applied to a file, create a stream of a couple of hundred bits (a string), that is characteristic for the file the algorithm was applied to. In fact, it's some sort of fingerprint: changing one bit in the file causes the hash to change, too. That is why hashes allow you to determine whether files have been tampered with: send the file/document, send the hash. Compute the hash at the receiver's end, and check whether the hashes match.
In order to facilitate this, a hashing algorith must forfill certain prerequisites:
- The result (the hash) is unique; no two different documents or files generate the same hash.
- It may not allow to reconstruct the original data from the hash
Collisions
What Wang does, is looking for collisions. And she found them. For the MD5 as well as for the SHA1 hashing algorithms. MD5 is old (developed in 1991), and supposedly not used very much anymore. It is, however, remarkably often found.
Xiaoyun Wang detects collisions by looking carefully at the original data when it is being hashed. She develops a feeling for that data, and thus "feels" when collisions might occur. All in all, she reduces the original 2^80 combinations, via a subset (reduction to 2^64) to 2^39 possible sequences. Breakable in about a day, on a fast PC.
The standing ovation when this was presented at Eurocrypt, was deserved, I'd say! As well as the best paper award. Nice detail about the Eurocrypt site: their certificate is untrusted...
Soon after the publication, German mathematicians tried sign a PDF document and a Postscript file with a forged digital signature.
Panic
A Dutch researcher, De Weger, created a forged certificate, based on signatures, provided by Wang. Two different certificates had the same hash value, even though only one was genuine.
Wang went on, and announced to have broken SHA1 as well. That caused a bit of a stir, as it is often used hashing method for securing HTTP traffic, the Secure Socket Layer, or SSL.
She was not granted a visum to speak in the USA about her work. Now, who's an austrich here? Getting typical for the US, it seems, this kind of reaction.
[edit feb 2017: Google and CWI hacked SHA-1 160 bits. "Again?, you would say]
Hier is een link naar een Nederlands artikel over haar. Uitleg over botsingen.
No comments:
Post a Comment