7
$\begingroup$

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?

$\endgroup$
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$
    – SEJPM
    Apr 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$
    – poncho
    Apr 5, 2017 at 18:33

2 Answers 2

2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.