If $x$ and $y$ are both 128-bit strings would the function $h(x||y) = AES_x(y)$, where $x\|y$ means concatenation, be considered collision resistant ?

  • Is there an easy way to find $(x_1, y_1)$ and $(x_2, y_2)$ such that $h(x_1\|y_1) = h(x_2\|y_2)$ ?

I couldn't think of a way but since the hash function is un-keyed something tells me that there is a way to manipulate the key/string pairs?

  • is this a homework? Hint: what happens if you can find a collision? – kelalaka Nov 26 at 20:16
  • @kelalaka, I suppose that if the keys are different as well as the texts then collisions are possible in theory, since we have 2^256 options for the input and only 2^128 options for the output. But that doesn't contradict anything about AES, does it ? – caffein Nov 26 at 20:22
  • What i thought is that in average we will have to try 2^128 options to find a collision when they keys are different because in average every 2^128 strings from the 2^256 will map to a single ciphertext (and there are 2^128 ciphertexts) What i'm looking for is a formal proof of what you've mentioned - because brute-force is always correct but how can we prove that no other way exists to break it ? – caffein Nov 26 at 20:51
  • 1
    @kelalaka Er, no, AES decryption does not require brute force. Given a ciphertext $c$ and an arbitrary key $k$, you can find a plaintext $p$ such that $E_k(p) = c$. What would be difficult would be to find $k$ given $p$ and $c$. – Gilles Nov 26 at 21:04
up vote 4 down vote accepted

It isn't even second-preimage resistant. Hint:

$y = \mathrm{AES}^{-1}_{x}(\mathrm{AES}_{x}(y))$

For any 128-bit string $x_1$, $x_2$ and $y_1$,

$h(x_1||y_1) = \mathrm{AES}_{x_1}(y_1) = \mathrm{AES}_{x_2}\left(\mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right) = h\left(x_2 || \mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right)$

Follow-up question: is it preimage-resistant?

$h(x||y) = \mathrm{AES}_{x}(y)$ so $y = \mathrm{AES}^{-1}_{x}(h(x||y))$. For any hash value $H$ and any 128-bit string $x$, it's trivial to calculate a preimage that begins with $x$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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