How to protect DES against exhaustive key search

J. Kilian, P. Rogaway

The block cipher DESX is defined by DESX/sub k.k1.k2/(x)=k2(+)DES/sub
k/(k1(+)x), where (+) 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, FX/sub k.k1.k2/(x)=k2(+)F/sub k/(k1(+)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 k+n-1-1gm
bits, where k is the key length of F, n is the block length, and m bounds
the number of <x, FX/sub K/(x)> pairs the adversary can obtain.