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

Comments

Old

[suso]

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

Re:Old

[fatphil]

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

[slimey_limey]

Nope, the evil bit.

What?

[jrockway]

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.

Hashing != Encryption

[cpuh0g]

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.

Epoch Times

[rh2600]

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.

Snuffle

[tepples]

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.

Further information on the "crack"

[arevos]

I took a look at the Google Cache 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 and Bruce Schneider's Blog). 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.

Wrong, wrong, wrong.

[MadMidnightBomber]

"According to a Beijing digest, this SHA-1 encryption includes the world's gold standard Message-Digest algorithm 5 (MD5)."

Where do I start? SHA-1 stands for 'Secure Hash Algorithm 1' and is not an encryption scheme. Neither does it include MD5 which is a completely different hash (or message digest) algorithm.

See Schneier - http://www.schneier.com/blog/archives/2005/02/sha1 _broken.html and http://www.schneier.com/blog/archives/2005/02/cryp tanalysis_o.html for actual coverage of the break. "They can find collisions in SHA-1 in 2**69 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point." That's down from 2**80, so it's a concern, but not exactly the end of the world.

New apps being written should probably be using SHA-256 (256 bits) rather than with SHA1 (160 bits only).

Re:Not so fast.

[Simon Garlick]

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

Re:Not so fast.

[kasperd]

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?