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.