3DES security when K1=K3

Question

I am mainly looking for security on 2-key $\operatorname{3DES}$ implementation where $K_1=K_3$.

How hard or easy is it to crack $\operatorname{3DES}$ when $K_1=K_3$?

Answer 1

TL;DR: the official $2^{80}$-something theoretical security of 2-Key Triple DES w.r.t. key search¹ is still practically good enough in most of its many uses in 2020; but security authorities rightly do not condone it in new applications.

---

"3DES when $K_1=K_3$" is formally known as TDEA keying option 2 in FIPS 46-3 or 2TDEA or 2-Key Triple DES. It is still very common in current (2020) commercial applications, including Smart Cards, and its security is thus an important practical concern.

It's vulnerability to key search depends on many things, the most decisive being:

• both components $K_1$ and $K_2$ of the key have been chosen independently and uniformly at random (we assume that, and thus disregard attacks on key derivation);
• how many matching plaintext/ciphertext pairs are available for the attack;
• whether it is targeted a single key $(K_1,K_2)$, or any of many such key (and then how many, and if the available plaintext/ciphertext pairs share a common block).

Study case 1: single key, little plaintext

With two or three plaintext/ciphertext pairs enciphered under a single key, the best attack I know is brute force², with expected success probability $\approx2^{-112}\,n$ after work² totally dominated by $n$ DES encryptions with incremental keys.

By October 2020, the sizable fraction of the global resources devoted to bitcoin mining is reportedly achieving $144\cdot10^{18}\,\text{SHA256d}/s$, where one SHA256d is two SHA-256 compressions, each doing 64 rounds on a 256-bit state. DES does 16 rounds on a 64-bit state, so I'll count $2\,\frac{64}{16}\,\frac{256}{64}=2^5$ DES for one SHA256d, which gets us to $2^{\approx97}$ DES/year. Thus after a year, the probability of success is $2^{\approx-15}$ or ≈0.003%.

Conclusion: there are few applications where this attack should get a rational decision maker bothered for the near future.

Study case 2: many keys, little chosen plaintext for each

On another extreme, if $m=2^{28}$ (270 million) Smart Cards have been issued with random keys, and adversaries having infected card loading devices managed to obtain ciphertext blocks for the same two or three plaintext blocks encrypted under each key, then they can mount a multi-target attack. It finds an expected $\approx2^{-112}\,n\,m$ keys after work² dominated by $2\,n$ DES operations and $n$ searches of a 64-bit result among a table of $m$ values using roughly $64\,m\,$bits for the portion that needs to be high speed.

Compared to the previous attack, the number of DES operations for a certain probability is reduced by a factor of $m/2$ (down to complexity of $2^{85}$ DES operations), and the bottleneck becomes search.

I can vaguely imagine an IC where a 2GiB table fits, subdivided into $\approx2^{8}$ sub-tables each searched at $2^{28}\,$Hz (3.7ns latency). Throw $2^{24}$ (17 million) such ICs at the task and after a year ($2^{\approx25}\,$s ), it's expected to find $2^{\approx8+28+24+25+28-112}\approx2$ keys, and the probability of getting a least one is high.

Further increasing $m$ may reduce the cost, but much slower than proportionally. With foreseeable technology, it seems the sweet spot is when the table to search fits one IC, and when we increase $m$ we must use a denser memory technology, thus slower for the best technologies available at a given time.

Conclusion: recovery of a few of the many keys can't be summarily dismissed as impossible for well-founded adversaries that design, build and operate custom ASICs. But in a system with the capacity to blacklist cards, that's most likely an acceptable risk.

Study case 3: single key, much plaintext

Here, "much" means up to $2^{\approx32}$ blocks ($32\,$GiB). Even approaching that threshold is not advisable for any 64-bit block cipher anyway. Attacks combining a lot of RAM (like textbook Meet-in-the-Middle for 2DES) and iterated collision search (the practical variant of MitM for 2DES, wich uses little RAM and can be bade "embarrassingly parallel") can reduce the number of DES operations considerably compared to case 1. The standard reference is Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990).

Circa 2012 I tried to determine if that attack had become feasible. My tentative conclusion was that a then unreasonable amount of RAM was needed to get below $2^{90}$ DES operations, even if we ignore a lot of costs, including for communication between the RAM nodes.

