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."

SHA1

[mysqlrocks]

So is SHA1 the recommended alternative?

Re:SHA1

[Mind Booster Noori]

SHA-1 is not the sollution [schneier.com].

Re:SHA1

[mboverload]

It was a JOKE people!

Re:SHA1

[psykocrime]

So is SHA1 the recommended alternative?

No, see:

http://www.computerworld.com/securitytopics/securi ty/story/0,10801,99852,00.html [computerworld.com]

and

http://www.computerworld.com/softwaretopics/softwa re/story/0,10801,105875,00.html [computerworld.com]

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.

Re:SHA1

[flosofl]

For the love of _______! (fill in appropriate name for your particular beliefs)

Someone mod the GP post Funny, before we get more "informative" posts. It looked like a tongue-in-cheek comment to me. I actually laughed. Then I saw the follow-ups from the Unfunny Brigade... It was a joke!

Seriously, who doesn't know about the SHA-1 weakness by now.

Re:SHA1

[Anonymous Coward]

No, MD5 and SHA1 were found to have better than brute-force attacks within a few months of each other.

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.

Re:SHA1

[jacksonj04]

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.

Re:SHA1

[Anonymous Coward]

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

Exactly!

[0xB00F]

Because that would require the hashed password and a preimage attack.

See here [cryptography.com].

Summary for those who are lazy:

• This is a collision attack. The attacker will be able to find two messages that will produce the same hash, but the attacker cannot choose what the hash will be. So this rules out attacks on hashed passwords.
• Since a collision attack can find to messages that will produce the same hash, it is possible to use this to break message signing, such as DSA and RSA. where a hash of the message is generated first and then signed cryptographically.
• Collision attacks cannot be used to tamper with existing SSL certificates. It can be used to craft a CSR which will allow you to receive a server certificate with a collision to one containing a wildcard for the domain name and an expiration date far in the future. This by far is one of the most dangerous exploits because most CA's will issue certificates without completely verifying the identity of the requester.
• Because of the way MD5 is used in SSL 3.0/TLS, these attacks do not affect it.
• Collision attacks do not affect MD5 and SHA-1 when they are used in an HMAC. So even though a hash function can be broken by either by collision attacks, they can still be used safely in HMAC.
• Tampering a signed binary is only possible using a preimage attack.
• All will have naturally collisions. How exploitable they are depends on how easy it is to find those collisions.

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.

Re:SHA1 (NO)

[photon317]

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) [wikipedia.org]
http://en.wikipedia.org/wiki/Whirlpool_(algorithm) [wikipedia.org]

SHA1 is not a good alternative in some cases

[chongo]

SHA1 is not a good alternative in some cases. For details on the cryptographic hash problem, see my paper:

SHA1 Cryptographic Hash Update [systemexperts.com]

My paper talks about the general problem at a high level. It gives a summary of common opinions expressed at the NIST Cryptographic Hash conference. Moreover, it gives developers some specific cryptographic hash recommendations.

For the impatient, here is a summary for my recommendations for 2005-2006:

• Avoid non-standard cryptographic hashes
• Stop using MD5 now except for:
  • MD5 HMAC and MD5 hashed Passwords
  • Replace MD5 HMAC and MD5 hashed Passwords with SHA256 or SHA1 before end of 2007
• Existing applications that use SHA1, where possible, should changed to use SHA256 before the end of 2008
  • For interoperability with older applications and hardware, these applications may have to also support SHA1
  • If you must support both SHA256 and SHA1, take care so that a "man in the middle" cannot inappropriately downgrade
• Until a new Advanced Hash Standard (AHS) is adopted, new applications and hardware should be designed to use SHA256
  • For interoperability with older applications and hardware, these applications may have to also support SHA1
  • If you must support both SHA256 and SHA1, take care so that a "man in the middle" cannot inappropriately downgrade
• All new applications and protocols must be designed to be algorithm agile
• Existing applications and protocols should be modified to be algorithm agile by the end of 2008, if not sooner
• SHA384 or SHA512 may be used in place of SHA256 in the above examples
  • Keep in mind that SHA384 and SHA512 are slower and larger than SHA256 or SHA1
• Because it is possible that SHA1 will become unacceptably weak before 2008, and because SHA256 may become vulnerable to attack before Advanced Hash Standard (AHS) is adopted, a defense in depth approach must be taken

