0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ is this a homework? Hint: what happens if you can find a collision? $\endgroup$ – kelalaka Nov 26 '18 at 20:16
  • $\begingroup$ @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 ? $\endgroup$ – caffein Nov 26 '18 at 20:22
  • $\begingroup$ 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 ? $\endgroup$ – caffein Nov 26 '18 at 20:51
  • 1
    $\begingroup$ @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$. $\endgroup$ – Gilles Nov 26 '18 at 21:04
4
$\begingroup$

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

$\endgroup$

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.