# Is the hash function $h(x\|y) = AES_x( y)$ collision resistant?

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 '18 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 '18 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 '18 at 20:51
• @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 '18 at 21:04

$$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)$$
$$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$$.