## How to protect DES against exhaustive key search

** Authors:** Joe Kilian and Phillip Rogaway

** Reference:**
* J. of Cryptology*, vol. 14, no. 1, pp. 17-35, 2001.
(Earlier version in
*Advances in Cryptology - CRYPTO '96*,
Lecture Notes in Computer Science, Vol. 1109, N. Koblitz, ed., Springer-Verlag, 1996,
pp. 252-267.)

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

Full version available in
PDF or
PostScript.

*Cryptobytes* summary available as
PDF or
PostScript

Rogaway's home page.