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. "

How long until...

[dada21 (163177)]

...the State Department decides this is considered a terrorist activity and finds a way to make it law/international treaty that this is abolished? Honestly, I can see the out-of-whack State security thugs deciding that this is an act of war.

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?

That's not the big question.

[Kadin2048 (468275)]

Here's what you really need to look out for: what's the NSA's reaction?

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.

[antirelic (1030688)]

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 [laser2laser.co.nz] . 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.

Re:How long until...

[by Anonymous Coward]

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.

Re:How long until...

[symbolic (11752)]

And I hear that Microsoft is still looking for that one person.

Not so fast.

[BrokenHalo (565198)]

TFA refers to its own source as the New Scientist. A quick search there reveals the article in question [newscientisttech.com] 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.

Re:Not so fast.

[wherrera (235520)]

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 :).

Re:Not so fast.

[kasperd (592156)]

I wonder why a comment with two thirds of misinformation gets rated Informative.

There are actually several SHA-1 replacements out there, including SHA-224, SHA-256, SHA-384, and SHA-512.

True.

None cracked yet.

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.

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 :).

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:Not so fast.

[Simon Garlick (104721)]

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 [nist.gov]

Re:Not so fast.

[debrain (29228)]

Even the US government, which moves at the speed of a glacier

With due thanks to the environmental policies of the US government, glaciers are moving faster now, too.

Re:How long until...

[myowntrueself (607117)]

We gain the obvious: The more we know, the better off we are.

You never read any H.P Lovecraft then...

Re:How long until...

[fyngyrz (762201)]

Is [goatse.cx] that [tubgirl.com] so [lemonparty.org]?

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.

And technology does do bad things, for one we're helluva lot better at polluting the planet than we were without technology

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.

Or another totalitarian regime backed up by massive databases, computer checks and surveilance cameras. KGB or Stasi would just drool over the possibilities they'd have today.

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:How long until...

[diablomonic (754193)]

there is no anti bush propaganda machine, only truth...

