Why two key DES algorithm provides only 80 bits security

In the wiki link, it is mentioned that due to "chosen-plaintext" or "known-cipher" attacks, two key DES provides only 80 bits of security.

My question is how these attacks work and how did NSIT came up with 2<80> bits of security

• Commented Sep 10, 2013 at 17:37

To understand what happens with Double-DES, consider the meet-in-the-middle attack (completely unrelated to "man-in-the-middle attacks").

Setup: there is double-DES, where a data block is encrypted with key K1, then again with K2. The attacker could have access to two plaintext/ciphertext blocks: attacker knows A, B, C = EK2(EK1(A)) and D = EK2(EK1(B)).

Then the attacker can compute all EK(A) for all values of K (there are 256 of them). Then he can also compute all DK'(C) for all values of K' (again, 256 keys to try). At that point, he will have about 248 candidates for the (K1,K2) pair: these are all the pairs (K,K') for which EK(A) = DK'(C). The "248" comes from the fact that we are encrypting 64-bit blocks, so about 1 block value every 256 is one of the EK(A) values, so about 1 value K' every 256 will yield a matching DK'(C).

The 248 candidates can then be tried with the plaintext B and ciphertext D; it is expected that only the right one will pass that test.

Cost: 257 invocations of DES (plus an extra average of 248 for the verification of candidates, but that's negligible), and some memory storage able to hold 256 intermediate values, and sorted. Since the values are sorted, each will differ from the previous by only 8 bits on average, but it must also store the corresponding K, so let's say that a practical implementation would use 10 bytes per value. That's then 10*256 bytes of storage, which is rather large (about 650 thousands of terabytes) but can be envisioned with existing technology (it would not be cheap, though). The sorting step would be the biggest cost in an "academic" way (about 264 comparisons) but the 257 DES invocations would still be, in practice, more expensive.

I don't see any "80 bits" here. In fact, security of Double-DES should be considered to be close to "57 bits". The storage requirements make it harder to break than a simple "57-bit block cipher", but nowhere near as hard as an 80-bit block cipher.

(A similar method works for 3DES, which means that 3DES has security "about 112 bits" despite its 168 bits of key.)

The thing with 80 bits security doesn't apply to Double-DES but to one option of 3DES.

If you use 3DES with three different keys you end up with 112 (and not 168!) bit security because of the meet-in-the-middle attack Thomas Pornin mentioned in his answer.

If you use 3DES with k_1 = k_3 and put some assumptions in then you end up with 80 bits.

Wikipedia refers to this pdf by NIST for: http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf