Slashdot Mirror
New, Faster Attack against SHA-1 Revealed
VxSote writes "According to Bruce Schneier's
blog, a team of Chinese cryptographers has announced new results against SHA-1 that speed up the time required to find collisions compared to their previously published attack. Schneier says that a SHA-1 collision search is now 'squarely in the realm of feasibility,' and that further improvements are expected."
Is that the same attack the chinese exchange student used in Lineage II?
Next there will be massive ASIC machines crunching your PGP ciphertext and nobody will be able to proove anything until Lt Cmdr Data comes up with another Fractal Encryption algorythm that even the Borg cannot break.
I repeat the saying I've heard comes from inside the NSA: "Attacks always get better; they never get worse."
And THAT kind of forward thinking, gentlemen, is why we're number one over here in the good ol' U.S. of A. So glad we spend money in all the right places.
** "It's not my job to stand between the people talking to me, and the ones listening to me." -- Pego the Jerk
All they did was look for a near-collision
differential path which has low Hamming weight in the "disturbance vector" where each 1-bit represents a 6-step local collision. Then they simply adjusted the differential path in the first round to another possible differential path so as to avoid impossible consecutive local collisions and truncated local collisions. Then obviously the final step taken was to transform two one-block near-collision differential paths into a twoblock
collision differential path with twice the search complexity.
Duh...
Ironically, the word ironically is often used incorrectly.
Okay so we still have SHA-256 and SHA-512 but can we really feel good about them?
Wanted: One reliable hash...
One is, is this really relevant when most terrorist threats these days are so low tech? Two, does anyone know what kind of funding the NSA gets these days? I remember a news report a couple years back that said they were deeply out of date with hardware and so forth.
How would you know what you need to improve without knowing the weaknesses of current algorithms?
Trust the Computer. The Computer is your friend.
Someone can only improve when he understands his own mistakes...
- Leon Mergen
http://www.solatis.com
Why create stronger algorithms if no one is going to break them? I'd rather the NSA found the exploits and told the right people, or the world, then somebody with bad intent.
I mean, I'm sure that these guys are the real thing, judging by their past experience breaking SHA-1 and how much notoriety they have. But they have been inconsistent with presenting information. It would be nice to see something thats really solid with information rather than what looks at best like a bit of speculation. Last I checked information on their last attack (2^69) was still pretty thin and I suppose its time to move on to SHA-256 anyways.
Of course it's important to find fault in 'secure' computing. If the white hats don't uncover it first, someone with malicious intent will discover it to their benefit.
As to your comment about spending time to develope a better algorithm, how do you know it's secure, if you don't try to break it???
We're all hypocrites. We all have hidden parts, it's the contrast between them that make us more a hypocrite than others
When these algorithms are created, they often represent a time tradeoff, the time to hash/encrypt versus the time to compare the hash/decrypt. These guys are just sharing with the world its time to move on to another algorithm. Although I agree it would be nice to find an algorithm that is guaranteed never to be weak!
I've just changed away from using SHA-1. Double ROT13 seems most appealing these days. ;)
http://slashdot.su/
Well, the method for "DNA-printing" a file would have to allow for the complete recreation of the file from the DNA-printing.
This has been actually done for a long time, it's called "file compression".
I am unamerican, and proud of it!
Things like this are inevitable. Crypto is an evolving science, and this kind of thing is healthy.
I for one am very excited about the future of crypto.
Ignore Alien Orders
I wonder how this will effect RFC 4109 in that it depreciates MD5 in favor of SHA1. Does this mean that SHA1, at 2^63 is less secure than MD5 at a brute-force 2^64? I'm not a crypto expert or anything, just asking the question; will this effect the proposed standard for the HASH algorithm used in IPsec?
I'd rather the NSA found the exploits...
The NSA did this six years ago. Just pick up any phone and ask them.
HJ
This is no better than increasing the hash key size. In fact, it's worse than increasing the hash key by the same.
If you take hash algo A at 32 bits, and algo B at 32 bits, but B is weaker than A, then hash collision calculation would be less than the complexity of A squared. (Since B is weaker than A)
If instead you double the hash size of A to 64 bits, then your collision calculation would be the square of the complexity of A at 32.
So, combining MD5 with SHA-1 could cause some problems, with both of them having weaknesses, neither is going to provide you much protection, even if you use them together.
If you built a safe out of paper and cardboard. Sure such a safe would, yes, be better than one made of just paper, or just cardboard, but it's still not better than a safe built out of two cardboard sheets.
Ideally, you don't want to build a safe out of either.
I am unamerican, and proud of it!
Even if they are unpronouncable ;-)
Two of the Chinese researchers (Xiaoyun Wang and Hongbo Yu) were due to present their SHA results at the CRYPTO 2005 conference in the US, but were denied visas in time to attend. Adi Shamir (the A in RSA) ended up announcing this latest result on their behalf.- chinese-crypto-researchers.html
http://cipher-text.blogspot.com/2005/08/visas-for
While this finding definitely shows a weakness in the SHA algorithm, it isn't a weakness that makes most applications that use SHA any more vulnerable. They found a way to generate two texts that produce the same hash using an algorithm with a time complexity of 2^63 instead of 2^80 as would be required for a brute force attack. However, being able to generate two texts that produce the same hash won't help you exploit most systems that rely on SHA. If someone finds a way to generate text that produces a SPECIFIED hash in 2^63 time, then there's reason to be concerned. However, since these findings show that SHA-1 has some weaknesses, it's probably time to start looking for a better hashing algorithm before a more serious vulnerability is found.
#1) That the NSA has better cryptologists than everyone else. Remember AES was widely reviewed before becomming an accepted standard, and not just by US researchers. Top experts from all over the globe looked at it, an decided it was secure. So for the NSA to know a weakness, means that they have experts beyond all others combined.
#2) They are very ballsy, and very certian that no one will find those exploits. The US government uses AES for secret and top secret data. It would be amazingly arrogant to know how to crack the crypto, and yet to still use it for the most secure documents.
#3) They are willing to trust that the authors, two foriegners (Dr. Daemen and Dr. Rijmen are Belgian) were unaware of this exploit. Remember that if an exploit was found, it is always possible the authors knew, and intended that they'd be able to use it.
It thus seems EXTREMELY unlikely that the NSA would know of a crack for AES and simply be sitting on it. It would put a great deal of incerdibly sensistive government data at risk, as well as US economic intrests.
No, what seems far more likley is that the US government came to the realization that strong crypto is widely available outside the US, and thus is makes no sense to try and restrict it from the public as it would only serve to give other nations an advantage.
So no, I don't believe AES is strong because the NSA is strong, though I respect their opinon to a great degree, I believe it's strong because the world cryptography community believes it is.
To date there have been two proposed attacks. One is called the XSL attack. It's not an actual break, simply something that would in theory make it easier to brute force, but still well out of the realm of possibility. More, the math behind it is suspect, it may not even be workable at all. Then there was teh cache timing attack. It does work, but required a special SSL server that gave out as much timing information as possible, and 200 million known plaintext bytes. Nifty, but not practical in the real world.
What no one seems to mention is that their attack finds "freeform" collisions. I mean, they go and find two plaintexts with the same hash. I wouldn't worry about it until they find 2^63 attack against given plaintext/hash.
You can read about the distinction in Birthday Paradox article on Wikipedia. In short, when the difficulty of finding collision against a given message is 2^n, the difficulty of finding any two colliding plaintexts is 2^(n/2).
So, while they may have found 2^63 attack against SHA-1, it is still a "birthday attack", and to find collision against my message signed with sha-1 the attack would still be 2^126.
Or did I miss something?
Robert
Bastard Operator From 193.219.28.162