Slashdot Mirror
MD5 To Be Considered Harmful Someday
Effugas writes "I've completed an applied security analysis (pdf) of MD5 given Xiaoyun Wang et al's collision attack (covered here and here). From an applied perspective, the attack itself is pretty limited -- essentially, we can create 'doppelganger' blocks (my term) anywhere inside a file that may be swapped out, one for another, without altering the final MD5 hash. This lets us create any number of binary-inequal files with the same md5sum. But MD5 uses an appendable cascade construction -- in other words, if you happen to find yourself with two files that MD5 to the same hash, an arbitrary payload can be applied to both files and they'll still have the same hash. Wang released the two files needed (but not the collision finder itself). A tool, Stripwire, demonstrates the use of colliding datasets to create two executable packages with wildly different behavior but the same MD5 hash. The faults discovered are problematic but not yet fatal; developers (particularly of P2P software) who claim they'd like advance notice that their systems will fail should take note."
I can only hope I live that long.
Aha! So it was MD5 and not MP5...
The owls are not what they seem
Another option is to hash against two very different algorithms, that even if both are partially insecure, the chances of being able to trick both are exponentially higher.
-nB
whois gawk date unzip strip find touch finger mount join nice man top fsck grep eject more yes exit umount sleep dump
So does this mean that it's possible to find a useful MD5-equivalent file for any file? Just because someone alters a file does not mean they have done anything destructive. Would one be able to take a binary, make a change of some sort, and then run a tool to determine the block of data to add to the binary to both allow the change to take effect and cancel out the MD5 change? How complex would it be to construct this tool?
You are not the customer.
There will ALWAYS be collisions with any kind of hashing algorythm.
Thats the nature of the game we play.
The only hashing system without collisions is sending the original file itself.
liqbase
Is there a translator from ultra-nerd to english?
By examining the MD5 hash using a sophisticated Fourier schema followed by deconvolution with a bit binary-inequal collision analysis, it is quite obvious I have no freaking clue what this stuff is about.
I am glad somebody does.
No trees were harmed in the composition of this; however, numerous electrons were inconvenienced.
Someone with the knowledge and will and time can come up with a way to circumvent almost any protective scheme they come up with. Likely the only way to really safeguard something like this is to do a very time consuming and cpu intensive comparison of the two files. It will come back to "do you trust the source of the file".
http://en.wikipedia.org/wiki/Md5
:)
here is a very good link about the algo...
If your cursor finds a menu item followed by a dash,
And your double-clicking icon puts your window in the trash,
And your data is corrupted 'cause the index doesn't hash,
Then your situation's hopeless and your system's gonna crash!
He can create a file that MD5sum's to the same result as a legitimate file, but does not have full control over the content or size of the result (making this a mostly useless avenue of exploitation except for people who want to spread trash on P2P networks -- I.E. it shouldn't particularly bother anyone except people who already don't care about security).
Or he can create two files that MD5sum to the same result. But he has to have control over both files, which offers effectively no advantage to someone who is trying to spread malware or tamper with existing archives that have been MD5summed.
Consequently, while this is of academic interest I don't see what the big deal is; any time you reduce a large file to a fingerprint you will inevitably run into problems like this because it is impossible to represent one-to-one every individual possible combination of a large set of data in smaller sets ("fingerprints"). You can reduce the risk by increasing the set domain with a larger variadic function but it is impossible to escape this constraint without using fingerprints as large as the data itself.
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
Other weaknesses were reported in various other secure digests, including MD4, RIPEMD, HAVAL-128, SHA-0.
SHA-256 is a good replacement. SHA-1 should be fine but if you are going through the trouble of an upgrade, why not make it sufficiently future proof?
Two files with the same MD5 hash at once. Aaw yeah.
Yes, but a good hash makes it *extremely* difficult to find them. MD5 is looking pretty mediocre right now.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"[This is the author]
I've been doing some analysis on MD5 collision announced by Wang et al. Short version: Yes, Virginia, there is no such thing as a safe hash collision -- at least in a function that's specified to be cryptographically secure. The full details may be acquired at the following link:
http://www.doxpara.com/md5_someday.pdf
A tool, Stripwire, has been assembled to demonstrate some of the attacks described in the paper. It may be acquired at the following address:
http://www.doxpara.com/stripwire-1.1.tar.gz
Incidentally, the expectations management is by no means accidental -- the paper's titled "MD5 To Be Considered Harmful Someday" for a reason. Some people have said there's no applied implications to Joux and Wang's research. They're wrong; arbitrary payloads can be successfully integrated into a hash collision. But the attacks are not wildly practical, and in most cases exposure remains thankfully limited, for now. But the risks are real enough that responsible engineers should take note: This is not merely an academic threat, systems designed with MD5 now need to take far more care than they would if they were employing an unbroken hashing algorithm, and the problems are only going to get worse.
Some highlights from the paper:
* The attack itself is pretty limited -- essentially, we can create "doppelganger" blocks (my term) anywhere inside a file that may be swapped out, one for another, without altering the final MD5 hash. This lets us create any number of binary-inequal files with the same md5sum.
* MD5 uses an appendable cascade construction -- in other words, if you happen to find yourself with two files that MD5 to the same hash, an arbitrary payload can be applied to both files and they'll still have the same hash. This leads to...
* Attacks are possible using only the proof of concept test vectors released by Wang -- the actual attack is not necessary.
* Stripwire emits two binary packages. They both contain an arbitrary payload, but the payload is encrypted with AES. Only one of the packages ("Fire") is decryptable and thus dangerous; the other ("Ice") shields its data behind AES. Both files share the same MD5 hash.
* Digital Signature systems are vulnerable, as they almost always sign a hashed representation of data rather than the data itself.
* This is an excellent vector for malicious developers to get unsafe code past a group of auditors, perhaps to acquire a required third party signature. Alternatively, build tools themselves could be compromised to embed safe versions of dangerous payloads in each build. At some later point, the embedded payload could be safely "activated", without the MD5 changing. This has implications for Tripwire, DRM, and several package management architectures.
* HMAC's invulnerability has been slightly overstated. It's definitely possible, given the key, to create two datasets with the same HMAC. Attacker possession of the key violates MAC presumptions, so the impact of this is particularly questionable.
* Very interesting possibilities open up once the full attack is made available -- among other things, we can create self-decrypting executables (fire.exe and ice.exe) that exhibit differential behavior based on their internal colliding payloads. They'll still have the same MD5 hash.
* Several doppelgangers may (relatively quickly, as per Joux) be computed within a single multicollision-friendly block. As such, the particular selection of doppelganger sets within a file can itself be made to represent data. It's relatively straightforward to embed a 128 bit signature inside an arbitrary file, in such a way that no matter the value of the signature, a constant MD5 hash is maintained. This is curiously steganographic.
* Many popular P2P networks (and innumerable distributed content databases) use MD5 hashes as both a reliable search handle and a mechanism to ensure file integrity. This makes them blind to any sign
For the most part, big deal, all of current security procedures will be harmful ie compromised in the future...
Using MD5 with SHA1, or even the older MD2 or MD4 will reduce the probability of creating a compatable binary with the same checksum to virtually zero.
If only one checksum is required then just XOR the resulting checksums from each algorithm.
"You shouldn't be able to because it simply isn't true."
I have to disagree with you here.
If I have algo A and algo B:
I hash with algo A and get a value which I store.
I hash with algo B and get a value which I store.
While the security does not add up to A^B it does ammount to > A+B, which is still better than A or B only. (I really wish I had my Crypto reference books handy)
Other posters mentioned it was more work and equiv to one secure algo, both those statements are true; as I pointed out this was an alternative to writing a new SHA-1 algo.
-nB
whois gawk date unzip strip find touch finger mount join nice man top fsck grep eject more yes exit umount sleep dump
I was a bit suprised recently when I tried to
sort 15,000 jpg image files to remove duplicates.
Since the names varied, and it is not uncommon
to have many images with the same length, it
seemed like a good idea to use md5 hashes.
So I coded it up in python to do the md5 hash,
and then stuffed the file name into a table
keyed by the md5 hash. Big suprise when multiple
different files landed in the same hash.
Some property of jpgs probably reduces the
randomness of the files and increases the
probability of hash collisions.
I'll give you $50 if you can back that claim up. I want to see two video files. They must start out the same, but have a difference about half-way through. And they have to have the same md5 sum. Just post where I can download the two files, and your paypal address.
The way I see it, you've got a 1/2^64 chance of being right. So I'm risking $50/184467440737095516, which isn't a whole lot.
No, but I believe this one is:
XiaoyunWang, Dengguo Feng, Xuejia Lai, and Hongbo Yu
"Collisions for hash functions md4, md5,haval-128 and ripemd"
Before you flame, change 256^4 / 256^1000 to 256^1000 / 256^4.
A P4 at 2.6GHz does >300MB/s md5 according to openssl speed md5. As noted, you probably wait for the data to be fetched from disk rather than the checksum to be computed.
Of course it runs NetBSD. BTC: 1NT7QvbetmANwaMzhpVL6
I've always called this dirt. Some folks call it padding, but it's essentially the same. However up until now, no one has known how to do it with md5 and come up with the same sum. This is nothing more than a hack to me.
The bottom line is that if you care enough about security this will only be a problem for a day or so when md5 is finally solved completely and the hashes don't take five days to brute force -- they could be solved in a matter of microseconds. As soon as that happens, the next hash system goes up and it would not likely be so easy to break, unless the whole hashing process is somehow cracked wide open (which would be very bad for a number of reasons).
What we'll likely see is that with the greater increases in CPU speeds available to end users, the hash breaking systems can be tested easier until a final reverse algorhythm is available for md5. There already is a site that will break your hash and give you *something* with the same hash, and it takes a couple days.
The dangers of knowledge trigger emotional distress in human beings.
That was his point.
Any hash that maps a large (infinitely large, in most cases) space onto a finite ones will always have collisions, it's just a question of how easy they are to find. If you don't want to have have collisions, you have to send the whole file.
A Minesweeper clone that doesn't suck
I haven't had time to think this out, so I'm throwing it out for you guys:
Is doing a 2nd pass helpful?
In other words, if
ABCfireDEF
and
ABCiceeDEF
hash the same, does
ABCfireDEFABCfireDEF
necessarily, or even frequently, hash to
ABCiceeABCiceeDEF?
Even if it were to provide protection, in practical terms,
1) other hashing althorithms are likely faster than "MD5 times two"
2) there may be some - hopefully a lot fewer - places in a long file where where
ABCfireDEFABCfireDEF
can be replaced with
ABCiceeDEFABCmeltDEF
I'm beginning to like the "pick two algorithms and call me in the morning" approach.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
It's well known that encrypting twice doesn't always improve your security, so it wouldn't be surprising if hashing twice didn't always improve your security either.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Sure, there are an infinite number of possible passwords, but they're all impossibly huge. I can come up with a password which is one trillion characters long and which hashes to the right result, but that's not practical.
Your statement is ironic in the extreme. The big risk here is NOT P2P apps. Here's the real risk.
Using one of these collision generators, I can create two x.509 certificate requests which have the same MD5 hash. One request says, "I am John Smith, kshdfkhs8i76y238888888" and the other request says, "I am Microsoft Corp., oiushir87dsfhgkjshdfg"
Now, I get Verisign to issue me a certificate for the first request. Since the hash is the same, I can rewrite the certificate to say that I am Microsoft Corp, and nobody will ever be able to tell the difference. Now, I am able to sign code as if I were Microsoft, and Dominate The Earth.
He can create a file that MD5sum's to the same result as a legitimate file, but does not have full control over the content or size of the result (making this a mostly useless avenue of exploitation except for people who want to spread trash on P2P networks -- I.E. it shouldn't particularly bother anyone except people who already don't care about security).
Suppose you're storing passwords as encrypted hashes, so that intercepting the hashes doesn't tell you what the password is. But if you can generate a password to match that MD5...
You know that GPG keys are identified and signed by their MD5 hashes? Suppose that I can generate a GPG key that would be identified as yours, and distributed it.
Or he can create two files that MD5sum to the same result. But he has to have control over both files, which offers effectively no advantage to someone who is trying to spread malware or tamper with existing archives that have been MD5summed.
There's a coin-flipping protocol that goes as follows. Suppose that Alice and Bob want to flip a coin (over the Internet), but they don't trust each other.
Now, suppose that Alice generated multiple files in step 1. When Bob makes his guess, she tries to pick a file that will make her win. If she generated only two files, completely randomly, this would let Alice win 75% of the time.
These are just the first ideas I thought of. If I were looking for other problems, I'd think about undeniable signatures, keysigning (which as GPG and X.509 SSL are heavily based on) and other specialized signature systems. In particular, I expect that the first type of crack could cause issues with SSH keys, both user keys (used for authentication) and host keys (to prevent man-in-the-middle attacks).
Digital signatures are used for much more than just testing for file tampering.
You're using a different definition of a secure hash than everybody else. It's rather obvious that for files larger than the length of the hash (128 bit for md5), there must be quite a lot sharing the same hash, for a given file length about 2^(filelength in bits - hashlength in bits). However for a hash to be considered secure, it's only required that finding two files with the same hash must be as hard as trying (in md5's case 2^127 different files), but in md5's case you can compute those collisions much cheaper under certain circumstances.
Another condition is obviously that the message should not be reconstructable from the hash.
The point is not that there is collision. The point is that given a particular file, you can compute other files that collide with that file in an amount of time many orders of magnitude less than it would take if you randomly tried files until you hit one that happened to collide.
paintball
Intuitutively, yes, and i'm just pulling this out of the air here cuz i'm supposed to be working on something else, but solve a slightly different problem.
If you are concerned that the result-space of a hash algorithm is going to lead to collisions (this is not an ordinary concern because the algorithms claim to have dealt with this for us already) then using two very different hash functions in concert will definitely expand the range of possible results and reduce the probability of collisions by Asize * Bsize.
If however you are concerned about bad guys faking things up, then there is a slightly different problem...
A == MD5
B == SHA
Hashing to both A and B yields a huge range of results.
However, if A known or suspected to be broken, then you're down to the security provided by B. A is out of the picture.
If A can be tossed then, then you're totally reliant on B for a safe hash. If that's true, then you didn't need A at all and you'd better be confident that B is gonna do what you need it to do, cuz A don't dance.
Note to experts: Please do not grade harshly.
The ISO approval also carries some weight in industry, although after some rather disasterous specifications (such as ISO 9000), they have lost some of their image. However, there are plenty of organizations that would consider an ISO standard an absolute must.
I don't know of anyone using Whirlpool for highly secure systems. It certainly wouldn't be ok in the US, as it's not a FIPS standard. France or Germany would be better bets.
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)
You can just ask Verisign for a certificate in the name of Microsoft, and they'll give you one. Much simpler.
It's happened in the past.
Be honest. How many of you have checked the MD5 sums on a file with a TRUSTED source, as opposed to from the same source you got the file? How many of you do this regularly?
THAT is the biggest problem with MD5 for most users.
These posts express my own personal views, not those of my employer
Where time isn't critical (eg: creating and validating checksums for files), I'd say use both. The overhead isn't great, and you'd get much more security.
Where time is critical AND you don't have to be concerned with computers not under your control, use Whirlpool. Rijndael is fast, SHA-1 is slow. Whirlpool also offers a longer hash string than SHA-1.
In any other situation, use SHA-1. Whirlpool might turn out to be the greatest algorithm out there, but that doesn't help if you're trying to talk to a remote computer that doesn't support it.
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)
Agreed that folding A with B after A has been compromised is a nonstarter.
However, isn't there merit to the general idea of combining two 'dissimilar' (i.e., the theoretical basis for the 'security' of each share as few attributes as feasible) hash functions X and Y where both X and Y are currently though to be 'secure'?
In those very common cases where the hash is protecting something with decreasing time value (such as software binaries which become obsolete in a few years) or where the original source is secure and it is only alterations of copies that are a concern (perhaps historical legal documents), this buys time if X or Y (but not both) is compromised (or seem more likely to be compromised - as MD5 is now)?
For example, if X=MD5, the concerns about MD5 would result in an effort to discontinue its use and replace it with a new hash function Z and start using Y+Z. While the community switches to a new combination, everything is still pretty safe (as safe as Y in this case) during this transition period.
It seems that in the private sector (spooks aside), it's quite unlikely that X and Y would both be effectively compromised simultaneously and with little warning unless the notion of dissimilarity is also compromised. Fortunately, the skills needed to compromise such functions seem to be concentrated in the guys with the white hats so they tend to publish their preliminary results.
Disclaimer: I'm not a cryptomaniac so my observations are worth substantially less than you paid for them.
Why is there an "insightful" mod and why isn't it "-1"? If I wanted insight, I wouldn't be reading
That's OK..just invent MD6!
### If it's a hash, the message CANNOT be reconstructable from it
Depends on the hash function, if the input length is equal or smaller then output length reconstructing the message might be possible, ie:
$ echo "hello" | md5sum
b1946ac92492d2347c6235b4d2611184 -
Should be easily reversible with a dictonary attack. However in the more common case a hash maps a large input domain, to a much smaller output domain, so yep, hashes are not reversible unless input is somehow smaller then the hash itself.
If the orginal data is: "abcdefg", I can insert some malicious bits 'M', along with some padding bits 'X', and ensure that the result of A would be the same: A("abcdefg") == A("abcdMXfg").
Assuming that I found a similar attack on B, I could find padding bits 'Y' such that B("abcdefg") == B("abcdMYfg").
Of course to fool both checksums, X must equal Y. Finding a value that keeps both checksums the same might turn out to be a non-trivial problem.
PGP is easily broken by a brute force attack given enough time, it's just that the amount of time isn't feasible at the moment.
Worst BBC News Stories
I'm not sure if you are being sarcastic or something, but as said before, Bittorrent uses SHA-1, not MD5....
So you are safe downloading linux for now via bittorrent. Besides, the chances of MD5 collisions happening from sheer luck/unluck are very slim. (after all, we've been using it for ages with no reports)
The most dangerous factor to continued use of MD5 are malicious individuals.
Maybe, maybe not. The new technique would certainly be more difficult to analyse mathematically, but just stacking complicated but flawed methods does not necessarily result in a more secure method: typically, the security of the weakest link determines the security of the whole system.
What you say reminds me of Don Knuth's experience when he wrote his first innocent 'super' pseudo random number generator (reported in his Art of Computer Programming, Volume 2, page 4: "Algorithm K" ;-): he composed all sorts of complicated operations, but had to learn the resulting number sequence was far from more (pseudo-)random, in fact much worse than the the standard 1-line modulo function.
Another case of (false sense of) security through obscurity?
--
Try Nuggets , our SMS search engine which uses question answering technology; now available across the UK.