Linear hull

Previously, we touched upon a linear trail with a weird property. In multiround linear cryptanalysis, the primary object of study are just these linear trails: a sequence of input and output masks that describe how a linear approximation propagates through consecutive rounds of a cipher. These trails form the backbone of most linear attacks and are used to estimate the correlation between input and output bits of the cipher.

Linear trails

We'll now treat the matter a bit more formally. Let a block cipher consist of $r$ rounds, each composed of a key addition, substitution (S-box layer), and linear diffusion layer. A linear trail is defined as a sequence of bitmasks ($\alpha_0, \alpha_1, \dots, \alpha_r$), where:

• $\alpha_0$ is the input mask (applied to plaintext),
• $\alpha_r$ is the output mask (applied to ciphertext),
• and $\alpha_i$ represents the linear mask after round $i$ and before round $i+1$.

As discussed prior, the correlation of a linear trail is computed as the product of the correlations of all active S-box approximations within the trail. If a trail activates $w$ S-boxes and each has a corresponding correlation $\textbf{corr}i$, then the total correlation is: $$\textbf{corr} = \prod{i=1}^w \textbf{corr}_i$$ This does assume that the linear layer maps masks linearly across rounds, which is the case for SPN constructions such as PRESENT.

Sometimes, when discussing trails, it's easier to have the correlations be an integer rather than a fraction. We define the weight of a trail as: $$\text{weight} = -\log_2|\text{corr}|$$ Lower-weight trails are preferable, as they indicate stronger correlations and thus better distinguishability. Weights, by virtue of being integers, are also much nicer to use in e.g. integer programming.

Linear hulls

The key difference between linear and differential cryptanalysis has thus far been how we construct multiround trails. As mentioned, we don't deal with probabilities here, rather we focus on bias and correlation. However, this comes with an unexpected side-effect.

In practice, a single linear trail rarely dominates. Instead, for a fixed input mask $\alpha_0$ and output mask $\alpha_r$, there can be multiple trails $\mathcal{T}_j = (\alpha_0, \dots, \alpha_r^{(j)})$ that begin and end with the same masks but differ internally.

The linear hull is the set of all such trails sharing the same input and output masks. The effective correlation observed during an attack is the sum of the correlations of all contributing trails, accounting for their relative signs (phases): $$\text{corr(hull)} = \sum_{j} \text{corr}(\mathcal{T}_j)$$ The squared correlation of the hull, $\text{corr(hull)}^2$, determines the overall bias used in a linear distinguisher.

As a result of all this, trail interference can cause either constructive or destructive interference, and the net correlation can be much smaller (or larger) than any individual trail.

This is all in stark contrast to how differential trails behave. While the concept of a "differential hull" can be made out, it can only impact a trail positively i.e. constructively, and so is rarely as important.

Estimating hulls

The existence of linear hulls tell us that our approximations need not hold in ways we may expect them to. How can we estimate the impact of a trail's linear hull?

The obvious approach is to do so empirically: we try the approximation, and see by how the bias differs. This can work fine, especially when we expect our attack to be practical, but is difficult to use in a theoretical context.

The alternative, and far more computationally expensive approach, is to search the valid trail-space for all trails matching belonging to our hull, and compute an exact hull bias. While this works, it can easily prove computationally infeasible, though improving this is an area of active research [citation(s) here].

In practice, a linear hull, especially over many rounds, is rarely as impactful, and one trail usually dominates. More often, we're interested in identifying useful linear hulls than having to worry about them.