1
$\begingroup$

enter image description here

I am trying to learn attack on hash collision. I guess for this scheme, it might be possible to use messages with different lengths to find a pair of same ciphertexts. An attempt is to use the same first block, and let M1 = M[1] and M2 = M[1]M[2]. Then, it might be possible to find a collision because the first one outputs C[1] and the second one outputs the C[2], but I am a little confused about how to analyze M[2] so that they form a collision.

$\endgroup$
2
  • 1
    $\begingroup$ Is $K$ public knowledge, or do you only have Oracle access to $H_k$ (for some unknown $k$)? $\endgroup$
    – poncho
    Apr 4, 2022 at 12:22
  • $\begingroup$ K is known to the adversary, so u can actually calculate Hk without using an oracle but by hand. $\endgroup$ Apr 4, 2022 at 21:16

1 Answer 1

0
$\begingroup$

You are trying to learn, and so I'll just give you a hint:

  • You know the value C[1]; how do you find a fixed point, that is, a value M[2] that maps C[1] to itself (so C[1] = C[2])

  • Further hint: it's easier to work backwards; start at the target value of C[2], and figure out how to select M[2] so that B[2] is something appropriate

$\endgroup$
3
  • $\begingroup$ I figured out. It's little tricky, which doesn't make sense to me in the first glance, but it seems like u can duplicate M[1] but still get the same hash value if E(M[1]) = 0^128, which is really smart when I first noticed this approach. $\endgroup$ Apr 5, 2022 at 0:23
  • $\begingroup$ @Turingtest: no, I don't believe that is correct; what would M[2] need to be to make sure that B[2] = C[2]? $\endgroup$
    – poncho
    Apr 5, 2022 at 7:39
  • $\begingroup$ Consider AES = E, then C1 output C[1] = E(E(M[1] xor 0^128) xor M[1]) = E(E(M[1]) xor M[1]) = E(0^128 xor M[1]) = E(M[1]) = 0^128. C[2] = E(E(M[2] xor C[1]) xor M[2]) = E(E(M[2] xor o^128) xor M[2]) = E(E(M[2]) xor M[2]) if M[1] = M[2], C[2] = E(E[M[1]) xor M[1]) = E(0^128 xor M[1]) = E(M[1]) = 0^128. Then C[1] = C[2]. $\endgroup$ Apr 5, 2022 at 21:38

Your Answer

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

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