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

  • $\begingroup$ 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. $\endgroup$ Sep 1 '18 at 17:03
  • $\begingroup$ No it an exercise question in Bernard Menezes book $\endgroup$
    – bubloo
    Sep 1 '18 at 17:13
  • 2
    $\begingroup$ 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. $\endgroup$ 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).

  • 1
    $\begingroup$ 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)$. $\endgroup$ Sep 5 '18 at 10:10
  • $\begingroup$ @Ilmari Karonen: Thanks for pointing my mistake, fixed now. $\endgroup$
    – 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)} $.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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