I am trying to understand the mixcolumn design of AES. I read that the branch number is 5 and there was a definition that referred to weight of vectors. What is weight of a vector?


In cryptography, "weight" of a vector of bits is most often the Hamming weight, that is the number of non-zero bits in the vector. But in this AES context, that's most probably the "bundle weight" of a vector of bundles of bits (e.g. a vector of bytes), defined as the number of non-zero bundles.

In the AES context, the "(differential) (bundle) branch number" of a Boolean transformation with respect to a bundle partition, as defined by Joan Daemen and Vincent Rijmen in The Design of Rijndael (2002), section 9.3, is a measure of diffusion. It is defined as the minimum bundle weight of the XOR of two distinct input/output combinations of said transformation. For MixColumns, that's the minimum number of bytes that can change between two distinct input/output combinations (of a total of 32 bytes), or equivalently the minimum number of bytes in a non-zero input/output combination; which is 5.

This is consistent with the general definition of Hamming weight in coding theory, where, for a given symbol alphabet, the weight of a nonzero symbol is $1$ while the weight of the zero symbol is $0.$ The designers of AES used MDS codes over the finite field $GF(2^8)$ (which can be represented by binary vectors of length 8, i.e., the vector space $GF(2)^8$). This is a $[length=8,dimension=4,min.~distance=5]$ code and the minimum weight (same as minimum distance since the code is linear) is $5$. This minimum weight corresponds to the guarantee that there are at least 5 total nonzero bytes amongst the 4 input and 4 output bytes (the number of input bytes is the dimension of the code and the number of input+output bytes is the length) of the $\textsf{MixCols}$ mapping.

This answer further discusses the branch number.

Thanks for the many useful contributions in comments!

  • 4
    $\begingroup$ I have seen branch number consistently defined as $B(\theta) = min(w_t(a) + w_t(\theta(a)))$ for nonzero 0 in the works of Joan Daemen and company $\endgroup$
    – Ella Rose
    Feb 17 '17 at 19:38
  • 2
    $\begingroup$ The weight for AES, e.g., is based on symbol weight where symbols are in $GF(2)^8,$ and any nonzero Vector in $GF(2)^8$ (any nonzero Byte if you like) has weight 1. This is because the MDS code used in mixing has the same alphabet. $\endgroup$
    – kodlu
    Feb 17 '17 at 23:06
  • $\begingroup$ @fgrieu you are right that the term is overloaded and carelessly used. $\endgroup$
    – kodlu
    Feb 19 '17 at 21:27
  • 1
    $\begingroup$ Note that the Hamming weight is defined as the number of nonzero symbols, which don't have to be bits. So Hamming weight also applies to $\mathbb{F}_2^8$ and the comment by @kodlu doesn't contradict with the term "Hamming weight". $\endgroup$
    – Aleph
    Feb 20 '17 at 9:54
  • $\begingroup$ In the second paragraph, it is written "of a total of 32 bytes". Is this mean that two round have separately 32(16+16) "bundle", and at max 32 of then can be active(when at least one byte from each column is active initially)? @Aleph $\endgroup$
    – Radium
    Dec 21 '20 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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