Diffusion and Branch Numbers in Block Cipher Design

Every block cipher is a trade between two quantities: the probability that a differential characteristic holds, and the number of rounds over which it must be tracked. The differential probability of a characteristic is the product of the probabilities at each active S-box, and each active S-box multiplies in a factor determined by its uniformity. Designers can therefore bound resistance by ensuring that any characteristic spanning several rounds must activate many S-boxes. The wide-trail strategy makes that counting argument rigorous, and the branch number is the number it needs.

Counting active S-boxes

A differential characteristic is a sequence of differences, one per round. At a round that consists of substitution, linear mixing, and key addition, the differences propagate as follows: the S-box layer may map a nonzero input difference to a nonzero output difference, or to zero — but not the reverse, since a zero input difference always yields a zero output. The linear layer then spreads the surviving nonzero bytes across the state, and the key addition leaves differences unchanged.

An active S-box is one whose input difference is nonzero. Only active S-boxes contribute to the probability deficit, because an S-box with a zero input difference passes zero through with certainty. If a characteristic over $r$ rounds must activate at least $A$ S-boxes, and each active S-box holds a given difference pair with probability at most $p$, the characteristic’s probability is at most $p^A$. For AES, $p = 4/256 = 2^{-6}$ as established in S-box construction, so a bound on $A$ becomes a bound on probability.

The entire design problem reduces to: arrange the linear layer so that any characteristic must activate many S-boxes, and prove it.

Branch number defined

For a linear map $L$ acting on a vector of bytes, the branch number is

$$\mathcal{B}(L) = \min_{x \neq 0} \big( \mathrm{wt}(x) + \mathrm{wt}(L(x)) \big)$$

where weight counts nonzero bytes. It measures the smallest total number of nonzero bytes on the two sides of the map. A map that sends one nonzero byte to sixteen nonzero bytes has branch number 17; a map that sends one nonzero byte to one nonzero byte — a permutation of positions — has branch number 2. The maximum possible for a map on 16 bytes is 17, achieved by maximum-distance-separable constructions, and the AES column transform reaches it locally.

MixColumns, acting on one column of four bytes, has branch number 5. That is the maximum for a map on 4 bytes, since the minimum weight on each side is at least 1 and the two sides together must be at least 5. The bound is attained because the matrix is MDS: every square submatrix is invertible, so a nonzero input cannot produce an output with too few nonzeros. The circulant structure with coefficients 2, 3, 1, 1 gives exactly this property, and the reason it does is that the polynomial $3x^3 + x^2 + x + 2$ has no root in the field and no root after any of the relevant reductions — the MDS condition for a circulant matrix.

AES’s linear layer applies MixColumns independently to each of four columns, so a difference with $w$ nonzero bytes spread across the columns produces at least $5 - w$ nonzeros per column, summing to at least $5 \cdot 4 - 16$ — an unhelpful number. The useful statement is local: within any single column, input weight plus output weight is at least 5.

ShiftRows has branch number 2 in the byte-position sense, since it only permutes positions. Its role is not to increase the count but to move bytes between columns so that the next MixColumns sees inputs drawn from four different columns.

The four-round argument

The wide-trail argument combines the two layers over pairs of rounds. Consider two consecutive rounds. After the first round’s S-box layer, the differences are some set of nonzero bytes. MixColumns acts column by column, and ShiftRows moves the results so that the second round’s S-boxes see, in each column, bytes that came from four distinct columns of the previous round.

The counting proceeds as follows. Let $w$ be the number of active bytes at the input to a MixColumns, counted over the full state. Because MixColumns is applied per column, the branch number of 5 gives, for each column with $w_c$ active input bytes, at least $5 - w_c$ active output bytes. Summing: total output active bytes $\geq 20 - w$, provided $w \leq 16$. Combining the two rounds and accounting for the fact that ShiftRows spreads the active bytes of each column into four different columns before the next substitution, the argument yields a lower bound of 25 active S-boxes over four rounds. Twenty-five active S-boxes at $2^{-6}$ each gives $2^{-150}$, and the standard count is stated as at least $2^{-100}$ because the bound is applied with the S-box contribution of 4 bits per active box rather than 6 — the difference is bookkeeping about what “probability deficit” means relative to a random permutation.

