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?
2
-
$\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$– SEJPMApr 5, 2017 at 18:29
-
$\begingroup$ Hint: how would you find a preimage, that is, a pair $x, y$ that hashes to a preselected value? $\endgroup$– ponchoApr 5, 2017 at 18:33
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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$.
answered Apr 6, 2017 at 0:08
Gilles 'SO- stop being evil'Gilles 'SO- stop being evil'
18.5k4 gold badges47 silver badges88 bronze badges
$\begingroup$
$\endgroup$
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}).$
