Slashdot Mirror
Chinese Prof Cracks SHA-1 Data Encryption Scheme
Hades1010 writes to mention an article in the Epoch Times (a Chinese newspaper) about a brilliant Chinese professor who has cracked her fifth encryption scheme in ten years. This one's a doozy, too: she and her team have taken out the SHA-1 scheme, which includes the (highly thought of) MD5 algorithm. As a result, the U.S. government and major corporations will cease using the scheme within the next few years. From the article: " These two main algorithms are currently the crucial technology that electronic signatures and many other password securities use throughout the international community. They are widely used in banking, securities, and e-commerce. SHA-1 has been recognized as the cornerstone for modern Internet security. According to the article, in the early stages of Wang's research, there were other data encryption researchers who tried to crack it. However, none of them succeeded. This is why in 15 years Hash research had become the domain of hopeless research in many scientists' minds. "
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?
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?
There are two kinds of people: 1) those who start arrays with one and 1) those who start them with zero.
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/ and distributed rainbowtable generation http://hashbreaker.com:8700/ http://wired.s6n.com/files/jathias/ http://www.freerainbowtables.com/index-rainbowtabl es-distributed.html/
http://www.darknet.org.uk/2006/02/password-crackin g-with-rainbowcrack-and-rainbow-tables/
-Spudster
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.
Thats making a huge assumption that the NSA or any other organisation relies heavily on "one particular encryption mechanism" to transmit information. The industry has moved its focus away from relying on more powerful encryption schemes to more difficult to intercept transmition methods such as http://www.laser2laser.co.nz/laser_products.htm . There is no particular piece of the puzzle that makes a network or data more secure. Believing this is a major "shake up" or is going to cause a "major reaction" shows a lack of understanding about security on the part of the person making the speculation.
20th century Marxism is not progress...
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 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, the other major contender, has received very little scrutiny.
I've save a bunch of interesting links about hash functions on del.icio.us.
Need a Python, C++, Unix, Linux develop
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 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" 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.
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
>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.
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.
TFA refers to its own source as the New Scientist. A quick search there reveals the article in question is dated February 2005. So I guess this should probably come under "oldnews", but in any case the NSA had had plenty of time to play with it.
What concerns me is that in the last two years I've heard no news about a replacement for SHA-1. Maybe every's hoping that if they ignore the problem, it'll go away.
Sun has been investing in Elliptic Curve Cryptography for many years. Now that SHA1 has been broken, ECC appears to be urgently needed as a strong encryption replacement for common internet usage. According to the Sun Labs page, ECC is also a high-performance technology.
Zen tips: Pay attention. Don't take it personally. Believe nothing.
Call me a total thicky, but can't we strengthen any application that uses a hash by using several different hashes? e.g. concatenate the md5sum, SHA-1, SHA-256 and RIPEMD-160 of the input data to make a composite "super-hash". Wouldn't that make finding a collision very difficult?
Even if you have a way to find a collision for each of the algorithms in isolation, you now have to find a collision for all of them at the same time, which is surely far far harder.
Please do correct me if I'm wrong, I'm interested to know why this won't work because it seems to be the obvious approach in light of the problems that have emerged with MD5 and SHA-1.
>north
You're an immobile computer, remember?
Oh freakin crap. God I hate slashdot. Between that and "it's been x minutes since you last posted" ... Hey how about javascript to enable the god damned submit button after the timeout expires, mmkay? Let's try that again, I got nothing to do right now but wait.
The actual problem comes in something like this:
Document 1:
Give fwr a 10% raise this year
<!-- No one will see this unless they view the source: sdhf892598sljIU)*@(5986ljglkjsdlkgjg -->
Document 2:
Fire fwr immediately
<!-- No one will see this unless they view the source: 093w49sdjgljxlmxvbms.dmlksjlklkjwekj -->
(obviously this is oversimplified, but you can hide all kinds of undisplayed stuff in a PDF)
Done with slashdot, done with nerds, getting a life.
Any big group that operates as part of a government, particularly a government as enormous as that of the USA, WITHOUT extensive public oversight, will be hopelessly crippled by earmarking, cronyism, and all other manner of corruption and incompetence. I mean, if the NSA was worth half a shit in a tin can they'd have been able to stop people like McVeigh, Kaczynski, or the doofuses* that thought it would be a good idea to hijack a few planes.
A handful of really bright people working on a project that they truly care about can perform miracles of creativity and insight. If governments really want to get things done, they need to focus more on identifying those people and giving them the support they need -- whether it's a research grant, a loan with which to start a small business, or even just an environment where creativity and hard work are appreciated and respected. A "keep up the good work" now and then can go a long, long way (a woman I talked to who worked in HR suggested that a bit of respect and encouragement could easily avert 90% of the labour issues that her department dealt with BEFORE they became severe enough that HR had to waste time and money on them).
* Doofuses? Just look how well that has worked out for their feelow Muslims... their 70 virgins are probably going to turn out to be 70 desperate truckers with a taste for the dark meat...