# Is a second preimage attack on MD5 feasible?

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?

-
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