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?
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$ Commented Feb 17, 2017 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$– kodluCommented Feb 17, 2017 at 23:06
-
$\begingroup$ @fgrieu you are right that the term is overloaded and carelessly used. $\endgroup$– kodluCommented Feb 19, 2017 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$– AlephCommented Feb 20, 2017 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$– RadiumCommented Dec 21, 2020 at 6:20