1
$\begingroup$

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

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

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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