• In a brute force attack on DES, it seems to me that one plaintext-ciphertext pair suffices to launch the attack. (I.e. suppose we are given a message $x$ and a ciphertext $c$ such that $DES_k ( x ) = c$, where the $56$-bit key $k$ is unknown. Then going through all $2^{56}$ keys will eventually give the result.) I am, however, unsure about this, as in Katz/Lindell's book Introduction to Modern Cryptography on page 179 (line -9) they seem to suggest that "these attacks require a large number of input/output pairs...". This sentence thus confuses me, as to me it seems that one pair suffices.

  • Related to the first point, is the following statement true?

    Statement. For all messages $x$ and all keys $k_1, k_2$, if $DES_{k_1} ( x ) = DES_{k_2} (x)$ then $k_1 = k_2$.

    I'm not sure if it holds. Have been thinking about it for a while.

  • In Katz/Lindell they say that an exhaustive key search happens "in time $2^{56}$". I do not completely understand this statement. I do understand that there are $2^{56}$ keys in total. So, in the worse case scenario, it will take $2^{56}-1$ "steps" (i.e. DES-applications). So if they speak about "time", do they always mean worse-case scenario-time?

    However, the expected value (of the needed "time") seems to me to be $2^{56} / 2 = 2^{55}$. Is this correct?


1 Answer 1


You are right that a brute force attack on DES requires a single plaintext/ciphertext pair; another plaintext/ciphertext pair is useful to confirm the result once found (and rule out a false positive).

No, $DES_{k_1}(x) = DES_{k_2}(x)$ does not imply $k_1=k_2$; the same holds with high probability for any ideal cipher with the same parameters as DES, modeled as a key-dependent family of random permutation (explicitly finding a counterexample requires significant work, but still much less work than a brute-force key search: that's essentially a collision search, memory or/and cycle-finding can help; in fact that is an interesting hands-on computer project).

DES key search with a single plaintext/ciphertext using a black-box DES implementation requires $2^{56}$ invocations at worse (we discount the "optimization" of concluding after $2^{56}-1$ keys did not match that the single remaining one must be right, which is unrealistic, and saves only $2^{-56}$ of the effort with odds $2^{-56}$). That is "in time $2^{56}$" (the default assumption is a sequential attacker). There will be $2^{55}$ invocations on average (the expected time/effort). Chance/risk (depending on point of view by attacker/user) that the key is found after only $2^t$ tests is $2^{t-56}$ for $t\le56$ using sequential key search, or $t\ll56$ using random key search.

Notice that if one has two pairs $(x,E_k(x))$ and $(\overline x,E_k(\overline x))$, the DES complementation property gives $E_k(\overline x)=\overline{E_\overline k(x)}$ and allows to half the work, for we can test $k$ and $\overline k$ in a single operation. Also notice that in a computer program (rather than a black box) we can change the keys in a manner such that a little of the work with earlier keys is reusable, saving some time; and more generally test $t$ keys with appreciably less work than what's required for $t$ encryptions with arbitrary different keys.

The DESCHALL project and EFF DES Cracker have been historical demonstrations that the DES key space of $2^{56}$ was too small even for civilian application in 1998.

  • 1
    $\begingroup$ Indeed, finding a pair of DES keys $k_1 \ne k_2$ such that $DES_{k_1}(x) = DES_{k_2}(x)$ for some freely chosen plaintext $x$ is quite doable in a less than an hour even on an old slow laptop. I know because I just found such a pair. I won't spoil it, though, since it is a good programming exercise. $\endgroup$ Sep 23, 2016 at 3:46

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.