Differential and Linear Cryptanalysis

For most of its life, the prime concern with DES has been its vulnerability to brute-force attack because of its relatively short (56 bits) key length. However, there has also been interest in finding cryptanalytic attacks on DES. With the increasing popularity of block ciphers with longer key lengths, including triple DES, brute-force attacks have become increasingly impractical. Thus, there has been increased emphasis on cryptanalytic attacks on DES and other symmetric block ciphers. In this section, we provide a brief overview of the two most powerful and promising approaches: differential cryptanalysis and linear cryptanalysis

Differential Cryptanalysis

One of the most significant advances in cryptanalysis in recent years is differential cryptanalysis. In this section, we discuss the technique and its applicability to DES.The rationale behind differential cryptanalysis is to observe the behavior of pairs of text blocks evolving along each round of the cipher, instead of observing the evolution of a single text block. 

Differential cryptanalysis is the first published attack that is capable of breaking DES in less than $2^{55}$ encryptions. The scheme can successfully cryptanalyze DES with an effort on the order of $2^{47}$ encryptions, requiring $2^{47}$ chosen plaintexts. Although $2^{47}$ is certainly significantly less than $2^{55}$.

Here, we provide a brief overview so that you can get the flavour of the attack.

Differential cryptanalysis is a type of chosen-plaintext attack, where the attacker studies how differences in the input to a cryptographic algorithm affect the differences in the output. The goal is to find patterns that reveal information about the key used in the encryption process.

Steps in Differential Cryptanalysis

• Select input pairs: Choose two inputs with a specific difference.
• Compute the output difference: After encryption, compare the two ciphertexts to analyze the differences.
• Track differences through the rounds: Study how the input difference affects the difference after each round of the cipher.
• Guess the key: Based on the differential characteristics and patterns observed, make educated guesses about the subkeys used in different rounds.

We begin with a change in notation for DES. Consider the original plaintext block $m$ to consist of two halves $m_0, m_1$. Each round of DES maps the right-hand input into the left-hand output and sets the right-hand output to be a function of the left-hand input and the subkey for this round. So, at each round, only one new 32-bit block is created. If we label each new block $m_i (2 ... i ... 17)$, then the intermediate message halves are related as follows:

$$m_{i + 1} = m_{i - 1 } \oplus f(m_i, K_i), i = 1, 2, \ldots,16$$

In differential cryptanalysis, we start with two messages, $m$ and $m'$, with a known XOR difference $\Delta m = m \bigoplus m'$, and consider the difference between the intermediate message halves: $\Delta m_i = m_i \bigoplus m_i'$.Then we have

Now, suppose that many pairs of inputs to $f$ with the same difference yield the same output difference if the same subkey is used. To put this more precisely, let us say that $X$ may cause $Y$ with probability $p$, if for a fraction $p$ of the pairs in which the input XOR is $X$, the output XOR equals $Y$. We want to suppose that there are a number of values of X that have high probability of causing a particular output difference. Therefore, if we know $\Delta m_{i - 1}$ and $m_i$ with high probability, then we know $m_{i + 1}$ with high probability. Furthermore, if a number of such differences are determined, it is feasible to determine the subkey used in the function f.

The overall strategy of differential cryptanalysis is based on these considerations for a single round. The procedure is to begin with two plaintext messages $m$ and $m'$ with a given difference and trace through a probable pattern of differences after each round to yield a probable difference for the ciphertext. Actually, there are two probable patterns of differences for the two 32-bit halves: ($\Delta{m}_{17}|| \Delta{m}_{16})$. Next, we submit $m$ and $m'$ for encryption to determine the actual difference under the unknown key and compare the result to the probable difference. If there is a match,

