6
$\begingroup$

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)$ ?

The final answer:

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
mask1 = mask2 = polyred = None

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()))]    

    global mask1, mask2, polyred
    mask1 = mask2 = 1 << degree
    mask2 -= 1
    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
        if p1 & mask1:
            p1 ^= polyred
        p2 >>= 1
    return p & mask2

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]))))
      return total

# ===========================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!

$\endgroup$
7
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Sasha Jan 4 '17 at 19:36
  • $\begingroup$ 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$"? $\endgroup$ – Sasha Jan 4 '17 at 20:00
  • 2
    $\begingroup$ The branch number is 5 not 4. Also, your definition of the weight uses the bit weight not byte weight., which is wrong. $\endgroup$ – kodlu Jan 4 '17 at 20:21
  • $\begingroup$ Do you mind me editing the question since the way the weight is used from the NIST doc is the problem. $\endgroup$ – kodlu Jan 4 '17 at 20:26
  • $\begingroup$ 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) $\endgroup$ – Sasha Jan 4 '17 at 20:28

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.