3
$\begingroup$

Beyond the birthday problem analysis how feasible is a preimage attack or speed up brute force on a substring of MD5. For instance let's say from the 128 bits I decide to strip 24 bits, the first four and last 20 of a generated MD5.

How can you attack or fast generate a preimage that will collide on the same substring.

ps.It is known MD5 is broken, some hardware can compute billions of MD5 hashes per second. The intent of the question is theoretical understanding.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Right now, the cheapest known algorithms for (partial) preimage search are generic algorithms, costing ${\sim}2^b/t$ to compute a preimage for any of $t$ target $b$-bit strings in time ${\sim}2^b/t^3$ if parallelized $t^2$ ways—here $b = 128 - 24 - 4 - 20 = 80$.

The Sasaki–Aoki algorithm, while perhaps theoretically interesting, costs about a petabyte of memory, when at much lower cost you could power 32 CPUs (or just MD5 circuits) instead and get an answer faster with a naive generic search in parallel.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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