How exactly is MD5 vulnerable to collision attacks?

Question

I've often read that MD5 (among other hashing algorithms) is vulnerable to collisions attacks. I understand the collision part: there exist two (or more) inputs such that MD5 will generate the same output from these distinct and different inputs. There are 20 examples of such inputs given here.

Fair enough, but how does this specifically lead to a vulnerabilities? What is the vector of attack on a system with this kind of a flaw?

For example, say I have a system that simply hashes users' passwords using MD5 for "encryption". Now I want to look at 2 scenarios. (For simplicity, also assume no new users/passwords are added to the system).

Scenario 1: None of the passwords in the system are the kind of inputs that could generate collissions. In other words, all passwords processed by MD5 generate unique hashes. Is there still a collision vulnerability there?

Scenario 2: One of the passwords in the system is this beauty (Collision 14, Message 1 from the list):

Ó)\dvµ‡‚G ÌÕÀ˘∏8;å∑œPäÌ/+6éE≠3}˝óÙ|o‡¬{Ç9¸–Û≤‚Mgª%DWÌé$∞\˛UÊiJ;fÉ;™÷ÎQëµCI<˝y≠˜LùΩ]Owå˜1Ú'¬vo`âÃ(©tú√\îùf#4ú¿�(

So there exists another unsightly string that generates an MD5 collision with this password. However, unless the attacker already know this information, how is the vulnerability exposed?

Answer 1

One common example I've seen involves digitally signing documents using MD5.

Say you have two documents. One of the documents is very innocent, and the other is something malicious. Since you can create both of these documents, you can make it so that they have the same MD5 signatures (using postscript to make the PDFs, for example).

Now you you get somebody to sign the innocent document (which is typically done by signing a hash of the document), but because the hash of both documents is the same, the person just accidentally also signed the malicious document (which might say something like "I give permission for this person to take a million dollars out of my bank account). Now you can present the malicious document to someone else and they will believe the signature on it because of the collision in the document.

Answer 2

Password hashing works on preimage resistance: the password hashing process should be such that it is not computationally feasible to find an input (a password) matching a given output (the hash), save by trying a lot of potential inputs and "get lucky". The "get lucky" attack is still a concern, because passwords are chosen by human users, who are not as imaginative and random as could be wished for; which is why we need more than a simple hash function (we need salts, we need slowness; see this). However, collisions have no impact on the security of password hashing. The ability to generate collisions at will does not give extra cracking power to the attacker.

As others have pointed out, collisions can be used for attacks in other setups involving signatures. These are scenarios where the attacker can:

1. generate colliding pairs of messages, with sufficient control on the format of these messages so that one message looks "innocent" and the other suits the attacker's goals;
2. have the innocent-looking message signed by a third party whose signature function begins by hashing the message "as is".

Under both these conditions, the third party will produce the signature, which will be valid (as far as signature verifiers are concerned) for both messages. This is like having the signer issue a signature on a message without showing it to the signer. A demonstration has been done in 2008 with the "messages" being X.509 certificates, and the signer a Certification Authority. A real-life application of the same concept was done in the Flame malware.

A point to be made is that though raw signatures are vulnerable to collisions, as explained above, they can be protecting by having the signer include some randomness at the beginning of what it signs. In the context of fake X.509 certificates, the attacker must be able to predict, all the bits of the certificates up to the public key; this includes the certificate serial number which is chosen by the CA. If the CA uses big random serial numbers, then the attack does not apply, even if MD5 is used as hash function. On the other hand, CA who use sequential or time-based serial numbers are predictable.

---

Another worry with collisions is about security proofs. Some cryptographic protocols can be proven secure under some specific assumptions about the cryptographic primitives used in the protocol; for instance, some protocols using hash functions can be proven to be secure as long as the hash function is assumed to be collision-resistant, or some other property. An example is HMAC. HMAC reuses an underlying hash function, and was designed so as to accommodate hash functions of the Merkle–Damgård persuasion, notably MD5 and the whole SHA family. Such a hash function is built around an internal "compression function". HMAC has been proven secure under the assumption that the compression function behaves like a pseudorandom function.

However, if the compression function of MD5 is a PRF, then it is not feasible to compute collisions for MD5 with cost less than 2⁶⁴ on average. We know how to produce MD5 collisions for much less than that. This implies that the MD5 compression function is not a PRF. So this voids the security proof on HMAC/MD5.

This does not mean that we know how to break HMAC/MD5 with collisions ! It is "just" that whatever mathematical guarantee of security that we had has just evaporated like morning dew under the merciless midday Sun. In that respect, MD5 collisions are not a tool to be leveraged by the attacker, but are still worth some attention.

Answer 3

Take a look at this link - http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions/ - to see an explanation and the example.

It works exactly as Oleksi said in his answer: you have two documents that will generate the same MD5 hash. The hash is signed, so that both documents can be "valid".