Why this isn't second preimage resistance?

Question

I've been reading on preimage resistance and trying out few examples for the same and I'm trying to figure out why the following hash function does not have the second preimage resistance and any suggestions would be appreciated.
$$h(M) = operatorname{AES-Enc}big(M[0ldots n], M[(n+1)ldots 2n]big) oplus M[0ldots n]$$
For the given hash function, since we XOR the output of AES with the first half of the input message, if I consider a message all bits zero then my hash-function would simply resolve to $operatorname{AES-Enc}(0^n, 0^n)$. Now to show it doesn't have second preimage resistance I understand, that I need to find another message $M' != M $. But, if I consider another message $M'$ which is an all bit 0 except last bit flipped then the hash function will be $AES(0^n, 0^{n{-1}}1)$ but the output, in this case, won't be the same as $h(M)$ and so on.. so I'm a bit confused at this point and any hint would be greatly appreciated!

kelalaka · Accepted Answer

Using the hash function;
$$h(M) = operatorname{AES-Enc}big(M[0ldots n], M[(n+1)ldots 2n]big) oplus M[0ldots n]$$
One can find many pre-images with the given hash value $h$

take arbitrary $M[0ldots n]$
calculate $x = M[0ldots n] oplus h$
Decrypt AES with the key $M[0ldots n]$ and the ciphertext is $x$
$$m =operatorname{AES-Dec}big(M[0ldots n],xbig)$$

let $M[(n+1)ldots 2n] = m$ then we are done, found a pre-image. Now if the founded pre-image is different than the provided $M$ with the $h = h(M)$, then this is a second pre-image for the hash function. If not, one can look for others to find a secondary image for this hash function. Therefore, this is neither a pre-image resistant nor second pre-image resistant hash function.
We just used the property of AES that is a permutation under a key and the key is free to the attacker.

Why this isn't second preimage resistance?

One Answer

Add your own answers!

Ask a Question