Slashdot Mirror
MD5 Collision Source Code Released
SiliconEntity writes "The crypto world was shaken to its roots last year with the announcement of a new algorithm to find collisions in the still widely-used MD5 hash algorithm. Despite considerable work and commentary since then, no source code for finding such collisions has been published. Until today! Patrick Stach has announced the availability of his source code for finding MD5 collisions and MD4 collisions (Coral cache links provided to prevent slashdotting). MD4 collisions can be found in a few seconds (but nobody uses that any more), while MD5 collisions (still being used!) take 45 minutes on a 1.6 GHz P4. At last we will be able to implement various attacks which have been purely hypothetical until now. This more than anything should be the final stake in the heart of MD5, now that anyone can generate collisions whenever they want."
Recommended replacements are SHA (preferably SHA-2), WHIRLPOOL and/or RIPEMD.
http://en.wikipedia.org/wiki/SHA-2
http://en.wikipedia.org/wiki/WHIRLPOOL
http://en.wikipedia.org/wiki/RIPEMD-160
SHA-1 is not the sollution.
Mind Booster Noori
So is SHA1 the recommended alternative?
i ty/story/0,10801,99852,00.html
a re/story/0,10801,105875,00.html
No, see:
http://www.computerworld.com/securitytopics/secur
and
http://www.computerworld.com/softwaretopics/softw
I like this quote:
"SHA-1 is a wounded fish in shark-infested waters, but I'm more worried about MD5 because it's used everywhere," said Niels Ferguson, a cryptographer at Microsoft Corp. "Try to switch away from SHA-1 as quickly as you can, but switch away from MD5 first," he said when asked what recommendations he has regarding the algorithms during a panel discussion at the conference.
// TODO: Insert Cool Sig
This program is an efficient way to generate two source blocks with the same resulting MD5. This program does NOT allow you to match an arbitrary MD5 hash. That may come some day, but unless I've missed a very important paper somewhere, it has not happened yet.
This does not totally invalidate MD5 for verification. This attack still does not let you poison a torrent feed, etc, unless you are the author of the original source data and you engineered the data specifically to be vulnerable to this attack.
BitTorrent uses SHA-1.
That's not what MD5 sums are used for. TCP/IP already has packet integrity. MD5 sums are indeed used to make sure you don't have a malware-filled ISO. The trick is that you grab the MD5 sum from a trusted source, then you can grab the ISO image from any mirror site. Assuming MD5 is safe (obviously not the case), you know your downloaded ISO is exactly the same as the one distributed from the central repository.
Oceania has always been at war with Eastasia.
No. This only helps you find collisions in two randomly generated strings.
It is still very difficult to produce a colliding file given a pre-existing file on the network.
It should also be noted that edonkey splits a file into 9500KB chunks, and then into smaller chunks again, and hashes each one. It would be far more difficult to produce a chunk that causes collisions on all three levels.
Anyway, I expect an eMule extension will come out soon to allow for sharing of SHA1 hashes between clients (if it doesn't already exist).
$ rpm --checksig lynx-2.8.5-23.2.x86_64.rpm
lynx-2.8.5-23.2.x86_64.rpm: (sha1) dsa sha1 md5 gpg OK
$
So, even if it is also possible to generate collisions for DSA and GPG keys as well as SHA1 and MD5, the chances of being able to generate a collision for all four checksums/signatures at the same time is quite likely infinitesimally small. And that's just for a random file, things are going to get much more complex if you want that random file to can pass as whatever format the original was supposed to be and actually deliver a payload that might do something useful for the cracker.
UNIX? They're not even circumcised! Savages!
$2$blah instead of $1$blah MD5 http://www.thkukuk.de/pam/pam_unix2/. Quite useful.
See this: http://www.cits.rub.de/MD5Collisions/
It demonstrates the generation of two postscript files with the same MD5 hash that nevertheless display completely differently.
Crypto people are recommending SHA-256 or SHA-512 which is only like SHA-1 in name.
Obviously check your the hash length beforehand and make sure your database column is wide enough.
When migrating existing hashes to the new hash be careful not to store the old hash anywhere -- that can be the weak link in the chain. For example, generating passwords and having the MD5 around lets attackers generate valid inputs and then try them against the more computationally complex hash. It gives them an approach to attacking your stronger hash.
Take a copy of your database and hash all the existing passwords into SHA-512 form, and you'll need some way of distinguishing the MD5-to-SHA512 hashes from the SHA512 hashes, so add a date column with todays date in it. Then write a function "hashString" as a wrapper that can identify when something was hashed, and go down a different branch of code based on that.
The first branch does MD5 then SHA512, the second branch does SHA512, and it does this based on the date column.
And, of course, re-salt both branches.
This program generates ARBITRARY collisions. Given a tarball of a Linux kernel, you can generate some other file with the same MD5 hash. But can you generate a collision that is also a valid tarball that unpacks cleanly and compiles? The chances of that are so remote that I don't see it happening any time soon.
Here's the real trick. Take your kernel tarball X, and your hacked version Y. Using this collision finder, can you find some garbage Z such that Y appended with Z has the same hash as X? (Tar will, however, complain about extra stuff at the end of the tarball, but it would unpack and compile.) That's a MUCH harder problem than finding arbitrary collisions and would take a HELL of a lot longer to produce than 45 minutes on a PC.
=> Checksum SHA1 OK for unzip-5.52/unzip552.tar.gz.
=> Checksum RMD160 OK for unzip-5.52/unzip552.tar.gz.
===> Extracting for unzip-5.52nb2
One might also imagine that colliding two different hash types at the same time would be much more difficult than only at a time, anyway.
t's also the default algorithm to hash passwords (i.e. if you type in your password, it gets hashed into an MD5 sum which is then compared to what the MD5-ed password should be, thereby avoiding plaintext password storage).
Doesn't matter. This attack has no significant effect on password hashing, with or without salt.
This attack allows you to find a pair of plaintexts that hash to the same value; you don't get to pick either the plaintexts or the hash value. It does not help you find a plaintext that hashes to a given value. To use this to attack an unsalted password hashing system you would need to first generate a collision, then convince the target of your attack to set one of those plaintexts to be his/her password, then you could log in using the other plaintext. But if you can convince the target to use a particular password, why not just use that to log in?
This is not an insignificant cryptologic result, and people should move away from MD-5 as fast as practically possible (actually, people have been moving away from it for years due to some results against MD-4, which MD-5 is very similar to) but it doesn't really have any practical implications right now.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Huh? The SHA-2 family have been standardized, approved by NIST, and recommended by the NSA as part of their suite B for some time now. They are *much* more proven than Whirlpool and required for government use, whereas Whirlpool is not allowed for government use. Look at the SHA-512, SHA-384, SHA-256 CMVP instructions and validation lists before you say that NIST has not approved these hashes.
When in doubt, have a man come through a door with a gun in his hand.
This cannot be used to crack passwords
It can be used to generate two byte streams having the same hash[....]
The MD5 (or SHA, or whatever) password authentication, the hash is the only thing stored on the machine. When a user inputs a password, the input password is hashed using the same algorithm, and that's compared to the stored hash.
So, a colision would create the same hash, and would thus authenticate just like the real password, assuming it didn't break some input size limit or something.
Question: Does this mean all my MD5 passwords for all my users can be cracked?
Answer: The short answer is yes, they can be cracked. The long answer is no, not if you used a salt, and the attacker has to get those md5 hashes first. You are not safe you are storing your user's password field input directly to the database ala the php/sql method of:
Question: How should I remedy this?
Answer: Always use a salt or salts. For example in the case above you could use this php/sql method instead:
Question: How/Why is this safer?
Answer: Collisions are only direct input for the md5 function to get the same md5 hash. So in the above case, $password was directly taken from the user and made into a hash. Assuming an attacker got an SQL injection in and grabbed the database, they could run this collision creator on a hash and produce an input that gave that exact hash.
But, this would be much more difficult with any code that introduced a salt. That is why the second code is better, it includes two salts that the attacker (through his SQL injection) is unable to account for.
MD5 is dead. SHA-1 is currently dying. They're both based on the same fundamental math, and the attacks on SHA1 are getting stronger and stronger. Now would be a really good time to get off of that entire family of hashes if you can (MD4, MD5, RIPEMD-* SHA-*, etc).
The crypto world is in a little bit of a bind when it comes to strong hashes now. We simply don't have any left that both have a long proven track record of analysis and haven't been seriously compromised. Best bet, IMHO, is to go with a new-blood hash algorithm. They seem to be the answer we're looking for - but of course what they lack is more years of intensive study by the experts for flaws they themselves might harbor.
So if you want to give them a whirl, I'd recommend looking at Tiger and Whirlpool:
http://en.wikipedia.org/wiki/Tiger_(hash)
http://en.wikipedia.org/wiki/Whirlpool_(algorithm
11*43+456^2
If you RTFRFC you might notice that those are the variable and section names used in the algorithm specificaiton.
All's true that is mistrusted
The Coral Cache is extremely slow. Please point the links to the original site www.stachliu.com/collisions.html as the html is small/static and the machine it's sitting on has a decent (100mb) connection. Thanks.
The program generates byte stream A and B, both having the same hash C. You can't input C and get an arbitrary B out (with this algorithm).
Just like mixing medications can have very bad synergistic side effects, so should encryption or hashing technologies be mixed and matched.
As an example, when DES was first known to be broken, the most intuitive solution would be to double-encrypt the plaintext. However, upon cryptographic analysis, this acutally fails to improve the complexity of an attack (and in some cases may simplify it). Thus, Triple DES.
Be very wary of trying to combine "broken" algorithms in an attempt to gain security, especially if you have no real grounding in cryptanalysis. Vulnerabilities in each have a nasty tendency to either amplify or at least complement each other in highly unpredictible ways.
Remember one of the basic tenets of cryptography: it's easy to create an algorithm that you can't break. But just because you can't think of a way to break it doesn't mean there's not a trivial way to do so.
No comment.
How?
The collision vulnerabilities do not allow this. They require both the MD5, and the original plaintext, to produce a modified plaintext that has the same MD5.
Think about it - how do you know it's a collision at all, unless you have the original plaintext? A collision is two different plaintexts that produce the same MD5. You can't know if you have a different plaintext unless you have the original plaintext.
If you had the original plaintext, that means you've got the original password, so collisions are entirely irrelevant. You've already got what you need to log in.
There is still no way, other than the brute force enumeration which is made easier to look up through Rainbow Tables, to get from an MD5 to a plaintext that hashes to that MD5 value. The discovery of methods to produce collisions has not weakened MD5 any further - so far only the increase in computing power to produce Rainbow Tables has weakened this particular use. But trivial salting of the values makes Rainbow Tables useless once more.
The use of MD5 as a method to checksum files has been blown out of the water, of course. That's the other use, which I'm not arguing about at all. You know both the plaintext and the MD5 there, because you've downloaded the file and the MD5 for the file which you trust can't be forged - which is no longer true.
Yes, so
hash1 = md5(input1)
hash2 = sha1(input1)
Then to validate you run the input through the same thing. Like I said, the chances of a valid input colliding with both are ignorably slim.
How many people can read hex if only you and dead people can read hex?
You're half right, SHA-256, 384, 512 are part of FIPS 180-2. That is, they are approved for government use. FIPS 180-2 (PDF Warning!)
Brief Caveat: SHA-1 is still more algorithmically secure, as finding a hash is not feasible on desktop computers. SHA-256 and higher length are in the same vein of logic that provides this security, but like any new algorithm, there is an insufficient amount of study to verify this. This applies to Whirlpool as well, AES might be sufficiently secure, but Whirlpool != AES.
So, even if it is also possible to generate collisions for DSA and GPG keys as well as SHA1 and MD5, the chances of being able to generate a collision for all four checksums/signatures at the same time is quite likely infinitesimally small.
Actually, only SHA1 and MD5 need collide. DSA and GPG aren't used for hashing. DSA is used for signing the hashes, and GPG just implements and structures all of the above.
Still, you're right that finding collisions for both MD5 and SHA-1 on the same pair of files is extremely unlikely.
And that's just for a random file, things are going to get much more complex if you want that random file to can pass as whatever format the original was supposed to be and actually deliver a payload that might do something useful for the cracker.
Hammerhead, meet nail.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
While we might discover that "Donald Duck" has the same hash as "a", we don't get to choose either. We can't say "gimme a plaintext that hashes to this: 0x4faed...", all we can do so far is say "find two plaintexts that will give us the same hash"
Not that this doesn't mean this is a very serious matter. My take on the situation is: "Oh. Shit."
You don't seem to understand... Having the MD5 hash of a piece of software and the ability to generate a collision for that hash will--
Stop right there, because it's quite clear that the one who doesn't understand is you. Nobody has the ability to generate a collision for a given MD5 hash. All we have is the ability to generate two bits of random junk that share the same hash. This makes some attacks possible, but it does not make it possible for you to distribute a malicious version of someone else's software that has the same MD5 hash as their version.
The main problem with MD5 as it's used today comes when MD5 is used as a component of a digital signature scheme. Most digital signature schemes based on public key crypto work like this:
To verify a digital signature, the following is performed:
Now, it's easy to see why this spate of collision attacks on hashing algorithms is so deadly. If, given some signed document, you can produce another document that verifies to the same signature, well, I guess you're in a world of hurt. If these documents happen to be public key certificates, well, the whole PKI more or less collapses. And well, here's a bit of news: someone has done just that with X.509 certificates based on MD5.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
"You can generate collisions at any point in a file simply by starting with the partial MD5 sum up to the point in the file that you want to insert the block at. //Initialize hash value for this chunk:
var int a := h0 := h1 := h2 := h3
//Main loop: := (b and c) or ((not b) and d) := i := (d and b) or ((not d) and c) := (5×i + 1) mod 16 := b xor c xor d
g := (3×i + 5) mod 16
else if 48 i 63 := c xor (b or (not d))
g := (7×i) mod 16
:= d := c := b := ((a + f + k(i) + w(g)) leftrotate r(i)) + b := temp
//Add this chunk's hash to result so far:
h0 := h0 + a := h1 + b := h2 + c := h3 + d := h0 append h1 append h2 append h3 //(expressed as little-endian)
What these guys have done is to find 512 bit blocks or larger that return the same hash given the same initial state h0, h1, h2, h3.
As u can see above, if you find a collision for state i, ho, h1, h2, h3 the same collision will not work for the different state MD5 will have say after processing a number of blocks.
It is computationally feasible to find many collisions for the initial state but to find collisions for all possible states and to have these collisions occuring in the original file is very hard.
So, no you cannot simply search the file for blocks that are among the blocks for which u found a collision and then simply replace them with their collision. The MD5 for which you found the collision and the MD5 that is used over the file are essentially two different functions and will not hash to the same value.
As for the rest of your comments: I hope you realize that you don't just give their program an MD5 hash and it outputs two values that hash to that output. MD5 has been shown not to be collision resistant but it is still preimage and second preimage resistant.
I explicitly said that we assume the signer is trusted, you did not need to say anything about trusted parties. If the signer is not trusted the whole signed code scheme is meaningless.
" That's incorrect. MD5 operates over 512-bit blocks and uses state generated from the hash of the previous blocks to generate the new state for the current block. The state is actually the 4 words of the 128 digest.
Here is the alg from wikipedia:
init h0
init h1
init h2
init h3
for each 512-bit chunk of message
break chunk into sixteen 32-bit little-endian words w(i), 0 i 15
var int b
var int c
var int d
for i from 0 to 63
if 0 i 15 then
f
g
else if 16 i 31
f
g
else if 32 i 47
f
f
temp
d
c
b
a
h1
h2
h3
var int digest
The parent comment, which I wrote, was based on a severe misunderstanding of the extent of the capability of the attack. In particular, I didn't realize that the attack could find collisions even with arbitrary, attacker-specified IVs. What that means is that it is indeed possible to generate x.509 certificates containing different keys but the same MD5 hash (and therefore the same signature). In fact, it's been done.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
One Minor problem is that BitTorrent actually uses SHA not MD5 for it's hashing. Check out the following link for more information. http://dessent.net/btfaq/#hash-check
A lot of people have the programs md5sum and sha1sum installed, but they often don't have equivalent programs for the SHA-2 family. To calculate those you can use the command:
or you can download a dedicated program: http://www.ouah.org/~ogay/sha2/.
There's a hidden treasure in Python 3.x: __prepare__()
If you can find a collision in one, you can, for pretty much the same work, find a collision in the second hash. Cascading hash functions like this DOES NOT WORK.
Look up the Joux Multicollision paper from 2004 CRYPTO. This is a famous result.
This scheme you propose has been broken by Joux.
-Matt
Yes, Active Directory enviroments still strongly encourage storing the password in MD4 hash format. Also, to take advantage of the 802.1x authentication client built into XP SP2 also requires the password to be stored in MD4 hash format.
When you read "nobody" on Slashdot, it means that the egos of SiliconEntity and Zonk does not allow them to believe that there is an entire world that use something different than they do. If you replace "nobody" with "I" (or royal "we") then the comment makes more sense, such as "We the Zonk choose never to use MD4."
The biggest problem with this "me" focused view of the world is that it misses where people indirectly use MD4. If you are an employee, have a bank account, use any utilities, belong to an HMO/PPO, etc. then you probably indirectly trust MD4 to authenticate who has access to your personal information.
Thank goodness for disclosure laws like in CA which at least notify use after the fact how truely 0wn3d our personal data is.
He was talking about poisoned seeds. And theoretically SHA-1 isn't fine for this and is vulnerable to the same flaws as MD5. It isn't practical now (and certainly not as practical as poisoning kazaa shares... where every other byte in a file is skipped(!) for performance when generating a hash).
--
WHO ATE MY BREAKFAST PANTS?
(from material at the Pure Crypto Project - http://senderek.de/pcp/ )
Quote below from http://senderek.de/pcp/pcp-security.html
The nice thing about Adi Shamir's hash function is that it, as well as the RSA cryptosystem co-created with Rivest and Len Adleman is all based on simple modular exponentiation.
Too bad the Feds consider arbitrary precision mathematics used for encryption purposes to be 'a munition' and 'a controlled export'....
Years ago, they raked Phil Zimmerman over the coals over his email cryptosystem PGP then (eventually) left him alone.
Can't cryptosavvy individuals secure the details of their affairs with strong encryption WITHOUT being hassled by 'the Man'?...
P.S. However, Rivest came up with a scheme that gives you 'confidientiality *without* encryption' through a scheme he calls Chaffing and Winnowing
Enjoy!
Because that would require the hashed password and a preimage attack.
See here.
Summary for those who are lazy:
In conclusion, the value of this attack/exploit is only relative to how the hash function is used in an application. Just because this exploit and source code for it exists, that does not that these hashing algorithms are completely useless.