double DES (thing)

A method of data encryption, namely the use of DES twice in a row. Be P the plaintext message, k₁ and k₂ two DES keys, then the result of double DES is the ciphertext C = DES(DES(P,k₁),k₂).

As everybody proficient in cryptography knows, DES is not safe due to its fixed keylength of 56 bit, which is nowadays too little to be resilent against brute force attacks. Unfortunately, double DES does not alleviate this problem - it's not much safer than a hypothetical DES with 57 bit keys, which is entirely too little. The reason why it doesn't offer the equivalent of 112 bit encryption that one might naively expect is its vulnerability to a so-called meet-in-the-middle attack.

It works like this:

1. For every possible DES key k_i, compute M_i = DES(C,k_i) and store the tuple (M_i, k_i).
2. Loop again through all possible DES keys k_j and compute N_j = DES^-1(C,k_j). Check whether N_j is the same as one of your stored M_i. If you find a match, it's pretty likely likely that you've just found the two keys you're looking after!

Since the comparison in step two can be done in more or less constant time using hashing, you basically only have to go through all possible DES keys twice, resulting in the effective key lenght of 57 bit.

Of course, step one requires a godawful amount of storage, but if you just store a hash of M_i and recompute the full ciphertext for the (still very few) matches, it shrinks to something that might be feasible in the not-so-far future: roughly one Exabyte for a hash size of 64 bit, which should be sufficient to avoid false matches in nearly all cases.

This is the reason why people use triple DES instead, which provides an effective key lenght of about 108 bit (not the 3*56 bit you might expect for the same reason described above).