Understanding the wide trail design strategy

Question

I am trying to understand the wide trail design strategy. I have read the paper (paywall-free preprint) which describes it from the point of view of AES. From what I understand, it is a technique to increase diffusion in a particular way to resist differential and linear cryptanalysis. My background is in information security but not cryptography, so my understanding of some of the more math-heavy descriptions is limited. Can anyone explain the basics of the wide trail design strategy, and why and how it works?

Answer 1

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief summary and some context. Hopefully this will help you understand the paper by Daemen and Rijmen (paywal-free preprint) better.

Since the (public) discovery of differential and linear cryptanalysis, an active research area within symmetric-key cryptography has been dedicated to bounding the probability of differentials and the correlation of linear approximations in practical constructions. The goal of this line of work is to prove (or heuristically argue) the security of a construction against linear and differential cryptanalysis. The most successful approach to this end is the wide-trail strategy.

Differential and Linear Cryptanalysis

This is not the right place to explain differential and linear cryptanalysis (you can find introductions elsewhere), but some notation has to be introduced for the remainder of this post. Recall that differential cryptanalysis studies the propagation of differences $\Delta_0 \to \Delta_r$. Such differentials have an associated probability that I shall denote by $p(\Delta_0, \Delta_r)$. Linear cryptanalysis considers linear approximations which are described by a pair of masks $(u_0, u_r)$. They have an associated correlation $c(u_0, u_r)$, which is twice the bias.

In practice, one does not find differentials but rather differential characteristics, i.e. sequences of input and output differences of parts of the cipher that are easier to understand (typically, the round functon). So a differential characteristic may be defined as a tuple $(\Delta_0, \Delta_1 \ldots, \Delta_r)$. Similarly, one has linear trails in linear cryptanalysis and these are sequences of input and output masks $(u_0, u_1, \ldots, u_r)$. In some cases, the probability of a differential and the correlation of a linear approximation can be estimated as follows:

$$p(\Delta_0, \Delta_r) \approx \prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i)$$ $$c(u_0, u_r) \approx \prod_{i = 1}^r c(u_{i-1}, u_i),$$

where the choice of intermediate differences/masks is understood to be the optimal one.

I must stress again that these are approximations, and in many cases these are not valid. For example, it is clear that one often needs to take into account multiple characteristics or trails. In fact, there is an entire branch of research dedicated to refining the above estimates in both the differential and linear settings. I will not go in to these matters as they are (mostly) outside of the scope of your question.

In the remainder of this post, I will focus on heuristic security arguments that are based on showing that all characteristics have small probability, and all trails have a small correlation. I will also not really discuss how small "small" should be (this is based on cost estimates of differential/linear attacks).

Bounds on Characteristics and Trails

From here on, assume we are dealing with an SPN (but the argument will apply to several other constructions too). Suppose the round function consists of a nonlinear S-box layer, a linear layer and a key addition.

Suppose the nonlinear layer consists of $m$ S-boxes which are applied in parallel. The S-boxes have some maximum differential probability $p_{max}$ and a maximum absolute correlation $c_{max}$. By this I mean the maximum over all non-zero input differences and non-zero masks. This is important because a zero input difference always yields a zero output difference and similarly for linear approximations (assume we are dealing with permutations).

So clearly, we have the upper bounds

$$\prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i) \le (p_{max})^{n_D}$$ $$\left|\prod_{i = 1}^r c(u_{i-1}, u_i)\right| \le (c_{max})^{n_L}.$$

Here, the number $n_D$ is equal to the number of S-boxes in the characteristic with non-zero input difference. We call this differentially active S-boxes. Similarly, $n_L$ is the number of linearly active S-boxes in the trail.

Role of the Nonlinear Layer

A lot of early work focused on the choice of the nonlinear layer. That is, one attempts to minimize the quantities $p_{max}$ and $c_{max}$. Of course, one still needs to have some sort of bound on $n_D$ and $n_L$, but that is not the main concern in this line of work. For example, this 1995 paper by Nyberg and Knudsen (paywall-free preprint) uses a DES-like structure and then discusses how to choose the nonlinear function to minimize $p_{max}$. Do note that their security argument is stronger than what I describe here, as they consider (in more modern terminology) the EDP (expected differential probability) rather than individual characteristics.

Because efficiency tends to impose limits on the size of the S-boxes that can be used in a construction, $p_{max}$ and $c_{max}$ cannot be made very small. The natural conclusion is that we need to increase $n_D$ and $n_L$ somehow. This will be the role of the linear layer.

Role of the Linear Layer

