Differential cryptanalysis

Differential cryptanalysis aims to break round-based block ciphers and cryptological hash functions . To this end, she examines the effects of differences in plain text blocks on the differences in the ciphertext blocks generated by encryption.

introduction

The method of differential cryptanalysis was published in 1991 by cryptologists Eli Biham and Adi Shamir . This is a statistical attack on any Feistel ciphers . The attack is carried out as a chosen plaintext attack . This means that it is assumed that the attacker has access to any, self-selected plaintext-ciphertext pairs. The aim of the attack is to determine the secret key of the cipher (or parts of it). The attacker examines what effect certain differences in plaintext pairs have on the differences in the resulting ciphertext pairs. These differences can be used to calculate the probabilities of possible keys and to determine the most likely key. The key can then be used by the attacker to decrypt other ciphertexts of the victim.

Relation to DES

Biham and Shamir developed differential cryptanalysis to analyze the security of the DES encryption standard, which has been widely used since 1976 . They found that DES is very resistant to this process due to the construction of the non-linear substitution boxes. Don Coppersmith , one of the DES developers at IBM , stated in 1994 that security against this attack was one of the development goals. As a result, the developers knew about the attack as early as 1974. After a discussion with the NSA , they decided not to publish either the attack itself or the security against it. Knowing about the attack explains why DES has exactly 16 rounds: The complexity of a naive attack using the brute force method lies in operations, since the effective length of the key is 56 bits. If DES only had 15 rounds, then the complexity of an attack with differential cryptanalysis with operations would be less. However, at 16 rounds, the attack is slightly more complex with operations than with the brute force method. ${\displaystyle 2^{56}}$ ${\displaystyle 2^{52}}$ ${\displaystyle 2^{58}}$

principle

The core of the process is the analysis of the effect of differences in plaintext pairs on the differences in the resulting ciphertext pairs.

Differences

The differences are formed bit by bit using an XOR link. Be and two plaintexts, so is their difference . This difference can be observed through the individual encryption steps. Steps that only contain XOR operations do not change the difference. Even permutations and expansions , such as those found in most Feistelchiffren can be easily calculated by the bits of the differences are reversed in the way or duplicated as provide the permutations and expansions. It is only not possible to calculate the differences across the non-linear substitution boxes. ${\displaystyle P}$ ${\displaystyle P^{\ast }}$ ${\displaystyle P^{\prime }=P\oplus P^{\ast }}$

The behavior of the differences in a substitution box ( S-box to examine more closely), you are different input values and the same input differential in an S-box one, that is . You can then see that the differences in values and are unevenly distributed at the output. This means that if the input difference is constant, some output differences occur more frequently, others less often or not at all. This property of an S-Box is recorded in a difference distribution table: ${\displaystyle SX_{I}}$ ${\displaystyle SX_{I}^{\ast }}$ ${\displaystyle X}$ ${\displaystyle SX_{I}^{\prime }=const}$ ${\displaystyle SX_{O}^{\prime }}$ ${\displaystyle SX_{O}}$ ${\displaystyle SX_{O}^{\ast }}$

	${\displaystyle SX_{O0}^{\prime }}$	${\displaystyle SX_{O1}^{\prime }}$	${\displaystyle SX_{O2}^{\prime }}$	...
${\displaystyle SX_{I0}^{\prime }}$	${\displaystyle x_{0,0}}$	${\displaystyle x_{1,0}}$	${\displaystyle x_{2,0}}$	...
${\displaystyle SX_{I1}^{\prime }}$	${\displaystyle x_{0,1}}$	${\displaystyle x_{1,1}}$	${\displaystyle x_{2,1}}$	...
...	...	...	...

The value indicates how often the output difference occurs in the event of an input difference, if one examines all possible pairs of input values ​​with the S-Box . The input difference then causes the output difference with a probability ${\displaystyle x_{i,j}}$ ${\displaystyle SX_{Ij}^{\prime }}$ ${\displaystyle SX_{Oi}^{\prime }}$ ${\displaystyle X}$ ${\displaystyle SX_{Ij}^{\prime }}$ ${\displaystyle SX_{Oi}^{\prime }}$

