How to Protect DES Against Exhaustive Key Search
Lecture notes in computer sciencePublished 1 January 1996
Joe Kilian, Phillip Rogaway
Citations184
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proves, in a formal model, that the DESX construction is sound, and shows that, when F is an idealized block cipher, FXk.k2 is substantially more resistant to key search than is F, and has an effective key length of at least ϰ+n - 1 - lg m bits.
Abstract
The block cipher DESX is defined by DESX k.k1.k2(x) = k2 ⊕ DESk(k1 ⊕ x), where ⊕ denotes bitwise exclusive-or. This construction was first suggested by Ron 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 pairs the adversary can obtain.
Keywords
Computer Science
Bell System Technical JournalCommunication Theory of Secrecy Systems*
9,330 Citations1949Claude E. Shannon
A theory of secrecy systems is developed on a theoretical level and is intended to complement the treatment found in standard works on cryptography.
Lecture notes in computer scienceAdvances in Cryptology — CRYPTO ’94
678 Citations1994
The first, successful experiment in breaking the full 16-round DES is reported, based on new linear approximate equations, each of which provides candidates for 13 secret key bits and reliability of the key candidates is taken into consideration, which increases the siicccss r a k .
Journal of CryptologyParallel Collision Search with Cryptanalytic Applications
631 Citations1999Paul C. van Oorschot, Michael J. Wiener
The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions; and double encryption and three-key triple encryption.
ComputerSpecial Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard
557 Citations1977Whitfield Diffie, Martin E. Hellman
A cryptographic file system for UNIX
415 Citations1993Matt Blaze
Encryption techniques for file system-level encryption are described, and general issues of cryptographic system interfaces to support routine secure computing are discussed.
Lecture notes in computer scienceThe First Experimental Cryptanalysis of the Data Encryption Standard
414 Citations1994Mitsuru Matsui
An improved version of linear cryptanalysis is described and its application to the first, successful computer experiment in breaking the full 16-round DES with high success probability if 243 random plaintexts and their ciphertexts are available.
Journal of CryptologyA construction of a cipher from a single pseudorandom permutation
359 Citations1997Shimon Even, Yishay Mansour
A scheme for a block cipher which uses only one randomly chosen permutation, F, which removes the need to store, or generate a multitude of permutations.
Lecture notes in computer scienceHow to Protect DES Against Exhaustive Key Search
184 Citations1996Joe Kilian, Phillip Rogaway
This paper proves, in a formal model, that the DESX construction is sound, and shows that, when F is an idealized block cipher, FXk.k2 is substantially more resistant to key search than is F, and has an effective key length of at least ϰ+n - 1 - lg m bits.
Lecture notes in computer scienceA construction of a cipher from a single pseudorandom permutation
176 Citations1993Shimon Even, Yishay Mansour
In this chapter Shannon defined a random cipher as a collection of randomly chosen permutations, one for each value of the key.
Parallel collision search with application to hash functions and discrete logarithms
148 Citations1994Paul C. van Oorschot, Michael J. Wiener
A simple new method of parallelizing collision searches that greatly extends the reach of practical attacks and ideas from Pollard's rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method.
Efficient DES Key Search
142 Citations1993Michael J. Wiener
Lecture notes in computer scienceLimitations of the Even-Mansour construction
101 Citations1993Joan Daemen
It is shown that this construction of a block cipher from a single pseudorandom permutation suffers from severe limitations that are immediately apparent if differential cryptanalysis is performed, leading the authors to question the relevance of computational complexity theory in practical conventional cryptography.
Lecture notes in computer scienceAdvances in Cryptology — ASIACRYPT '91
81 Citations1993Gerhard Goos, Juris Hartmanis +1 more
Lecture notes in computer scienceHow to strengthen DES using existing hardware
42 Citations1995Eli Biham, Alex Biryukov
This paper describes methods of strengthening DES against exhaustive search, differential attacks, linear attacks and improved Davies' attacks that can be applied on existing DES hardware, and introduces the concept of key-dependent invariant S-box transformations.
Practical cryptography for data internetworks
30 Citations1996William Stallings
This book provides a comprehensive introduction to the use of cryptographic algorithms in data network security, with a special emphasis on practical internetworking applications and the underlying principles and main approaches to cryptography.