Consider the following hash function for a message x = x1||x2|| · · · ||xn: h(x) = Mn i=1 AES0(xi) = AES0(x1) ⊕ AES0(x2) ⊕ · · · ⊕ AES0(xn) where the key used in AES is k = 0. Can someone explain what is wrong with this hash function?

  • 2
    Please learn to use $LaTeX$/MathJax and edit your questions. And, it is quite cleat that this is homework, explain the source of the question, and your work so that people can be more helpfull to you. – kelalaka Nov 15 at 10:13
  • Hint: I don't need to find some other blocks than your in the question to find a collision – kelalaka Nov 15 at 10:53
  • 1
    Check out what happens when you reorder the blocks. – Maeher Nov 15 at 10:57
up vote 1 down vote accepted

The definition of the function in the question is not clear. My understanding is that the question is about the function $H$ defined by $$ H(x_1 || \ldots || x_n) = E(x_1) \oplus \ldots \oplus E(x_n) $$ where the message is broken into 16-byte blocks $(x_1,\ldots,x_n)$ (the function is only defined on messages whose size is a multiple of 16 bytes) and $E$ is AES encryption with the key all-bits-zero.

What's wrong with this function as a hash? Plenty! Take the definition of a cryptographic hash function. Can you find a counter-example for each property?

Pre-image resistance: if I give you a target value $V$, can you find a message $M$ such that $H(M) = V$? Hint:

For a 1-block message $x$, $H(x) = E(x)$.

So…

For any value $V$, $V = H(x)$ where $x = D(V)$, where $D$ is AES decryption with the key all-bits-zero ($D$ is the inverse function of $E$).

Second pre-image resistance: given $M$, can you find a different message $M'$ such that $H(M) = H(M')? Hint:

How does $H$ work when you append one block to the message?

So…

If $x$ is one block, $H(M || x) = H(M) \oplus E(x)$. You have $H(M || x) = H(M)$ if $E(x) = \mathbf{0}$ (where $\mathbf{0}$ is the all-bits-zero block). So $H(M || \mathbf{0}) = H(M)$.

Collision resistance:

Each counterexample to second pre-image resistance is also a counterexample to collision resistance.

Follow-up: the counterexamples I give depend on knowing how to decrypt. If somehow you could encrypt blocks but not decrypt them, would the hash properties be fulfilled? (Hint: no, but you'll need different ways of constructing counterexamples. Pre-image resistance would “almost” be true, but not the other two.)

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.