# Brute force attack on DES + property of DES

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

-

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, 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, for we can make a time/memory trade-off; 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 about $2^{t-56}$ for $t\ll 56$.
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.