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?
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 large as the file itself.
Near as I can tell, you've just strung some clever-sounding words together to try and appear clever yourself. It might get you karma, but it's nonsense, all the same.
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!
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
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.
Even if they are unpronouncable ;-)
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"
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.)
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
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'); ?>
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.
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.
Look up Joux's construction for breaking concatenated hashes. Concatenated hashes are only as strong as the strongest among them, whereas you would expect that the concatenation of an n-bit hash with an m-bit hash would provide (n+m)-bit security.
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.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
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/
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.
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.
A 128 bithash, has got a lot of possible values. 2 to the power of 128 values. Which is estimated to be a bit more than there are atoms in the universe. So the lack of possible permutations is not a problem (otherwise you could just take a larger hash), there are just weaknesses in the algorithm.
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 start out as the same sort of thing, but the environment adds information that you want to authenticate.
This is not really a philosophical issue, it's a numbers game.
SCO employee? Check out the bounty
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