In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, is a dedicated statistical cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

 method for attacking the Data Encryption Standard

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...

 (DES). The attack was originally created in 1987 by Donald Davies

Donald Davies

Donald Watts Davies, CBE FRS was a Welsh computer scientist who was one of the inventors of packet switching computer networking, and originator of the term.-Career history:...

. In 1994, Eli Biham

Eli Biham

Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...

 and Alex Biryukov

Alex Biryukov

Alex Biryukov is a cryptographer, currently an assistant professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together...

 made significant improvements to the technique. It is a known-plaintext attack

Known-plaintext attack

The known-plaintext attack is an attack model for cryptanalysis where the attacker has samples of both the plaintext , and its encrypted version . These can be used to reveal further secret information such as secret keys and code books...

 based on the non-uniform distribution

Probability distribution

In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

 of the outputs of pairs of adjacent S-boxes

Substitution box

In cryptography, an S-Box is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext — Shannon's property of confusion...

. It works by collecting many known plaintext/ciphertext pairs and calculating the empirical distribution

Empirical distribution function

In statistics, the empirical distribution function, or empirical cdf, is the cumulative distribution function associated with the empirical measure of the sample. This cdf is a step function that jumps up by 1/n at each of the n data points. The empirical distribution function estimates the true...

 of certain characteristics. Bits of 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...

 can be deduced given sufficiently many known plaintexts, leaving the remaining bits to be found through brute force

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...

. There are tradeoffs between the number of required plaintexts, the number of key bits found, and the probability of success; the attack can find 24 bits of the key with 2⁵² known plaintexts and 53% success rate.

Davies' attack can be adapted to other Feistel cipher

Feistel cipher

In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel who did pioneering research while working for IBM ; it is also commonly known as a Feistel network. A large proportion of block...

s besides DES. In 1998, Pornin developed techniques for analyzing and maximizing a cipher's resistance to this kind of cryptanalysis.