${\displaystyle p_{D}={\frac {x_{i,j}}{2^{l}}}}$

through the examined S-Box with a one- bit wide input. ${\displaystyle X}$ ${\displaystyle l}$

Key candidates (one round)

Excerpt from a round function of the Data Encryption Standard : The subdivision of the input value and the round key into 8 blocks of 6 bits each is intended to symbolize the assignment of the bits to the 8 S-boxes.

For a Feistel cipher with only one round, one can exclude certain keys with this knowledge. The remaining keys are the key candidates. The illustration on the right makes the terms used below a little clearer using the DES example.

The attacker has two plain texts encrypted with a self-selected difference. He learns the secret texts or at least their difference. From the knowledge of the plain text, he can calculate the status of the encryption prior to the XOR link ( ) with the round key . From the ciphertext difference, he can calculate the output difference of the S-Box . Using the difference distribution table, the input difference and the output difference show the number of input values ​​of the S-Box that can be considered. The pairs of input values and , with difference , which generate the output difference , must be calculated by the attacker or read from a table. It is assumed that the attacker knows the calculation rule for the S-boxes ( Kerckhoffs' principle ). ${\displaystyle SX_{E}}$ ${\displaystyle \oplus }$ ${\displaystyle K}$ ${\displaystyle SX_{O}^{\prime }}$ ${\displaystyle X}$ ${\displaystyle SX_{I}^{\prime }}$ ${\displaystyle SX_{O}^{\prime }}$ ${\displaystyle SX_{I}}$ ${\displaystyle SX_{I}^{\ast }}$ ${\displaystyle SX_{I}^{\prime }}$ ${\displaystyle SX_{O}^{\prime }}$

The attacker now knows the values ​​of and the possible values ​​of . With this he can calculate candidates for the round key: ${\displaystyle SX_{E}}$ ${\displaystyle SX_{I}}$

${\displaystyle K=SX_{E}\oplus SX_{I}}$

This can be repeated with different plaintext pairs. The correct lap key is always among the key candidates for a run. Keys that are not included in the key candidates of all runs are therefore excluded as round keys.

Characteristics (several rounds)

The amount of input and output differences over rounds with respect to any plaintext pair, as well as the plaintext and ciphertext difference, is called the n-round characteristic . If the swapped halves of the plaintext difference of an n-round characteristic are equal to the ciphertext difference of an m-round characteristic , that is ${\displaystyle n}$ ${\displaystyle \Omega }$ ${\displaystyle \Omega _{1P}=(L_{0}^{\prime },R_{0}^{\prime })}$ ${\displaystyle \Omega _{2T}=(L_{m}^{\prime },R_{m}^{\prime })}$

${\displaystyle L_{m}^{\prime }=R_{0}^{\prime }}$and , ${\displaystyle R_{m}^{\prime }=L_{0}^{\prime }}$

then these can be linked together to form a round characteristic. ${\displaystyle (m+n)}$

Each characteristic can be assigned a probability that a random plaintext pair with the given difference has exactly the differences assumed in the characteristic in the individual rounds. The probability of an n-round characteristic is the product of the probabilities of all 1-round characteristics from which the n-round characteristic is composed. ${\displaystyle \Omega }$ ${\displaystyle p^{\Omega }}$ ${\displaystyle \Omega _{P}}$ ${\displaystyle p^{\Omega }}$ ${\displaystyle p_{i}^{\Omega }}$ ${\displaystyle \Omega }$

${\displaystyle p^{\Omega }=\prod _{i=1}^{n}p_{i}^{\Omega }}$

The probability of a 1-round characteristic is (see above), i.e. the probability that the input difference of this characteristic causes the output difference of this characteristic. ${\displaystyle p_{D}}$

A special case are so-called iterative characteristics , with which can be attached to themselves again and again. The swapped halves of the plaintext difference are therefore equal to the ciphertext difference of the same characteristic. These can therefore easily be related to n-round characteristics of any size. While in the case of non-iterative characteristics the probability decreases faster and faster due to the avalanche effect , the probabilities of the partial characteristics from which iterative characteristics are composed remain the same. Iterative characteristics are therefore preferred for an attack. ${\displaystyle \Omega _{1}=\Omega _{2}}$ ${\displaystyle n}$

A plaintext pair whose plaintext difference and the corresponding input and output differences of the individual rounds match a certain n-round characteristic is called a correct pair . Plain text pairs that do not produce these differences are false pairs . The probability that a plaintext pair with the plaintext difference given by an n-round characteristic is a correct pair is equal to the probability of the n-round characteristic if random independent round keys are used. The generalization that the round keys are independent simplifies the analysis and ensures that the differential cryptanalysis can be applied to different encryption methods. ${\displaystyle p^{\Omega }}$

attack

In order to determine the round key of the rounds, you first need several n-round characteristics (with the highest possible probability ). The attacker then selects a sufficiently large amount of plaintext pairs with differences which correspond to those of the n-round characteristics. It can (in an indefinite way) calculate the associated ciphertext pairs or their differences. This corresponds to the procedure of a chosen plaintext attack . If the attacker already knows enough plaintext pairs with the appropriate differences and the associated ciphertexts, the attack can also be carried out as a known plaintext attack . ${\displaystyle n}$ ${\displaystyle p^{\Omega }}$

If the difference between the ciphertexts also corresponds to the ciphertext difference given by the n-round characteristic, the corresponding plaintext pair is most likely a correct pair . The sets with key candidates belonging to the individual rounds of the characteristic therefore contain the correct round key for the respective round with probability . ${\displaystyle p^{\Omega }}$ ${\displaystyle p^{\Omega }}$

This procedure is repeated with different n-round characteristics. The round keys that occur most frequently among the candidates in a round are, with a correspondingly high probability, the round keys sought. Depending on the calculation method of the round key in the respective encryption algorithm, the secret key (or parts of it) can be calculated from this.

If the encryption process has more than rounds, a small number of remaining rounds can also be bridged by trying all possible round keys for them (brute force method) and checking in each case whether the difference between the value pair obtained in this way corresponds to the ciphertext difference of the n- Lap characteristics match. ${\displaystyle n}$

Example (DES)

The following example is based on the Data Encryption Standard (DES). It should help to understand the basic principles. Numerical values ​​with the suffix h are hexadecimal .

Difference distribution table

The following table shows an excerpt from the difference distribution table for the S-Box : ${\displaystyle S1}$

	0h	1h	2h	3h	4h	5h	6h	7h	8h	9h	Ah	Bra	Ch	Ie	Eh	Fh
0h	64	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1h	0	0	0	6th	0	2	4th	4th	0	10	12	4th	10	6th	2	4th
2h	0	0	0	8th	0	4th	4th	4th	0	6th	8th	6th	12	6th	4th	2
...
34h	0	8th	16	6th	2	0	0	12	6th	0	0	0	0	8th	0	6th
...
3Fh	4th	8th	4th	2	4th	0	2	4th	4th	2	4th	8th	8th	6th	2	2

The first column shows the input differences . The input of an S-Box is 6 bits wide. A total of value pairs are therefore possible. These can have various differences, namely 0h… 3Fh. ${\displaystyle S1_{I}}$ ${\displaystyle 2^{6}\cdot 2^{6}=2^{12}=4096}$ ${\displaystyle 2^{6}=64}$

The title line shows the possible output differences . The output of an S-Box is 4 bits wide. A total of value pairs are therefore possible. These can have different differences, namely 0h… Fh. ${\displaystyle S1_{O}}$ ${\displaystyle 2^{4}\cdot 2^{4}=2^{8}=256}$ ${\displaystyle 2^{4}=16}$

There are 64 combinations of input values ​​that generate an input difference. The line total must therefore always be 64. It is also intuitive that with two identical input values ​​( input difference ) the same output value (output difference ) should occur. As can be seen in cell (0h, 0h) of the table, this applies to all 64 possible value pairs with . So the probability that it causes is 1. ${\displaystyle S1_{I}=0h}$ ${\displaystyle S1_{O}=0h}$ ${\displaystyle S1_{I}=0h}$ ${\displaystyle S1_{I}=0h}$ ${\displaystyle S1_{O}=0h}$

The likelihood of causing that is . ${\displaystyle S1_{I}=34h}$ ${\displaystyle S1_{O}=4h}$ ${\displaystyle {\frac {2}{64}}=0{,}03125}$

Find key candidates

It is assumed that an attacker knows a plaintext pair:

${\displaystyle P=(L_{0},R_{0})}$with and ${\displaystyle R_{0}=A800.0001h}$

${\displaystyle P^{\ast }=(L_{0}^{\ast },R_{0}^{\ast })}$ With ${\displaystyle R_{0}^{\ast }=0800.0000h}$

Then he can apply the expansion to the right half of the two plaintexts (the part that goes into the round function):

${\displaystyle E(A800.0001h)=3510.0000.0003h}$ and

${\displaystyle E(0800.0000h)=0110.0000.0000h}$

So it is

${\displaystyle S1_{E}=35h}$ and

${\displaystyle S1_{E}^{\ast }=1h}$.

Then is the difference of the values ​​before the link with the round key. Since both values ​​are XOR-linked with the same round key , the difference remains unchanged: ${\displaystyle S1_{E}^{\prime }=S1_{E}\oplus S1_{E}^{\ast }=34h}$ ${\displaystyle K}$

${\displaystyle S1_{I}^{\prime }=S1_{I}\oplus S1_{I}^{\ast }=(S1_{E}\oplus K)\oplus (S1_{E}^{\ast }\oplus K)=S1_{E}\oplus S1_{E}^{\ast }=S1_{E}^{\prime }=34h}$

It is also assumed that the attacker knows the initial difference:

${\displaystyle S1_{O}^{\prime }=4h}$

The difference distribution table for the S-Box shows that there are 2 possible assignments of the input values ​​for which and is. ${\displaystyle S1}$ ${\displaystyle S1_{I}^{\prime }=34h}$ ${\displaystyle S1_{O}^{\prime }=4h}$

With knowledge of the S-Box (this is publicly known) it is possible to calculate which 2 assignments for the input values, with the given input difference, generate the given output difference. For this purpose, the attacker can have created a table in advance from which he can read the values. In this case the possible input value pairs are

${\displaystyle (S1_{I},S1_{I}^{\ast })=(13h,27h)}$ or

${\displaystyle (S1_{I},S1_{I}^{\ast })=(27h,13h)}$.

The key candidates arise from . So the correct lap key is either ${\displaystyle K=S1_{I}\oplus S1_{E}}$

${\displaystyle 13h\oplus 35h=26h}$ or

${\displaystyle 27h\oplus 35h=12h}$.

The round key can be found either by trying it out or by repeating it with another plaintext pair.

See also

• Cryptanalysis
• Linear cryptanalysis

Web links

• Detailed paper: Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems . (PDF) In: Journal of Cryptology . 4, No. 1, January 1991, pp. 3-72. doi : 10.1007 / BF00630563 .
• Simplified example (German): internship attempt . (PDF; 965 kB), p. 42 ff.

Individual evidence

1. ^ ^{A b c} Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems . (PDF) In: Journal of Cryptology . 4, No. 1, January 1991, pp. 3-72. doi : 10.1007 / 3-540-38424-3_1 .
2. ^ ^{A b} Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks . (PDF) In: IBM Journal of Research and Development . 38, No. 3, May 1994, p. 243.