Is a second preimage attack on MD5 feasible?

Question

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?

Answer 1

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