New, Faster Attack against SHA-1 Revealed 298
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 attack... (Score:5, Funny)
Re:Is that the attack... (Score:2, Funny)
They sped up time? Impressive!
Re:Is that the attack... (Score:4, Funny)
Not really. They moved, which meant that, relative to them, they sped up time for the rest of us!
Re:Is that the attack... (Score:2, Funny)
Re:Is that the attack... (Score:5, Funny)
So it's the same attack.
Oh, wait...
The world is collapsing around me! (Score:5, Funny)
oh God bless them, those kooky spookies (Score:5, Funny)
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.
Re:oh God bless them, those kooky spookies (Score:3, Insightful)
Re:oh God bless them, those kooky spookies (Score:5, Informative)
Like public-key encryption. People in Britain discovered it first, but kept the research secret.
Re:oh God bless them, those kooky spookies (Score:3, Insightful)
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.
Well that would assume a few things (Score:5, Insightful)
#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.
Re:Well that would assume a few things (Score:3, Funny)
- NSA
PS. pwned
Re:Well that would assume a few things (Score:3, Insightful)
2) I'm impressed that you know what they use for top secret data - do you have any references for that? I'd note that, if USA top-secret data were encrypted by a different system, the NSA might well decide it was worth the risk of AES being cracked to be able to read their enemies' data.
3) If the authors, on their own, were capable of finding a break then their work would most likely have
Re:Well that would assume a few things (Score:3, Interesting)
Consider, it took the IBM cryptographers less than five years to discover differential cryptanalysis (they called it the "T-attack"), so maybe open academia were simply unlucky or unfocused when it came to block cipher crypta
Re:oh God bless them, those kooky spookies (Score:3, Insightful)
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.
Re:oh God bless them, those kooky spookies (Score:3, Insightful)
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.
Re:oh God bless them, those kooky spookies (Score:4, Interesting)
They fixed SHA up cuz they knew of a flaw, but didn't explain what the fix does.
For DES, they were
But their interference in DES is to restrict DES DOWN to a 56-bit keyspace, cuz they knew that DES was TOO good.
Almost anyone with a million bucks can search through 56-bit key space nowadays. As far as I know, there currently does not exist a DES attack that is more efficient (cheaper) than exhaustive search. Not bad for a 20 year old algorithm, huh? That's SECURITY!!
It is commonly believe in the crypto community the weakest point of attack for DES is its small key space.
Now imagine how many more years of service we could had squeezed out of DES, if the keyspace was set to 128?
Re:oh God bless them, those kooky spookies (Score:2)
Re:oh God bless them, those kooky spookies (Score:3, Informative)
Re:oh God bless them, those kooky spookies (Score:2, Informative)
OK so thats bait.
Re:oh God bless them, those kooky spookies (Score:2, Funny)
Re:oh God bless them, those kooky spookies (Score:3, Funny)
Big deal (Score:5, Funny)
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...
Re:Big deal (Score:2, Informative)
Would someone with mod points please mod parent funny?
I, for one, would not have thought of that... :-)
I've gone blind! (Score:2)
I mean I've lost situational awareness!
Re:Big deal (Score:2, Funny)
Re:Big deal (Score:2, Funny)
Re:Big deal (Score:2)
Re:Big deal (Score:4, Funny)
Re:Big deal (Score:5, Funny)
Re:Big deal (Score:2)
Re:Big deal (Score:2, Funny)
But did they use a flux capacitor?
Re:Big deal (Score:5, Funny)
Not Found
The requested URL
Oh, yes, I've just wet my pants with excitement.
Now can we panic? (Score:4, Funny)
Okay so we still have SHA-256 and SHA-512 but can we really feel good about them?
Wanted: One reliable hash...
Re:Now can we panic? (Score:5, Funny)
Re:Now can we panic? (Score:3, Funny)
Buddy, if you're keeping that cyanide pill close by, the guy with the tinfoil hat isn't the only crazy one. You might as well label yourself correctly and put your own tinfoil hat on.
Re:Now can we panic? (Score:2)
Commit everything to memory, keep a cyanide pill close by and hope like hell that that crazy guy with the tinfoil hat is wrong.
You do know he's wearing that hat so people can't read his mind right? Maybe your memory isn't the safest place to store things.
Re:Now can we panic? (Score:2, Funny)
I know of one. It has a problem with snack collisions though... or rather, the user has a problem with snack collisions.
Re:Now can we panic? (Score:3, Interesting)
It's slower than SHA-1 but guess what? Security costs CPU cycles. A lot of people tend to forget this most important lesson.
Simon.
Two questions... (Score:3, Interesting)
Re:Two questions... (Score:5, Insightful)
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.
Re:Two questions... (Score:2)
Come on. You know that report was a plant!
--Rob
Few Details? No report? No paper? (Score:5, Insightful)
Personally, I'd dump SHA. (Score:2)
Re:Few Details? No report? No paper? (Score:2)
Re: (Score:2)
Re:Few Details? No report? No paper? (Score:3, Informative)
Security (Score:5, Funny)
Re:Security (Score:2, Funny)
Re:Security (Score:2)
Comment removed (Score:5, Funny)
Re:Security (Score:5, Funny)
Re:Security (Score:3, Informative)
In this example for simplicity's sake, I'm going to use a ficticious function to shorten the output. The same logic will apply to any hashing function that gives output of a specific length.
Let's give this function a name, so that people don't assume I'm using SHA-1, and flame me for it. Let's call the function "melandy_hash", and say that for whatever input it receives, it gives a 6 digit hex number for the output (yes, I know that this is ridiculously short, but this is a
Crypto is an evolutionary process (Score:4, Interesting)
I for one am very excited about the future of crypto.
Re:Crypto is an evolutionary process (Score:3, Funny)
/ minor sarcasm-- could you tell?
Re:Crypto is an evolutionary process (Score:4, Insightful)
RFC4109 (Score:5, Interesting)
Re:RFC4109 (Score:2)
Now, this SHA-1 attack is 2^63 complexity, but this is orders of magnitude less than the 2^80 brute force.
Now, what makes you think that there isn't a faster MD5 attack than just the plain brute force 2^64? Assuming a relative number of orders of magnitude, we're talking around 2^50 or so complexity for an MD5 hash attack.
Re:RFC4109 (Score:5, Insightful)
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 [schneier.com]
Re:RFC4109 (Score:4, Informative)
1) Figure out what the secret key is based on the data and hashes being sent. If you could do this, you could generate your own HMAC and send your own data without being detected.
2) Intercept the packet and find a way to change the data in a way that will still generate the same hash value. This would allow you to change packets without being detected.
The vulnerability the researchers found doesn't help you accomplish either of these tasks, but it does show that SHA-1 has some weaknesses. Therefore, it's probably a good idea to start moving to a different hashing algorithm before somebody figures out a practical way to do #1 or #2. Also keep in mind that an HMAC exploit wouldn't help an attacker decrypt IPsec packets. To do this, a vulnerability would need to be found in either the encryption algorithm or the key exchange algorithm. In reality, a HMAC exploit by itself would only allow an attacker to send garbage data to the target address.
Re:RFC4109 (Score:4, Informative)
Second, RFC 4109 refers to the HMAC algorithms used for computing per packet integrity checksum that is resistant to tampering by a man in the middle. HMACs take as input both a known message and a shared secret (often, a session key for a symmetric key algorithm like DES, triple DES, AES, RC4, etc) and compute hash result ( MD5, or SHA1, or SHA-256, etc. ). In other words, part of the input to the hash algorithm is unknown. This makes it very difficult to find two messages, X and Y that compute the same HMAC. I.e. find X and Y such that HMAC(X, K) == HMAC(Y, K), where K is the shared secret. The attacks on MD5 and SHA-1 so far assume that there is no K, or if there is, it is known. And if the man in the middle knows K, he doesn't need to use these new cool attacks to tamper with messages; he's the man in the middle, he just tampers and re-computes the HMAC with far less computational overhead.
I've see no indication in Schneir's blog entry that these attacks break HMACs.
That said, it is surprising that SHA-256 wasn't added to the MUST list for RFC4109, given that when this RFC was published, it was known that SHA1 had be shown to be vulnerable to attacks of less than O(2^69). But then again, the RFC also mentions AES128 as MUST, but not AES256. Odd.
Solution? (Score:2, Insightful)
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?
Re:Solution? (Score:4, Insightful)
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.
Re:Solution? (Score:2)
Re:Solution? (Score:3, Interesting)
Although I'm not sure how these shortcut collision attacks fit in Joux's construction -- my recollection of it was that it was useful for collision search using the birthday paradox.
Alternatives? (Score:2)
How about RIPEMD? Anyone using it seriously?
Re:Alternatives? (Score:2)
At the moment, Tiger and Whirlpool seem to be the only hash algorithms outside of the family that haven't been successfully attacked. I'd go with Whirlpool, personally.
Re:Alternatives? (Score:2)
All these hashes are in the same family, but it's not clear at present how likely it will be that attacks will be found on the longer RIPEMD/SHA variants.
Anonymous "team of Chinese cryptographers" (Score:5, Insightful)
Even if they are unpronouncable ;-)
Re:Anonymous "team of Chinese cryptographers" (Score:5, Insightful)
Thank you for posting that (Score:3, Interesting)
Kind Regards
I'm lazy and not a mathematician ... (Score:2)
Re:I'm lazy and not a mathematician ... (Score:3, Insightful)
Dumb question (Score:3, Funny)
Re:Dumb question (Score:2)
Re:Dumb question (Score:2)
Afaik all attacks against MD5 and SHA1 are not "post-image" attacks. That is, the acttacker can generate two hashes with different data but with same hash, but not take existing data and generate new data with same hash.
Visa problems for the authors (Score:5, Informative)
http://cipher-text.blogspot.com/2005/08/visas-for
Re:Visa problems for the authors (Score:5, Informative)
Re:Visa problems for the authors (Score:3, Insightful)
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.
SHA-1 is still good for a lot of applications (Score:5, Interesting)
"Freeform" collision (Score:5, Interesting)
You can read about the distinction in Birthday Paradox article on Wikipedia [wikipedia.org]. 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" [wikipedia.org], and to find collision against my message signed with sha-1 the attack would still be 2^126.
Or did I miss something?
Robert
Re:i'll never understand why... (Score:3, Insightful)
Re:i'll never understand why... (Score:4, Insightful)
Someone can only improve when he understands his own mistakes...
Re:i'll never understand why... (Score:4, Insightful)
Re:i'll never understand why... (Score:5, Funny)
The NSA did this six years ago. Just pick up any phone and ask them.
HJ
Re:i'll never understand why... (Score:2)
Re:i'll never understand why... (Score:3, Insightful)
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???
Re:i'll never understand why... (Score:3, Insightful)
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!
Re:i'll never understand why... (Score:2)
Does anyone else get the delicious irony that this got modded "troll"?
Re:It's an insurmountable problem. (Score:5, Insightful)
This has been actually done for a long time, it's called "file compression".
Re:It's an insurmountable problem. (Score:3, Interesting)
Detecting minute differences, like the ones between twins, is EXACTLY what hashes should do. The minute differences between a check in the amount of $100 or a check in the amount of $1000, for example. They both sta
Re:It's an insurmountable problem. (Score:2, Informative)
The problem is that these algorithms rely on external characteristics of the data sources and render them to a short description. Indeed, a "DNA" approach would look at what makes up the files (binary) rather than the obvious (ASCII characters) and create a profile that could only match that file.
Er, what are you talking about? SHA-1 works with blocks of binary data, not ASCII characters, and it's impossible to "create a profile that could only match that file" since such a hash would be at least as la
Re:It's an insurmountable problem. (Score:2)
You forgot about lossy compression. In a way, you could view gzip, and bzip2 as hashing algorithms that take a larger file and reduce it to a smaller size.
This "hash" would only match one file per "hash", and the "hash" would be smaller than the file itself.
Re:It's an insurmountable problem. (Score:2)
Like all lossless compression algorithms, they make most arbitrary files bigger (e.g. use dd to right a couple MB from
Re:It's an insurmountable problem. (Score:2)
00
01
10
11
Could you devise a hash that uniquely identifies each of those values in fewer bits? No? What if my files were 3 bits and I wanted a 2 bit hash? 4 bits in a 3 bit hash? n bits in an n-1 bit hash?
Ahh well. Guess unique hashes aren't possible in fewer bits than the message.
Re:It's an insurmountable problem. (Score:2, Insightful)
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 pro
Re:It's an insurmountable problem. (Score:3, Informative)
Uunless the size of the "DNA" is larger than the size of the information being hashed, there will always be duplicates in the hash space.
Basic information theory. Nothing to do with file formats, transfer protocols, or endianness.
links to papers (Score:3, Informative)
Re:Sorry, no proof? (Score:2)
Spiral hash map? (Score:3, Interesting)
More interestingly (to me), you just inspired an idea. Caveat: IANACryptographer; I know little about it, so the following may be useless, stupid, or wrong. Or, as a professor once said about someone's paper, "This isn't right. It's not even wrong!"
One