Differential cryptanalysis
Encyclopedia
Differential cryptanalysis is a general form of cryptanalysis
applicable primarily to block cipher
s, but also to stream cipher
s and cryptographic hash function
s. In the broadest sense, it is the study of how differences in an input
can affect the resultant difference at the output
. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformations, discovering where the cipher
exhibits non-random
behaviour, and exploiting such properties to recover the secret key
.
and Adi Shamir
in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in the Data Encryption Standard
(DES). It was noted by Biham and Shamir that DES is surprisingly resistant to differential cryptanalysis, in the sense that even small modifications to the algorithm would make it much more susceptible.
In 1994, a member of the original IBM DES team, Don Coppersmith
, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal.
According to author Steven Levy
, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.
IBM kept some secrets, as Coppersmith explains: "After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique of differential cryptanalysis, a powerful technique that could be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography."
Within IBM, differential cryptanalysis was known as the "T-attack" or "Tickle attack".
While DES was designed with resistance to differential cryptanalysis in mind, other contemporary ciphers proved to be vulnerable. An early target for the attack was the FEAL
block cipher. The original proposed version with four rounds (FEAL-4) can be broken using only eight chosen plaintexts
, and even a 31-round version of FEAL is susceptible to the attack.
for some set of plaintext
s of his choosing. The scheme can successfully cryptanalyze DES with an effort on the order 247 chosen plaintexts. There are, however, extensions that would allow a known plaintext or even a ciphertext-only attack
. The basic method uses pairs of plaintext related by a constant difference; difference
can be defined in several ways, but the eXclusive OR (XOR) operation is usual. The attacker then computes the differences of the corresponding ciphertexts, hoping to detect statistical patterns in their distribution. The resulting pair of differences is called a differential. Their statistical properties depend upon the nature of the S-boxes used for encryption, so the attacker analyses differentials (ΔX, ΔY), where ΔY = S(X ⊕ ΔX) ⊕ S(X) (and ⊕ denotes exclusive or) for each such S-box S. In the basic attack, one particular ciphertext difference is expected to be especially frequent; in this way, the cipher
can be distinguished from random
. More sophisticated variations allow the key to be recovered faster than exhaustive search
.
In the most basic form of key recovery through differential cryptanalysis, an attacker requests the ciphertexts for a large number of plaintext pairs, then assumes that the differential holds for at least r-1 rounds, where r is the total number of rounds. The attacker then deduces which round keys (for the final round) are possible assuming the difference between the blocks before the final round is fixed. When round keys are short, this can be achieved by simply exhaustively decrypting the ciphertext pairs one round with each possible round key. When one round key has been deemed a potential round key considerably more often than any other key, it is assumed to be the correct round key.
For any particular cipher, the input difference must be carefully selected if the attack is to be successful. An analysis of the algorithm's internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a differential characteristic.
Since differential cryptanalysis became public knowledge, it has become a basic concern of cipher designers. New designs are expected to be accompanied by evidence that the algorithm is resistant to this attack, and many, including the Advanced Encryption Standard
, have been proven
secure against the attack.
For example, if a differential of 1 => 1 (implying a difference in the LSB of the input leads to a output difference in the LSB) occurs with probability of 4/256 (possible with the non-linear function in the AES cipher for instance) then for only 4 values (or 2 pairs) of inputs is that differential possible. Suppose we have a non-linear function where the key is XOR'ed before evaluation and the values that allow the differential are {2,3} and {4,5}. If the attacker sends in the values of {6, 7} and observes the correct output difference it means the key is either 6 xor K = 2 or 6 xor K = 4, meaning the key is either K = {2,4}.
In essence, for an n-bit non-linear function one would ideally seek as close to 2-(n-1) as possible to achieve differential uniformity. When this happens, the differential attack requires as much work to determine the key as simply brute forcing the key.
The AES non-linear function has a maximum differential probability of 4/256 (most entries however are either 0 or 2). Meaning that in theory one could determine the key with half as much work as brute force, however, the high branch of AES prevents any high probability trails from existing over multiple rounds. In fact, the AES cipher would be just as immune to differential and linear attacks with a much weaker non-linear function. The incredibly high branch (active sbox count) of 25 over 4R means that over 8 rounds no attack involves fewer than 50 non-linear transforms, meaning that the probability of success does not exceed Pr[attack] <= Pr[best attack on sbox]50. For example, with the current sbox AES emits no fixed differential with a probability higher than (4/256)50 or 2−300 which is far lower than the required threshold of 2−128 for a 128-bit block cipher. This would have allowed room for a more efficient sbox, even if it is 16-uniform the probability of attack would have still been 2−200.
There exists no bijections for even sized inputs/outputs with a 2-uniformity. They exist in odd fields (such as GF(27)) using either cubing or inversion (there are other exponents that can be used as well). For instance S(x) = x3 in any odd binary field is immune to differential and linear cryptanalysis. This is in part why the MISTY designs use 7- and 9-bit functions in the 16-bit non-linear function. What these functions gain in immunity to differential and linear attacks they lose to algebraic attacks. That is, they are possible to describe and solve via a SAT solver. This is in part why AES (for instance) has an affine mapping after the inversion.
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...
applicable primarily to 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...
s, but also to stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
s and cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s. In the broadest sense, it is the study of how differences in an input
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...
can affect the resultant difference at the output
Output
Output is the term denoting either an exit or changes which exit a system and which activate/modify a process. It is an abstract concept, used in the modeling, system design and system exploitation.-In control theory:...
. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformations, discovering where the cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
exhibits non-random
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
behaviour, and exploiting such properties to recover the secret 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...
.
History
The discovery of differential cryptanalysis is generally attributed to Eli BihamEli 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 Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in 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). It was noted by Biham and Shamir that DES is surprisingly resistant to differential cryptanalysis, in the sense that even small modifications to the algorithm would make it much more susceptible.
In 1994, a member of the original IBM DES team, Don Coppersmith
Don Coppersmith
Don Coppersmith is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-boxes, strengthening them against differential cryptanalysis...
, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal.
According to author Steven Levy
Steven Levy
Steven Levy is an American journalist who has written several books on computers, technology, cryptography, the Internet, cybersecurity, and privacy.-Career:...
, IBM had discovered differential cryptanalysis on its own, and the NSA was apparently well aware of the technique.
IBM kept some secrets, as Coppersmith explains: "After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique of differential cryptanalysis, a powerful technique that could be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography."
Within IBM, differential cryptanalysis was known as the "T-attack" or "Tickle attack".
While DES was designed with resistance to differential cryptanalysis in mind, other contemporary ciphers proved to be vulnerable. An early target for the attack was the FEAL
FEAL
In cryptography, FEAL is a block cipher proposed as an alternative to the Data Encryption Standard , and designed to be much faster in software. The Feistel based algorithm was first published in 1987 by Akihiro Shimizu and Shoji Miyaguchi from NTT...
block cipher. The original proposed version with four rounds (FEAL-4) can be broken using only eight chosen plaintexts
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...
, and even a 31-round version of FEAL is susceptible to the attack.
Attack mechanics
Differential cryptanalysis is usually a chosen plaintext attack, meaning that the attacker must be able to obtain encrypted ciphertextsEncryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
for some set of 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....
s of his choosing. The scheme can successfully cryptanalyze DES with an effort on the order 247 chosen plaintexts. There are, however, extensions that would allow a known plaintext or even a ciphertext-only attack
Ciphertext-only attack
In cryptography, a ciphertext-only attack or known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts....
. The basic method uses pairs of plaintext related by a constant difference; difference
Subtraction
In arithmetic, subtraction is one of the four basic binary operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...
can be defined in several ways, but the eXclusive OR (XOR) operation is usual. The attacker then computes the differences of the corresponding ciphertexts, hoping to detect statistical patterns in their distribution. The resulting pair of differences is called a differential. Their statistical properties depend upon the nature of the S-boxes used for encryption, so the attacker analyses differentials (ΔX, ΔY), where ΔY = S(X ⊕ ΔX) ⊕ S(X) (and ⊕ denotes exclusive or) for each such S-box S. In the basic attack, one particular ciphertext difference is expected to be especially frequent; in this way, the cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
can be distinguished from random
Randomness
Randomness has somewhat differing meanings as used in various fields. It also has common meanings which are connected to the notion of predictability of events....
. More sophisticated variations allow the key to be recovered faster than exhaustive search
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...
.
In the most basic form of key recovery through differential cryptanalysis, an attacker requests the ciphertexts for a large number of plaintext pairs, then assumes that the differential holds for at least r-1 rounds, where r is the total number of rounds. The attacker then deduces which round keys (for the final round) are possible assuming the difference between the blocks before the final round is fixed. When round keys are short, this can be achieved by simply exhaustively decrypting the ciphertext pairs one round with each possible round key. When one round key has been deemed a potential round key considerably more often than any other key, it is assumed to be the correct round key.
For any particular cipher, the input difference must be carefully selected if the attack is to be successful. An analysis of the algorithm's internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a differential characteristic.
Since differential cryptanalysis became public knowledge, it has become a basic concern of cipher designers. New designs are expected to be accompanied by evidence that the algorithm is resistant to this attack, and many, including the Advanced Encryption Standard
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
, have been proven
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
secure against the attack.
Attack in Details
The attack relies primarily on the fact that a given input/output difference pattern only occurs for certain values of inputs. Usually the attack is applied in essence to the non-linear components as if they were a solid component (usually they are in fact look-up tables or sboxes). Observing the desired output difference (between two chosen or known plaintext inputs) suggests possible key values.For example, if a differential of 1 => 1 (implying a difference in the LSB of the input leads to a output difference in the LSB) occurs with probability of 4/256 (possible with the non-linear function in the AES cipher for instance) then for only 4 values (or 2 pairs) of inputs is that differential possible. Suppose we have a non-linear function where the key is XOR'ed before evaluation and the values that allow the differential are {2,3} and {4,5}. If the attacker sends in the values of {6, 7} and observes the correct output difference it means the key is either 6 xor K = 2 or 6 xor K = 4, meaning the key is either K = {2,4}.
In essence, for an n-bit non-linear function one would ideally seek as close to 2-(n-1) as possible to achieve differential uniformity. When this happens, the differential attack requires as much work to determine the key as simply brute forcing the key.
The AES non-linear function has a maximum differential probability of 4/256 (most entries however are either 0 or 2). Meaning that in theory one could determine the key with half as much work as brute force, however, the high branch of AES prevents any high probability trails from existing over multiple rounds. In fact, the AES cipher would be just as immune to differential and linear attacks with a much weaker non-linear function. The incredibly high branch (active sbox count) of 25 over 4R means that over 8 rounds no attack involves fewer than 50 non-linear transforms, meaning that the probability of success does not exceed Pr[attack] <= Pr[best attack on sbox]50. For example, with the current sbox AES emits no fixed differential with a probability higher than (4/256)50 or 2−300 which is far lower than the required threshold of 2−128 for a 128-bit block cipher. This would have allowed room for a more efficient sbox, even if it is 16-uniform the probability of attack would have still been 2−200.
There exists no bijections for even sized inputs/outputs with a 2-uniformity. They exist in odd fields (such as GF(27)) using either cubing or inversion (there are other exponents that can be used as well). For instance S(x) = x3 in any odd binary field is immune to differential and linear cryptanalysis. This is in part why the MISTY designs use 7- and 9-bit functions in the 16-bit non-linear function. What these functions gain in immunity to differential and linear attacks they lose to algebraic attacks. That is, they are possible to describe and solve via a SAT solver. This is in part why AES (for instance) has an affine mapping after the inversion.
Specialized types
- Higher-order differential cryptanalysis
- Truncated differential cryptanalysisTruncated differential cryptanalysisIn cryptography, truncated differential cryptanalysis is a generalization of differential cryptanalysis, an attack against block ciphers. Lars Knudsen developed the technique in 1994. Whereas ordinary differential cryptanalysis analyzes the full difference between two texts, the truncated variant...
- Impossible differential cryptanalysisImpossible differential cryptanalysisIn cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits...
- Boomerang attackBoomerang attackIn cryptography, the boomerang attack is a method for the cryptanalysis of block ciphers based on differential cryptanalysis. The attack was published in 1999 by David Wagner, who used it to break the COCONUT98 cipher....