2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ The present question makes no explicit restriction about the attack needing to be feasible with plausibly much RAM. It's still very close to Duration for attacking Two-Key Triple-DES Encryption using all RAM ever built?, which might help. $\endgroup$ – fgrieu Oct 15 at 12:01
  • 1
    $\begingroup$ define what you mean by K1 and K3. look at some of the related questions on 3DES they appear on the right, and ask a properly specified question. $\endgroup$ – kodlu Oct 15 at 12:03
  • 3
    $\begingroup$ @kodlu they likely mean the first and third keys that are used as part of 3DES, i.e. two-key 3DES. $\endgroup$ – samoz Oct 15 at 12:37
  • 1
    $\begingroup$ Beware that besides the security of the algorithm itself there are also restrictions on how it can be used. For instance, the small block size of 3DES is an issue in many schemes & protocols. There might be issues with parity bits, or (in special circumstances) with the fact that weak keys exist for 3DES. 3DES with 3 keys should really not be used anymore, 3DES with two keys is really really stretching the definition of security. Besides that, if you haven't been able to switch to a more modern cipher by now, you probably never will. $\endgroup$ – Maarten Bodewes Oct 15 at 14:30
  • 2
    $\begingroup$ @samoz is right, it is 2Key 3DES, It is a production unit and 3DES is built in Hardware, we make sure that no weak or semi-weak is used. But if I've to put the same question in another way, then, I'm looking , what are weakness of 2Key 3DES , if there are any, and when it can be considered a real threat to use it in field, and I should start phasing out the units from field or replace them with AES. $\endgroup$ – SSA Oct 15 at 15:15
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ If someone has a link to a justification of why NIST assigns 80-bit security to 2-Key Triple DES, it's welcome! Same for an improvement to case 1 where chosen plaintext or/and ciphertext allows an improvement (e.g. using the DES complementation property). $\endgroup$ – fgrieu Oct 17 at 10:42
  • $\begingroup$ Case 2 seems to be more nearer to my case and the 2 which seems van Oorschot-Wiener attack, I've two questions... [1] how birthday paradox can help here. [2] what if an attacker has c ciphertext vs p plaintexts where # c is around 100, and # p and #K2 is 10000 or larger. $\endgroup$ – SSA Oct 17 at 11:23
  • $\begingroup$ @shwetang acharya: The hypothesis in my case 3 is intended to match the van Oorschot-Wiener attack. Mitchell remarks that plaintext pertaining to different keys can be used too. The birthday bound (only an apparent paradox) helps in my case 3, not 1/2. In your comment above, point [2]: is that $m\ge10000$ keys, $c$ ciphertext blocks corresponding to $p$ plaintexts blocks with $c/p\approx100\ll m$? That would make Mitchell the applicable reference. Perhaps, add this info (clarified) to the question. $\endgroup$ – fgrieu Oct 17 at 11:50
  • 1
    $\begingroup$ @fgrieu , I think the 80-bit security is explained in document of [NIST SP 800-57 section 5.6] (nvlpubs.nist.gov/nistpubs/SpecialPublications/…). And this Draft also published in 2019 [NIST SP 800-131A] (csrc.nist.gov/CSRC/media/Publications/sp/800-131a/rev-2/draft/…) $\endgroup$ – SSA Oct 19 at 9:15
  • 1
    $\begingroup$ @Hypatia: agreed; it's already in my answer, case 3 (and 4 by reference), with a link to an even so slightly later version. The technological difficulties of the attack are better described in the earlier van Oorschot and Wiener reference. $\endgroup$ – fgrieu Oct 19 at 16:03
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The answer is short on the hypothesis and reasoning leading to the stated 80-bit security, or even a reference (here's one, in French, stating $2^{40}$ known plaintext/ciphertext as hypothesis, but no further explanation). Independently: it might be worth noting that the don't use 3DES link is about an attack that applies to any 64-bit cipher, irrespective of key size. $\endgroup$ – fgrieu Oct 15 at 14:20
  • 1
    $\begingroup$ The Supercomputer Titan can reach about 2^{77} per year, Bitcoin miner can reach around $2^{93}$ per year. $2^{80}$ is no longer secure for today's standards. One should have at least 128-bit security ( some says above 120-bit ) $\endgroup$ – kelalaka Oct 15 at 14:39
  • $\begingroup$ @kelalaka: I agree that modern designs should target near 128-bit security or better. Still, it remain interesting to examine if currently deployed systems (many using 2-key 3DES) can be realistically attacked. If it is possible to break a system with cost comparable to $2^{90}$ SHA-256, that's a concern. I'm cautiously skeptical that it applies to 2-key 3DES with any amount of plaintext/ciphertext, because of the cost of RAM. The problem is comparable to relative cost of breaking a password protected by iterated SHA-256 vs as many hashes in a memory-hard password-based hash. $\endgroup$ – fgrieu Oct 15 at 16:26
  • $\begingroup$ @fgrieu it is one true side of the story. The others, multi-target attack much easier compared to 128-bit, and the three-word agencies can use built special hardware like the one listed in this answer. As far as I know, years ago there was a firework project of the SUN microsystems that aimed to combine all US national labs' power in one hand if necessary ( that is a little short story. I don't know the status). Maybe we should look at the Copabagana on 3DES with 2 key for key search on modern devices or even consider the ASICs, $\endgroup$ – kelalaka Oct 15 at 16:36
  • 1
    $\begingroup$ @Hypatia: The right ballpark to get below $2^{90}$ DES operations could be $2^{68}$ bit (a hundred exabyte). See this. Post-scriptum: I would not bet the house on that number, but at least it seems to be an awful lot of RAM. $\endgroup$ – fgrieu Oct 15 at 16:55
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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