Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What's the effective key length of Two-Key Triple-DES, for some (possibly several) reasonably well-defined and sensible definitions of effective key length, say assuming attack using ample chosen plaintext?

A sensible definition of effective key length (in bits) of a block cipher under some attack assumptions could be: one plus the base-2 logarithm of the number of evaluations of the cipher (for arbitrary key and plaintext) that could have been made for a cost equivalent to the expected cost of recovering the key using the best known attack applicable to said assumptions.

By this definition, for any secure block cipher, effective key length is at most about the number of key bits that can influence the output. Proof sketch: consider brute force key search, and that a block cipher having a cost of evaluation not much larger than a comparison would be insecure.


Two-Key Triple-DES (also known as TDEA Keying option 2) is a 64-bit block cipher with a 16-octet key, of which 112 bits can influence the output, defined by $$\operatorname{3DES}(K_1\|K_2,P)=\operatorname{DES}(K_1,\operatorname{DES}^{-1}(K_2,\operatorname{DES}(K_1,P)))$$ where $K_1$ and $K_2$ are 8-octet keys, of which 56 bits can influence the output.

NIST has stated that with $2^{40}$ plaintext/ciphertext pairs, the security is at least 80 bits, but gives no upper bound beyond the obvious 112 bits, which is quite a wide margin.

The effective key length of 3DES assuming two or three chosen plaintexts (per the definition proposed) is no more than about 109.5 bits (see proof below); that obviously can only be lower with more (chosen) plaintext/ciphertext pairs.

One of the best known attack is: Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990); but it is not easily translated into effective key length, at least for the definition that I propose, for the cost is dominated by memory accesses.


The 109.5 bits upper bound stated is 112, minus $\log_2(3)\approx 1.58$ because the core attack loop only performs a DES thus is about 3 times less costly than a 3DES, minus 1 thanks to the the complementation property, plus a little something for the two comparisons in the core loop.

More in details: 3DES inherit from DES the complementation property: $$\forall K, \forall P, \operatorname{3DES}(\overline K,\overline P)=\overline{\operatorname{3DES}(K,P)}$$ and that allows a brute force search with maximum cost quite close to $2^{111}$ DES encryptions, that is $\approx2^{111}/3$ 3DES encryptions (and expected cost half that), with two or three chosen plaintexts:

  • obtain, for some $P$, the ciphertexts $\operatorname{3DES}(K,P)\to C$ and $\operatorname{3DES}(K,\overline P)\to C'$
  • for each of $2^{55}$ value of $K_1$ with high bit zero
    • compute $\operatorname{DES}(K_1,P)\to A$, $\operatorname{DES}^{-1}(K_1,C)\to B$, $\operatorname{DES}^{-1}(K_1,\overline{C'})\to B'$
    • for each of $2^{56}$ value of $K_2$
      1. compute $\operatorname{DES}^{-1}(K_2,A)\to X$; this step dominates the cost
      2. if $X=B$ (implying $\operatorname{3DES}(K_1\|K_2,P)=C$)
        • if $\operatorname{3DES}(K_1\|K_2,\overline P)=C'$, output $K_1\|K_2$
      3. if $X=B'$ (implying $\operatorname{3DES}(\overline{K_1\|K_2},\overline P)=C'$)
        • if $\operatorname{3DES}(\overline{K_1\|K_2},P)=C$, output $\overline{K_1\|K_2}$

This is guaranteed to output the right $K$, and (heuristically) will seldom output others for random choice of $K$; and then another plaintext/ciphertext pair allows to rule out a false positive with overwhelming odds. The cost is dominated by $2^{111}$ DES at step (1); $2^{112}$ relatively cheap comparisons at steps (2) and (3), with very occasional false positives costing an expected $3\cdot 2^{48}$ evaluations of DES for their resolution; and the $3\cdot 2^{55}$ DES for computation of $A$, $B$, $B'$.

This attack is impractical: the total effort devoted to bitcoin mining (which is comparable in nature) as of February 2016 would have explored much less than one millionth of the search space for a single attacked key.

share|improve this question

Des is 56 bits/key with 2Des the key is is 56*2 or 112bits. It is not multiplicative like 56 * 55

3des is EDE encrypt with k1, decrypt with k2 and encrypt with k3. or 3*56 or 168 bits. Quit often, cypherblock chaining is used with the sicond or third pass. The cbc makes it even or difficult to guess the encryption keys.Decryption = DED

share|improve this answer
5  
I don't think this addresses the question – kodlu Feb 25 at 5:09
    
I'm trying not to be a grammar Nazi, but writing "cypher" wrong doesn't inspire confidence. Neither does the contents of this answer. I see 5 upvotes for that last comment but I'm afraid they will turn into downvotes sooner rather than later. – Maarten Bodewes Feb 25 at 22:11

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.