3DES 112

[Przemyslaw Frasunek]

Z FAQ FreeS/WAN'a:

[...]
Double DES is ineffective. Using two 56-bit keys, one might expect an 
attacker to have to do 2^112 work to break it. In fact, only 2^57 work is 
required with a meet-in-the-middle attack, though a large amount of memory 
is also required
[...]
     A divide-and-conquer attack which breaks a cipher into two parts, 
works against each separately, and compares results. Probably the best 
known example is an attack on double DES. This applies in principle to any 
pair of block ciphers, e.g. to an encryption system using, say, CAST-128 
and Blowfish, but we will describe it for double DES.

     Double DES encryption and decryption can be written:

	C = E(k2,E(k1,P))
	P = D(k1,D(k2,C))

     Where C is ciphertext, P is plaintext, E is encryption, D is 
decryption, k1 is one key, and k2 is the other key. If we know a P, C pair, 
we can try and find the keys with a brute force attack, trying all possible 
k1, k2 pairs. Since each key is 56 bits, there are 2^112 such pairs and 
this attack is painfully inefficient.

     The meet-in-the middle attack re-writes the equations to calculate a 
middle value M:

	M = E(k1,P)
	M = D(k2,C)

     Now we can try some large number of D(k2,C) decryptions with various 
values of k2 and store the results in a table. Then start doing E(k1,P) 
encryptions, checking each result to see if it is in the table.

     With enough table space, this breaks double DES with 2^57 work. The 
memory requirements of such attacks can be prohibitive, but there is a 
whole body of research literature on methods of reducing them.

-- 
* Fido: 2:480/124 ** WWW: http://www.frasunek.com/ ** NIC-HDL: PMF9-RIPE *
* Inet: przemyslaw at frasunek.com ** keyId: 2578FCAD | C0613BE3 | EC78FAB5 *