2
$\begingroup$

In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said

" Let F be a linear transformation acting on byte vectors and let the byte weight of a vector be the number of nonzero bytes. The byte weight of a vector is denoted by $W(a)$.

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

If the branch number is 5, a difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input (or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between input and output bits involves bits from at least 5 different bytes from input and output."

The AES chose polynomial $c(x)=03x^3+01x^2+01x+02$ to construct MixColumn operation , where the coefficients are hexadecimal representation of numbers in $GF_{256} $(e.g. $03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial\,representation}$) The MixColumn operation is done by multiplying $c(x)$ and mod $x^4+1$

However, the document doest not give a mathematical proof. My questions are

  1. Prove the maximum branch number is $5$. Besides, AES MixColumn can achieve the maximum value as $5$.
  2. given a branch number, how to construct the linear transforamtion $F(\,)$ (in the case of AES, it is $5$) ?
  3. Reversely, given $F$ (a matrix), how to estimate its branch number?
    For example, how should I prove that if the linear transformation is self-inverse
    ($\;(c(x))^2\equiv 1 \;mod\,x^4+1$ or $F^2=I$ ), then the branch number is at most $4$?

I suppose these problems are related to matrix norm, but I do not know where to start to tackle these problems.

$\endgroup$
  • 2
    $\begingroup$ Correction: idempotent means "doing it twice is the same as doing it once", that is a function $f$ is idempotent iff $f(f(x)) = f(x)$. What they mean is "self-inverse". $\endgroup$ – poncho May 3 '17 at 19:11
  • $\begingroup$ It is self -inverse indeed. I had edited this post. Thank you for correction. $\endgroup$ – Rikeijin May 3 '17 at 19:29
  • 1
    $\begingroup$ Possible duplicate of two questions.crypto.stackexchange.com/questions/42764/… and crypto.stackexchange.com/questions/35073/… $\endgroup$ – kodlu May 4 '17 at 3:26
4
$\begingroup$

The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument.

We have two definitions for MDS (Maximum Distance Separable) Matrix:

First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular.

Second definition: A matrix $M_{n\times n}$ is MDS if and only if

$$ Y_{n\times 1}=M_{n \times n}\, X_{n \times 1} \Longrightarrow \mathop{\rm min}_{X\neq 0}(W(Y)+W(X))=n+1 $$

where $X={[x_0,x_1,\cdots , x_{n-1}]}^T$ and $Y={[y_0,y_1,\cdots , y_{n-1}]}^T$ are vectors in an arbitrary field and $W(X)$ is the number of non-zero elements of $X$.

Now, suppose that we use a MDS matrix( by first definition) of order $4$ and we want to proof by second definition that it's branch number is 5. Consider our MDS matrix be as follows

$$ M=\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] $$ the entries $m_{i,j}$ are non-zero because $M$ by first definition is MDS. Now consider the following equation $$ MX=Y \Longrightarrow \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ y_{{3}}\\ y_{{4}}\end {array} \right] $$ where $x_i$'s and $y_i$'s are elements of finite field. By second definition $X$ should be non-zero. For simplicity, consider $x_1\neq0$ and other $x_i$ can be zero or non-zero.

We should consider some cases to show that for every selection of $x_2$, $x_3$ and $x_4$, at least four elements of $x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are non-zero.

The first case is $x_2=x_3=x_4=0$. in this case we have:

$$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\0 \\ 0\\ 0\end {array} \right]= \left[ \begin {array}{c} x_1\,m_{1,1}\\ x_1\,m_{2,1} \\ x_1\,m_{3,1}\\ x_1\,m_{4,1}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ y_{{3}}\\ y_{{4}}\end {array} \right] $$ because $m_{i,j}$'s and $x_1$ are nonzero then the elements $y_1,y_2,y_3,y_4$ are nonzero. The next case is that are there non-zero values for $x_2,x_3,x_4$ such that

$$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right] $$ due to the $M$ matrix is non-singular we can conclude that $$ \left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right]^{-1}\left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right]=\left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right] $$ and it contradict to our assumption that $x_1,x_2,x_3,x_4\neq 0$ and so one of the $y_1,y_2,y_3,y_4$ should be non-zero.

The next case is that: are there for example $x_1\neq0, x_2\neq0 ,x_3=x_4=0$ that result $y_1\neq0, y_2\neq0 ,y_3=y_4=0$. Consider there was this case as follows

$$ \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_2 \\ 0\\ 0\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ 0\\ 0\end {array} \right] $$ so we have $$ \left[ \begin {array}{cc} m_{{3,1}}&m_{{3,2}}\\ m_{ {4,1}}&m_{{4,2}}\end {array} \right] \left[ \begin {array}{c} x_{{1}}\\ x_{{2}} \end {array} \right]= \left[ \begin {array}{c} 0\\ 0\end {array} \right] $$ from the first definition all sub-matrix of $M$ has non-zero determinant and hence we can conclude from the above equation that the values of $x_1=x_2=0$ and it contradict to our assumption.

The other cases are similar to mentioned cases and use from this fact that all sub-matrix of $M$ have non-zero determinant.

I hope you find it useful.

$\endgroup$

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.