Slashdot Mirror
Chinese Prof Cracks SHA-1 Data Encryption Scheme
Hades1010 writes to mention an article in the Epoch Times (a Chinese newspaper) about a brilliant Chinese professor who has cracked her fifth encryption scheme in ten years. This one's a doozy, too: she and her team have taken out the SHA-1 scheme, which includes the (highly thought of) MD5 algorithm. As a result, the U.S. government and major corporations will cease using the scheme within the next few years. From the article: " These two main algorithms are currently the crucial technology that electronic signatures and many other password securities use throughout the international community. They are widely used in banking, securities, and e-commerce. SHA-1 has been recognized as the cornerstone for modern Internet security. According to the article, in the early stages of Wang's research, there were other data encryption researchers who tried to crack it. However, none of them succeeded. This is why in 15 years Hash research had become the domain of hopeless research in many scientists' minds. "
It looks like she did this almost 2 years ago. So why is this being announced now?
Aside from confusing hashing with real encryption, and saying that MD5 is part of SHA-1, isn't this article just repeating what was covered in these two slashdot stories?
Ewige Blumenkraft.
The article doesn't make sense. There are no technical details and SHA-1 is a cryptographic digest algorithm, not an encryption algorithm. AES is what everyone uses for encryption now -- message digests are used for signatures. Important, yes, but encryption hasn't been rendered useless.
They also use the word "online" too many times for me to take them seriously. The implication is that because the professor broke SHA 1 that my online bank account is going to be drained. Not likely.
My other car is first.
The original article is full of misstatements like this doozy:
this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5). Before Professor Wang cracked it, the MD5 could only be deciphered by today's fastest supercomputer running codes for more than a million years.
SHA-1 is NOT encryption, and it certainly doesn't "include" MD5. They are 2 completely different hashing algorithms. Hash algorithms are not "deciphered". Neither of them has been "cracked". They have been found, in theory, to not be as collision-proof as previously thought, but noone has yet found a way to take one block of data and modify it such that it would have an identical hash signature as the original. Both are merely found to be not quite as collision-proof (the most important thing for any hashing algorithm) as previously thought. This is old news.
The original article blows and contains no useful information whatsoever, it was written by someone who hasn't the faintest hint of knowledge about cryptography or mathematics in general.
The Epoch times is a strange newspaper (http://en.wikipedia.org/wiki/The_Epoch_Times) - it seems to be an anti-establishment periodical with lots of fluff stories about people living in China and articles on the Falun gong movement (http://en.wikipedia.org/wiki/Falun_Gong)..
Far from being a Chinese newspaper it's actually published out of New York, and you might see (Chinese) people handing out copies on the street in your country (I see them in NZ from time to time).
So yeah, it wouldn't surprise me if the article was vague... I'd take it all with a grain of salt.
Any hash algorithm can be used as a stream cipher: hash the key and take successive values to make a pseudorandom stream, and then XOR it against the plaintext. This is the idea behind Daniel J. Bernstein's Snuffle ciphers.
In other words, this attack is 2^17, or 131,072 times faster than brute forcing the hash, and from what I've read, this is considered pretty impressive stuff. That said, crypto researchers have known for a while that SHA-1 is on its last legs. From Schneider's blog in February, 2005: Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off." That's basically what I said last August. So there's nothing much to see here, except a sensationalist newspaper article. This has almost certainly been reported before on Slashdot two years ago, so this story probably counts as a dupe.
This appears to be the professors website:
h tm
l isions%20in%20the%20Full%20SHA-1.pdf
e arch%20Attacks%20on%20SHA1.pdf
http://www.infosec.sdu.edu.cn/people/wangxiaoyun.
The details on the hash collision can be found in the following papers:
Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1,Crypto'05
http://www.infosec.sdu.edu.cn/paper/Finding%20Col
Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005
http://www.infosec.sdu.edu.cn/paper/Collision%20S
She has also previously found methods for collisions in X.509, MD4/MD5, HAVAL-128, RIPEMD and SHA-0.
However, the problem is not entirely the algorithms, there will always be collisions on hashing algorithms, if you could represent an infinite amount of data in 160/128/whatever bits then there would be no point in having 161/129/whatever bits, the fact that your hard drive is much larger than that is a testament that collisions in any type of algorithm where you try to uniquely represent X bits in Y bits (where X > Y) (Yes I realize this is a somewhat oversimplified exaplantion).
The problem is in the paradigm in which these algorithms get used, 'one hash to represent them all' is a broken mentality, use multiple hashing algorithms when it matters, while it is indeed possible that the same data can cause a collision in all of the employed algorithms, its incredibly unlikely and AFAIK no one has created a PoC where two sets of data produce the same checksum in both md4 and sha-0.
Incredibly old news. EE Times reported on it at the time, correctly referring to SHA-1 as a hashing algorithm, nothing more... by itself, anyway.
It is actually run by the notorious Fa Lun Gong cult. The 'epoch' here refers to the new era the cult is supposed to bring us into, with the leader kind like Jesus. A lot of the stuff on that media, especially the Chinese version, is total crap. Despite its lack of credibility, Epoch Times seems always have quite a lot of money to burn. You can sort of pick up the recent copy FREE at major convenience shops in your local Chinatown, amongst stuff like Jehovah Witness's pamphlets. I even once found copies of both language versions at a community library here in UK.
People who dislike China tend to mention Tiananmen Square a lot, but they always forget the Tank Man is also a Chinese.
"According to a Beijing digest, this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5)."
Where do I start? SHA-1 stands for 'Secure Hash Algorithm 1' and is not an encryption scheme. Neither does it include MD5 which is a completely different hash (or message digest) algorithm.
See Schneier - http://www.schneier.com/blog/archives/2005/02/sha1 _broken.html
and http://www.schneier.com/blog/archives/2005/02/cryp tanalysis_o.html for actual coverage of the break. "They can find collisions in SHA-1 in 2**69 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point." That's down from 2**80, so it's a concern, but not exactly the end of the world.
New apps being written should probably be using SHA-256 (256 bits) rather than with SHA1 (160 bits only).
"It doesn't cost enough, and it makes too much sense."
There are actually several SHA-1 replacements out there, including SHA-224, SHA-256, SHA-384, and SHA-512. None cracked yet. And for just creating a signature-bound digest of a text that is then acted upon by a more secure scheme, like 2048 bit RSA, SHA-1 is still fine. An attacker in that case would generally need the private RSA key to just get to the point he could start cracking the SHA1 digest :).
What concerns me is that in the last two years I've heard no news about a replacement for SHA-1.
WTF? Have you been living in a cave or something?
Crypto mailing lists, newsgroups, and discussion forums talked about almost nothing else for about six months following the announcement that SHA-1 had been broken.
Even the US government, which moves at the speed of a glacier, proposed replacements for SHA-1 in FIPS back in March last year.
http://csrc.nist.gov/publications/drafts.html
-----
PGP Key ID 0xCB8FF658
This exact proposal shows up, like clockwork, literally dozens and dozens of times for each slashdot story about hash functions. Since the number of people who know why this proposal fails is miniscule compared to the number of people who think of the idea, it is literally impossible to respond to all the people who keep suggesting this idea. I mean, even if all of us spent literally every minute of every day responding to people who suggest this idea, we would still not have time to reply to every single post.
Here is an old post on slashdot explaining exactly why this idea doesn't work. The post has some details wrong ... for example, the correct security strength of the combined md5+sha1 hash is in reality 2^80 + 160*2^64, which is much weaker than even the already weakened security level cited in the post. However, the general idea is correct, and if you google for the title of the paper cited in that post, you can find much more information.
I hope that this reply helps to educate at least one poster, but judging by the regularity with which this idea keeps reoccurring, it's a little bit like rearranging chairs on the Titanic.
True.
Also true AFAIK. I have not heard of anyone breaking those. But I must admit, I don't know if the weaknesses found ind SHA-1 applies to other variants of SHA as well.
You are completely mistaken about this part. A chain is not stronger than the weakest link. If you do signatures using SHA-1 and RSA, only one of the two has to be broken to forge a signature. When you sign a message, you put a signature on the output of the hash. If anybody can find another message with the same hash, they can simply put together your signature with the other message, and it will be a valid signature on a message you had never seen.
What could save you is the fact that there are different degrees of brokenness for a hash function. There are three kinds of common attacks to attempt on a hash function. The easiest one is to just generate a collision where you get to choose both messages. Next comes the problem of generating a collision where you are given one of the messages. Finally the hardest case is to be given a hash value and having to generate a message with that hash without having already an example of how to reach that hash value.
For MD5 an actual collision has been found, but still now algorithm to find a collision with an arbitrary message. For SHA1 there is AFAIK only demonstrated weaknesses. I have yet to see an actual SHA1 collision.
For signatures it might not be considered enough to just find a collision, after all you have to match the hash of a message, which was already signed. But even though you might feel secure, there are some things to worry about. First of all, once a technique to find collisions have been found, it only takes a little extra work to generate meaningful collisions. This is obvious to people with sufficient knowledge of the field, but a wouldn't believe this until it was actually demonstrated. With MD5 it has been demonstrated how to take two arbitrary plaintext files and from those generating two postscript files containing the two different texts but the same hash. Postscript was obviously chosen because the format contains a Turing complete language and thus was an easy target. But even simpler formats might be targeted with some additional work.
Consider the following scenario you send a signed email to somebody. You receive a reply saying something like "thank you for your email, but we need the signature on a postscript version, could you please sign the attached file?", and you find attached a postscript file containing the exact text you originally wrote. Would you sign that postscript file?
Do you care about the security of your wireless mouse?