# Are any block ciphers provably free of equivalent keys?

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?

• 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. Aug 21 '19 at 23:58
• @MarcIlunga It really is $\forall$. For a real-life example, check out the TEA block cipher's equivalent keys. Aug 22 '19 at 2:04

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.