This is reexamined by Chris J. Mitchell, On the Security of 2-Key Triple DES (in IEEE Transactions on Information Theory, 2016 and arXiv, 2016). It brings an improvement: for chosen plaintext, using the DES complementation property halves the cost. As in van Oorschot and Wiener, more plaintext does not help much, and the bottleneck is the cost of memory and accesses to it (much like in 2).

My opinion is that this attack still remains (2020) extremely hypothetical, harder than that of case 2 with current technology; but we would have to analyses factors beyond RAM availability (like energy for their operation, and communication costs as tentatively explored in this) to conclusively repel the attack as infeasible in the next 5 years for well-funded adversaries; and I know no such analysis.

Study case 4: many keys, significant plaintext for each

That could be the situation e.g. in a VPN that changes session key regularly, and only limited known plaintext is available for each key.

The above Mitchell reference argues that the total amount of ciphertext necessary for a given probability of finding at least one of the many keys at a given cost is largely independent of how many keys are targeted. As far as I see, we're back to case 3 and it's hardness if we follow Mitchell, and case 2 if we do not.

---

I did not consider cryptanalytic attacks like linear or differential cryptanalysis, because I've not found that they are applicable to 3DES, even with 2 keys; but that's far from a proof that they are not!

---

Official status

NIST has deprecated use of DES including all keying variants of 3DES/TDEA. It still mentions that 2TDEA used to offer 80-bit security. The superseded SP 800-57 Part 1 Rev. 4 gave more details:

Determining the security strength of an algorithm can be nontrivial. (..) For 2TDEA, if exhaustion were the best attack, then the strength of 2TDEA would be 56 × 2 = 112 bits. This appears to be the case if the attacker has only a few matched plain and cipher pairs. However, the security strength of 2TDEA decreases as the number of matched plaintext/ciphertext pairs increases. If the attacker can obtain approximately $2^{40}$ such pairs and has sufficient memory and computational power, then 2TDEA can provide an estimated maximum security strength of about 80 bits; if the attacker has $2^{56}$ plaintext/ciphertext pairs, with significantly more memory and computational power, then the estimated maximum security strength would be about 56 bits.

An official French regulation (Référentiel Général de Sécurité version 2.0, annexe B1) explicitly recommends against 2-key TDES for use envisioned after 2020, with mention of insufficient block size and vulnerability to known-plaintext attack of complexity $2^{80}$ (resp. $2^{100}\,$) for $2^{40}$ (resp. $2^{20}\,$) plaintext/ciphertext pairs. Their $2^{80}$ something is roughly in line with Mitchell's conclusions.

NIST's measure of complexity appears to be DES encryptions, and I guess the same for the French source. Neither gives a reference to the attacks considered.

---

¹ as opposed to key extraction from physical devices holding keys, thru the like of exploitation of implementation errors, fault injection, micro-probing, DPA, DFA…; and attacks on the mode of operation that do not target key recovery, perhaps by exploiting the 64-bit block size.

---

² That "embarrassingly parallel" attack can go:

• obtain two distinct plaintext/ciphertext pairs $P_0/C_0$ and $P_1/C_1$
• for each of $2^{56}$ keys $K_1$
  • compute $A=E(K_1,P_0)$ and $B=D(K_1,C_0)$
  • for each of $2^{56}$ keys $K_2$
    • if $E(K_2,B)=A$ (occurs for one computation out of $\approx2^{64}$ )
      • if $E(K_2,D(K_1,C_1))=E(K_1,P_1)$, output $(K_1,K_2)$

The first output (if any) is most likely the key, with a probability of the contrary $\approx2^{-16}$ on plausible heuristic grounds.

Answer 2

If K1 = K3 and K1 and K2 are independent, your key length is 112 bits ($2*56$), but due to meet-in-the-middle attack, you have only 80 bits of security.

Note: don't use 3DES and any other 64-bit block ciphers

Answer 3

When two of the three keys with 3DES are the same, you are using a 2*56-bit keyspace that would need to be brute forced. So, when K1=K3, the brute force difficulty will be 2^112. As @hypatia points out though, a meet-in-the-middle attack exists though so you could run an attack in 2^80 time, which is faster than brute force.

Wikipedia has some more details as well as a few scholarly references you can use to learn more.