# How to find the AES branch number?

By definition, branch number

Definition: The branch number of a linear transformation $F$ is $$min_{a\neq0}(W(a) + W(F(a)))$$

Source here (7.3.1)

For AES MixColumns $a \in GF(2^8)^4$ since the input is the four bytes in a column of the state.

Where $W(a)$ is a weight vector i.e. the number of nonzero components of the vector

$$a \in GF(2^m)^4, a = (a_1, \ldots, a_4)\\ W(a) \iff ||a|| = |\{i | a_i\neq 0 \}|, i = 1,\ldots,4$$

In AES uses a pre-defined matrix operations MixColumns. I need prove (like the proof of a theorem) that the branch number of matrix is equal to 5.

Questions:

1. In the same article (7.3.1) is said

the output can have at most 4 active bytes

and

Hence, the upper bound for the branch number is 5

In such a way that $W(F(a))$ the maximum can be $4$ (why?) and $W(a) = 1$. Why $W(a) = 1$, because the number of non-zero component can be greater than $1$? Or it is there to pay attention to $min()$?

2. How to calculate $W(F(a))$, for each $a \in GF(2^m)$ ?

Use theorem No. 2 (on page 4) here

is MDS if and only if every square submatrix of A is nonsingular

Ok, the initial data taken from here.

To test, I wrote a script test.py (see below) that:

1. Defines all sub-matrices of the original
2. For each of the sub-matrices calculate the determinant in GF(2^8)
3. The result is an array of values of the determinant of each submatrix.

test.py

from functools import reduce
import sys

# ===========================Galois field===========================

# constants used in the multGF2 function

def setGF2(degree, irPoly):
# Define parameters of binary finite field GF(2^m)/g(x)
#    - degree: extension degree of binary field
#    - irPoly: coefficients of irreducible polynomial g(x)

def i2P(sInt):
# Convert integer into a polynomial
return [(sInt >> i) & 1
for i in reversed(range(sInt.bit_length()))]

polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])

def multGF2(p1, p2):
# Multiply two polynomials in GF(2^m)/g(x)
p = 0
while p2:
if p2 & 1:
p ^= p1
p1 <<= 1
p1 ^= polyred
p2 >>= 1

def determinant(matrix, mul):
width = len(matrix)
if width == 1:
return multGF2(mul, matrix[0][0])
else:
sign = 1
total = 0
for i in range(width):
m = []
for j in range(1, width):
buff = []
for k in range(width):
if k != i:
buff.append(matrix[j][k])
m.append(buff)
total = total ^ (multGF2(mul, determinant(m, multGF2(sign, matrix[0][i]))))

# ===========================All submatrix===========================
import numpy as np

def get_all_sub_mat(mat):
rows = len(mat)
cols = len(mat[0])
def ContinSubSeq(lst):
size=len(lst)
for start in range(size):
for end in range(start+1,size+1):
yield (start,end)
for start_row,end_row in ContinSubSeq(list(range(rows))):
for start_col,end_col in ContinSubSeq(list(range(cols))):
yield [i[start_col:end_col] for i in mat[start_row:end_row] ]

def swap_cols(arr, frm, to):
arr = np.matrix(arr)
arr[:,[frm, to]] = arr[:,[to, frm]]
return arr.tolist()

def swap_rows(arr, frm, to):
arr = np.matrix(arr)
arr[[frm, to],:] = arr[[to, frm],:]
return arr.tolist()

def print_matrix(matrix):
matrix = np.matrix(matrix)
print matrix

submatrix = []
def foo(matrix):
for i in get_all_sub_mat(matrix):
if len(i) == len(i[0]) and len(i) != 1:
submatrix.append(i)

# Initial matrix
matrix = [
[2, 3, 1, 1],
[1, 2, 3, 1],
[1, 1, 2, 3],
[3, 1, 1, 2]
]

# All submatrix here
for i in [[0,0], [1,2], [1,3], [2,3]]:
_matrix = swap_cols(matrix, i[0], i[1])
for j in [[0,0], [1,2], [1,3], [2,3]]:
_matrix = swap_rows(matrix, i[0], i[1])
foo(_matrix)

# print len(submatrix)  # 224

if __name__ == "__main__":
setGF2(8, 0b10001)  # 0b10001 equal modulo x^4+1 from https://en.wikipedia.org/wiki/Rijndael_mix_columns
data = []
N = 2 ** 8

result = []
for m in submatrix:
result.append(determinant(m, 1))
print 'Final result: ', result
print '0 in result: ', 0 in result


Thanks @kodlu for the help!

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

• in AES uses a fixed polynomial $$c(x) = 3x^3 + x^2 + x + 2$$ The coefficients have been chosen in such a way that the upper bound is reached. "Any nonzer byte contributes 1 to the minimum weight" - Thank you, well done! "ensures that the 8 bytes" and "See the answer to this question for more" - Yeah, I saw this answer, but still not very well understood, how is the calculation (from a mathematical point of view) – Sasha Jan 4 '17 at 19:36
• in other words, how to prove "The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$"? – Sasha Jan 4 '17 at 20:00
• The branch number is 5 not 4. Also, your definition of the weight uses the bit weight not byte weight., which is wrong. – kodlu Jan 4 '17 at 20:21
• Do you mind me editing the question since the way the weight is used from the NIST doc is the problem. – kodlu Jan 4 '17 at 20:26
• Ok, I use byte weight. But I still don't understand why 5? In the documentation of AES is described as a fact. There is no mathematical explanation of why chosen this polynomial (exactly this polynomial allows to obtain a branch number = 5) – Sasha Jan 4 '17 at 20:28