Thread (13 posts)

Looking at the paper's definitions, a characteristic in differential cryptanalysis consists of:

Components of a Characteristic

In modern notation, an n-round characteristic Ω is a tuple:

$\Omega = (\Omega_P, \Omega_\Lambda, \Omega_T)$

where:

1. $\Omega_P$: The plaintext difference (XOR) between two plaintexts
2. $\Omega_T$: The ciphertext difference (XOR) between the corresponding ciphertexts
3. $\Omega_\Lambda = (\Lambda_1, \Lambda_2, ..., \Lambda_n)$: A sequence of round differences

Each round difference $\Lambda_i = (\lambda_i^I, \lambda_i^O)$ consists of:

• $\lambda_i^I$: The input difference to the F function in round $i$
• $\lambda_i^O$: The output difference from the F function in round $i$

What the Probability Means

The probability of a characteristic is:

$P[\text{characteristic } \Omega] = P[\text{pair follows the specified path} | P' = \Omega_P]$

In other words: Given a pair of plaintexts $(P, P^*)$ with difference $P' = P \oplus P^* = \Omega_P$, what is the probability that:

1. In round 1: The F function input difference is $\lambda_1^I$ and output difference is $\lambda_1^O$
2. In round 2: The F function input difference is $\lambda_2^I$ and output difference is $\lambda_2^O$
3. ... and so on for all rounds ...
4. The final ciphertext difference is $T' = \Omega_T$

Example from the Paper

The paper gives a concrete two-round characteristic (Example 11):

• $\Omega_P = \text{00 80 82 00 60 00 00 00}_x$
• Round 1: $a' = \text{60 00 00 00}_x \rightarrow A' = \text{00 80 82 00}_x$ with probability 14/64
• Round 2: $b' = 0 \rightarrow B' = 0$ with probability 1
• $\Omega_T = \text{60 00 00 00 00 00 00 00}_x$

The overall probability is $(14/64) \times 1 = 14/64$.

Key Insight

The probability calculation assumes that each round's behavior is independent (given the input difference to that round). So:

$P[\text{characteristic}] = \prod_{i=1}^n P[\lambda_i^I \rightarrow \lambda_i^O]$

where $P[\lambda_i^I \rightarrow \lambda_i^O]$ is the probability that input difference $\lambda_i^I$ to the F function produces output difference $\lambda_i^O$.

The paper describes how characteristics are used to recover key material through a counting method. Here's the key recovery process:

Basic Principle

From the paper's description in Example 7:

"Assume we know that $S1_E = 1_x$, $S1_E^* = 35_x$, and $S1'_0 = D_x$ and we want to find the key value $S1_K$. The input XOR is $S1'_E = S1'_I = 34_x$ regardless of the actual value of $S1_K$. By consulting Table 2 we can see that the input to the S box has eight possibilities. These eight possibilities make eight possibilities for the key..."

The Counting Method

The paper describes the general approach (page 17):

"For each possible key value, count the number of pairs that result with the expected output XOR using this key value in the last round. The right key value is the (hopefully unique) key value suggested by all the pairs."

Why This Works

The key insight is explained on page 19:

"We know that the right key value should result from all the right pairs which occur (approximately) with the characteristic's probability. All the other possible key values are fairly randomly distributed... Consequently, the right key appears with the characteristic's probability (from right pairs) plus other random occurrences (from wrong pairs). To find the key we just have to count the number of occurrences of each of the suggested keys. The right key is likely to be the one that occurs most often."

Signal-to-Noise Ratio

The paper introduces a crucial concept (Definition 13):

"The ratio between the number of right pairs and the average count in a counting scheme is called the signal-to-noise ratio of the counting scheme and is denoted by S/N."

The formula given is: $S/N = \frac{2^k \cdot p}{\alpha \cdot \beta}$

where:

• $k$ = number of key bits being counted
• $p$ = characteristic's probability
• $\alpha$ = average count per counted pair
• $\beta$ = ratio of counted to all pairs

Practical Example: 6-Round DES

From Section 4:

"Each one of the two characteristics lets us find the 30 key bits of K6 which are used at the input of five S boxes in the sixth round... For each pair derive the expected output XOR of as many S boxes in the last round as possible from the plaintext XOR and the ciphertext pair... For each possible key value, count the number of pairs that result with the expected output XOR using this key value in the last round."

Filtering Wrong Pairs

An important optimization (page 30):

"Since about 20% of the entries in the pairs XOR distribution tables of the S boxes are impossible, about 20% of the wrong pairs can be discarded by each S box before they are actually counted."

This filtering dramatically improves the signal-to-noise ratio by eliminating pairs that cannot possibly follow the characteristic.