Collision attack on hash

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?

• 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. – SEJPM Apr 5 '17 at 18:29
• Hint: how would you find a preimage, that is, a pair $x, y$ that hashes to a preselected value? – 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$.

• Nice, I missed this in my answer. – 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}).$