Differential and Linear Cryptanalysis as Trail Counting

Two attacks from the early 1990s still define how block ciphers are evaluated. Differential cryptanalysis tracks how a chosen difference in the plaintext propagates to the ciphertext; linear cryptanalysis tracks a linear approximation that holds with probability slightly away from one half. They look like different techniques, and historically they were discovered independently, but they are duals: the differential probability of a characteristic and the linear correlation of a trail are Fourier transforms of each other, and the same combinatorial structure bounds both.

The differential attack

Suppose a characteristic predicts that plaintext difference $\alpha$ produces ciphertext difference $\beta$ after $r$ rounds with probability $p$. The attack encrypts many plaintext pairs with difference $\alpha$, decrypts the final round under each candidate last-round key, and checks whether the resulting difference matches $\beta$ at the round-$r$ boundary. For the correct key the match rate is $p$; for a wrong key it is $2^{-n}$ where $n$ is the number of bits constrained. The correct key stands out once the number of pairs exceeds roughly $c/p$ for a small constant $c$ determined by the signal-to-noise ratio.

The counting is unforgiving. For a 64-bit block with a final-round constraint on 32 bits, the wrong-key rate is $2^{-32}$ and the correct-key rate is $p$. If $p = 2^{-20}$, the attack needs on the order of $2^{20}$ pairs — cheap. If $p = 2^{-40}$, it needs $2^{40}$ pairs, each requiring an encryption, which is at the edge of feasibility. Biham and Shamir’s attack on full 16-round DES used a characteristic with probability around $2^{-56}$ and required on the order of $2^{47}$ chosen plaintexts, which was impractical in 1990 and became practical later.

The characteristic’s probability is the product of the round probabilities only if the rounds are independent, which they are not — the state entering round $i+1$ is correlated with the state entering round $i$. The correct object is the differential: the probability that some pair with input difference $\alpha$ has output difference $\beta$, regardless of intermediate values. A differential is the union of all characteristics with those endpoints, and its probability can exceed any single characteristic’s. This is why designers state resistance against differentials rather than characteristics, and why the wide-trail bound’s gap matters.

The linear attack

Linear cryptanalysis looks for a mask pair $(\alpha, \beta)$ such that

$$\alpha \cdot x \oplus \beta \cdot E_k(x) = \alpha \cdot k_{\text{eff}}$$

holds with probability $1/2 + \epsilon$ for a fixed effective key bit $k_{\text{eff}}$, where $\cdot$ is the bitwise dot product. The approximation is built round by round: each S-box has linear approximations with known biases, the linear layer propagates masks exactly, and the key addition either cancels masks or introduces key bits into the expression.

The bias of a trail is the product of the S-box biases along it, and the total bias of a mask pair is the sum over trails — with signs, which is why trails can cancel. For the AES S-box the maximum bias of a nonzero approximation is $2^{-3}$, corresponding to a correlation of 32/128. Four rounds with 25 active S-boxes give a bias on the order of $2^{-75}$ before cancellation, and cancellation is a real effect that the wide-trail argument handles by bounding the sum rather than the product.

Matsui’s attack on DES used two approximations, one for 16 rounds with bias around $2^{-24}$ and a better one for the first 14 rounds combined with exhaustive search over six key bits. The data requirement scales as $\epsilon^{-2}$, so a bias of $2^{-24}$ needs on the order of $2^{48}$ known plaintexts. The 1994 experiment that demonstrated the attack against DES recovered a key using $2^{43}$ known plaintexts, which was a substantial computation at the time.

Why the two are duals

Write the round function’s differential probability table as a matrix $D$ indexed by input and output differences, and its linear approximation table as a matrix $L$ indexed by input and output masks. The two are related by the Walsh–Hadamard transform: the linear approximation table is the transform of the differential table, up to sign and scaling. A high differential probability for $(\alpha, \beta)$ corresponds to a large Walsh coefficient at some mask pair, though not the same pair — the correspondence is through the transform, not identity.

This duality has a practical consequence: an S-box optimised for low differential uniformity tends also to have low linearity, but not necessarily at the same pairs, and a design must check both. The AES S-box’s uniformity of 4 and linearity of 32 are both optimal in the sense that no eight-bit permutation does better on either measure. For a four-bit S-box the corresponding optima are uniformity 4 and linearity 8, and the PRESENT S-box attains both.

