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