Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What's the practical status of MD5 w.r.t. second-preimage?

Integrity of a piece of data is protected by an MD5 hash, itself assumed genuine. The data (and thus the hash) is known to the adversary. The adversary can change the data, and wants to do that while leaving the hash identical. Denote the data size as $K$, in 512-bit block increment, and assume that could be sizable (e.g. $K\approx2^{35}$, which is less than one big hard disk). The original data could follow some pattern (e.g. repeated 512-bit blocks). To some degree, the adversary could even choose some data in the original (e.g. embedded in some innocent-looking file); but we must assume that the adversary can't predict some of the data before what it injects, else the now classic collision attacks against MD5 apply.

A generic second-preimage attack is applicable to Merkle–Damgård hashes, with cost $2^{129-k}+2^{65}$ hash rounds for MD5, where $k=\log_2K$, but that's not exactly cheap (it is attributed to R. D. Dean in his 1999 thesis sect. 5.3.1, and also exposed by J. Kelsey and B. Schneier in their 2005 paper).

Has anything more practical surfaced?

share|improve this question
2  
Your use of k seems inconsistent. $ k = 2^{35} $ and putting it into the exponent in $2^{129-k}$ can't be right. –  CodesInChaos Aug 2 '12 at 21:28
    
@CodesInChaos: Yes, thanks; that should be fixed now. –  fgrieu Aug 3 '12 at 6:19
add comment

1 Answer

up vote 5 down vote accepted

As far as I am aware, there are no practical known second pre-image attacks on MD5, under the conditions you listed.

However: if the attacker can control any part of the original, I would worry about using MD5 in this setting. Its security in this setting may be fragile and there may well be cleverer attacks than anything currently in the literature. I wouldn't be shocked to discover that second pre-image attacks are possible if the attacker has control over part of the original, even if we assume that the original starts with some unpredictable stuff before the part that the adversary can control.

So using MD5 in this way in new systems would not be prudent. (I don't think I'm telling you anything you don't already know...)

share|improve this answer
1  
AFAIR there are even no practical attacks for MD4. –  Smit Johnth May 22 '13 at 19:37
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.