How to protect DES against exhaustive key search (an analysis of DESX). (English) Zbl 1068.94531

Summary: The block cipher DESX is defined by \(\text{DESX}_{k.k1.k2}(x)=k2\oplus\text{DES}_k(k1\oplus x)\), where \(\oplus\) 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\oplus F_k(k1\oplus 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-\lg m\) bits, where \(\kappa\) is the key length of \(F\), \(n\) is the block length, and \(m\) bounds the number of \(\langle x,FX_K(x)\rangle\) pairs the adversary can obtain.


94A60 Cryptography
Full Text: DOI