# How to calculate active s-boxes from branch number?

If MDS in AES has branch number 5 (so 5 active s-boxes in 2 rounds), wouldn't that mean 4 rounds of AES has $5*2=10$ active s-boxes?

AES paper says it has 25 ($5^2$?) active s-boxes in 4 rounds.

How to calculate minimal active s-boxes from branch number for any given number of rounds?

Edit: J.D. noted that you can't calculate the minimum number of active s-boxes from the branch number of MixColumns, because MixColumns isn't the only operation. So let's assume cipher has full state MDS like SHARK and Khazad.

• Which paper are you referring to? – user9070 Jun 3 '16 at 17:06
• – LightBit Jun 3 '16 at 17:13
• You can't just calculate the minimum number of active s-boxes from the branch number of MixColumn, because MixColumn isn't the only operation - there is also ShiftRow. See Theorem 2 on page 37 of the paper you linked for the proof of 25 s-boxes over 4 rounds. This proof can be trivially expanded to $4n$ rounds for any natural number $n$. – J.D. Jun 4 '16 at 11:39
• For a cipher like Khazad, the branch number of the MDS gives us an easy to compute lower bound on the minimum number of active s-boxes - for $2n$ rounds ($n=1,2,3$...) and branch number $B$, the minimum number of active s-boxes is $nB$. The true minimum may be larger than this lower bound, but it cannot be smaller. – J.D. Jun 4 '16 at 15:45
• @LightBit - yes, an 8 round characteristic involves at minimum 36 active s-boxes. That said, a differential attack on Khazad would generally proceed by stripping off a round or two at the beginning and/or end, so the relevant number of rounds would be 6 (27 active s-boxes). – J.D. Jun 9 '16 at 0:07

Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are:
1. The minimum number of active Sboxes, i.e., the minimum branch number across 2 rounds is $9,$ the minimum weight of the MDS code.
See here for the weight distribution. Briefly, $A_i$ denotes number of codewords of weight $i$, thus also the number of occurrences of branch number $i.$ In this case $A_0=1,$ and $A_i=0,$ for $1\leq i \leq d-1.$ The other nonzero weights are $$A_i= \binom{n}{i} \sum_{j=0}^{i-d} (-1)^{j}\binom{i}{j} \left( q^{i+1-d-j}-1\right),$$ for $d\leq i \leq n.$
Here $q=2^8, d=9.$