10
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Which paper are you referring to? $\endgroup$
    – user9070
    Jun 3, 2016 at 17:06
  • $\begingroup$ csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf (page 31) $\endgroup$
    – LightBit
    Jun 3, 2016 at 17:13
  • $\begingroup$ 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$. $\endgroup$
    – J.D.
    Jun 4, 2016 at 11:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – J.D.
    Jun 4, 2016 at 15:45
  • 1
    $\begingroup$ @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). $\endgroup$
    – J.D.
    Jun 9, 2016 at 0:07

1 Answer 1

Reset to default
4
$\begingroup$

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.

  2. MDS codes have a fully known weight distribution, so the full branch number distribution is also known, assuming a uniform input distribution into the Sboxes.

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.$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @LightBit does this answer your question? $\endgroup$
    – kodlu
    Jul 7, 2016 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.