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?
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.
This article is completely devoid of any real content. It just says she "cracked it" over and over, not explaining whether a crack is a collision, preimage, or other attack. It also seems technically inaccurate, saying that SHA-1 'includes' MD5? I know that no one RTFA, but c'mon, at least cover for a crappy article by having a good summary: this story has neither.
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.
Besides; my suspicion is that if she's gone and cracked it, the odds are at least reasonable that the NSA and crew already had
Not necessarily. There are often times when major leaps like this are made because of the efforts of one exceptionally brilliant person. It doesn't matter if you have whole teams of really smart people working on a problem, because this one person will come along and break the field open in a new way. That seems to be what's happened here.
"Well said. I'm pretty sure that this is just the English translation of a Chinese state-run newspaper. (The "read original Chinese" link at the bottom gives this away.)"
Errr, you are aware that the Epoch Times is a virulently anti-Communist newspaper don't you? They're famous for doing some sort of 10-part history of Chinese Communism (which read like a lurid and hysterical diatribe. I picked up a copy once; I don't know much about the history of China but they had a summary of the Paris Commune of 1871 which was an utterly atrocious travesty of history). If anything, the Epoch times is far more likely to distort the facts in a manner that defames the Chinese government, hard as that may be to believe.
Not everything written in the Chinese language is censored by the Chinese government
"Do the editors read ANYTHING before posting!?"
I find the irony of THIS statement quite remarkable, given the above.
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.
We gain the obvious: The more we know, the better off we are.
You never read any H.P Lovecraft then...
In the free world the media isn't government run; the government is media run.
There is no other way to protect unpopular views. The whole purpose of tenure is to allow scientists with new or minority ideas that are outside of the scientific/political/economic orthodoxy to continue to do research in spite of the fact that their work can't get wide publication. We make them prove that they are competent by meeting the extremely high standards of the tenure review process - getting tenure is no cake walk - then we give them the freedom to follow research avenues without regard to how popular that area of research is, and without fear that unconventional avenues or conclusions will cost them their job.
Part of the price we pay for this is that some people will be lazy. Academia as a whole feels that this is worth the risk because:
1. The tenure review process will screen out the overwhelming majority of the lazy people - you simply can't get tenure if you're lazy - it's too damn hard.
2. Carrying a few lazy professors is more than worth the benefit of having a faculty that is unafraid to voice the truth as they see it without fear of reprisal from administration, established researchers in their field, powerful alumni, government, etc.
3. Knowing what work will lead to something "useful" is tantamount to being able to predict the future. The idea that one can tell in advance where important breakthroughs will come from or where they will lead is a bean counter's fantasy. Therefore we have to trust that extremely competent scientists when allowed to follow their own chosen research paths without coercion will come up with important results. It's worked for us so far.
Thats making a huge assumption that the NSA or any other organisation relies heavily on "one particular encryption mechanism" to transmit information. The industry has moved its focus away from relying on more powerful encryption schemes to more difficult to intercept transmition methods such as http://www.laser2laser.co.nz/laser_products.htm . There is no particular piece of the puzzle that makes a network or data more secure. Believing this is a major "shake up" or is going to cause a "major reaction" shows a lack of understanding about security on the part of the person making the speculation.
20th century Marxism is not progress...
And I hear that Microsoft is still looking for that one person.
TFA refers to its own source as the New Scientist. A quick search there reveals the article in question is dated February 2005. So I guess this should probably come under "oldnews", but in any case the NSA had had plenty of time to play with it.
What concerns me is that in the last two years I've heard no news about a replacement for SHA-1. Maybe every's hoping that if they ignore the problem, it'll go away.
"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."
Absolutely. I'm not in the least offended by what other people choose to do to themselves and with intelligently consenting partners. Amused sometimes, but not offended. I'm only offended by what people do to non-consenting partners or partners who cannot consent in a reasonably intelligent fashion. And in such cases, it is useful to know what is going on.
You said yourself: "we're helluva lot better at polluting the planet"... the culprit isn't technology. The culprit is people. Technology can clean up pollution, even eliminate it at its source in some cases. You're blaming the gun for the thoughts and actions of the person who decided to fire it, which is wrong. Guns and technology have no way to say "No, wait, don't do that!" It's not the same as when Bush orders a cop to pick someone up without a warrant; the action is evil, and the cop is evil for obeying because that cop could (and should) have said "no, this is wrong" and aborted the process. The lesson is: You can't blame intermediaries in any human action unless those intermediaries are also human.
Well, we call that the Government of the United States of America; they used to be controlled by a document we call the constitution, which laid a very nice groundwork for a government, but that era appears to be completely over.
Witness Commerce clause absurdities, 2nd amendment erosion, ex post facto law and punishment, phone tapping, mail opening, "free speech zones", theft of land for tax revenue, government backing of religion in multiple venues, loss of habeas corpus, torture... and all these changes made in how we operate without the (supposedly) required constitutional hoop-jumping. The only question that remains is, what new way will they find to foul our nest?
How close are we, really, to becoming something that in no serious way resembles what the founders put in place? As this happens, from where does the government derive its authority? If it won't obey the constitution (and that seems very clear indeed), then how is the government going to justify any action it takes? I really don't understand how a government official can look a run of the mill citizen in the eye today. But again, we're talking about the actions of human beings, not the capabilities of a government. Just because you have databases doesn't mean you have to make no-fly lists; you could have a list of people who need cancer surgery, instead.
Technology, inanimate objects, ideas - even horrifying ideas - these aren't the enemy. People without ethics that take other people's rights into account, or with canned ethics based on apocalyptic religious bullshit like G. W. Bush, those people are the problem.
I've fallen off your lawn, and I can't get up.