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."
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!
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!
I think that the greatest threat in this case is not terrorists but the institutions such as government and security forces. Terrorists have a great interest in keeping their own transmissions secure but little interest in the communications of others.
Their tagets are soft, security is fairly low and information can be obtained using people on the street.
Counterintelligence is a game played by large beauracracies who are at peace at the moment but would really like not to be. It involves the use of large ammounts of resources for the main purpose of maintaining the status quo. Terrorists are not interested in the status quo, they want things to change.
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 ;-)
It does have implications for IPsec but the main question you are starting from the wrong place. The first question you should be asking youself is "Who is my enemy?". For the sake of this discussion let's assume the worst and go with the NSA.
.gov would really rather you not blow up.
The next thing you should be asking yourself is "What am I protecting?" Since we are assuming that the NSA is your enemy let's go ahead and say that you want to blow up rather large and expensive things that the USian
And the last factor is "How long do I want to keep this secret?"
For the sake of argument let's assume that the NSA can do twice as well as any known attack. Given all of that if the answer to the last question is "years" you have something to worry about. If it is months you very likely have something to worry about. If it is "weeks", "days", or "hours" you are very likely safe.
So yes at some point in the future if you have a long planning horizon it could matter.
What this all means is that you want to pay attention to all of this but there is no need to panic. At this point SHA1 is still better than MD5 for most things. So use it, pay attention to it, and most of all you might want to evalute what traffic you are passing. I've *always* been against passing secrets over a IPSec tunnel with a lifetime of more than a few months. This is simply because, IMO, IPsec is too complex to ever be safe over a long planning horizon. I'm in pretty damn good company here.
So pay attention and be ready to change when things change. And they *will* change. And I would not send anything that has a long lifetime over the wire.
http://www.schneier.com/paper-ipsec.html
Cypherpunks: Civil Liberty Through Complex Mathematics. Those who live by the sword die by the arrow.
Right, because every other nation freely gives away any edge it has in the world. Its like saying the U.S. was a spoiled brat because it didn't make public the information on how to construct a nuclear bomb.
Secrecy DOES give an advantage, and ALL countries employ it and benefit from its advantages. I don't know where you come from, but if this isn't the case in your country, then perhaps they're just incapable of keeping secrets or not innovative enough to have any worth keeping.
What, healthy that groundbreaking research is being done outside of the USA while the researchers are unable to even enter the country to talk about it?
-----
PGP Key ID 0xCB8FF658
#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.