finding second pseudo preimage faster than brute force

Question

As far as I know finding second preimage of a hash function is almost as hard as finding preimage. But I want to know that is there any way to finding second pseudo preimage faster than brute force? I mean ,for example, in MD5 for a given $h$ (hash) we have $MD5(IV_1 , P_1) = h $.is there any way to find $(IV_2 , P_2)$ such that $$ MD5(IV_2 , P_2) = MD5(IV_1 , P_1) = h$$ in time complexity less than $2^{128}$?

Also if the answer of question is YES please tell me that if I change the $IV$ , is it possible to modify $P$ to get same hash in time complexity less than $2^{128}$?

Answer 1

For MD5, it is only known for the first (pseudo) preimage it is given by Yu Sasaki and Kazumaro Aoki in 2009

• Finding Preimages in Full MD5 Faster than Exhaustive Search

In this paper, we present the first cryptographic preimage attack on the full MD5 hash function. This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5.

In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$, In the second preimage attack we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.

If we can execute a pre-image attack, then we may carry it into a secondary pre-image attack. First, execute a pre-image attack, if we find $y \neq x$ than we are done. If not, continue the search. If brute-forcing, just continue, if a special attack, change the parameters and/or continue to find another.

A similar idea can work for the pseudo secondary preimage attack, too. I've not seen an example on MD5. Usually, the first pseudo preimage attack is extended to secondary pre-image attack. Like done on Gost hash function

A (Second) Preimage Attack on the GOST Hash Function

Note: pseudo-preimage is also called free-start target attack.