Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Chinese Prof Cracks SHA-1 Data Encryption Scheme

Zonk posted more than 7 years ago | from the mad-math dept.

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

Sorry! There are no comments related to the filter you selected.

How long until... (4, Interesting)

dada21 (163177) | more than 7 years ago | (#17696648)

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

Re:How long until... (3, Insightful)

fyngyrz (762201) | more than 7 years ago | (#17696684)

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 had. Time to move on.

Re:How long until... (5, Insightful)

Anonymous Coward | more than 7 years ago | (#17696764)

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... (5, Funny)

myowntrueself (607117) | more than 7 years ago | (#17696960)

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... (-1, Troll)

Kjella (173770) | more than 7 years ago | (#17697098)

The more we know, the better off we are.

Is [goatse.cx] that [tubgirl.com] so [lemonparty.org]? And technology does do bad things, for one we're helluva lot better at polluting the planet than we were without technology... Most of the time, we simply assume that we'll work something out in the future, more technology to fix technology. So far, so good but I'm not sure what happens the next time we get a Hitler with racist theories and current genetics tech. 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.

Re:How long until... (1)

wrf3 (314267) | more than 7 years ago | (#17697178)

Technology absent intelligence doesn't do anything. We're the problem, not the things we develop. "Knowledge puffs up, but love builds up."

Re:How long until... (0, Troll)

drgonzo59 (747139) | more than 7 years ago | (#17696750)

And what does a professor at your local university gain from having tenure and sitting on his ass all day without doing anything (teaching 2 classes a week doesn't count as "doing something"), getting paid $70k, without the possibility of ever being fired until the day he dies...?


Here is a professor that actually does something and everyone is amazed - "wow, a professor that actually works, something is fishy..."

Re:How long until... (1, Informative)

Anonymous Coward | more than 7 years ago | (#17696882)

The tenure and high salary is a reward for the years said professor spent doing and publishing meaningful research. Why are you harassing them when they have already provided their talents?

Re:How long until... (0, Offtopic)

drgonzo59 (747139) | more than 7 years ago | (#17696984)

Because they are paid to do nothing. If their research was meaningful and worthy they should be paid for it while they were doing it. Why not instead reward those who actually research something or produce something useful.

Wouldn't your rather spend your tax money paying somebody who is finding a cure for cancer instead of paying somebody to sit around do nothing because they published stuff 20 years ago? What now they are too stupid to publish or not able to research anymore? -- No, they are just lazy. I don't see any reason whatsoever to reward laziness.

Re:How long until... (2, Funny)

Anonymous Coward | more than 7 years ago | (#17697012)

Speaking as a graduate student already avoiding all teaching duties and enjoying grants that basically asking nothing in return (my country is generous with funding), I think rewarding laziness is a very good thing.

Re:How long until... (1)

kfg (145172) | more than 7 years ago | (#17697130)

Wouldn't your rather spend your tax money paying somebody who is finding a cure for cancer. . .

Please identify this person.

KFG

Re:How long until... (1)

drgonzo59 (747139) | more than 7 years ago | (#17697170)

Go to the NIH website

Re:How long until... (5, Insightful)

Raffaello (230287) | more than 7 years ago | (#17697140)

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.

Re:How long until... (2, Insightful)

Instine (963303) | more than 7 years ago | (#17696754)

Like most things there, I'm guessing (tho this could well be very predjudist) that the Government pays... But she has done anyone who banks online a favour, by showing the flaw in the system. It would be naive to think that only she would ever crack it. What is interesting is that she has made it public knowledge that she has cracked it. This is probably China flexing its IT knowhow muscles a little. Not in such a threatening way, but a "look at the level at which we can play" kind of way. And no! This is not an act of war, nor would the US Gov be wise to call it one. But hey, their not so wise....

Re:How long until... (0)

Anonymous Coward | more than 7 years ago | (#17696936)

A three letter US Government agency already knows...

1) SHA-1 is more vulnerable to collisions then first calculated and...
2) Knows how spoofable SHA-1 packets are in the real world, if they don't already know how to spoof them.

It would be prudent for our secret TLA's to have technologic capabilities that are deemed 'mathematically improbable' to do.

Re:How long until... (3, Interesting)

Workaphobia (931620) | more than 7 years ago | (#17696992)

I think there's a difference in the way the government would treat someone who finds a critical vulnerability in an otherwise secure system, and someone who find just another practical exploit in an inherently insecure system.

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. Without these white-hat hackers, the black-hats have less ammunition.

Compare this to breaking a hash algorithm, where the security repercussions are not specific to any one application, but rather a whole domain that was previously thought to be secure. If you persecute a researcher in that field, you don't stop some major government intelligence agency from financing the same kind of research with even worse results, as they wouldn't be so public about it once they reach a conclusion.

However hopeless hash researchers think their field is, it can't be nearly as bad as trying to secure software implementations of buffer overflows (and whatever their modern successors are). Mundane flaws like that will always exist, so publishing specific information about them doesn't really help too much. Systematic, interesting flaws like this one however, are much more important and should be made public.

Re:How long until... (0)

Anonymous Coward | more than 7 years ago | (#17697172)

if there is a critical vulnerability, it isn't a secure system.

buffer overflows are far from impossible to eliminate entirely, they are the result of lazy programming.

That's not the big question. (4, Insightful)

Kadin2048 (468275) | more than 7 years ago | (#17697030)

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.

Whoops. (0, Flamebait)

fyngyrz (762201) | more than 7 years ago | (#17696652)

Science, 1. Religion, 0.

:)

Re:Whoops. (0, Offtopic)

eosp (885380) | more than 7 years ago | (#17696696)

I do not see how religion has to do with this one. Also, if you want real, somewhat efficient hashing, just take the MD5, take the SHA-1, and concatenate them.

Re:Whoops. (0, Offtopic)

fyngyrz (762201) | more than 7 years ago | (#17696748)

Religion in the sense of dogma. "It can't be done", "hopeless", etc. as described in the summary. Rather than try to actually examine the issue at hand, those people took the dogma and tread water. The Chinese researcher used science and got the results the others were taking from the book of common presumption. It's a religious approach against a scientific approach in the most common sense of the word. With the caveat that we assume that the story is true, of course. This is slashdot... :)

Re:Whoops. (1)

midnighttoadstool (703941) | more than 7 years ago | (#17696866)

"Since the probability of life in a given universe is astronimically small then since there is no God then there must be an infinite number of universes." [tacit presumption of Stephen Hawking, et al]

Science 1, Logic 0

Re:Whoops. (0)

Anonymous Coward | more than 7 years ago | (#17696962)

Doesn't mean Hawking is right...

Couple of errors there (2, Funny)

tgv (254536) | more than 7 years ago | (#17696982)

The probability is very small in a random universe, not any one you pick. And it still only implies a finite number of universes. And the correct spelling is "astronomically", which however means extremely large. You probably meant "infinitesimally"

That is 1 for school masterism, 0 for responding without thinking.

Re:Whoops. (1)

colinrichardday (768814) | more than 7 years ago | (#17697022)

And what justification does Hawking have for the claim that the probability of life in a given universe is [very] small? And what does he mean by a universe?

Re:Whoops. (-1, Troll)

Anonymous Coward | more than 7 years ago | (#17697016)

the number of reasons "not to do something" are pretty much limitless.

so just one of those reasons "not to do something" is the "dogmatic" reasoning, which you built up to be some huge foe that science had to battle (rolls eyes)

the other thousands of researchers had entirely different reasons not to research that area, perhaps one guy had to walk his dog, another guy was offered more money to research something else, another person was influenced by his parents to study horse dicks, another one liked to sleep a lot....

it's more like

science:1 humans:99999999999999999999999

you're a fucking moron.

Old (5, Informative)

suso (153703) | more than 7 years ago | (#17696656)

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

Re:Old (5, Funny)

Anonymous Coward | more than 7 years ago | (#17696712)

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 (5, Funny)

slimey_limey (655670) | more than 7 years ago | (#17696930)

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

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

Re:Old (1, Funny)

itlurksbeneath (952654) | more than 7 years ago | (#17697088)

set the evil-bit
The SUID bit?

Re:Old (0)

Anonymous Coward | more than 7 years ago | (#17696800)

AFAIK someone did.. that's why various OSS packagers switched to a hybrid checksum

e.g. check all of size, SHA1, SHA256, MD5 at the same time, with the theory being
that you might spoof one but not all three..

Re:Old (4, Insightful)

Schraegstrichpunkt (931443) | more than 7 years ago | (#17696884)

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

Re:Old (0)

Anonymous Coward | more than 7 years ago | (#17697038)

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

While collisions can't be eliminated entirely as long as the hash result has a limited size, intentional collisions can be made much more difficult by using two different hashes to help reduce substitution attacks, such as was exhibited for md5 where any subsection of data that hashes to X can be replaced with a different subsection of data as long as it still hashes to X, and the hash of the entire block of data will remain the same, depending on the likelihood that for a MD5 substitutable subsection MD5(x1)=MD5(x2), F(x1)!=F(x2) for some other hash function F.

Re:Old (4, Insightful)

nacturation (646836) | more than 7 years ago | (#17697048)

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 (1)

wfberg (24378) | more than 7 years ago | (#17697100)

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


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 (1)

smitty_one_each (243267) | more than 7 years ago | (#17696822)

In the international political chess match what you know is as important as how and when you knew it.
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 (0)

Anonymous Coward | more than 7 years ago | (#17697054)

let me just fix this for you, as you seemed to overdress the comment.

when you know is as important as what you know.

Re:Old (0)

Anonymous Coward | more than 7 years ago | (#17697122)

Original comment stands. The fact that the encryption was broken is one thing. When it was broken is another. By what means it was broken is a third. All three are of equal importance.
When encryption is compromised, everything using the key, from that point backwards in time, becomes a possible information leak.
No overdressing at all, AC.

Re:Old (1, Informative)

Anonymous Coward | more than 7 years ago | (#17697104)

No, this was announced two years ago in the press, and two years ago on Slashdot.

Re:Old (5, Informative)

fatphil (181876) | more than 7 years ago | (#17696846)

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.

Re:Old (1)

bcrowell (177657) | more than 7 years ago | (#17696926)

So why is this being announced now?
Because the /. editors don't care?

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 perl Digest::Whirlpool module still hasn't been packaged for Debian. I guess we need to have a high-profile crime involving SHA1 to convince people to start taking the issue seriously. It doesn't take a rocket scientist to know that the algorithm's days are numbered. It's a candle being burned at two ends. From one end, we have computers' performance getting faster exponentially. (Generating collisions is parallelizable.) On the other end, we have cryptographers doing theoretical work that widens the crack in the algorithm.

Why announce now? (4, Funny)

Original Replica (908688) | more than 7 years ago | (#17696950)

All your bank, are belong to us.

Slashdot editors are idiots. (1, Informative)

Anonymous Coward | more than 7 years ago | (#17696662)

SHA-1 is a hash algorithm, not an encryption algorithm. Achieve competence or quit.

Snuffle (5, Informative)

tepples (727027) | more than 7 years ago | (#17696892)

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 (3, Insightful)

nacturation (646836) | more than 7 years ago | (#17697076)

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:Snuffle (1)

swillden (191260) | more than 7 years ago | (#17697144)

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.

Re:Snuffle (0)

pedantic bore (740196) | more than 7 years ago | (#17697174)

Let me politely point out the typo in your posting, which should read:

This is the absolutely terrible idea behind ...

Article is a bit confused (4, Informative)

qbwiz (87077) | more than 7 years ago | (#17696672)

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?

Bullshit propaganda (1, Insightful)

GigsVT (208848) | more than 7 years ago | (#17696680)

This is total crap. I can't believe anyone would give any second thought to Chinese propaganda.

MD5 and RC4 was not "cracked" and I highly doubt SHA-1 was "cracked" either. Some weaknesses were found in MD5 that do not affect the majority of uses of it. I suspect the situation is the same here.

Re:Bullshit propaganda (1)

jrockway (229604) | more than 7 years ago | (#17696706)

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

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 (5, Insightful)

Aim Here (765712) | more than 7 years ago | (#17696794)

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

Re:Bullshit propaganda (0)

Anonymous Coward | more than 7 years ago | (#17697024)

Just shows you that "anti-communism" is and really always was just a way for the right to continue to engage in racism without having to admit to same in a post-segregation, post "yellows, reds, and the negroes, too!" world.

All of the "anti-communist" stuff that you read in the press and especially here is nothing short of white pride.

Re:Bullshit propaganda (0, Redundant)

pilgrim23 (716938) | more than 7 years ago | (#17696792)

remember the "do cell phone cause cancer"? Well I can just see the future: "New crack of security systems requires all citizens to have the firmware in thier mastoid implants re-flashed. Government speaks-person assures that the process is harmlelss harmless harmless....."

Re:Bullshit propaganda (1)

cg0def (845906) | more than 7 years ago | (#17697106)

ok first of all this is NOT propaganda and it IS very real. Do you think that the government along with MS and Sun would decide to move away from sha-1 if the was a chance for any of this to be a hoax? I know that this is a very circumstantial argument but if you want to know exactly how she did it all her research is published or is waiting to be released and you or anyone else is more than welcome to find a flaw in it. However, the article is very misleading because it implies that the internet is in some kind of imminent danger of destruction when in fact there is no such thing. The only thing is that if you piss off some REALLY smart cracker he/she can steal and read your information even if it's encrypted with SHA-1. There is a substantial part of the decryption process that has to be done by hand and involves a serious amount of decision making that CANNOT be done by a computer yet. So you can sleep well tonight ... noone will get to your bank account just yet.

Re:Bullshit propaganda (1)

nacturation (646836) | more than 7 years ago | (#17697148)

This is total crap. I can't believe anyone would give any second thought to Chinese propaganda.
The correct term is that it's broken [schneier.com] . The term "cracked" is actually Slashdot propaganda. Will you now give a second thought to the research regardless of the researchers' nationality?
 

What? (5, Informative)

jrockway (229604) | more than 7 years ago | (#17696688)

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:What? (1)

Zaknafein500 (303608) | more than 7 years ago | (#17696830)

Agreed. The author is obviously not well versed in the area of cryptography. A quick trip to Wikipedia [wikipedia.org] would be advisable.

Data security vs. physical security (1)

tepples (727027) | more than 7 years ago | (#17696952)

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.

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 (2, Informative)

tqbf (59350) | more than 7 years ago | (#17696956)

Without bothering to read the article, I will point out that as far as your bank is concerned, digest algorithms protect SSL negotiation in general and the key exchange in particular. A worst-case break in SHA-1 and MD5 can negate the protections provided by RSA and AES.

Re:Digest Functions In Relation To Encryption (3, Interesting)

hal9000(jr) (316943) | more than 7 years ago | (#17697090)

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.

Re:What? (1)

waynemcdougall (631415) | more than 7 years ago | (#17697080)

The implication is that because the professor broke SHA 1 that my online bank account is going to be drained. Not likely.

Yup, $23.71. You're right. Barely covers the cost of the CPU time.

News for nerds? (5, Insightful)

Toveling (834894) | more than 7 years ago | (#17696692)

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.

Re:News for nerds? (1, Funny)

Anonymous Coward | more than 7 years ago | (#17696808)

SHA-1 includes both addition and modulo, which we can no longer consider secure.

Encryption algorithm? (0)

Anonymous Coward | more than 7 years ago | (#17696704)

The article seems to mix "hashing" and "encryption". SHA1 is not encryption algorithm. It is hashing algorithm.

Re:Encryption algorithm? (0)

Anonymous Coward | more than 7 years ago | (#17697002)

SHA1 is not encryption algorithm. It is hashing algorithm.
Didn't you already post this [slashdot.org] ?

Full of surprises! (-1, Troll)

Anonymous Coward | more than 7 years ago | (#17696710)

I mean... her? Wang?

Anyone have a link to a *coherent* translation? (1)

pla (258480) | more than 7 years ago | (#17696720)

Okay, I started to read TFA...

According to a Beijing digest, 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.

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 "completely absurd" - It would have to make at least some sense to actually evaluate as "wrong".

Anyone have a link to info on this that makes sense? Like perhaps the nature of the specific weakness Xiaoyun found, and by how much it weakens SHA-1? Makes a big difference whether this means you can obtain an arbitrary SHA1, vs reducing the search space by one or two bytes.

Re:Anyone have a link to a *coherent* translation? (4, Informative)

Anonymous Coward | more than 7 years ago | (#17697040)

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.

Re:Anyone have a link to a *coherent* translation? (0)

Anonymous Coward | more than 7 years ago | (#17697102)

Was Eve Fairbanks of The New Republic a contributor to this article?

Would explain everything.

Hashing != Encryption (5, Informative)

cpuh0g (839926) | more than 7 years ago | (#17696740)

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 (1)

Martin Blank (154261) | more than 7 years ago | (#17696814)

For that matter, MD5 hasn't been the gold standard in several years, even before the MD5 weaknesses came to light. That it is one of the most commonly used hashing algorithms doesn't make it the gold standard.

Re:Hashing != Encryption (0)

Anonymous Coward | more than 7 years ago | (#17696818)

MD5 without salt should be already considered broken though - all you need to do is invest in a quite large (but not impossibly so) linux cluster and a set of "rainbow tables".

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

Re:Hashing != Encryption (4, Insightful)

wfberg (24378) | more than 7 years ago | (#17696978)


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

Re:Hashing != Encryption (2, Insightful)

iion_tichy (643234) | more than 7 years ago | (#17696872)

"Repeat after me: A hash algorithm is NOT encryption."

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 (1)

tepples (727027) | more than 7 years ago | (#17696964)

A hash algorithm is NOT encryption.

Yes it is [wikipedia.org] .

If a hash falls in the cluster... (1)

CaptainDefragged (939505) | more than 7 years ago | (#17697162)

...does anyone hear the mathematicians scream?

Coral cache (1)

junglee_iitk (651040) | more than 7 years ago | (#17696762)

http://en.epochtimes.com.nyud.net:8080/news/7-1-11 /50336.html [nyud.net]

I guess she cracked any encryption schemes, but found some loopholes. Great job indeed, given she has all those encryption schemes to her name, but the linked article is full propaganda, and less on details
According to a Beijing digest, 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.

However, professor Wang Xiaoyun, a graduate of Shandong University of Technology's mathematics department, and her research team obtained results by using ordinary personal computers.

and

  Within ten years, Wang cracked the five biggest names in data encryption. Many people would think the life of this scientist must be monotonous. However she said, "That ten years was a very relaxed time for me."

During her work, she bore a daughter and cultivated a balcony full of flowers. The only mathematics related habit in her life is how she remembers the license plates of taxi cabs.

Duh...

A Couple years? (1)

Psychotic_Wrath (693928) | more than 7 years ago | (#17696788)

major corporations will cease using the scheme within the next few years...
so its cracked by the chineese and it takes a couple years to change. sounds great anybody know where to get ahold of this :)

Makes me wonder (2, Interesting)

xigxag (167441) | more than 7 years ago | (#17696796)

Makes me wonder just how much trouble the US or international financial community would be in if an adversarial organization cracked a major security encryption and didn't politely announce it, but instead kept their achievement secret. And then either cracked mountains of banking/military data at a leisurely pace, selling it piecemeal to finance rogue networks OR timed a widespread release of the crack algorithm for a catastrophic hit upon (inter)national security. What steps are being taken to combat this from eventually occurring?

Re:Makes me wonder (1)

Workaphobia (931620) | more than 7 years ago | (#17697034)

I have a related question: If SHA-1 were suddenly made useless in a heartbeat, specifically what systems would fail? It'd probably be an issue for /etc/shadow and any systems that use it for password storage and checking, but what else besides that would crumble? Is it used within other protocols like RSA or AES?

Re:Makes me wonder (1)

Antique Geekmeister (740220) | more than 7 years ago | (#17697068)

The more common approach is to refuse to allow robust encryption, forcing local companies to use weak ciphers or to only permit robust encryption and authentication tools where the key can be obtained trivially by the government. This has certainly been done by the NSA for decades, with their old unconstitutional interference with exporting encryption technologies, with their Skipjack encryption authorized for use in cell phones and digital communications, and with the new Trusted Computing initiative led by Microsoft but with NSA cooperation. In both recent technologies, the keys are centrally held and managed in repositories where no court oversight exists and where the keys can be obtained by anyone who can convince the repository to release them, and where an agency like the NSA need simply steal them without a warrant to have any key they desire.

Yes, it sounds paranoid: but it's cerainly consistent with their tapping of core fibe-optic backbones in the USA and their current lack of judicial review under the umbrella of the Patriot Act.

no need to panic (4, Funny)

johncalltwo (521360) | more than 7 years ago | (#17696816)

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 (0)

Anonymous Coward | more than 7 years ago | (#17696862)

BZTJGSEBG13

Re:no need to panic (4, Insightful)

malakai (136531) | more than 7 years ago | (#17696920)

Fbzrgvzrf vg'f orfg gb uvqr va gur bcra.

Epoch Times (5, Informative)

rh2600 (530311) | more than 7 years ago | (#17696852)

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.

MD5 & SHA-1 might not be cracked..... (2, Interesting)

Spudster (875838) | more than 7 years ago | (#17696864)

But they are certainly weak against attacks using rainbowtables. Both algorithms should be tossed into the bit bucket for something a little more secure. New services including Hashbreaker, Schmoo, freerainbowtables etc show how easy it is to brute force using rainbowtables. RE: http://www.hashbreaker.com/ [hashbreaker.com] and distributed rainbowtable generation http://hashbreaker.com:8700/ [hashbreaker.com] http://wired.s6n.com/files/jathias/ [s6n.com] http://www.freerainbowtables.com/index-rainbowtabl es-distributed.html/ [freerainbowtables.com] http://www.darknet.org.uk/2006/02/password-crackin g-with-rainbowcrack-and-rainbow-tables/ [darknet.org.uk] -Spudster

Re:MD5 & SHA-1 might not be cracked..... (-1, Flamebait)

Anonymous Coward | more than 7 years ago | (#17697154)

Rainbow tables? I had NO IDEA that the gays were so into cracking passwords! Does that mean it is fashionable now? Will there be a show on Bravo about it?

Published in New Scientist 17 December 2005 (2, Informative)

gessel (310103) | more than 7 years ago | (#17696900)

From the original article cited by the epoch times article (at the moment /.ed)

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" (5, Informative)

arevos (659374) | more than 7 years ago | (#17696916)

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.

It WAS reported on Slashdot two years ago... (3, Informative)

Pi3141592 (942724) | more than 7 years ago | (#17697046)

...Here. [slashdot.org]


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! (1)

Cytlid (95255) | more than 7 years ago | (#17696944)

We're been Pwned! I just hope they don't hrack our ID-10-Tee hash algorithm encryption! Then all our base will belong to them!
   

What is this, Digg? (-1, Troll)

Anonymous Coward | more than 7 years ago | (#17696948)

This article sucks.

A few facts (4, Insightful)

Jerry Coffin (824726) | more than 7 years ago | (#17696976)

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.

Re:A few facts (1)

StealthyRoid (1019620) | more than 7 years ago | (#17697074)

A less than brute-force (2^80) attack against full SHA-1 was reported by Prof. Wang at the 2005 CRYPTO conference. I can't seem to find a copy of her paper, but there she reported a collision in 2^63 (within the realm of feasibility) operations. Full collisions in MD5 were found shortly before that. Neither hashing algorithm should be trusted for securing anything at this point. Not that these collisions mean that every script kiddie and l33t ahx0r are going to be out there changing digitally signed documents or cracking shadow files in mere seconds, but there are known flaws with both that make using them irresponsible.

Little Kernels Of Truth? (1)

StealthyRoid (1019620) | more than 7 years ago | (#17697042)

While the article is pretty much useless, there may be something to the overall point. I mean, it's not as though anyone can expect your average newspaper reporter, much less a Chinese state run paper reporter, to know much about the subject of encryption/hashing/etc..., so I think it's useful to look past the obvious errors in the article, and talk about what the underlying story actually is. _IF_ this is a new report of a collision in SHA-1, that wouldn't be surprising. Prof. Wang and her team have been responsible for discovering more than a few attacks against SHA and MD5 ( http://www.schneier.com/blog/archives/2005/02/sha1 _broken.html [schneier.com] ), so it's possible that she discovered a method of causing a collision in full SHA-1 in even less than the 2^63 operations that had previously been the max. This article could just be poorly reporting that. Or it could be 2 years behind the times. Either way, MD5, SHA-0 and SHA-1 have been known to have collision issues for a while now. At least in my own applications, I've moved on to using SHA-512 (a SHA-2 variant with a larger block size and 512 bit output), and as far as I know, there've been no reports of a collision attack against it.

Re:Little Kernels Of Truth? (1)

hal9000(jr) (316943) | more than 7 years ago | (#17697150)

so here is a question. in SHA-512, there are 2^512 possible hash values--a finite set. So there will be two different inputs that will result in the same value, right? There is not an infinite number of hash values.

Disinformation Theory (0)

Anonymous Coward | more than 7 years ago | (#17697128)

In the crossfire between Disinformation and counter-Disinformation, it takes Disinformation Theory to figure out what's going on.

Fortunately, my coauthor Prof. Philip Fellman (Southern New Hampshire University) and I have been working for years on a rigorous foundation for Mathematical Disinformation Theory. Or so we want you to believe.

-- Prof. Jonathan Vos Post

HDCP (0)

Anonymous Coward | more than 7 years ago | (#17697138)

Cool...

SHA-1 hashes are used in HDCP authentication. This may be one more step in making HDCP (even more) useless.

The `threat' (-1, Flamebait)

bogaboga (793279) | more than 7 years ago | (#17697166)

This is yet another conformation of the so called "China threat" mostly perpetuated by the current US government. For those who might not know, China successfully shot its own satellite out of orbit; a feat that was till then, only performed by Russia and the USA.

No matter what we do as Americans, we'll become less relevant in world affairs within a few decades as China overtakes us - worrisome indeed.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?