How to protect DES against exhaustive key search (an analysis of DESX)

The block cipher DESX is defined by DESXk.k1.k2(x) = k2 circle plus DESk (k1 circle plus x), where circle plus denotes bitwise exclusive-or. This construction was first suggested by Rivest as a computationally cheap way to protect DES against exhaustive key-search attacks. This paper proves, in a formal model, that the DESX construction is sound. We show that, when F is an idealized block cipher, FXk.k1.k2(x) = k2 circle plus F-k(k1 circle plus x) is substantially more resistant to key search than is F. In fact, our analysis says that FX has an effective key length of at least kappa + n - 1 - 1gm bits, where kappa is the key length of F, n is the block length, and m bounds the number of pairs the adversary can obtain.