2Des is double secure of DES?

Question

I read this question in my book (that doesn't have a response).

2DES is doubly more secure than DES?

I know that 2DES can be attacked from meet in the middle attack.

In fact, from Wikipedia Meet in the middle say :

The MITM attack is one of the reasons why Data Encryption Standard (DES) was replaced with Triple DES and not Double DES. An attacker can use a MITM attack to bruteforce Double DES with 2^57 operations and 2^56 space, making it only a small improvement over DES.[5] Triple DES uses a "triple length" (168-bit) key and is also vulnerable to a meet-in-the-middle attack in 2^56 space and 2^112 operations, but is considered secure due to the size of its keyspace.[1][2]

But DES use key from 2^56. 2DES with meet in the middle have 2^57 operation (that is exactly a double of 2^56) I'm not sure if the question ask a "doubly secure " in order to key space , so want a key big as 2^112 (that is double of 56 in previous DES).

I think that DES is double secure from this other phrase on Wikipedia that says:

Diffie and Hellman first proposed the meet-in-the-middle attack on a hypothetical expansion of a block cipher in 1977.[3] Their attack used a space-time tradeoff to break the double-encryption scheme in only twice the time needed to break the single-encryption scheme.

So if 2 times Diffie/Hellman uses twice time to break the algorithm, also for 2DES we can use a double time of DES to break this algorithm.

Anyone can confirm my hypothesis?

Answer 1

The Meet-in-the-Middle attack was (first?) exposed publicly in the context of DES by Whitfield Diffie and Martin E. Hellman, in Exhaustive Cryptanalysis of the NBS Data Encryption Standard (published in IEEE Computer magazine, 1977). In this attack, if we count only the time spent doing DES computations (thus discount the time and cost of memory and memory accesses), then we can find the 112-bit key of 2DES from a few known plaintext/ciphertext pairs using only a little more than twice the time it takes to find the key in DES. The factor is actually closer to 17/8 for worst-case time; and closer to 3 for average time.

That's a strong indication that 2DES is over twice as safe against key search as DES is, given a few plaintext/ciphertext pairs. That's (slightly over, but most importantly only) 1 useful extra key bit out of 56 (or over 55 under CPA due to the complementation property), when examination of the key space would (wrongly) conclude 56 extra key bits.

But the question can be understood as asking to confirm that 2DES can be broken with about twice the time it takes for DES. That's a broader statement, and very wrong in practice. Fact is, cost of memory and cost and time of memory accesses make a straight MitM attack impractical.

There are practical alternatives to straight MitM, but the increase in time is much larger than a factor 2. As far as I know, the best reference on that is section 5.3 in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Application (1996), published in Journal of Cryptology, 1999. They state that 2DES offers "only 17 more bits of security" than DES does (that would still be over a hundred thousand times more).

Additionally: key search is far from being the only cryptanalytic attack. Sometime the 64-bit block size is the weak spot, and 2DES is just as weak as DES from that standpoint (see Sweet32 attack pointed by Lery in comment). Also, a DES key can sometime be found other than by key search, e.g. by compromise of a device holding the key (in which case the duration of the attack is often essentially independent of the number of chained DES), or Differential Power Analysys (in which case 2DES or 3DES often are only marginally more secure that DES).