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 why a team from CHINA are the ones making this discovery?
/From the USA :)
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.
Im no expert but wouldnt using several different hashes on the same file be better?
Sure you could get a hash collision in one or more of them but getting the collision to happen in all would be somewhat more tricky no?
The basic problem is that the length of the hash is always much less than that of the data being hashed. If you compress a 9 bit message into a mere 8 bits, you have to appreciate that there is a 50% chance of a collision i.e. two input messages having the same hash because there are twice as many hashs values as possible messages.
All the hash algorithms are basically up against this problem, and on a much greater scale. The defense is that they use various techniques to make it such that if I were to produce a meaningful message, it is very difficult for an attacker to produce a different message with the same hash value.
To make matters worse, it has already been pointed out elsewhere that many message formats (email, PDF, PS, Word Docs etc...) already contain lots of redundant data that can be manipulated to reach some desired hash value in a way that is not easily observable by the user. Given this, and fast algorithms to find collisions, I think such research is quite signifiant.
-- Mike
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.
LOL, yea...
If there exists a flaw, it does not matter that we are the only ones that know about it. Sooner or later one of US is going to sell it.
Depends if it's your hotmail password, then no. if it's the passphrase on your private key on a server with millions of dollar's worth of transactions then yes. Going forward, I wouldn't use them (MD5 or SHA-1) for anything resembling security anymore
<? include ('signature.inc'); ?>
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
The problem is knowing whether the decrypt you get is what was originally encrypted. It is perfectly possible that you can decrypt one way, and get one perfectly valid plaintext, but decrypt it another way and get a different valid plaintext.
This is why a one time pad is completely secure: any cipher text can be deciphered to any plaintext.
#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.
NSA has been known to "fix" a major flaw in what was SHA, but now known as SHA-0. The did a minor change to the algorithm, but didn't tell anyone why they changed it, and what attack that change was meant to fix.
:)
It's not until years later that civilian crytographers discovered an attack that works fairly well with SHA-0, but not with the modifications made by the NSA.
So do give the NSA some credit.
The NSA doesn't release its finding about new attacks against encryption algos. They use the info to crack and keep secure. Promote AES as a standard, and have a decades worth of research about useful attacks against AES that no-one knows about but the NSA.
You're so wrong. When NSA discovered a flaw in SHA-0, they did not announce what flaw it was (to protect those who used it after they recommended it) and then released a new strengthened version, called SHA-1 (and yes, they recommended everyone to migrate to SHA-1 from the insecure SHA-0). Stop being paranoid, and get the facts before making a fool of yourself.
"Two things inspire me to awe -- the starry heavens above and the moral universe within." - Albert Einstein
Do you understand the difference between a hash function and a cipher? It doesn't appear so. And why on earth, if these researchers were indeed working nefariously for the Chinese government, would they try to publish their results at an American conference? Hmm, yeah...a good conspiracy theory, that one.
Xiaoyun Wang and Hongbo Yu write their names that way in their papers and on their website; that's good enough for me.
Oh, I remember. This is Slashdot and you're trolling. Silly me.