The duality also explains why the wide-trail counting works for both. The active S-box pattern of a differential characteristic and of a linear trail are determined by the same linear layer, so the bound of 25 active boxes over four rounds applies to both, and the per-box contributions are 6 bits of differential probability deficit and 3 bits of linear bias deficit. Since bias compounds as a product but the attack cost scales as its inverse square, the linear bound converts to a data requirement of roughly $2^{2 \times 25 \times 3} = 2^{150}$ — far beyond feasibility, and the two attacks are comparably infeasible against full AES for structurally similar reasons.

Truncated differentials and integrals

The classical attacks track exact differences and exact masks. Two generalisations matter.

A truncated differential tracks only which bytes are active, not their values. The probability of a truncated characteristic is the sum over all exact characteristics consistent with the pattern, and it can be far higher than any individual one. The square attack — also called the integral or saturation attack — is the extreme case: it uses a set of 256 plaintexts that vary one byte through all values while the others are constant, and observes that after three rounds every byte of the state is balanced, meaning the XOR of the 256 values at that position is zero. This holds with probability one, not with some bias, so it bypasses probability accounting entirely. The attack extends one round beyond the balanced property by guessing a last-round key byte and checking whether the balance survives.

The square property is a direct consequence of the diffusion structure: after one round the varying byte has spread to four bytes, after two to all sixteen, and after three the nonlinearity has scrambled values but the XOR-sum property survives because the S-box is a permutation. Designs must therefore be evaluated against integral properties as well as differential ones, and the four-round distinguisher is why AES’s ten rounds are the minimum defensible count rather than a generous one.

# Differential uniformity of a table, by exhaustive enumeration.
# For AES this is 4; the count is over all (alpha, beta) pairs.
def uniformity(sbox):
    n = len(sbox)
    worst = 0
    for alpha in range(1, n):
        counts = [0] * n
        for x in range(n):
            counts[sbox[x] ^ sbox[x ^ alpha]] += 1
        worst = max(worst, max(counts))
    return worst

# Linear bias: max |#{x : parity(alpha & x) == parity(beta & S(x))} - n/2|
def linearity(sbox):
    n = len(sbox)
    worst = 0
    for alpha in range(1, n):
        for beta in range(1, n):
            agree = sum(
                1 for x in range(n)
                if bin(alpha & x).count("1") % 2 == bin(beta & sbox[x]).count("1") % 2
            )
            worst = max(worst, abs(agree - n // 2))
    return worst

Both functions are exhaustive over 65,536 evaluations for an eight-bit S-box and take a fraction of a second. That is the entire cost of evaluating a candidate table’s resistance to the two classical attacks — which is why S-box choice is one of the few parts of cipher design where the numbers are directly checkable.

What the attacks do not cover

Neither attack is a proof of security, and both have been superseded as the primary evaluation method for new designs. Impossible differentials use characteristics that hold with probability zero and then run the attack backwards from the ciphertext; the miss-in-the-middle technique combines a forward and a backward characteristic that cannot meet. Boomerang and rectangle attacks combine two short differentials into a longer one, with a probability that is the product of the two short ones squared. Meet-in-the-middle attacks on the key schedule exploit the invertibility of the expansion rather than any property of the rounds.

Each of these was developed against specific designs and then generalised, and modern design evaluation includes automated search over all of them. The practical implication for anyone assessing a cipher is that a clean differential and linear profile is necessary but not close to sufficient. The published analyses of AES’s reduced-round variants — integral attacks to seven rounds, impossible differentials to seven, key-recovery to eight or nine depending on the variant — are the relevant benchmark, and the margin between the best published attack and the full round count is what “security margin” means in practice.

The counting machinery developed for these attacks also feeds back into design. The active S-box bound in diffusion and branch numbers exists because of differential cryptanalysis, and the S-box properties that make the bound useful are exactly the uniformity and linearity measured above. The two are one subject viewed from opposite ends: one asks how a difference propagates, the other asks how to stop it.

There is also a practical asymmetry between the two attacks that matters for implementers. A differential attack needs chosen plaintexts, which are often unavailable; a linear attack needs only known plaintexts and its data requirement scales as the inverse square of the bias, so a small bias is expensive but not impossible. That asymmetry is why linear cryptanalysis was the first to be demonstrated against full DES in an experiment, and why designers treat the linear branch number as a first-class parameter rather than a by-product.

Against structures without byte boundaries the same framework needs reworking. An ARX cipher’s differential probabilities arise from carry propagation rather than from table entries, and the trail counting is done by automated search over differences in a rotated-bit space, as described in ARX carry chains. The attacks do not disappear; only the tool that bounds them changes.