4
$\begingroup$

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[0\ldots n], M[(n+1)\ldots 2n]\big) \oplus M[0\ldots 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!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ There's a problem with the statement: since "we XOR the output of AES with the first half of the input message", and said output is 128-bit, it must be that $n=127$ so that there are 128 bits in $M[0\ldots n]$ on the right of the expression. And then $M[(n+1)\ldots 2n]$ is 127-bit. Also, we are left to guess if that later thing is the key (in which case there is preimage resistance), or if this is data (in which case there is not, as explained in the answer). $\endgroup$ – fgrieu♦ Nov 7 '20 at 10:06
  • $\begingroup$ Thanks @fgrieu! In the question I forgot to mention the input M for hash function is 256 bit which means M[0... n] is indeed 128 bits but I'm glad I didn't because your comment has given me an important tip for future reference and cases where the input is not necessarily 128 bits! $\endgroup$ – Alex Nov 7 '20 at 22:17
  • 1
    $\begingroup$ Another way to make the same remark; there are $n+1$ bits in $M[0\ldots n]$, not $n$. That's why computer scientists count intervals with the second side excluded: $M[0\ldots 2n)=M[0\ldots n)\mathbin\|M[n\ldots 2n)$. $\endgroup$ – fgrieu♦ Nov 8 '20 at 9:17
  • $\begingroup$ @fgrieu sorry I misunderstood your earlier comment. Now I got what you mean. Thanks! $\endgroup$ – Alex Nov 8 '20 at 10:30
6
$\begingroup$

Using the hash function;

$$h(M) = \operatorname{AES-Enc}\big(M[0\ldots n], M[(n+1)\ldots 2n]\big) \oplus M[0\ldots n]$$

One can find many pre-images with the given hash value $h$

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

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks @kelalaka for explaining this so well. I didn't thought of the decryption and was just focusing on the encryption aspect. Thanks again, much appreciated! $\endgroup$ – Alex Nov 7 '20 at 22:14

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.