1
$\begingroup$

Assume $H$ is a collision resistant and preimage resistant (unkeyed) hash function and $E(k,y)$ is a block cipher where $k$ is the key.

I am interested into the collision resistance of the composed function $F(k,x)=E(k,H(x))$. A collision for $F$ is defined as $(π‘˜,π‘₯)β‰ (π‘˜β€²,π‘₯β€²)$ such that $𝐹(π‘˜,π‘₯)=𝐹(π‘˜β€²,π‘₯β€²)$.

This post seems to say that $F$ should be collision resistant but I can't seem to find a way to formally prove it.

ps: Could you please indicate which definition of preimage resistance you would use to prove it? As there seems to be multiple ones.

edit: I have changed the formulation from permutation to block cipher. As explained by @poncho, the implication holds for permutation.

$\endgroup$
8
  • 2
    $\begingroup$ A permutation just arranges the output, it doesn't effect the collision or 1-2 pre-image resistances. $\endgroup$
    – kelalaka
    Feb 3 at 15:49
  • 2
    $\begingroup$ "You show me two colliding messages in $F$, and I'll show you two colliding messages in $H$" $\endgroup$
    – poncho
    Feb 3 at 15:55
  • 2
    $\begingroup$ A block cipher (for a fixed key) is a permutation, since it needs to be invertible on decryption. So, no change to the answer $\endgroup$
    – kodlu
    Feb 3 at 18:17
  • $\begingroup$ Is F to be understood as a keyed function or would pairs (k,x) and (k',x') such that F(k,x)=F(k',x') be a collision? $\endgroup$
    – Maeher
    Feb 3 at 19:27
  • $\begingroup$ Obviously, you would need to make some assumptions about your block cipher. If you had $E(k,y) = k \oplus y$, that would make finding collisions easy... $\endgroup$
    – poncho
    Feb 3 at 20:44

3 Answers 3

2
$\begingroup$

You can probably prove this to be collision-resistant if $E$ is an ideal cipher (and $H$ a random oracle). But it cannot be proven from the simple PRP (SPRP) security of $E$. A simple counterexample is to consider $E$ that ignores the last bit of $k$. Then $(k\|0, x)$ and $(k\|1,x)$ are a collision in your construction.

$\endgroup$
3
  • 1
    $\begingroup$ You probably mean that $E$ is ignoring the last bit. And if someone tells you that this is contrived, show them almost any implementation of DES and slowly walk away. $\endgroup$
    – Maeher
    Feb 5 at 5:30
  • $\begingroup$ Yes, let me correct $F \leadsto E$ in what I wrote. $\endgroup$
    – Mikero
    Feb 5 at 5:42
  • $\begingroup$ This answer is very interesting. What would happen if E is an ideal cipher and H is only collision resistant and preimage resistant (i.e. not a random oracle). $\endgroup$
    – Morz
    Feb 5 at 9:27
0
$\begingroup$

I imagine the following security experiment: 1) first the challenger (not the adversary) picks a key $K$ for $E$ uniformly at random from the key space of the block cipher; 2) the challenger then hands $K$ to the adversary; 3) the experiments ends with the adversary outputting $X$ and $Y$, and it wins if $F_K(X) = F_K(Y)$ and $X \neq Y$. Is this a fair interpretation of what you had in mind?

If so, here's a proof showing that $F$ is as collision-resistant as $H$. Suppose $X \neq Y$ are such that $F_K(X) = F_K(Y)$. Let $Z = H(X)$ and $Z' = H(Y)$, so in particular we have $E_K(Z) = E_K(Z')$. But since $E$ is a block cipher (i.e., $E_K(\cdot)$ is a permutation), we must have $Z = Z'$. But this means that $H(X) = H(Y) = Z$. In other words: a collision in $F$ implies a collision in $H$.

$\endgroup$
1
  • $\begingroup$ Hi thanks for your answer. But what I had in mind is a little bit different. Finding a collision for F is defined as $𝐹(π‘˜,π‘₯)=𝐹(π‘˜β€²,π‘₯β€²)$ and $(π‘˜,π‘₯)β‰ (π‘˜β€²,π‘₯β€²)$. $\endgroup$
    – Morz
    Feb 4 at 23:35
0
$\begingroup$

Under your non-standard definition of collision resistance given below, the composition of a hash and block cipher is not collision resistant at all:

Assume $H$ is a collision resistant and preimage resistant (unkeyed) hash function and $E(k,y)$ is a block cipher where $k$ is the key.

I am interested into the collision resistance of the composed function $F(k,x)=E(k,H(x))$. A collision for $F$ is defined as $(π‘˜,π‘₯)β‰ (π‘˜β€²,π‘₯β€²)$ such that $𝐹(π‘˜,π‘₯)=𝐹(π‘˜β€²,π‘₯β€²)$.

There are at least $2^{d+n}$ inputs $(k,x)$ to your function $F(k,x)$ assuming $k$ is $d$ bits long and the cipher blocklength is $n.$ If anything there are many more since a hash function takes inputs that are in general longer than its output bitlength of $n$ bits.

So even under this conservative assumption there are on average $2^d$ inputs that yield the same output. Just by randomly trying different $(k,x)$ pairs you can find a collision in roughly $2^{n/2}$ trials by the birthday paradox regardless of whether $H$ is collision resistant or not.

$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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