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...
i think it's human nature to just look for fault in other's work (in this case, a crypto algorithm)... but wouldn't it be more sensible if they spend their brilliance on creating a more stronger algorithm than proving and finding weaknesses in somebody else's work?
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.
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.
I've just changed away from using SHA-1. Double ROT13 seems most appealing these days. ;)
http://slashdot.su/
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.
This has been less than practical to this point because of a difference in file formats and transfer protocols. Anybody who uses FTP can attest to how easy it is to transfer binary when you mean ASCII and visa versa, and newline characters and little-endian/big-endian conversions make developing a DNA standard for file comparison difficult at best.
But I think that we're quickly reaching a point where standard fingerprint checksums are running out of usefulness.
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
Cripes, given these newer 256 and 512 bit algorithms why am I still stuck on this crummy 1 bit version?!
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
Whirlpool is based on AES, which seems a stronger approach at the moment. SHA-256 uses the same algorithm but more bits, so may be vulnerable. I'd rather go with the more trustable algorithm.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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?
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?
Anyone know for sure whether the SHA-1 attack also will compromise SHA-256? I've seen conflicting reports.
How about RIPEMD? Anyone using it seriously?
pffffft, yeah, duh... You guys didn't know that? ;)
I mean I've lost situational awareness!
Even the greats like Bruce can get hoaxed.
This Chinese research team has yet to publish their proof for the last SHA attacks. Or maybe I missed it? Please show everyone the proof. I honestly want to be able to read the proof. Links, please.
If it's real, withholding information on these attack vectors doesn't make it any safer for the rest of us who use SHA or any other algorithm.
Even if they are unpronouncable ;-)
So tell me : should I stop using SSHA to store password hash ?
:wq
Let's say I take a binary file and I grab both it's MD5 and SHA1 hashes. I then combine the output of those two into one really long string. Them I take the SHA1 hash of that string. How secure is this?
Entrepreneur : (noun), French for "unemployed"
that the strength of an algorithm is a constant. As has been shown, new attacks are always possible, so at some point in the future, the situation may be reversed and A be weaker than B. By using multiple means, the chance of a failure due to a new attack is reduced.
It's like that cardboard used glue which changes to an acid after a couple of years, except you didn't know in advance. You would have been better off using just paper.
"National Security is the chief cause of national insecurity." - Celine's First Law
The article has links to the previous SHA attack papers and Xiaoyun Wang's publication list. (These links were added after the article was posted, so maybe you missed them.)
Time to start searching for some good SHA-512/-1024(?) applications...
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
If an alg can be decrypted, doesn't that mean that it can't be unbreakable? Even if there is one and only one way to decrypt it; couldn't brute force always work?
"You will do foolish things, but do them with enthusiasm." - S. G. Colette
Her visa application's SHA1 hash matched Osama's.
So now that SHA-1 has been rendered largely useless for any security application, what is the current "recommended" cryptographic hash algorithm? One of the SHA-2 variants (SHA-256, for example)?
09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0 Whoops, silly middle mouse button...
Also, do not throw rabbits into the briar patch...
My name is Achmed, and I endorse this post
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.
I absolutely love how this was modded redundant. Apparently, the mods have a sense of humor today!
And the l33t shall inherit the 34r7h.
Consider that the effects of preprocessing seem to make the near-collision detection methods fallible, or so they cite. Better preprocessing == fewer 'hits' to then anchor reduction/decriment detection for real collision vectors. This is heartening, but are only a speed bump for a while. I think SHA-X will get attacked in a different way. At DefCon, an interesting tabling method was described that has some possibilities, by reducing both the input methods, linked to a rapidly anded table to see what pooped out the other end of the algo. That's tested for smell (pardon the metaphor) and therefore decriments rather rapidly. It sure beats the sifting method.
---- Teach Peace. It's Cheaper Than War.
when I was learning how these hash functions work, i was amazed to find that they work through the file to be hashed in a linear manner so that an attacker can target 1 small round and create a colision. does anyone know of any hash function that operates on the entire file in a single expanding round that can expand to take the entire file? it is my understanding that these attacks focus on defeating a single round of a set size hash. an expanding hash would make this many times more difficult to crack.
A hash that reduces the size of the original by only 50% could be re-iterated to create progressively smaller and smaller results untill a hash in a certain size range was created. any attack would have to break the first round, and that first round could be defined to produce a result no smaller than 10MB or something. that should be enough to keep us safe for a while.
-John Fenley
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
You might look into steganography, which uses the text as a mapping function on a digital image, which becomes the key. If only the sender and the receiver know what picture was used, with the proper mapping the encryption can be 'completely unbreakable'.
:)
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 might consider the input text as a multi-dimensional space, using some mapping from the original linear text to the space. Then, the loci in that space could be fed into the hash according to another mapping. The mapping amounts to at least one additional hash function for each dimension.
For a simple example, consider the text as a rectangular array in row major order. Then, starting in the middle, using some small block size (perhaps variable) the bytes of the text in a rectangular 'spiral' are combined into input chunks for the hash process. If we use the alphabet (A-X) in a 4x6 matrix as an example, the first row would be ABCDEF, the 2nd GHIJKL, 3rd MNOPQR, 4th STUVWX. Using a 2-byte chunking, the chunks input into the hash would be IJ, PO, NH, BC, DE, KQ, WV, UT, SM, GA, BC, DE, FL, RX. Note that BC and DE are presented twice - I don't know if that's a good thing or a bad thing, but I think it can be good. Various strategies can be employed to map non-square or non-regular 'shapes'.
There are an infinity of ways to perform such mappings, a majority of which apparently destroy any benefit an attacker may receive from observing adjacencies and periodicities in the data. I say apparently because a major area of potential vulnerability will be in the transmission of the mapping rules. If the rules are encoded some way in the cyphertext, an attacker's first objective would be to crack the encrypted information about the mapping, which would allow the attacker to then consider the input to the hash as a linear text. This could be avoided if only a miniumu amount of information is included in the cyphertext that would allow a legitimate receiver to determine the correct mappings from among a large potential set of mappings with low mutual similarity.
One might view this method as "Through the Looking Glass", because, it performs spatial distortions on the data, though often of types not easily accomplished by a physical lens. Steganography is a one-dimensional mapping in this sense, where the location of a bit in the two dimesional space is not changed but it's position in color, phase, parity or other space (the value dimension) is changed.
This little flight of fancy may be old news or stupid, I don't know. If it's new and useful, I'll be glad to assert patent rights and other IP rights, so as to avoid proprietary lock-in and make the technology available under a Creative Commons -type license for the general good!
It's easier to be a result of the past, but more fun to be a cause of the future! http://www.spacefinancegroup.com/
That change did in fact improve the security of DES.
Not Brits, Poles. http://en.wikipedia.org/wiki/Bomba_(cryptography)
Why not just append the MD5 and SHA1 hashes together? What are the chances of getting hash collisions with two difference algorithms from the same input? I don't think I'd lose much sleep over it.
I didn't miss anything. The Wiki articles just reference Bruce's blog, which doesn't provide any proof.
I don't see how you're modded informative, and I'm modded a troll, since I asked a valid question, and you didn't provide the answer.
Please, *please* provide a link to the proof.
Google for a25f7f0b29ee0b3968c860738533a4b9 OR a25f7f0b, an example of how to exploit a hash collision.
To avoid this exploit, the signer needs to make an unpredictable modification to the document prior to signing.
Alice and Bob use hash function H and signature function F to validate documents. Alice signs a message M by finding signature S such that F(S) = H(M). Bob accepts (M,S) as signed by Alice. Eve can calculate H(M) and F(S) but cannot find S given M.
Eve creates documents M1 and M2 which have the same hash, and asks Alice to sign M1. If Alice uses the expected hash, Eve can substitute M2 and Bob will accept (M2,S) as signed by Alice.
So Alice and Bob need to agree to a safer method. When Eve presents M1 for signature, Alice generates a new random key K, encrypts M1 with K and hashes, giving H(K(M1)). She then signs this by finding S such that F(S) = (K,H(K(M1))), and gives (S,K) to Eve.
Eve sends (M2,S,K) to Bob. Bob checks the signature by calculating F(S) and comparing it to (K,H(K(M2))).
Eve is foiled, because H(K(M1)) != H(K(M2)), even though H(M1) = H(M2).
Thus, immediately, the protocols for signing software distributions should be adjusted so that the signing authority Alice generates random key K and signs H(K(M)) instead of just H(M). The automatic software update agent Bob checks the signature (S,K) by calculating F(S) and (K,H(K(M))).
This will prevent substitution of a useful M2 for M1 by Eve, who is allowed to present an arbitrary M1 for testing and signature. Eve cannot predict K, and hence even if she can find M2 after the fact, such that H(K(M1)) = H(K(M2)), she is not allowed to change M1 after K is chosen. Hence M2 will not be useful.
Bob can safely install M1 automatically, confident that if M1 passes a simple syntax check (which M2 cannot possibly satisfy), it is the same program which Alice accepted for signature, even if hash collisions can be found.
WTF the Chinese have Cracked my Afghani Hash ?*!@rr
Man I knew I was feeling pretty damn wired, I knew this was a bad week to give up glue-sniffing.
I hear from the tech/geek community all the time that we don't have a problem with racisim or sexism. Everyone is equal, it's a meritocracy, etc. etc. It's easy to ignore these problems when your the dominant culture, or cocoon your self in a bubble and pretend you are.
Kind Regards
"A few great minds are enough to endow humanity with monstrous power, but a few great hearts are not enough to make us w
We are starting to see more and more case of hash algorithms, such as MD5 and SHA-1, suffering from these type of exploits. Would it not be possible to simply have a key which is actually two keys, using two different algorithms? The idea being that it would be more difficult to get round exploit a key which is the result of two different algorithms. As computing power increases the ability to exploit hash-algorithms improves, but at the same time the effort required to generate multiple keys is reduced.
Jumpstart the tartan drive.
"Your theory is crazy, but it's not crazy enough to be true."
- Niels Bohr (1885-1962)
Is this a sigs-optional kind of place? 'Cause I am totally down with that if you know what I mean.
FYI: RSA stands for Rivest, Shamir, Adelman so Shamir is the "S"
W00t? no "I for one welcome our new WHIRLPOOL overlords..." or "In Soviet Russia, hashing algorithms attack YOU!"
The news reporters had trouble saying that the Wang/Yin/Yu team did it with a straight face, perhaps?