Recall that the S-box layer consists of $m$ S-boxes which are applied in parallel. So it makes sense to split the differences and masks into $m$ parts: $\Delta_i = \Delta_i^{(1)} \| \Delta_i^{(2)} \| \cdots \| \Delta_i^{(m)}$ and $u_i = u_i^{(1)} \| u_i^{(2)} \| \cdots \| u_i^{(m)}$. Let us denote the number of nonzero $\Delta^{(j)}$ in $\Delta = \Delta^{(1)} \| \cdots \| \Delta^{(m)}$ by $\mathrm{wt}(\Delta)$ and likewise for $\mathrm{wt}(u)$.

The set of $j$ such that $\Delta^{(j)} \neq 0$ is often called the activity pattern of $\Delta$. One has a similar definition for masks.

The number of active S-boxes $n_D$ and $n_L$ in a characteristic/trail can then be expressed as $$n_D = \sum_{i = 0}^{r-1} \mathrm{wt}(\Delta_i),$$ $$n_L = \sum_{i = 1}^r \mathrm{wt}(u_i).$$

Remember that one wants to maximize $n_D$ and $n_L$, so the weights $\mathrm{wt}(\Delta_i)$ and $\mathrm{wt}(\Delta_i)$ should be made large. This can be done using the linear layer, because the linear layer restricts which transitions $\Delta_i \to \Delta_{i + 1}$ and $u_i \to u_{i + 1}$ are possible. That is, if the S-box layer has differential $\Delta_i \to \Delta_i^\ast$ with nonzero probability, then $\Delta_{i + 1} = L(\Delta_i^\ast)$ for a linear layer $L$. Without the DDT of the S-boxes, we don't really know what $\Delta_i^\ast$ is, but we do know that it has the same activity pattern and in particular the same weight. So we can optimize $L$ independently of the S-boxes by maximizing the quantity

$$\mathcal B_D(L) = \min_{\Delta \neq 0} [\mathrm{wt}(\Delta) + \mathrm{wt}(L(\Delta))]$$

This quantity, called the branch number, was introduced by Daemen in his PhD thesis. Later, $\mathcal B_D$ was called the differential branch number in contrast with the linear branch number defined below.

Similar ideas apply for linear cryptanalysis: the linear layer restricts which mask activity pattern transitions are possible. If $L$ is invertible (let's assume this for simplicity), then $u_{i + 1} = L^{-\top}(u_i)$ where $\top$ denotes the transpose. Hence, the linear branch number for an invertible $L$ is defined as $$ \mathcal B_L(L) = \mathcal B_D(L^{-\top}) = \mathcal B_D{(L^\top)}.$$ Note that one can also define the linear branch number of a noninvertible map.

So we want to maximize $\mathcal B_D$ and $\mathcal B_L$. In his PhD thesis, Rijmen related the branch number to coding theory. I will not go into details here, but this leads to the use of MDS codes to obtain $L$. The first cipher to use these ideas was probably SHARK by Rijmen et al. In practice, the entire linear layer $L$ is usually not an MDS matrix. Instead, one combines a column-wise MDS linear layer with a cellwise permutation that ensures diffusion between columns.

Wide trail strategy

The wide trail strategy is the design strategy that you get when you combine the ideas above (I have made several simplifications though.) Quoting from the paper:

The reasoning above suggests two possible mechanisms to eliminate low-weight trails:

1. Choose S-boxes with high minimum differential and correlation weight.
2. Design the round transformation such a way that there are no relevant trails with low bundle weight.

The first part is the role of the S-boxes, the second part relates to the linear layer (in principle one can also consider nonlinear diffusion layers, but this goes out of scope). An important difference between the wide trail strategy and earlier/other approaches (for example Nyberg and Knudsen) is the emphasis on the linear layer:

Instead of spending most of the resources on large S-boxes, the wide trail strategy aims at designing the round transformation(s) such that there are no trails with a low bundle weight. In ciphers designed by the wide trail strategy, a relatively large amount of resources is spent in the linear step to provide high multiple-round diffusion.

An immediate bound on the probability of characteristics over two rounds of such a cipher is $(p_{max})^{\mathcal B_D}$ and the absolute correlation of 2-round trails is upper bounded by $(c_{max})^{\mathcal B_L}$. Better bounds can usually be obtained for 4 rounds (here the effect of the cellwise permutation becomes relevant). I will not go into the details.

The wide-trail strategy led to the block ciphers SHARK, Square and ultimately Rijndael (which became the AES). After the AES competition, many other ciphers where designed based on (or at least inspired by) the wide-trail approach.

Beyond Wide Trails

Despite the length of this post, I have only described the very basics.

New techniques (e.g. based on SAT and MILP solvers) have been developed to compute the number of active S-boxes. Research has not ended, but it's really not feasible to try and give an overview of developments here.

Bounding characteristics and trails is not enough, because it only leads to heuristic security arguments. One can for instance try to compute the MEDP (maximum expected differential probability) and MELP (maximum expected linear potential) for a block cipher. Such calculations typically rely on the assumption that round keys are independent. There are examples of designs that were broken (using linear/differential attacks) despite good heuristic arguments for their security against these attacks.