DES-X
Encyclopedia
In cryptography
, DES-X (or DESX) is a variant on the DES
(Data Encryption Standard) block cipher
intended to increase the complexity of a brute force attack
using a technique called key whitening
.
The original DES algorithm was specified in 1976 with a 56-bit key size
: 256 possibilities for the key
. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States' National Security Agency
(NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by Ron Rivest
in May 1984.
The algorithm has been included in RSA Security
's BSAFE cryptographic library since the late 1980s.
DES-X augments DES by XORing an extra 64 bits of key (K1) to the plaintext
before applying DES, and then XORing another 64 bits of key (K2) after the encryption:
The key size is thereby increased to 56 + 2 × 64 = 184 bits.
However, the effective key size (security) is only increased to 56+64-1-lb(M) = 119 - lb(M) = ~119 bits, where M is the number of chosen plaintext/ciphertext pairs
the adversary can obtain, and lb denotes the binary logarithm
. Moreover key size drops to 88 bits given 232.5 known plaintext and using advanced slide attack. (Because of this, some implementations actually make K2 a strong one way function of K1 and K.)
DES-X also increases the strength of DES against differential cryptanalysis
and linear cryptanalysis
, although the improvement is much smaller than in the case of brute force attacks. It is estimated that differential cryptanalysis would require 261 chosen plaintexts (vs. 247 for DES), while linear cryptanalysis would require 260 known plaintexts (vs. 243 for DES.) Note that with 264 plaintexts (known or chosen being the same in this case), DES (or indeed any other block cipher
with a 64 bit block size
) is totally broken via the elementary codebook attack.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, DES-X (or DESX) is a variant on the DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
(Data Encryption Standard) block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
intended to increase the complexity of a brute force attack
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
using a technique called key whitening
Key whitening
In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key before the first round and after the last round of encryption.The first block cipher to use a form of key whitening is...
.
The original DES algorithm was specified in 1976 with a 56-bit key size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
: 256 possibilities for the key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
. There was criticism that an exhaustive search might be within the capabilities of large governments, particularly the United States' National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
(NSA). One scheme to increase the key size of DES without substantially altering the algorithm was DES-X, proposed by Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
in May 1984.
The algorithm has been included in RSA Security
RSA Security
RSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
's BSAFE cryptographic library since the late 1980s.
DES-X augments DES by XORing an extra 64 bits of key (K1) to the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
before applying DES, and then XORing another 64 bits of key (K2) after the encryption:
The key size is thereby increased to 56 + 2 × 64 = 184 bits.
However, the effective key size (security) is only increased to 56+64-1-lb(M) = 119 - lb(M) = ~119 bits, where M is the number of chosen plaintext/ciphertext pairs
Chosen-plaintext attack
A chosen-plaintext attack is an attack model for cryptanalysis which presumes that the attacker has the capability to choose arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts. The goal of the attack is to gain some further information which reduces the security of the...
the adversary can obtain, and lb denotes the binary logarithm
Binary logarithm
In mathematics, the binary logarithm is the logarithm to the base 2. It is the inverse function of n ↦ 2n. The binary logarithm of n is the power to which the number 2 must be raised to obtain the value n. This makes the binary logarithm useful for anything involving powers of 2,...
. Moreover key size drops to 88 bits given 232.5 known plaintext and using advanced slide attack. (Because of this, some implementations actually make K2 a strong one way function of K1 and K.)
DES-X also increases the strength of DES against differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
and linear cryptanalysis
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
, although the improvement is much smaller than in the case of brute force attacks. It is estimated that differential cryptanalysis would require 261 chosen plaintexts (vs. 247 for DES), while linear cryptanalysis would require 260 known plaintexts (vs. 243 for DES.) Note that with 264 plaintexts (known or chosen being the same in this case), DES (or indeed any other block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
with a 64 bit block size
Block size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...
) is totally broken via the elementary codebook attack.