Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question

migrated from programmers.stackexchange.com Jul 11 '13 at 23:38

This question came from our site for professional programmers interested in conceptual questions about software development.

    
the vector is really apparent when the attacker can control both versions (the one the victim wants that has been vetted and signed by a third party and the one the attacker wants the victim to have) –  ratchet freak Jul 11 '13 at 23:09
    
Is that the only vector for such an attack? In reality, how likely is the attacker to have/gain control of both versions? –  Arman H Jul 11 '13 at 23:12
    
Would you like this migrated to IT Security? You might get better answers there than here. –  World Engineer Jul 11 '13 at 23:32
    
In electronic payment, for example, the attacker may get someone to sign a cheque for 10$, then replace that cheque with another one that hashes to the same value so that the signature is still valid. (Cryptographic signatures typically sign only the hash of the document, not the document itself, because signing an arbitrarily large document instead of a very small fixed-size hash would be much too expensive.) –  Jörg W Mittag Jul 11 '13 at 23:33
    
@WorldEngineer, let's migrate if it belongs there more. –  Arman H Jul 11 '13 at 23:38
show 6 more comments

3 Answers

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

share|improve this answer
    
Excellent example and explanation. Reading though the details right now. –  Arman H Jul 12 '13 at 2:01
    
glad to help, but the first answer (oleksi) explained it all.. I just remembered the example and googled it :). –  woliveirajr Jul 12 '13 at 2:25
    
The example on that site involves doctoring BOTH documents, Prior to having one of them signed. is there a way to execute the attack when the original, authentic document has already been signed - ie by only doctoring ONE file, to match the existing one? –  caesarsgrunt Jul 12 '13 at 2:51
    
@caesarsgrunt : take a look at en.wikipedia.org/wiki/Cryptographic_hash_function#Properties . What you ask is the second pre-image attack. This answer was about the collision resistance... –  woliveirajr Jul 12 '13 at 3:08
1  
Ah, right - so in fact poor collision resistance is not a problem in that situation. Thanks for the answer/link. –  caesarsgrunt Jul 12 '13 at 3:15
show 1 more comment

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.

share|improve this answer
    
I'm looking at the kinds of messages that generate collisions, and they all look like string garbage. How does one go from something like Ó)\dvµ‡‚G ÌÕÀ˘∏8;å∑œPäÌ/+6éE≠3}˝óÙ|o‡¬{Ç9¸–Û≤‚Mgª%DWÌé$∞... to generating a pair of collision-vulnerable documents? –  Arman H Jul 12 '13 at 0:38
    
When you create a postscript document to make a PDF, not all characters are displayed on the screen. There are often many mechanism for including non-printable characters (like comments) –  Oleksi Jul 12 '13 at 0:40
    
Won't the actual visible/printable characters, PDF document's formatting, etc, all affect the final hash output? Regardless of how it is achieved, the core of my question is: Does abusing hashing collisions ultimately come down to tricking a user, or can it be used to directly interfere with a system (and if yes, how)? –  Arman H Jul 12 '13 at 0:42
1  
Yes, but you can "fix" part of the document to be meaningful text, and then build a hash conflict by messing with characters which don't get displayed without affecting the characters which do get displayed. This is generally up to the method of generating collisions, but the methods for generating MD5 collisions are flexible enough to let you do this. –  Oleksi Jul 12 '13 at 0:45
1  
see th.informatik.uni-mannheim.de/people/lucks/HashCollisions/… and th.informatik.uni-mannheim.de/people/lucks/HashCollisions/… : both have the same md5, both are very different... –  woliveirajr Jul 12 '13 at 1:54
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.