(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:technology is active

[fyngyrz (762201)]

What you're saying is if the bullets reach the right people for the right reason then guns can be good, but if the slugs hit the wrong person or for the wrong reason then they're bad.

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:How long until...

[Metasquares (555685)]

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:How long until...

[Raffaello (230287)]

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.

Old

[suso (153703)]

It looks like she did this almost 2 years ago. So why is this being announced now?

Re:Old

[by Anonymous Coward]

It looks like she did this almost 2 years ago. So why is this being announced now?

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

[slimey_limey (655670)]

we have to "up" the evil-status a bit.

I misread that as "set the evil-bit".

Re:Old

[slimey_limey (655670)]

Nope, the evil bit [wikipedia.org].

Re:Old

[fatphil (181876)]

It was even on Slashdot back in 2004, IIRC. But heck, this is slashdot

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!!!

[mosel-saar-ruwer (732341)]

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!!!

JPG: Xiaoyun Wang [ningning.org]

JPG: Xiaoyun Wang [spacedaily.com]

JPG: Xiaoyun Wang [ucl.ac.uk]

JPG: Xiaoyun Wang [tsinghua.edu.cn]

Man, what I wouldn't do to make babies with a chick like that...

Why announce now?

[Original Replica (908688)]

All your bank, are belong to us.

Re:Old

[Schraegstrichpunkt (931443)]

Honestly, using SHA-512 is probably more secure than using a bunch of hashes concatenated together.

Re:Old

[nacturation (646836)]

Honestly, using SHA-512 is probably more secure than using a bunch of hashes concatenated together.

Probably? I'll grant you that the output of SHA-512 is going to be longer than combining several small hashes, but I don't intuitively see that it's necessarily more secure. If there aren't any weaknesses in SHA-512, then it would have more security, but if there are weaknesses that could be exploited to find identical hashes is that more or less difficult than exploiting weaknesses in multiple smaller hash functions?
 

Re:Old

[CryBaby (679336)]

I'll grant you that the output of SHA-512 is going to be longer than combining several small hashes, but I don't intuitively see that it's necessarily more secure.

Intuition doesn't have anything to do with it. SHA-512 has not been cracked and so it meets the definition of a "secure" hash function. Concocting your own recipes, especially based on hash functions currently known to be insecure, is a classic mistake made by non-cryptographers.

WEP is a good example of what happens when non-cryptographers decide to make up a cryptographic function.

Re:Old

[CryBaby (679336)]

I can't tell you if SHA-512 is stronger than some combination of hashing functions you might come up with. The reason I can't tell you is because I'm not a cryptographer, which is my point -- neither are you.

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:Old

[Schraegstrichpunkt (931443)]

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.

Article is a bit confused

[qbwiz (87077)]

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 [slashdot.org] two [slashdot.org] slashdot stories?

Re:Article is a bit confused

[RAMMS+EIN (578166)]

And here I was, thinking that Zonk had finally posted something great. I even jumped through hoops to get at the story, which I normally wouldn't have seen, because Zonk is on my block list. I guess I'll keep him there.

What?

[jrockway (229604)]

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.

Re:Digest Functions In Relation To Encryption

[hal9000(jr) (316943)]

Having read the article adn having a cursory understanding of secure hashing, when used with SSL, the chances of this break being useable is very, very unlikely because even assuming an attacker could get in the middle, they would still have to calculate the collision in near real time. Wiht hashes, generating a collision is the "break."

This may be a bigger issue with long term storage like e-signing a contract.

News for nerds?

[Toveling (834894)]

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.

Hashing != Encryption

[cpuh0g (839926)]

Repeat after me: A hash algorithm is NOT encryption.

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:Hashing != Encryption

[wfberg (24378)]

It's only a matter of time before other hashes "fall" really - you're taking a large vector space, and mapping to a smaller one. You're in a "state of mathematical sin" relying on that for validation :-)

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').

no need to panic

[johncalltwo (521360)]

Gung'f jul V arire hfr nal bs gubfr arjsnatyrq rapelcgvba fpurzrf, guvf bar jbexf, naq fur jvyy arire jevgr n negvpyr ba oernxvat vg.

Re:no need to panic

[malakai (136531)]

Fbzrgvzrf vg'f orfg gb uvqr va gur bcra.

Epoch Times

[rh2600 (530311)]

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.

Further information on the "crack"

[arevos (659374)]

I took a look at the Google Cache [209.85.135.104] of the article, and it would appear this is old news. This is the collision attack first found back in February 2005, which requires fewer than 2^69 operations, rather than the 2^80 operations a brute force approach would need (see Wikipedia [wikipedia.org] and Bruce Schneider's Blog [schneier.com]). According to Wikipedia, this was later improved so that fewer than 2^63 operations were needed.

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.

A few facts

[Jerry Coffin (824726)]

For those who care, Bruce Schneier gave some real facts [schneier.com] about the attack on his site a couple of years ago. As he pointed out:

For the average Internet user, this news is not a cause for panic. No one is going to be breaking digital signatures or reading encrypted messages anytime soon. The electronic world is no less secure after these announcements than it was before.

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.

[MadMidnightBomber (894759)]

"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).

Re: MD5 is broken and should no longer be used

[Omnifarious (11933)]

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

[Beryllium Sphere(tm) (193358)]

>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.

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:Bullshit propaganda

[lxt518052 (720422)]

True. Except that Epoch Times is usually full of anti-Chinese propaganda.

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.

Re:Bullshit propaganda

[Aim Here (765712)]

"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.

Snuffle

[tepples (727027)]

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].

Re:Snuffle

[nacturation (646836)]

While that's definitely interesting, it's still not the case that SHA-1 is an encryption scheme. I mean, if you encrypt all your data with SHA-1 then I suppose you ought to be really happy that researchers have found a way to potentially reduce the monumental decryption effort.
 

Re:Anyone have a link to a *coherent* translation?

[by Anonymous Coward]

This appears to be the professors website:

http://www.infosec.sdu.edu.cn/people/wangxiaoyun.h tm [sdu.edu.cn]

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%20Coll isions%20in%20the%20Full%20SHA-1.pdf [sdu.edu.cn]

Xiaoyun Wang, Yiqun Yin, Hongbo Yu, Collision Search Attacks on SHA1,2005
http://www.infosec.sdu.edu.cn/paper/Collision%20Se arch%20Attacks%20on%20SHA1.pdf [sdu.edu.cn]

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.

Yes it is an encryption algorithm

[Myria (562655)]

Block ciphers and hash algorithms are basically the same thing in two different modes. If you look at the SHA-1 algorithm, you'll notice that the main part of the algorithm is taking a 160-bit input (previous hash) and a 512-bit input (data to hash) and producing a 160-bit result (new hash).

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

[David Jao (2759)]

Call me a total thicky, but can't we strengthen any application that uses a hash by using several different hashes?

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.