Chinese Prof Cracks SHA-1 Data Encryption Scheme 416
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. "
How long until... (Score:4, Interesting)
I'm a big fan of teams like this in unraveling the security defects out there -- giving others more reason to make more secure schemes. I'd love to know how one can finance these groups (legally?). What does her group specifically gain from all this labor? Who pays for them?
Re: (Score:3, Insightful)
We gain the obvious: The more we know, the better off we are. All science contributes to rolling back the veil of the unknown, and (eventually) almost all science benefits us. Encryption research is no exception. Suppressing research in favor of the dogma of the day is old-school religious thinking. Not a good way to go.
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, anyway — it's not like they would tell us if they ha
Re:How long until... (Score:5, Insightful)
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.
Re:How long until... (Score:5, Funny)
Re: (Score:3, Funny)
Not so fast. (Score:5, Interesting)
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.
Re:Not so fast. (Score:4, Informative)
Re:Not so fast. (Score:5, Informative)
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?
Re: (Score:3, Informative)
Saying it once more for clarity:
1. You send a digitally signed email A which states, for example, that you do not approve of a particular business proposal.
2. They email you an unsigned postscript file A', which you prin
Re:Not so fast. (Score:5, Informative)
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 [nist.gov]
Re:Not so fast. (Score:5, Funny)
With due thanks to the environmental policies of the US government, glaciers are moving faster now, too.
NSA (Score:3, Interesting)
Any big group that operates as part of a government, particularly a government as enormous as that of the USA, WITHOUT extensive public oversight, will be hopeles
Re: (Score:3, Insightful)
You are making an incorrect assumption here: that the purpose of Osama was to benefit his fellow muslims. It was not. It was to destroy the "infidels" (meaning every non-muslim, but especially the USA). The way to do that (in his mind) is to start a jihad, a holy war. Now which one is more likely to throw their life aw
Re:How long until... (Score:5, Funny)
You never read any H.P Lovecraft then...
Re: (Score:3, Funny)
Oh, I dunno. (Score:3, Funny)
Oh.
Re:How long until... (Score:5, Insightful)
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.
Re: (Score:3, Interesting)
That's funny, G.W.Bush speaks very openly about his religion, yet I've never heard him speak a thing about the apocalypse. You seem to be under the influence of the anti-Bush propaganda machine.
Re: (Score:3, Interesting)
that problably because Bush is aware that anyone who refers to the rapture as a real and upcoming vent will be seen as a nutter except by fundementalist christians. Althought the number of fundies are large, they are not large enough to vote him in. He is also likely not a fundie himself. Chances are he's only pander
Re:How long until... (Score:5, Insightful)
(actually I dont completely believe that. almost EVERYTHING on mainstream news seems to be propaganda from one group or another to me. Its just that where bush is concerned, they dont really have to try very hard)
Re:How long until... (Score:4, Insightful)
Conclusion: we barely have a Constitution any more. It's hanging on by a mere thread.
C//
Re:technology is active (Score:5, Insightful)
No. I'm not saying that at all.
I'm saying that people are good or bad, people's actions are good or bad, and it hasn't got a single thing to do with cars, bullets, or highways. That's just evasive nonsense, mumbo jumbo from addled thinkers (or those seeking to escape responsibility.) We're human. We can choose. Choose well, and bear responsibility for good; choose poorly, and bear responsibility for bad. Technology isn't the culprit here. It's you. It's me. It's people.
People make choices. They're responsible for those choices. Highways, guns and communications are not. Any philosophical mumbo jumbo that says the more choices are available the more blame the choices carry, is completely and utterly worthless. Likewise, when technology can amplify a choice we make, we carry additional responsibility; the technology carries none at all. This has been true since the first rock was used with intent to kill.
Responsibility is the lost idea in modern civilization. People do anything to avoid it, to slough it off onto someone else. Well, I'm here to tell you straight out that the existence of a gun makes you no less culpable when you kill someone because it is physically easier to do, and no more respectable when you refrain in the face of whatever tempts you. It is no more or less about you and me than it was a thousand years ago. Science and technology are neutral. We have the power to turn them in either direction. We always have. There's no one here but us, and objects don't make choices. As the power is ours, so is the responsibility. 100%.
Also: If you let media change your mind, that's your responsibility. Media can only be "active" through your actions. In other words, you can always choose. Some choices are more difficult than others, certainly, but who ever promised you an easy ride? If anyone did, they were lying and you were a fool to believe them. Just about every choice you make carries responsibility with it. There's no way out. You can't blame the Internet, highways or weapons for your problems. Your problems come from human sources, at least those that aren't sourced by the ongoing processes of nature. Technology, science... these are the last places to look to place blame.
Re: (Score:3, Insightful)
As a direct answer, probably not. I'm not sure that you can prevent choice in any case, or execution of choice (action.) If you try, they'll probably fight you on principle and do it anyway, find a way around the "safeguards", etc. You can react when people make a choice and take action on it; and in many cases, you should. In my view of the optimum world, my rights end where yours begin, and if
Re: (Score:3, Insightful)
Re: (Score:3, Interesting)
The reason businesses and governments don't appreciate the work of some Joe Researcher who finds another buffer overflow vulnerability is that they are a dime a dozen and impossible to eliminate entirely, so rather than go after the bug they go after the guys who find and publish them.
That's not the big question. (Score:5, Insightful)
In the past, it was widely understood that the NSA was well ahead of the private sector in terms of both encryption and decryption. During the 70s and 80s, the private sector basically closed the "encryption gap" and produced some ciphers that (at least most people suspect) are as secure as those used by the NSA.
What's still an open question, is how far ahead the NSA is of the private/corporate sector in terms of breaking other people's ciphers.
Depending on the NSA's reaction, it might be possible to know whether or not this break was anticipated. If they're using SHA-1 internally, one can assume they didn't know about this discovery already, and they've fallen behind of the position many folks assumed they had. If they just shrug and smile, then they may have already known about this (and possibly been using it) for some time now.
Re:That's not the big question. (Score:5, Interesting)
Re:How long until... (Score:5, Insightful)
Here's that longer response/apology I promised below:
The argument I hear implicit in your words, that professors should be compensated for their research activities, is one I support. However, as I mentioned below, this is often not feasible because the "worth" of one's research is not always immediately apparent. Additionally, you are referring to tenured academics as lazy, which I simply cannot countenance. You glorify something that you do not understand. Therefore, though I am only a Ph. D. student at the moment, I wish to share my view (doubtless with its misconceptions) of the career as an aspiring academic:
Becoming a professor is not a career decision to be taken lightly and it is not for the lazy; it truly is something that must be born of a devotion to the pursuit of knowledge to the exclusion of almost everything else. The training process required to get a Ph. D. is lengthy, difficult, and generally unrewarding. True, we are generally funded while graduate students, but the funding is paltry, requires a TA or RA position at the institution unless you are fortunate enough to obtain a fellowship, and carries an expectation to devote every moment of our time to our studies and research. Even fellowships contain clauses prohibiting us from working without permission of the dean. Following a successful defense, most professors must undergo a more difficult and only slightly more rewarding postdoctoral position. These do not necessarily lead to tenure-track positions; approximately 10% will be offered assistant professorships, which carry an average salary of $44,939. In other words, after I complete my Ph. D. and a postdoc, I can look forward to starting at about $10,000 less per year than I would with most jobs I could attain right now with only a bachelor's degree in CS if I happen to be in this fortunate 10%. This is despite all of the work I have published without demanding anything in return (indeed, such work is expected). If I please my superiors and bring lots of grant money in for my institution (which involves writing a lot of proposals I'd rather not be bothered with, as they interfere with my research and other duties), I may eventually be granted tenure and perhaps rise in academic rank.
We are not compensated for publishing our research, so unless we choose to patent our innovations, our salary is our sole source of income.
A lazy person would not get this far. Anyone capable of enduring that much to reach this point is dedicated enough to the pursuit of knowledge to continue of his own accord because it is truly what he wishes to do.
Re: (Score:2, Funny)
Re:How long until... (Score:5, Insightful)
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.
Re: (Score:3, Insightful)
In actuality, great ideas sometimes fail to gain recognition by the community for years and the research itself can take months to years to perform before any worthwhile results are available. I am of the opinion that it is impossible to o
Re: (Score:3, Funny)
And by the way, what has he done for us lately?
KFG
Old (Score:5, Informative)
Re:Old (Score:5, Funny)
Because China now uses anti-satellite weapons now, so we have to "up" the evil-status a bit.
Next week, we'll hear that this same prof has some pirated DVDs
Re:Old (Score:5, Funny)
I misread that as "set the evil-bit".
Re:Old (Score:5, Informative)
Re: (Score:2)
The fact that this comes out now is either a) a human screw-up, b) an general admission of what has long been obvious to those 'in the know', c) stealth advertising to score some more encryption funding for other researchers, or d) a blend of a-c.
Re:Old (Score:5, Informative)
Here are Wang's papers on cracking hashes, which show the age of the cracks, from her webpage:
1)Xiaoyun Wang1, Hongbo Yu, Yiqun Lisa Yin, Efficient Collision Search Attacks on SHA-0,Crypto'05.
2)Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Finding Collisions in the Full SHA-1,Crypto'05.
3)Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005.
4)Arjen Lenstra, Xiaoyun Wang,Benne de Weger, Colliding X.509 Certificates, E-print 2005.
5)Xiaoyun Wang, Collisions for Hash Functions MD4, MD5,HAVAL-128 and RIPEMD,Crypto'04,E-print.
6) X. Y. Wang, X. J. Lai etc, Cryptanalysis of the Hash Functions MD4 and RIPEMD, Eurocrypto’05.
7) X. Y. Wang, Hongbo Yu, How to Break MD5 and Other Hash Functions, Eurocrypto’05.
I believe in crypto 2004 she was given a standing ovation for her presentation, which is almost unheard of in the ultra-competative world of crypto.
Xiaoyun Wang is a BABE!!! (Score:4, Funny)
Dude, I don't know whether or not she cracked SHA-1, but, as brilliant, 39-year-old, female mathematics professors go, this chick is HOT!!!
Man, what I wouldn't do to make babies with a chick like that...
Re: (Score:2)
So why is this being announced now? /. editors don't care?
Because the
It looks like she did this almost 2 years ago.
Given that the problems with SHA1 started showing up that long ago, it's very disappointing that so little progress has been made in converting to stronger algorithms. I have a perl application that used to use SHA1 for watermarking, and when the problems started showing up, I decided to go ahead and switch to Whirlpool as my hashing algorithm. In all that intervening time, however, the
Why announce now? (Score:5, Funny)
Re:Old (Score:5, Insightful)
Re:Old (Score:5, Insightful)
Re:Old (Score:5, Insightful)
WEP is a good example of what happens when non-cryptographers decide to make up a cryptographic function.
Re:Old (Score:5, Insightful)
What I can tell you is that actual cryptographers are researching SHA-512 and, so far, it's held up pretty well. No one is researching your custom hashing recipe. It might be fantastically strong, but, if history is any indication, it's more likely to be highly vulnerable to an attack that you didn't think about.
Re: (Score:2)
Including length seems like common sense though.
I'm not quite convinced it's a bad idea to use multiple hashes, as long as they are all state-of-the-art AND fundamentally different, not just re-hashes of the same concept. E.g. SHA-512 AND whirlpool.
Re:Old (Score:4, Informative)
The problem is that you're essentially creating a new hash function, H(x) = SHA1(x) || SHA256(x) || MD5(x), for which collisions can be computed piece-wise. To compute a collision for H(x), you can always start by creating a sequence of MD5 collisions, and see if any of these are also collisions for SHA-1 and SHA-256---which, I imagine, is more likely than you might think, since SHA1, SHA256, and MD5 all use the same basic design (compared to algorithms like Whirlpool). That won't necessarily work with a single hash function like SHA-512.
Joux's multicollisions attack (Score:3, Informative)
Actually, I've actually run collisions in MD5 through SHA-1 and multiple different signatures including Ripe and several. Multiple collisions in MD5 don't generate a corresponding signature in SHA and it would take a lot of work to find one that does.
Actually, you don't know what you're talking about. Go read "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions" by Antoine Joux. Unfortunately, it's not generally available online, but Hal Finney wrote a nice explanation of the problem here [mail-archive.com].
Re: (Score:3, Informative)
Article is a bit confused (Score:5, Informative)
Re:Article is a bit confused (Score:5, Insightful)
HERE's the coral cache: (Score:3, Informative)
What? (Score:5, Informative)
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.
Re: (Score:2)
Data security vs. physical security (Score:2)
The use of the word "online" reminds the reader that data security over an untrusted network is a much less mature field than physical security.
Digest Functions In Relation To Encryption (Score:3, Informative)
Re:Digest Functions In Relation To Encryption (Score:4, Interesting)
This may be a bigger issue with long term storage like e-signing a contract.
Re: (Score:3, Informative)
This is a message from Me to You, send me some $$$!
If there was a weakness in the hash function you may be able to find another plaintext that generates the same hash code, for instance, the hash function may also return a code
Re: (Score:3, Interesting)
The actual problem comes in something like this:
Document 1:
Give fwr a 10% raise this year
<!-- No one will see this unless they view the source: sdhf892598sljIU)*@(5986ljglkjsdlkgjg -->
Document 2:
Fire fwr immediately
<!-- No one will see th
Re: (Score:2)
Yup, $23.71. You're right. Barely covers the cost of the CPU time.
News for nerds? (Score:5, Insightful)
Anyone have a link to a *coherent* translation? (Score:2)
Overlooking the fact that a hash function does NOT equal "encryption", the above-quoted paragraph goes far beyond word choice and grammar errors, and appears outright factually... Well, not "wrong" so much as "co
Re:Anyone have a link to a *coherent* translation? (Score:4, Informative)
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.
Hashing != Encryption (Score:5, Informative)
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.
Re: (Score:2)
Re: (Score:2, Insightful)
Not entirely correct, though. The thing is that many crypotgraphyc "processes" rely on fingerprints of documents (as one signs the fingerprint rather than the whole document and stuff like that). So I think many current protocols would be affected. It's perhaps not encryption in a mathematical sense, but in a practical sense.
Nevertheless the article was crap, it doesn't even say in what way SHA-1 was broken (making it impossible to judge the severity).
Re:Hashing != Encryption (Score:5, Insightful)
Hashes will always have collisions, if (and only if) the input space is larger than the output space, sure.
Nevertheless, if a hash were perfect, there would be no more efficient way to find a collision than brute force.
When people are designing cryptographic protocols, they always assume a perfect cipher, a perfect hash, etc.
Typically, what these attacks mean, is that some one found a short cut, so that actually forging a signature or deciphering text would take less than brute force. How much of a big deal this is, depends on how much the difference is, and also on whether it exposes any weaknesses (e.g. 'if your input starts with 123, you'll always get the same hash, whatever comes next').
Makes me wonder (Score:3, Interesting)
Re: (Score:2)
no need to panic (Score:4, Funny)
Re:no need to panic (Score:5, Insightful)
Re: (Score:3, Insightful)
Epoch Times (Score:5, Informative)
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.
MD5 & SHA-1 might not be cracked..... (Score:2, Interesting)
Published in New Scientist 17 December 2005 (Score:3, Informative)
Busted! A crisis in cryptography [newscientisttech.com]
"LAST year, I walked away saying thank God she didn't get a break in SHA-1," says William Burr. "Well, now she has." Burr, a cryptographer at the National Institute of Standards and Technology in Gaithersburg, Maryland, is talking about Xiaoyun Wang, a Chinese cryptographer with a formidable knack for breaking things. Last year Wang, now at Tsinghua University in Beijing, stunned the cryptographic community by breaking a widely used computer security formula called MD5. This year, to Burr's dismay, she went further. Much further."
cute... [ningning.org]
Further information on the "crack" (Score:5, Informative)
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:
It WAS reported on Slashdot two years ago... (Score:3, Informative)
Incredibly old news. EE Times [eetimes.com] reported on it at the time, correctly referring to SHA-1 as a hashing algorithm, nothing more... by itself, anyway.
Oh Noes! (Score:2)
A few facts (Score:5, Insightful)
A short note [mit.edu] about the attack has been available for a couple of years as well. The note shows collisions for two different reduced versions of SHA-1.
Though it's not absolutely certain, my guess is that the reality behind the new announcement is that they've actually found a collision for the full version of SHA-1, and possibly for MD-5 as well. OTOH, maybe the mention of MD-5 is just a journalist's hashed (no pun intended) version of the fact that SHA-1 is based closely enough on MD-5 that an algorithm that's successful against SHA-1 will probably be effective with respect to MD-5 as well.
Wrong, wrong, wrong. (Score:5, Informative)
"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 [schneier.com]
and http://www.schneier.com/blog/archives/2005/02/cryp tanalysis_o.html [schneier.com] 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).
Not a surprise - here are old references (Score:3, Informative)
Also Bruce Schneier [schneier.com] wrote about it back then.
I guess it takes a while for the US government and Microsoft, et al to take action on the news.
Re: (Score:2)
While important, it doesn't mean that the Chinese suddenly own the NSA and Microsoft, as the article implies.
Do the editors read ANYTHING before posting!?
Re:Bullshit propaganda (Score:5, Insightful)
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.
Re: (Score:3, Insightful)
Wang Xiaoyun lives and researches in Beijing. Whether she's a communist or an anti-communist or not, I don't know, but the fact that both the Chinese government, and it's US-based enemies have published relatively uncritical articles on this research does tend to give it a bit of credibil
Re: (Score:2)
Re: MD5 is broken and should no longer be used (Score:5, Interesting)
I disagree with your assessment of MD5 and the majority of uses of it. There is a property of MD5 which is broken. It is possible to construct two bytestrings that have the same MD5 hash. In fact, it's relatively easy to.
This breaks an important property that most people assume is true about cryptographic hash functions. I think it's actually very hard, in practice, to determine whether or not losing that property renders a particular system more vulnerable to attack. I don't believe that downplaying the associated risk does anybody any favors. I believe MD5 should be treated as "Effort should be made to remove the use of this algorithm from any existing code unless a convincing case can be made that the break doesn't affect it.".
SHA-1 is similarly 'broken'. But, the break in SHA-1 is not currently computationally trivial to exploit. It is just less computationally expensive than it should be to generate two bytestrings with the same SHA-1 hash than it should be given the length of the hash. But once people start discovering weaknesses in algorithms, it's common that someone refines the technique to make the weakness worse. So, I would treat SHA-1 as "No new code should use this, and it should be removed from existing code if the required effort isn't very large.".
The biggest problem is that there isn't a clear algorithm to move to from SHA-1. SHA-256 and SHA-512 [wikipedia.org] are based on the same principles as SHA-1, so there is worry (but no proof) that the break in SHA-1 could be extended to these two hash functions as well. But WHIRLPOOL [wikipedia.org], the other major contender, has received very little scrutiny.
I've save a bunch of interesting links about hash functions [del.icio.us] on del.icio.us [del.icio.us].
Re: MD5 is broken and should no longer be used (Score:5, Interesting)
It is computationally feasible, now, to build collding X.509 certificates.
It is possible, in some common environments and with a little cleverness, to Create two documents which are both human-readable and meaningful and which have the same MD5 hash [cits.rub.de].
Those are attacks which a collision-resistant hash function is supposed to prevent.
A collision-resistant hash function which has been shown not to be collision-resistant is broken. As of today, there's no published way for someone to start with a file you created and match its MD5 with a document they created. But in the case where an attacker can generate both files (say, the new $MUSTHAVE binary that gets signed by the repository and the separate binary with the same MD5 that contains a Trojan) MD5 has lost its usefulness.
Re: (Score:3, Insightful)
SHA-2 is a new family of hash algorithms. But that's kind of like saying that Twofish is a new cipher algorithm that isn't Blowfish. Realistically, if someone finds a major flaw in Blowfish that wasn't anticipated in the design of Twofish, it's quite possible that Twofish has the same flaw because they're built along the same lines, despite being different algorithms.
The SHA-2 family is designed by the same people who designed the SHA-1 algorithm, and they were designed before the flaws in SHA-1 were dis
Re: (Score:3, Informative)
It is relatively easy with MD5. It would probably require less than a week of time on a modern computer, possibly only hours.
If you spent 10 million on an SHA-1 cracking box, it's estimated that it would take about 127 days to find two colliding files.
Here is a PDF that's my source [qut.edu.au] for this information.
An additional problem is that you can embed interesting things in .pdf, .ps or even HTML documents. You could embed both the evil code, and the good code. Then use a colliding block someone found a long
Re:Bullshit propaganda (Score:5, Informative)
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.
Ummm well...... (Score:3, Informative)
Snuffle (Score:5, Informative)
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 [wikipedia.org].
Re:Snuffle (Score:4, Insightful)
Re: (Score:3, Informative)
While you can say that SHA-1 can be used as the basis for a cipher (such as Snuffle), that doesn't change the fact that SHA-1, by itself, is a has
Re: (Score:2)
SHA-1 is a hash algorithm, not an encryption algorithm.
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 [wikipedia.org].
And any block cipher can be used as a hash algorithm or a stream cipher and any stream cipher can be used as a block cipher or a hash algorithm. This doesn't, however, mean that hash algorithms, block ciphers and stream ciphers are all the same thing. Not only are there practical advantages to using the right tool for the job, there are often good security reasons as well.
Couple of errors there (Score:3, Funny)
That is 1 for school masterism, 0 for responding without thinking.
Re: (Score:2)
Yes it is an encryption algorithm (Score:5, Interesting)
Something about the SHA-1 algorithm is that if you know the 512 bits of data and the 160-bit output, you can find the 160-bit input. Just do all the rounds in reverse. This means that if you rearrange the parameters, you can make a 160-bit block cipher: the 512 bits are the key, and the 160 bits are the block to be encrypted. Knowing the key lets you reverse the whole thing. This is what the SHACAL algorithm [wikipedia.org] is.
You can turn a block cipher into a hash algorithm as well, by using the data to be encrypted as the key.
Block ciphers and hash algorithms are designed with different security goals, however. A block cipher cares most that you can't find the key if given plaintext/ciphertext pairs. A hash algorithm cares most that two keys do not have the same effect, because those two keys are a hash collision by definition. As a real-world example, the "Tiny Encryption Algorithm" [wikipedia.org] has a flaw where each key functions identically to 3 others. On a block cipher, this means that the algorithm is 4 times weaker, because there are 1/4 the keys - not a big deal if the keys are big enough. When using it as a hash algorithm, however, it means that each input has 3 other easily-found inputs that have the same hash! This is what the piracy group Xecutor exploited to break the "version 1.1" Xbox.
Re:Multiple hashes (Score:5, Informative)
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 [slashdot.org] 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.
Re: (Score:3, Funny)
Miles, meet Zonk.
BTW, I like how you tactfully left out the fact that it's a dupe.