MD5 Message Digest Algorithm Hash Collision Weakness
BID:11849
Info
MD5 Message Digest Algorithm Hash Collision Weakness
| Bugtraq ID: | 11849 |
| Class: | Design Error |
| CVE: | |
| Remote: | No |
| Local: | No |
| Published: | Dec 07 2004 12:00AM |
| Updated: | Dec 07 2004 12:00AM |
| Credit: | Dan Kaminsky <[email protected]> published information and proof of concept code describing this weakness, but numerous others have contributed to the overall research and cryptanalysis of MD5. Proof of concept code, and further information was also provide |
| Vulnerable: |
Ronald L. Rivest MD5 Algorithm |
| Not Vulnerable: | |
Discussion
MD5 Message Digest Algorithm Hash Collision Weakness
The MD5 algorithm is reported prone to a hash collision weakness. This weakness reportedly allows attackers to create multiple, differing input sources that, when the MD5 algorithm is used, result in the same output fingerprint.
It has been demonstrated that attackers can create multiple input sources to MD5 that result in the same output fingerprint. Reportedly, at this time, attackers cannot generate arbitrary collisions. At this time, it is also reported that only a very limited number of individual bits in an input message may be altered while maintaining an identical output fingerprint.
This weakness may allow attackers to create two messages, or executable binaries such that their MD5 fingerprints are identical. One of these messages or binaries would be innocent, and the other malicious. The innocent message or binary may be digitally signed, and then later would have the malicious file substituted into its place. This attack may allow malicious code to be executed, or non-repudiation properties of messages to be broken.
At this time, preimage attacks are not reportedly possible.
It is recommended that cryptosystems that utilize the MD5 algorithm should be reviewed, and the measures should be taken to protect against this weakness. Other hashing algorithms may possibly be utilized in replacement to, or in conjunction with MD5 to decrease the likelihood of a successful attack.
The MD5 algorithm is reported prone to a hash collision weakness. This weakness reportedly allows attackers to create multiple, differing input sources that, when the MD5 algorithm is used, result in the same output fingerprint.
It has been demonstrated that attackers can create multiple input sources to MD5 that result in the same output fingerprint. Reportedly, at this time, attackers cannot generate arbitrary collisions. At this time, it is also reported that only a very limited number of individual bits in an input message may be altered while maintaining an identical output fingerprint.
This weakness may allow attackers to create two messages, or executable binaries such that their MD5 fingerprints are identical. One of these messages or binaries would be innocent, and the other malicious. The innocent message or binary may be digitally signed, and then later would have the malicious file substituted into its place. This attack may allow malicious code to be executed, or non-repudiation properties of messages to be broken.
At this time, preimage attacks are not reportedly possible.
It is recommended that cryptosystems that utilize the MD5 algorithm should be reviewed, and the measures should be taken to protect against this weakness. Other hashing algorithms may possibly be utilized in replacement to, or in conjunction with MD5 to decrease the likelihood of a successful attack.
Exploit / POC
MD5 Message Digest Algorithm Hash Collision Weakness
An example exploit that demonstrates a possibility of creating multiple differing files with the same MD5 fingerprint has been provided by Dan Kaminsky <[email protected]>:
An example exploit that demonstrates a possibility of creating multiple differing files with the same MD5 fingerprint has been provided by Dan Kaminsky <[email protected]>:
Solution / Fix
MD5 Message Digest Algorithm Hash Collision Weakness
Solution:
Currently we are not aware of any vendor-supplied patches for this issue. If you feel we are in error or are aware of more recent information, please mail us at: [email protected] <mailto:[email protected]>.
Solution:
Currently we are not aware of any vendor-supplied patches for this issue. If you feel we are in error or are aware of more recent information, please mail us at: [email protected] <mailto:[email protected]>.
References
MD5 Message Digest Algorithm Hash Collision Weakness
References:
References:
- Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (International Association for Cryptologic Research)
- Cryptanalysis of MD5 Compress (Hans Dobbertin)
- Hash Collision Q&A (Cryptography Research)
- MD5 To Be Considered Harmful Someday (Dan Kaminsky
- Practical Attacks on Digital Signatures Using MD5 Message Digest (Ondrej Mikle)
- RFC 1321 - The MD5 Message-Digest Algorithm (RFC)
- Ronald L. Rivest Home Page (Ronald L. Rivest)
- MD5 To Be Considered Harmful Someday (Dan Kaminsky