1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ We could confirm an hypothesis if you wrote it precisely. What are your assumptions about what accounts for time? At least, exactly what attack is considered, how much RAM is used, what is counted/discounted, and when does timing stop? Independently: beware that in crypto "Diffie/Hellman" is often understood as the first asymmetric key exchange protocol, but in the quote it is the two inventors of that, working on a quite different subject. $\endgroup$
    – fgrieu
    Jan 14, 2020 at 20:24
  • $\begingroup$ The real problem that this question is this. I cant do more precisely. For me, this question is incomplete, and not really in detail. Generally, for you... u should define 2DES doubly secure of DES? @fgrieu $\endgroup$
    – theantomc
    Jan 15, 2020 at 10:43
  • $\begingroup$ Obviously I mean with the same attack, time considerations and other factors such as RAM or CPU .... Could it be considered doubly safe? @fgrieu $\endgroup$
    – theantomc
    Jan 15, 2020 at 11:00

1 Answer 1

2
$\begingroup$

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).

$\endgroup$
3
  • 1
    $\begingroup$ You might also want to mention the sweet32.info attack that led to the removal of 3DES from the DEFAULT cipher list in OpenSSL because of its blocksize, as 2DES is also affected by the problem. $\endgroup$
    – Lery
    Jan 15, 2020 at 11:52
  • $\begingroup$ Thank for the reply I got your point. The question is part of true false question. For this I dont apply more for dimostration or other. I Just calcolate the keyspace in base a of MitM . $\endgroup$
    – theantomc
    Jan 15, 2020 at 12:22
  • $\begingroup$ very nice answer, this comment is for the OPs benefit. Of course "doubly more secure" is ambigious. hopefully it wasn't asking whether the strength (in terms of effective bitlength) is doubled or not, since the answer is then a resounding no. $\endgroup$
    – kodlu
    Jan 16, 2020 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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