See the paper for mode details.

Managed to get just the last few lines...

[Saint Aardvark]

...before even the Coral cache was Slashdotted, and it turns out they've written it in LISP:

))))))) ))))))))

(With sincere apologies to Bryce Jasmer [netfunny.com].)

Re:Managed to get just the last few lines...

[Anonymous Coward]

I downloaded the source, but it doesn't seem to be working properly. Does anyone have an md5sum of the original so I can verify I got the right code?

-confused

shaken to our what?

[tomstdenis]

It's important news but not really that shocking. MD5 was not something professionals would recommend for a few years already.

Any half-way intelligent cryptographer would have suggested SHA-1, TIGER or perhaps HAVAL since quite some time already.

Tom

Re:shaken to our what?

[ZachPruckowski]

It's important news but not really that shocking. MD5 was not something professionals would recommend for a few years already.

But a household user can crack in an hour on a normal mid-line computer something that "a few years" ago professionals might have recommended. That's the news. If low-end PCs can crack encryption that's only a few years outdated, then the hounds are nipping at the heels of the cyptography industry. And imagine what hackers could do with more powerful computers (yes, I know ther

MD5 is not an encryption algo

[Junta]

It is a hash algo. It's used not to protect the content of anything, just to provide a method to validate content integrity, to show nothing accidental or intentional happened to change it.

Re:MD5 is not an encryption algo

[san]

It'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).

Lucklily, most sane systems use salt [wikipedia.org] so this algorithm won't work out of the box.

Re:MD5 is not an encryption algo

[swillden]

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.

breaking torrents?

[OrangeTide]

Ah! That's a very good point.

now if you you were a software company you could put torrents out (I assume they use blocks of MD5sum), and then after the torrent becomes popular start randomly seeding people with blocks that hash correctly but are complete garbage (since you can't pick what exactly you hash). if you do it right you would have games out there that would still mostly run. but would crash, or have garbled game data, etc.

I'm not sure if this is really all that useful. but this exploit certainly seems to make it easy to do.

Re:breaking torrents?

[dougmc]

That's what I was thinking -- this being used to break torrents and other p2p setups.

Though to be fair, most games seem to come in the form of a compressed archive of some sort -- either a bunch of .rar files (for warez) or a .exe file with .cab files (for Windows installers) or something similar. In that case, the corruption would be detected at installation, though it wouldn't be easy to determine from the torrent exactly which blocks are corrupt.

In short, MD5 being broken (and now the code being available) is very bad. I expect to see the anti-piracy vigilantes jumping on this very quickly to create code to totally break bit torrent and similar things -- it would come up and look like a seed, but would be spewing garbage that the other clients couldn't detect as garbage. Of course, such poisoning would also end up being used to corrupt completely legitimate torrents as well, just because people think it's fun.

(The fix? Update things like bittorrent to use hash routines that haven't been cracked yet, or to use multiple hash routines on the same blocks.)

Re:breaking torrents?

[swillden]

now if you you were a software company you could put torrents out (I assume they use blocks of MD5sum), and then after the torrent becomes popular start randomly seeding people with blocks that hash correctly but are complete garbage (since you can't pick what exactly you hash)

Yeah, they could do that. They could even use the same trick as the guys who showed the Postscript exploit and make the software do different things based on which of the collision pair is in the file. Get the right version and t

MD5 and digital signatures

[dido]

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:

1. Generate hash of document to be signed
2. Encrypt hash of document using signer's private key (this is the signature)
3. Send document along with signed hash to whoever cares

To verify a digital signature, the following is performed:

1. Recompute hash of signed document
2. Decrypt signature using signer's public key, producing ca

Re:MD5 and digital signatures

[swillden]

And well, here's a bit of news: someone has done just that with X.509 certificates based on MD5.

Ouch. I'm not sure how I missed that one. The first page of their paper shows that I greatly underestimated the severity of the attack. What I hadn't realized is:

Due to the ability of Wang's method to produce MD5 compression function collisions for any IV, and due to the iterative structure of MD5, we can append a collision to any block of data of our choice (provided that the bitlength is a multiple of

Re:MD5 is not an encryption algo

[swillden]

For one: any system that uses one-way hashed password storage or key generation mechanism, as many sites use, is now some percentage easier to violate because multiple strings may resolve to same hash.

It's the case with all one-way hashes that multiple strings hash to the same value. Since an n-bit hash function can only produce 2^n distinct hash values, if there are more than 2^n possible input plaintexts, than multiple plaintexts hash to single values. In fact, since MD5 and similar can hash inputs o

Re:MD5 is not an encryption algo

[Haeleth]

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.

Re:shaken to our what?

[Mind Booster Noori]

SHA-1 is not the sollution [schneier.com]. Take a look at SHA-224, SHA-256, SHA-384, and SHA-512.

SHA-1???

[jd]

SHA-1 has known attacks, although none have (yet) proven to be useful for an exploit. The SHA-2 family (eg: SHA-256) are "unproven" and not part of the FIPS-180 standard (so cannot be used for US Government work), but I would regard them as being "probably safer" than SHA-1 for secure work.

TIGER is good, as is Whirlpool. Whirlpool has the advantage that it uses AES as the basis, and AES is regarded as secure. It was also certified for secure work by NESSIE - a European group trying to do for the EU what NIST does for the US - which means that it's probably certified for use in secure environments in Europe.

According to the Hashing Function Lounge, there are other hashing functions that have not been broken (eg: cellhash and fft-hash) but these are sufficiently obscure that a lack of a known exploit may be through lack of study and not through the presence of good security. It would make them good for beating skript-kiddies, as they won't have the skills to find exploits and those skilled enough at finding them aren't studying those algorithms much. (I don't like security through obscurity, but technically these aren't obscured as anyone CAN study the algorithm.)

Re:SHA-1???

[poemofatic]

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.

How to calculate SHA-2 under GNU/Linux

[YA_Python_dev]

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:

gpg --print-mds [files]

or you can download a dedicated program: http://www.ouah.org/~ogay/sha2/ [ouah.org].

Re:SHA-1???

[jafac]

For my application, SHA-1 incurred a HUGE performance penalty. (factor of 1000). Given that there are few other variables I am free to change in this system, which hash, among these others you mention, tends to be more lightweight?

Re:SHA-1???

[jd]

It depends a little on the implementation, but using mhash I get the following results when generating hashes of a gigabit file from DVD: (Results calculated by using gnu time, and using the user time, not the real time, result)

• SHA-1 - 16 seconds
• SHA-512 - 1 min, 17 seconds
• Haval - 27 seconds
• Whirlpool - 1 min, 14 seconds
• Tiger - 18 seconds

And then, when generating hashes of a 5 gigabyte file on my hard drive (there's been a lot of good stuff on Freshmeat, recently):

• SHA-1 - 2 seconds
• SHA-512 - 3 seconds
• Haval - 5

So you found a collision, big deal

[goombah99]

Maybe someone could explain why collisions are a serious problem for MD5. Or at least in what instances they are. I can see that in some cases, such as password hashing this could be a problem. But for many other uses I don't see what harm a collision has. Maybe I misunderstand but as I understand it MD5s are normally used in a checksum manner to sign or provide a fingerprint of a document. If you have an original document and compute it's MD5 then it can match some certified MD5 check sum. If someone

Re:So you found a collision, big deal

[Krischi]

See this: http://www.cits.rub.de/MD5Collisions/ [cits.rub.de]

It demonstrates the generation of two postscript files with the same MD5 hash that nevertheless display completely differently.

Re:So you found a collision, big deal

[andyh1978]

Maybe someone could explain why collisions are a serious problem for MD5. Or at least in what instances they are. I can see that in some cases, such as password hashing this could be a problem.

It's not a problem in password hashing. There is still no feasible way to compute one of the infinite plaintexts that would generate a given MD5 from just the MD5. Rainbow Tables are the main threat there, but they're defeated by salting (e.g. HMAC-MD5) as you have to regenerate the tables all over again (and find the salt in the first place). It doesn't hurt to go to a larger, more complex hash, but for this purpose, there's no additional worries. It's still "preimage resistant".

Re:So you found a collision, big deal

[andyh1978]

the problem is that if someone knows the MD5 of a password, they can use this code to generate another password with the same MD5. since passwords are usually stored hashed, an attacker wouldn't need to know the original password, only another password that would generate the same MD5

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, unle

Re:So you found a collision, big deal

[iabervon]

This generates "weak collisions", which are where the attacker finds a pair of texts which hash to the same value, not "strong collisions", which are where the attacker finds a text that hashes to the same value as a text chosen by the user. So, someone could now set their password to some string, and then be able to type a different string to get in. (Except that neither are likely to be ascii text, making it a bit tough to type).

The actual issues are for document signing; the attacker could give you one document to sign, and use the signature on a different document with the same hash. There are smaller issues in the case where code expects no two documents to have the same hash. Obviously, collisions must exist, but the code to handle the case is likely not to be well-tested, since test cases were previously impractical to find.

You can spoof (almost) arbitrary documents!

[ChaosDiscord]

Maybe I misunderstand but as I understand it MD5s are normally used in a checksum manner to sign or provide a fingerprint of a document. If you have an original document and compute it's MD5 then it can match some certified MD5 check sum. If someone were to generate a fake document they coul dnot design it to match the MD5 fingerprint. They could create some bit of gibberish that did match it but not a document that was useful as a forgery.

Most document formats have lots of "dead space", parts you can pretty much modify at will without changing what the user actually sees. Comments in HTML or PostScript. Old junk data in Word documents. Executables can have just about anything you like added if you know your stuff. The MD5 attacks currently available only 128 "dead space" bytes to generate a collision. So far from being a gibberish document, one can generate almost any document you want. This page has a simple example with PostScript files. [cits.rub.de] Both files have the same MD5 hash, but one is a relatively harmless letter of recommendation while the other is a grant of security clearance. Get your boss to sign your letter of recommendation digitally, swap in the security clearance file, and pass it on. This is a Big Deal and a Major Problem.

MD5 broken, not useless

[Anonymous Coward]

Keeping in mind where MD5 is broken is important, so that good uses for this tool are not disposed of out-of-hand.

md5 is still good for keeping track of if your files have changed. It should not be used for document signing.

Re:MD5 broken, not useless

[slashdot-me]

md5 is still good for keeping track of if your files have changed

But only for non-security uses. Don't use MD5 in your intrusion detection system.

So what the hell do I do now?

[jeblucas]

I'm essentially crypto ignorant. About all I've known to do was verify MD5 hashes on downloads. Now that this is by-and-large pointless, how to check the veracity of things like Linux ISO's [linuxiso.org], video drivers [nvidia.com], etc, ad inifintum?

Re:So what the hell do I do now?

[k4_pacific]

I wouldn't worry about it too much, generating MD5 collisions large enough to be useful requires a multi-million dollar particle accelerator, so I wouldn't worry too much until someone figures out how to modify a microwave oven to do this.

Re:So what the hell do I do now?

[DreadSpoon]

Do nothing.

MD5 has not been invalidated for those uses. Checking the MD5 sum of an ISO download is not done for security purposes, it's done so that you can make sure you didn't get a bad byte or two somewhere in that 650MB. I mean, if hackers could upload a malware-filled ISO to the FTP server, they could upload a new MD5SUMS file too, right?

Re:So what the hell do I do now?

[yamla]

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.

Re:So what the hell do I do now?

[Aranth Brainfire]

"That's not what MD5 sums are used for."

Heh, sorry, but you lose. I use them for that.

I've never had a problem with an "infected" iso, but I have had one or two that downloaded wrong and flat out failed to work after I burned them. Sure enough, I check the md5 sum and it's not correct- download the iso again from the same site and it works.

So I guess maybe either my hard drive is funky (or some other system failure on one end) or this "packet integrity" isn't so great.

Re:So what the hell do I do now?

[harrkev]

Wrong. If the ISO has some spare room, you could throw in a trojan or two, and just throw in some random data in a junk file to make the hashes match. This is a big deal.

Re:So what the hell do I do now?

[diegocgteleline.es]

Which is why FTP mirrors never should mirror MD5SUMS files

Re:So what the hell do I do now?

[discordja]

well for the day to day I don't think the impact is overly important. Mind you, no one has been suggesting using MD5 for a few years now for important security measures. (pretty soon no one will suggest it for SHA-1 .. it's a never ending cycle as processing capacity grows). So always download your files from reliable sources and check the hash against the known good provided by the distributor and more likely than not you will have a good cd image or installer or whatever. So I'd not concern too much,

Re:So what the hell do I do now?

[Zocalo]

Most things use multiple checksums, for instance on the updated copy of Lynx I just grabbed for Fedora:

$ 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.

Re:So what the hell do I do now?

[swillden]

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.

The cycle begins anew...

[rcbarnes]

Great. Now that MD5 is dead, the slow/theoretical attacks on SHA1 can be the focus of collision research. I look forward to changing hash algorythms again from SHA1 in a year. :-/

Re:The cycle begins anew...

[Mind Booster Noori]

SHA-1 is not the sollution [schneier.com]. Take a look at SHA-224, SHA-256, SHA-384, and SHA-512.

Should I care?

[SlashAmpersand]

This is all really interesting theoretically, but who has the money to run a 1.6 GHz P4?

Replacement Hash Functions

[Anonymous Coward]

Recommended replacements are SHA (preferably SHA-2), WHIRLPOOL and/or RIPEMD.

http://en.wikipedia.org/wiki/SHA-2 [wikipedia.org]
http://en.wikipedia.org/wiki/WHIRLPOOL [wikipedia.org]
http://en.wikipedia.org/wiki/RIPEMD-160 [wikipedia.org]

Why?

[mboverload]

Why not just use 2 different algorithms? Yes, it's possible. Or hell, use 3. Can some one tell me why not this isn't a standard practice? Even if one has a weakness, you still have the other to back it up

I use HMAC-SHA-256 with PasswordMaker.

https://passwordmaker.org/passwordmaker.html [passwordmaker.org]

Re:Why?

[einhverfr]

Even if SHA1 and MD5 have attackable collisions the chances are very low that you can find a meaningful collision that affects both algorithms.

Re:Why?

[mboverload]

Although I was thinking of a hash of a hash, that works as well and fits into my question.

Re:Why?

[Zone-MR]

A hash of a hash? You mean something like SHA1(MD5('data')) ?

In that case, if MD5 is broken and 'data' can be constructed to give the same MD5 hash, the SHA1 hash provides no extra security. In fact calculating a hash of a hash reduces the security, as if ANY of the algorithms in the chain are broken, the final result can be manipulated easily.

Re:Why?

[jonabbey]

True, but you could use a hash function like SHA1('data').MD5('data'), where the . operator stands for string concatenation.

The reason that this isn't generally done is that should not provide more security than a proper cryptographic hash algorithm that produces hashes as long as the two different hash algorithms concatenated together.

If you want additional collision resistance, just generate a longer hash. I believe this is how people are advised to handle SHA-class algorithms right now.

Re:Why?

[einhverfr]

If you want additional collision resistance, just generate a longer hash. I believe this is how people are advised to handle SHA-class algorithms right now.

Hmmm....

I actually like the concatenation more. The reason is that the longer hash solution only provides protection provided that the hash algorythm is not broken. Once it is broken your entire system fails. In other words, the security doesn't have much of a concept of depth.

If you use two independant hash algorythms that are different, then the cha

Re:Why?

[Phleg]

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.

Re:Why?

[einhverfr]

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.

Your point is well taken. However, in this case, I believe you are mistaken. Indeed 3DES is just an extended form of DES which uses 2 keys and three encryptions. But here you are speaking of access so the analogy is likely to be fatal

Re:Why?

[jonabbey]

Now, with my proposal, one would include independant hashs which would be checked independantly. If either one fails, one assumes that the data has been tampered with. The issue is that it would be difficult to defeat both simultaneously for this specific type of check. Being able to do so on demand while editing the file in a meaningful way might well prove impossible.

Yes, but only if you mean 'might well prove impossible' in the same way that it 'might well prove impossible' to break SHA-1 or MD5. Th

Re:Why?

[nahdude812]

As I understand it:

Every re-hashing increases the collision rate, so generally for highest security, you use one unbroken hashing algorithm. Yes, using more than one hashing algorithm would reduce the chances that your whole line of defense is invalidated one day, but it increases the chance that a single hole could be found.

Re:Why?

[mysqlrocks]

Why not just use 2 different algorithms?

If this was in fact more secure than perhaps it would have already been released bundled as one algorithm. Why make people use two sets of algorithms unless the goal is to confuse potential crackers? However, mose uses of MD5 involve the recipient knowing the algorithm used so that wouldn't work.

Re:Why?

[ninjaz]

Why not just use 2 different algorithms? Yes, it's possible. Or hell, use 3. Can some one tell me why not this isn't a standard practice? Even if one has a weakness, you still have the other to back it up

I noticed that NetBSD's source-based package management system, pkgsrc [netbsd.org], already does this using SHA1 and RMD160 (apparently RIPEMD-160 [wikipedia.org] is the official name for the digest). Here's what it looks like in the archive fetching phase of a package installation:

=> Checksum SHA1 OK for unzip-5.52/unzip552.t

Re:Why?

[Lord Ender]

Combining hashes is effectively just inventing a new hash algorithm with longer digests.

As a mathematician, this "seems" like it would be intuitively much more difficult for someone to discover an attack against.

As an engineer, this seems like it is obviously NOT a "good" solution.

If H1() and H2() are both weak, the hybrid H12() is obviously stronger than either, but also fundamentally flawed.

Right now it's time to...

[Tackhead]

> This more than anything should be the final stake in the heart of MD5, now that anyone can generate collisions whenever they want."

In other words, right now it's time to...
...LICK OUT THE KAMS, NOTHERGUCKERS!

bittorrent?

[rayde]

doesn't bittorrent use md5 to verify the sections of files it has downloaded? will this facilitate poison seeds? or does BT use something more complex than md5?

Re:bittorrent?

[Wesley Felter]

BitTorrent uses SHA-1.

Re:bittorrent?

[Mind Booster Noori]

SHA-1? Wow, you're safe then... [schneier.com] :-P

Re:bittorrent?

[Mind Booster Noori]

Parent talked about poisoned seeds, and SHA-1 isn't fine to prevent them...

Re:bittorrent?

[Breakfast Pants]

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).

WTF this source is useless

[RootsLINUX]

I guess someone thinks he's a little too cool to comment his code properly. Yeah, like "/* B2 */" tells me anything useful you insensitive clog!

Re:WTF this source is useless

[plalonde2]

It's thoroughly documented: mind you you need to start with the reference given in the first comment. Variable names and comments relate to that paper.

Not all code documentation lives in the source.

Re:WTF this source is useless

[Theatetus]

If you RTFRFC [faqs.org] you might notice that those are the variable and section names used in the algorithm specificaiton.

This is misleading - MD5 is still useful

[hoggoth]

This new algorithm does not ruin the usefulness of MD5 hashes. The algorithm can generate two documents that have the same MD5 hash, an MD5 collision. But it can NOT generate an MD5 collision starting with an existing document. In practical terms, this means a file that has been signed with an MD5 hash is STILL secure. Nobody can replace the file with a different file that will have the same MD5 hash. However someone can prepare in advance two documents with the same MD5 hash and trick someone into believing one document is really the other. So if you trust the original source (a Linux distro for example) you can be confident you are downloading the original document.

Re:This is misleading - MD5 is still useful

[MoogMan]

Nobody can replace the file with a different file that will have the same MD5 hash.

Yet.
 

Re:This is misleading - MD5 is still useful

[miller60]

This is also important for SSL certificates, many of which use MD5. Existing certificates relying on MD5 are still secure, and new ones can be issued using different hashes. But this is one more motivator for NIST and the security community to decide on a way forward and start making it happen.

MOD ME DOWN

[swillden]

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 [win.tue.nl].

Collisions do not mean the end of MD5

[afaik_ianal]

This more than anything should be the final stake in the heart of MD5, now that anyone can generate collisions whenever they want.

No, no, no. This does not allow an attacker to generate any collision they like. They cannot find data that collides with a piece of data I provide them with. All they can do is provide me with 2 pieces of data that happen to collide.

This means that an attacker can theoretically provide 2 different documents to people with the same hash, but they cannot easily produce a document that has the same hash as a document I have written.

(Disclaimer: I haven't actually been able to RTFA (it's /.'d), but unless they have made an enormous breakthrough since this was last reported, this attack has very little implications for those of us who use MD5).

"broken" does not mean broken

[Edgewize]

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.

Re:"broken" does not mean broken

[petermgreen]

btw torrent block hashes are sha1 not md5

Will people stop saying this?

[ivan256]

This more than anything should be the final stake in the heart of MD5

No, no it won't be. It won't be, because MD5 is useful for many things where the existance of an "easy" (in quotes because easy is relative) method of generating colisions is irrelavant.

It won't even kill off the use of MD5 checksums as a signature for verifying authenticity, because if your data is smaller than the checksum there may not be a colision at all, and an exploit wouldn't matter.

This is an important discovery, but it doesn't make MD5 useless any more than CRC32 is useless.

Got Salt?

[Anonymous Coward]

OK, so clearly a scripted attack against MD5 is bad.

But aren't most people using MD5 using salted (as opposed to unsalted) hashes? (for those unclear on the difference, a "salted" has basically uses a local seed as part of it's MD5 hash, in addition to the value to be encrypted)

Doesn't seem likely that salted hashes can be easily broken by this technique, although clearly it's a concern that, should the salt value become known, all your passwords, etc, become breakable...

Not -that- bad

[Parity]

The only attacks that these md5 collisions allow are denial-of-service/destruction-of-data attacks, they don't generally allow the compromise of protected data or access to systems or suchlike. The collision blocks that are generated are effectively random data. It has yet to be shown how to -craft- a collision block.

If we could craft a collision block that contained a specified string at a specified position, that would be another issue altogether.

The ability to find collision blocks easily does suggest that crafted collision blocks might be possible, but for now, you have as good a chance of getting a viable exploit out of /dev/random as out of a collision block.

This doesn't mean we shouldn't look to other options for the newest releases of high-security software, but it doesn't mean that the md5 algorithm should be purged from our systems altogether either. It's still extremely valuable at detecting accidental corruption, and useful-with-caveats at detecting malicious corruption (45 minutes to discover a block of data that matches the sum is not really useful in either speed or resulting data for any kind of man in the middle attack, for example, so using md5 to validate network packets is safer than using it to validate disk files).

Of course, the black hats may know more than we do about md5 weaknesses, but 'may know' is just as true of any other algorithm.

MD5 and verification

[n0dalus]

Just because collisions can be generated doesn't mean that MD5 is dead.
It might only take minutes to calculate two random strings with the same hash, but it would still take a very long time to calculate a second string that collides with a pre-existing string. So even though it is now cryptographically weak, it can still be used effectively to check the integrity of files.

Re:MD5 and verification

[flynt]

And wouldn't that second string have to be 'meaningful' in the same context as the original, like code to be run?

Coral cache?

[Viper Daimao]

(Coral cache links provided to prevent slashdotting)

Im sorry, you must be new here.

For windows users

[Psionicist]

If you get the error "error getting crypto context..." replace

if(!CryptAcquireContext(&cryptHandle, NULL, NULL, PROV_RSA_FULL, CRYPT_NEWKEYSET ))

with

if(!CryptAcquireContext(&cryptHandle, NULL, NULL, PROV_RSA_FULL, 0 ))

To actually run the program you have to convert your MD5 to four ints. Take your MD5, such as 098f6bcd4621d373cade4e832627b4f6

Divide it in four pieces and convert them to dec.

Hex
=======
098f6bcd
4621d373
cade4e83
2627b4f6

Dec
=======
160394189
1176621939
340356672

Still not a preimage attack

[^BR]

It's the same attack that has already ben spoken about, just now it is available for the masses.

The scope of the attack is one can generate two files having the same MD5 sum, if he can have a random looking section in the middle of the file. i.e. possible in many binary formats but not possible in well formed ASCII text.

What the attack doesn't do is given a MD5 hash being able to find a byte stream that hashes to the same value. So passwords stored as their MD5 sums are still safe, you can't attack t

Weak code.

[kg_o.O]

This code is weak. I fired it up like 20 minutes ago and still haven't r00ted my box.

Q and A

[Sheepdot]

For those of you who store passwords as hashes in your web apps, I've developed a little "Q & A" post here that explains this as best as possible.

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:

INSERT INTO users VALUES ('user','" . md5($password) . "');

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:

INSERT INTO users VALUES ('user','" . sha1(md5($password . '¥1i9k') . 'a-thirty-five-ch4racter-l0ng-str1ng' . md5($password)) . "');

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.

Re:Q and A

[CodeRx]

sha1(md5($password . '¥1i9k') . 'a-thirty-five-ch4racter-l0ng-str1ng' . md5($password))

This is a very bad password salting scheme and vulnerable to a dictionary attack. Once I have your database and salts, I can run a dictionary of common passwords through your scheme and crack any weak passwords.

You can make things much harder by having your salt change for each password - include the username for example. Now I have to run my entire dictionary through the sha/md5 function for each user. By doing this, you make the attack O(m*n) instead of O(m) (where m = the number of words in my dictionary and n = the number of users).

And as you mentioned in a follow up post, this code only generates documents with identical md5 sums, it does not generate a document with a given sum. So MD5 is broken for document signing and the like, but secure for password hashing for the time being.

Re:Q and A

[PhiRatE]

No, a salt can be public knowledge, a salt is there to prevent the use of a pre-hashed dictionary, it does not help in the event of a matcher.

Way back when the hash was unix crypt(), everyone got a little nervous about the idea that someone with a lot of computing power to burn might just fill up a large hard-drive with a map of plaintext->hash for the entire oxford dictionary for example. If they did that, then all they'd need to do subsequently to figure out the plaintext for any of the values they did the crypt()'ing for would be to look through the rive for the crypt value that matched the crypt value in the password file.

The idea of a salt is simple, it changes the hashed result in a computably repeatable fashion, but one that requires that the entire hash has to be performed with the salt in mind in order to get the correct end result.

So using a completely public bit of knowledge is fine. What is preferable is that the salt be random yet repeatable. That's why you see unix passwd files have the salt prepended to the hash (in crypt, it use to be the first 2 characters for example), you generate it randomly once, then whenever you want to see if the plaintext you've been given is the same, you grab the salt, hash the plaintext with it, and then check to see if the result matches the original hash.

In summary, a salt protects you from the problem of a pre-computed hash dictionary, nothing else.

Doesn't Microsoft networking still use MD4?

[Medievalist]

MD4 collisions can be found in a few seconds (but nobody uses that any more)

I thought MD4-encrypted passwords were still flying around most of the world's MS-windows networks. I coulda sworn I had to explicitly turn them off on all my nets...

Adi Shamir's Hash Function *IS* 'unbreakable'....

[iamcf13]

Let Ron 'RSA' Rivest tell you why....

(from material at the Pure Crypto Project - http://senderek.de/pcp/ [senderek.de] )

Quote below from http://senderek.de/pcp/pcp-security.html [senderek.de]

Adi Shamir once proposed the following hash function:

          Let n = p*q be the product of two large primes, such that
          factoring n is believed to be infeasible.

          Let g be an element of maximum order in Z_n^* (i.e. an
          element of order lambda(n) = lcm(p-1,q-1)).

          Assume that n and g are fixed and public; p and q are secret.

          Let x be an input to be hashed, interpreted as a
          non-negative integer. (Of arbitrary length; this may be
          considerably larger than n.)

          Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

          hash(x) = hash(x')

which implies that

          x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

                  Cheers,
                  Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel [phone], Fax [phone], Email

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 [philzimmermann.com] 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 [mit.edu]

Enjoy! :)

Re:Torrent Poisoning

[Mind Booster Noori]

Maybe it's time for you to start using Anonymous p2p [wikipedia.org] networks like GNUnet [gnunet.org]...

Re:The end of edonkey

[n0dalus]

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).

Re:This cannot be used to crack passwords

[cnettel]

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).

I may not have been clear enough...

[^BR]

Or you may have a brain tumor...

The generaly accepted definition for "cracking a password" is, given the encrypted password, being able to generate a password the once entered in the authentication system will generate the same encrypted form.

For the second time, this attack does not permit that. This attack permits build two byte streams that hashes to the same value. So in a password context, assuming the password system permits the entry permits more than 1024 bits of arbitrary data to be entered as password (I don't remind the details well, but I think this is the amount of data that you must be able to change between the two streams) one could generate to "passwords" (being that long they don't qualify for this name anymore IMHO) that would hash to the same value.

How does that amount to an attack on MD5 passwords again? Never at any point the attack had been being able given a unknown to him MD5 hash to produce a stream that would hash to the same value.