Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
  • 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?

share|improve this question
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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