# If $E_{k_1}(p_1) = c_1$, what is the probability that there exists key $k_2$ such that $E_{k_2}(p_1) = c_1$?

Let $k_1$ be a 56 bit DES key that performs $E_{k_1}(p_1) = c_1$. What is the probability that there exists another key $k_2$ such that $E_{k_2}(p_1) = c_1$?

• Is this an assignment for some course? If so, you should describe your attempts at solving it so far, and specify which part you're stuck with. Sep 1 '18 at 17:03
• No it an exercise question in Bernard Menezes book Sep 1 '18 at 17:13
• The same advice still stands in that case, too. Instead of just copy-pasting the exercise here from the book, you should tell us why you find it unclear or difficult to solve. Sep 1 '18 at 17:17

DES is a block cipher with $b=64$-bit block width, and $w=56$-bit key width (ignoring key parity bits). An ideal model of a block cipher is that each key defines an independent, random-like permutation of the blocks. Under that model, if $E_{k_1}(p_1)=c_1$, then

1. For each key $k\ne k_1$ there is independent probability $u_1=2^{-b}=2^{-64}$ that $E_k(p_1)=c_1$
2. Hence for each key $k\ne k_1$ there is independent probability $v_1=1-u_1=1-2^{-b}=1-2^{-64}$ that $E_k(p_1)\ne c_1$
3. There are $n=2^b-1=2^{56}-1$ keys $k\ne k_1$, hence the probability $v$ that for each of these keys $E_k(p_1)\ne c_1$ is: $v={v_1}^n={(1-u_1)}^n=(1-2^{-64})^{(2^{56}-1)}$
4. Hence the desired probability $u$ that there exist any key $k\ne k_1$ such that $E_k(p_1)=c_1$ is: $u=1-v=1-{(1-u_1)}^n=1-(1-2^{-b})^{(2^w-1)}=1-(1-2^{-64})^{(2^{56}-1)}$
5. For integer $n>0$ and real $\epsilon$, it holds that $(1-\epsilon)^n=1-n\,\epsilon+O((n\,\epsilon)^2)$
6. Therefore, for $m\gg1$ and $m\,|\epsilon|\ll1$, it holds that $1-(1-\epsilon)^{(m-1)}\approx m\,\epsilon$
7. Applying the approximation in (6) to the expression in (4), with $\epsilon=u_1=2^{-b}=2^{-64}$ and $m=2^w=2^{56}$, it comes $$u\approx2^{w-b}=2^{-8}\approx0.39\%$$

Note per Ilmari Karonen's comment: the approximations made after step (4) fail when the key width $w$ approaches or exceeds the block size $b$, as would be the case for 3DES ($b=64$ and $w\in\{112,168\}$) or AES ($b=128$ and $w\in\{128,192,256\}$). We then want a better approximation. We can use ${v_1}^n=\exp(n\log(v_1))$ and $\log(1-\epsilon)=-\epsilon+O(\epsilon^2)$, giving at step (7) $u\approx1-\exp(-2^{w-b})$, valid for $b\ge20$ and $w\ge20$. That's mathematically more accurate, but numerical accuracy requires extended precision when $b-w$ is positive and sizable, which is dangerously close to hold for $b-w=8$ in the question.

Note: Our model of DES is imperfect, in particular when we consider many plaintexts $p$ : DES has additional properties that our model misses. In particular the complementation property $E_\overline k(\overline p)=\overline{E_k(p)}$; that the permutation of blocks for any particular key is even; existence of weak keys. More generally, DES is a particular block cipher (a Feistel cipher within a few cryptographically neutral bit permutations). But given that in the context there is as single plaintext $p_1$ considered, and that DES is a fair cipher (except for its last-century key and block size), it is reasonable to believe that our model is good enough for an excellent approximation of $u$ for random choice of $k_1$ and $c_1$.

Note: with DES a fixed cipher, we can no longer talk of the desired probability $u$ when the whole of both $k_1$ and $c_1$ is fixed. I conjecture that the approximation still holds when $c_1$ and all but say 16 bits of $k_1$ is fixed, but wonder what happens when $k_1$ is fixed to some particular values (like all-zero, which is a weak key).

• As a tiny nitpick, your linear approximation for $(1+\epsilon)^n$ is only good when $|n\epsilon| \ll 1$ (or, equivalently, $|\epsilon| \ll |1/n|$). This become relevant when considering ciphers like AES, where the key size is equal or greater to the block size. A more useful approximation in such cases would be $(1+\epsilon)^n = \exp(n \log(1+\epsilon)) \approx \exp(n\epsilon)$. Sep 5 '18 at 10:10
• @Ilmari Karonen: Thanks for pointing my mistake, fixed now.
– fgrieu
Sep 5 '18 at 12:05

I approached this problem like this:

Let the number of bits in ciphertext be $n$.

So the total number of possible ciphertexts is $2^n$ --------[1]

Probability of getting a particular ciphertext = $1/(2^n)$ (we used any key)

Let the number of tries taken to get the same cipher text be $t$ (Including first encryption).

From [1]: P(not getting the particular ciphertext) = $1-1/2^n$

P(getting the same cipher text from $t$ number of Encryption) =$(1/2^n) \cdot(1-1/2^n)^{(t-2)} \cdot 1/2^n$.

Here the first term $1/2^n$ is the first encryption (try) [@ $t=1$]

Here the first term $(1-(1/(2^n))^{(t-2)}$: $t-2$ failed attempts to get the same ciphertext.

Here the last term $(1/(2^n)$: final try where we got the same cipher text [@ $t$]

Therefore, P(getting the same cipher text from $t$ number of Encryption) = $(1/(2^{2n})) ( (2^n)-1)/(2^n) ) ^ {(t-2)}$.