# finding second pseudo preimage faster than brute force

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}$$?

• Strongly related prior question though that one didn't consider freestart attacks.
– SEJPM
Oct 21 '20 at 13:38
• Is "IV" in this question a regular part of the message or the (usually fixed) IV used internally by MD5?
– SEJPM
Oct 21 '20 at 13:39
• IV is initial value which is used in MD5 Oct 21 '20 at 13:41
• link.springer.com/chapter/10.1007/3-540-58108-1_19 Oct 21 '20 at 13:45
• kelalaka this paper is about double block of data. I try to find my answer in one block of data Oct 21 '20 at 13:47

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

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.