The number 25 is what makes AES’s ten rounds defensible. A nine-round characteristic would need at least 25 active S-boxes over its first four rounds and at least 25 more over the next four, with the remaining round adding more; the product falls far below any usable probability. The bound is a proof about characteristics, not about the cipher, and there is a gap: differentials — sets of characteristics sharing input and output differences — can have higher probability than any single characteristic in the set. That gap is why the security claim is stated as resistance to known attacks rather than as a proven bound.

Where the argument does not apply

Three limitations are worth naming, because each corresponds to a class of attack that designers had to handle separately.

The bound is on characteristics, and it assumes the S-box’s differential probabilities multiply independently, which is exact only when the active S-boxes are independent — that is, when their inputs are not correlated. Over many rounds the correlations accumulate, and truncated differentials, which track only the activity pattern rather than exact differences, can exploit patterns where the exact differences vary. Integral and square attacks are of this type: they use a property that holds with certainty for a set of 256 plaintexts varying one byte, and they bypass probability accounting entirely. AES’s round count includes margin for these.

The bound does not address linear cryptanalysis. Linear trails are counted by the same combinatorial structure but with the linear branch number, and the relevant S-box quantity is the linearity — the maximum deviation of a Walsh coefficient from zero. For AES’s S-box the maximum linearity is 32 out of 128, giving a correlation of $2^{-3}$ per active S-box and a four-round bound analogous to the differential one. Differential and linear cryptanalysis covers the mechanics of both.

And the bound is specific to the linear layer’s structure. Ciphers built on ARX primitives have no byte boundaries and no branch number in this sense; their diffusion is measured in bit rotations and additions, and the counting argument is replaced by different techniques. That design space is treated in ARX carry chains.

Achieving a high branch number

A linear map on 16 bytes with branch number 17 would be ideal, and constructing one is a solved problem: an MDS matrix of size 16 over $\mathrm{GF}(2^8)$ exists, but it costs 16 multiplications per column of 16 bytes rather than the four that MixColumns performs on a column of four. The cost is the reason AES uses a $4 \times 4$ MDS matrix per column rather than a $16 \times 16$ matrix over the whole state.

Designs that want a higher branch number per round accept a heavier linear layer. Some use a $8 \times 8$ MDS matrix over $\mathrm{GF}(2^8)$ with an eight-byte state, giving branch number 9 and a much shorter state; others use binary matrices with a large diffusion power, which are cheaper in hardware but harder to prove optimal. The choice interacts with the S-box width: an eight-bit S-box with a 16-byte state needs the full wide-trail structure to reach 25 active S-boxes, whereas a 16-byte state with a 4-bit S-box needs many more rounds because each active box contributes only 2 bits.

/* Active-byte count for a difference, and the branch-number check for one
   column: weight(x) + weight(MixColumns(x)) >= 5 for all nonzero x. */
static int weight(const uint8_t *b, int n)
{
    int w = 0;
    for (int i = 0; i < n; i++) w += (b[i] != 0);
    return w;
}

static int column_ok(void)
{
    uint8_t x[4], y[4];
    for (unsigned v = 1; v < 0x10000; v++) {
        for (int i = 0; i < 4; i++) x[i] = (v >> (8 * i)) & 0xFF;
        mix_column_into(x, y);                  /* the 2,3,1,1 transform */
        if (weight(x, 4) + weight(y, 4) < 5) return 0;
    }
    return 1;   /* exhaustive over 65535 nonzero columns */
}

The exhaustive check is cheap enough to be worth running: 65,535 columns, each a handful of field operations. It confirms the MDS property for the specific polynomial in use, which is the step where implementation mistakes are most likely — a coefficient typo in the matrix produces a map that still looks like a diffusion layer and still round-trips, but whose branch number has dropped.

The general design rule that emerges is a ratio. The product of active S-boxes per round and rounds must exceed the security target’s bit count divided by the per-box deficit. For a 128-bit security target and a 4-bit deficit, that is 32 active boxes; AES exceeds it by a wide margin over four rounds and has ten. Lightweight designs with 2-bit deficits need twice as many, and the round counts in that domain reflect the arithmetic rather than any difference in design philosophy.