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$
- compute $\operatorname{DES}^{-1}(K_2,A)\to X$; this step dominates the cost
- 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$
- 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.
