Let us define the hash function $h\colon \{0,1\}^{2n}\to\{0,1\}^n$ as $$h(x||y)=E(x,y),$$ where $E$ is a block cipher and $x,y\in\{0,1\}^n$. Any ideas on how to easily find collisions on this hash?

  • $\begingroup$ a) I think this is "only" a compression function and not a "full" hash and b) I think this is "kinda commonly" done in actual hash functions. $\endgroup$ – SEJPM Apr 5 '17 at 18:29
  • $\begingroup$ Hint: how would you find a preimage, that is, a pair $x, y$ that hashes to a preselected value? $\endgroup$ – poncho Apr 5 '17 at 18:33

It's straightforward to find a large set of preimages for any hash value!

For arbitrary $x,z \in \{0,1\}^n$, you can construct $Y(x,z)$ such that $h(x||Y(x,y))=z$. Let $D$ be the decryption function for the block cipher, i.e. $D(x,\cdot)$ is the inverse permutation from $E(x,\cdot)$. The goal $h(x||Y(x,z))=z$, i.e. $E(x,Y(x,z))=z$, is equivalent to $Y(x,z)=D(x,z)$.

Thus for any $x$, all of the inputs $x||D(x,z)$ for $z \in \{0,1\}^n$ are collisions for $h$.

  • $\begingroup$ Nice, I missed this in my answer. $\endgroup$ – kodlu Apr 6 '17 at 0:19

Repeating a comment this is not a full cryptographic hash.

Assuming $x$ represents the key, clearly $E(x,y)=E(x,y')$ is impossible for $y\neq y'.$

By birthday paradox, assuming the cipher has decent randomness properties, $O(2^{n/2})$ outputs should result in a collision.

The simplest attack would fix the "plaintext" $y$ and do a search along different $x$ storing the outputs in a (hash-)sorted table of size $O(2^{n/2}).$


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.