$$E(K, m)  \oplus  E(K, m') = (\Delta{m}_{17} || \Delta{m}_{16})$$

then we suspect that all the probable patterns at all the intermediate rounds are correct. With that assumption, we can make some deductions about the key bits. This procedure must be repeated many times to determine all the key bits.

Figure 3.8,  illustrates the propagation of differences through three rounds of DES. The probabilities shown on the right refer to the probability that a given set of intermediate differences will appear as a functionof the input differences. Overall, after three rounds, the probability that the output difference is as shown is equal to 0.25 * 1 * 0.25 = 0.0625.

Let’s walk through a simplified example of differential cryptanalysis on a hypothetical, small block cipher to illustrate how it works.

Cipher Setup:

Suppose we have a toy cipher with the following structure:

• Block size: 4 bits (for simplicity).
• Rounds: 2 rounds of encryption.
• S-box: A substitution box used for non-linear transformation, mapping 2 bits to 2 bits.

Let’s assume the S-box for this cipher is as follows:

Input	Output
00	11
01	00
10	01
11	10

The encryption process consists of two rounds:

1. Substitution using the S-box.
2. XOR with the round key.

Step-by-Step Example:

1. Plaintext Pair Selection:

We choose two plaintexts that differ by a known amount, typically a specific bitwise difference (often XOR). Let’s choose the two plaintexts as:

• Plaintext P₁ = 0101
• Plaintext P₂ = 0001

The difference between P₁ and P₂ is 0101 XOR 0001 = 0100. This is the input difference we’ll track through the cipher.

2. First Round:

• For P₁ = 0101, we apply the S-box to each pair of 2 bits.

  • First 2 bits: 01 → 00 (according to the S-box).
  • Last 2 bits: 01 → 00.
  • Result after substitution: 0000.

• For P₂ = 0001, we apply the S-box:

  • First 2 bits: 00 → 11.
  • Last 2 bits: 01 → 00.
  • Result after substitution: 1100.

3. Difference after Substitution:

Now, calculate the difference after this round of substitution.

• S(P₁) XOR S(P₂) = 0000 XOR 1100 = 1100.

This shows that the difference propagates through the S-box and affects certain bits.

4. Key Addition:

Next, we assume both plaintexts are XORed with the same round key (say, K₁ = 1010).

• For P₁, we XOR with K₁: 0000 XOR 1010 = 1010.
• For P₂, we XOR with K₁: 1100 XOR 1010 = 0110.

5. Second Round (Substitution):

Now, both results go through another round of S-box substitution.

• For P₁ = 1010:

  • First 2 bits: 10 → 01.
  • Last 2 bits: 10 → 01.
  • Result after substitution: 0101.

• For P₂ = 0110:

  • First 2 bits: 01 → 00.
  • Last 2 bits: 10 → 01.
  • Result after substitution: 0001.

6. Ciphertext Difference:

Finally, calculate the difference between the two ciphertexts:

• C₁ XOR C₂ = 0101 XOR 0001 = 0100.

So, the output difference between the two ciphertexts is 0100.

7. Conclusion:

Through this process, the differential cryptanalyst:

• Tracks how the differences propagate through the S-box and key addition stages.
• Builds a differential characteristic: in this case, an input difference of 0100 leads to an output difference of 0100with some probability.
• Repeats this process for many different pairs of plaintexts to gather information about how the cipher behaves under certain differences.

Using this knowledge, the cryptanalyst can begin to infer parts of the secret key by observing which pairs of differences are more likely than others and backtrack to the key used in the encryption process.

Why It Works

In a perfectly random cipher, all differences should propagate randomly. However, most practical ciphers, like DES, exhibit small biases in how differences propagate, especially in the S-boxes. These biases can be exploited to reduce the number of possible keys that need to be checked.

Countermeasures

To defend against differential cryptanalysis, modern ciphers are designed with the following in mind:

• Complex S-boxes: Non-linear substitution boxes (S-boxes) are designed to reduce the probability of exploitable differential patterns.
• Increased Key Sizes: Larger keys make brute-force attacks harder, even when partial information is gained through differential cryptanalysis.
• Multiple Rounds: By increasing the number of rounds in the cipher, the chances of successfully tracking the differences through the entire encryption process decrease.

Famous Examples

• DES: Differential cryptanalysis was initially developed to break DES. Although DES was not designed with differential cryptanalysis in mind, it was found to be resistant to this attack due to the number of rounds (16 rounds).
• AES: The Advanced Encryption Standard (AES) is designed with protection against differential cryptanalysis, utilizing robust S-boxes and a high number of rounds.

Linear Crypt Analysis

A more recent development is linear cryptanalysis.This attack is based on finding linear approximations to describe the transformations performed in DES.This method can find a DES key given $2^{43}$ known plaintexts, as compared to $2^{47}$ chosen plaintexts for differential cryptanalysis. Although this is a minor improvement, because it may be easier to acquire known plaintext rather than chosen plaintext, it still leaves linear cryptanalysis infeasible as an attack on DES. So far, little work has been done by other groups to validate the linear cryptanalytic approach.

For a cipher with $n$-bit plaintext and ciphertext blocks and an -$m$ bit key, let the plaintext block be labeled $P[1],\ldots,P[n]$, the cipher text block $C[1],\ldots,C[n]$, and the key $K[1],\ldots,K[m]$.Then define

$$A[i,j,\ldots,k]=A[i] \oplus A[j] \oplus \cdots \oplus A[k] $$

The objective of linear cryptanalysis is to find an effective linear equation of the form:

$$P[\alpha_1, \alpha_2, \ldots , \alpha_a] \oplus  C[\beta_1, \beta_2, \ldots, \beta_b] = K[\gamma_1, \gamma_2, \ldots, \gamma_c]$$

($ 1 \le a;b \le n; c \le m$, where $\alpha, \beta,\gamma$ represent unique bit locations.), that holds with probability $p \ne 0.5$.Once a proposed relation is determined, the procedure is to compute the results of the left-hand side of the preceding equation for a large number of plaintext–ciphertext pairs. If the result is 0 more than half the time assume $K[\gamma_1,\gamma_2,\ldots,\gamma_c]=0$.If it is 1 most of the time, assume $K[\gamma_1,\gamma_2,\ldots,\gamma_c]=1$.This gives us a linear equation on the key bits.Try to get more such relations so that we can solve for the key bits. Because we are dealing with linear equations, the problem can be approached one round of the cipher at a time, with the results combined.

Steps of Linear Cryptanalysis

Linear cryptanalysis involves the following steps:

1. Linear Approximation:

   • The attacker tries to find a linear equation that relates the bits of the plaintext, the bits of the ciphertext, and the bits of the key.
   • The goal is to find an approximation where the XOR of selected plaintext bits and the XOR of corresponding ciphertext bits equals the XOR of some key bits with a probability significantly different from 0.5.

2. Data Collection:

   • The attacker collects a large number of plaintext-ciphertext pairs (i.e., input-output pairs of the cipher) using known plaintext.
   • These pairs are used to build statistical evidence for the guessed key bits by applying the chosen linear approximation.

3. Key Guessing:

   • The attacker then guesses certain bits of the key.
   • Using the linear approximation, the attacker checks how often the approximation holds for different guesses of the key bits. A correct key guess should produce results that match the biased probability more closely.

4. Statistical Analysis:

• For each possible key guess, the attacker calculates the number of times the linear approximation holds true. If a key guess is correct, the approximation will be biased toward its predicted probability.
• By comparing how well the approximations fit for different key guesses, the attacker can determine the most likely correct key bits.

Why Does Linear Cryptanalysis Work?

Linear cryptanalysis works by exploiting statistical biases introduced by the non-linear operations (like S-boxes) in block ciphers. Although these operations are designed to make it hard to find simple relationships between plaintext and ciphertext, they are not perfect.

The cipher’s security relies on these biases being small and difficult to detect. However, with enough data, an attacker can statistically identify the biases and use them to extract key information.

Countermeasures Against Linear Cryptanalysis

1. Designing Better S-boxes:

   • Block cipher designers can improve resistance to linear cryptanalysis by designing S-boxes with minimal linear biases. A good S-box has no easily exploitable linear approximations.

2. Increasing Key Size:

   • Increasing the key size (like in Triple DES or AES) helps make linear cryptanalysis less practical by increasing the computational power needed for the attack.

3. More Rounds:

   • Increasing the number of rounds in a block cipher makes it harder for linear approximations to hold over the entire encryption process. For instance, adding more rounds increases the complexity of finding effective linear approximations.

Conclusion

Linear Cryptanalysis is a powerful method used to break symmetric-key block ciphers by finding linear approximations between the plaintext, ciphertext, and key bits. It works by analyzing the statistical bias in these approximations, and with enough data, it allows attackers to recover parts of the encryption key. While effective against older ciphers like DES, modern ciphers like AES are designed with mechanisms to resist linear cryptanalysis.

This attack emphasizes the importance of non-linearity and randomness in cryptographic algorithms, and it has significantly influenced the design of secure encryption methods in modern cryptography.

Example of Linear Cryptanalysis

Let’s go through a simplified example of linear cryptanalysis using a toy block cipher, designed to illustrate how this attack works.

---

Toy Cipher Setup

For this example, we’ll consider a simple cipher with:

• 4-bit blocks of plaintext and ciphertext.
• A 4-bit key.
• One round of encryption with a basic XOR-based function and an S-box for non-linearity.

Steps of the Toy Cipher

1. S-box:

   • We use a basic 4-bit S-box that performs substitution. Assume the S-box table is as follows:

   Input (X)	Output (S(X))
   0000	1110
   0001	0100
   0010	1101
   0011	0001
   0100	0011
   0101	1111
   0110	1000
   0111	1010
   1000	0010
   1001	1001
   1010	0110
   1011	1011
   1100	0000
   1101	0101
   1110	0111
   1111	1001

2. Key Addition (XOR):

   • The plaintext is XORed with the key, then passed through the S-box. The ciphertext is simply the output of the S-box.

---

Encryption Process

Let’s see an example encryption with this toy cipher:

• Plaintext: P = 1010

• Key: K = 1101

• Step 1: XOR the plaintext and the key:

  $$P \oplus K = 1010 \oplus 1101 = 0111$$

• Step 2: Pass the result through the S-box:

  $$S(0111) = 1010$$

• Ciphertext: C = 1010

---

Linear Cryptanalysis Attack

Now, let’s see how linear cryptanalysis works against this toy cipher.

Step 1: Linear Approximation

We aim to find a linear relationship between the plaintext (P), ciphertext (C), and key (K) that holds with some bias (i.e., a probability significantly different from 0.5).

We will try the following linear approximation:

• P[0] ⊕ P[2] = C[1]

This approximation means that the XOR of the first and third bits of the plaintext is equal to the second bit of the ciphertext. We want to see if this approximation holds with a probability significantly different from 50%.

Step 2: Collect Data

We collect some plaintext-ciphertext pairs. For simplicity, let's use the following pairs (we encrypted these earlier using the toy cipher):

Plaintext (P)	Ciphertext (C)
0000	1110
0001	0100
0010	1101
0011	0001
0100	0011
1010	1010
0110	1000
1111	1001

Step 3: Analyze Data

For each pair, we evaluate the linear approximation P[0] ⊕ P[2] = C[1]:

P[0] ⊕ P[2]	C[1]	Approximation Holds?
0 ⊕ 0 = 0	1	No
0 ⊕ 0 = 0	1	No
0 ⊕ 1 = 1	1	Yes
0 ⊕ 1 = 1	0	No
0 ⊕ 1 = 1	0	No
1 ⊕ 1 = 0	0	Yes
0 ⊕ 1 = 1	0	No
1 ⊕ 1 = 0	0	Yes

In this case, out of 8 pairs, the approximation holds for 3 out of 8. That’s a probability of 3/8 = 0.375, which is somewhat lower than 0.5, showing a bias.

Step 4: Guess Key Bits

If we had more data, we could use this approximation to guess key bits. In real-world linear cryptanalysis, the attacker uses thousands or millions of plaintext-ciphertext pairs to reduce uncertainty in key bit guesses.