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