6
$\begingroup$

There are $2^n!$ possible permutations of an $n$-bit block cipher $E_k:\{0,1\}^n \rightarrow \{0,1\}^n$, and any given key $k$ selects one of these permutations at random. Define equivalent keys as a pair of keys $k \neq k^\prime$ where $\forall P:E_k(P) = E_{k^\prime}(P)$ and $P\in\{0,1\}^n$. The probability that such a pair exists for realistic cipher parameters is very low. Can a block cipher be proven to be free of equivalent keys?

$\endgroup$
2
  • $\begingroup$ Might be stupid question but is it really a $\forall$ and not $\exists$ ? I can't really see how two different keys would choose the same permutation. $\endgroup$ Aug 21, 2019 at 23:58
  • $\begingroup$ @MarcIlunga It really is $\forall$. For a real-life example, check out the TEA block cipher's equivalent keys. $\endgroup$
    – forest
    Aug 22, 2019 at 2:04

1 Answer 1

7
$\begingroup$

Yes, some block ciphers provably have no equivalent keys.

For a start, it's very easy to exhibit such a block cipher, by restricting the key and message spaces to something enumerable. Granted, that makes the cipher insecure.

But we can also construct such a block cipher secure under chosen-plaintext attack. Assume a secure block cipher with the same key and block space (e.g. AES-128). Note $E_k(x)$ (resp. $D_k(x)$) for the encryption (resp. decryption) of $x$ under key $k$. And define $$E'_k(x)=\begin{cases} 0,&\text{if }x=k\\ E_k(k),&\text{if }x\ne k\text{ and }x=D_k(0)\\ E_k(x),&\text{otherwise} \end{cases}$$ In other words, $E'_k$ is the same function as $E_k$, except possibly for inputs $k$ and $D_k(0)$, which outputs are swapped.

Notice that for any fixed $k$, the function $E'_k$ is well-defined and a permutation of the block space, including in the rare case $E_k(k)=0$, which degenerates in $E'_k=E_k$. Hence $E'$ is a block cipher. And it is demonstrably secure under chosen-plaintext attack if $E$ is, because access to an encryption oracle gives no efficient way to query for $k$ or $D_k(0)$.

The corresponding decryption is $$D'_k(x)=\begin{cases} k,&\text{if }x=0\\ D_k(0),&\text{if }x\ne0\text{ and }x=E_k(k)\\ D_k(x),&\text{otherwise} \end{cases}$$ And since $k=D'_k(0)$, there can't be equivalent keys. For if keys $k_0$ and $k_1$ yielded the same bijections $E′_{k_0}$ and $E′_{k_1}$, then the reverse bijections $D′_{k_0}$ and $D′_{k_1}$ would be the same, hence we would have $D'_{k_0}(0)=D'_{k_1}(0)$, hence $k_0=k_1$; now by contraposition, different keys must yield different bijections, Q.E.D.

$\endgroup$
1
  • $\begingroup$ Wonderful! Thank you. It seems so obvious now. :) $\endgroup$
    – forest
    Aug 22, 2019 at 0:22

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.