Hot answers tagged

13

AES diffusion is taking cared of by 3 main functions: SubBytes Shift Rows Mix Columns SubBytes works as a 8-bit S-box. Thus if one bit change, the 8 bits of the byte are likely to change. With this step, each bit of a byte depend of each other. This modification on the byte is then translated through the state via Shift Rows (still 1 byte affected) and ...


8

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 ...


8

The most likely rationale to change the AES design is political. It's a NIST standard, designed in Western Europe. It's a bad idea! How much scrutiny has it received? Almost none. How much will it receive? Almost none. Bad idea.


7

I ("SEJPM" as of now) have contacted the authors asked them the same questions as in my question. I'm posting this as community wiki, as it's not my answer to this question but rather theirs. Now the responses follow: First off, the authors are working on a design rationale in english for their new cipher. As soon as it's published, it will be linked here. ...


7

Finally I've went to the source and I've mailed the Rijndael's authors. They have answered very fast and very nice. I've understood the other way around. The affine transformation is over the vector space $((GF(2))^8$ and what they've say as simplicity was that, between all the possible affine transformations they select one that can also be described as ...


6

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for ...


6

It seems that using an 8x8 MDS will have 27 Active Sboxes after 4 Rounds(There may exist a trail shorter than 27). The image below shows the counting of active Sboxes. The Active and non-Active byte is shown as 1 and 0 respectively. The 8 bytes of state which become input to the 8x8 MDS matrix are colored in similar color (pink or blue). The shift rows ...


6

They were chosen because they are the smallest non zero elements possible that make the matrix MDS and circulant. With an MDS matrix, if a single input changes, all the outputs change. When multiplying the matrix by a value, you need to multiply the input bytes by the values of the matrix in a finite field. These multiplications have a computational cost ...


5

I'm not sure to what paper you reference with "30th paper from FSE 2018" because in this list the 30. paper is not about implementing MDS matrices. As the 31. paper is, I assume you refer to this, entitled "Shorter Linear Straight-Line Programs for MDS matrices". When you take the XOR count as a metric for efficiency, you can just compute this for your ...


5

According to the original NESSIE submission of Whirlpool: "The finite field ${\rm GF}(2^8)$ will be represented as ${\rm GF}(2)[x]/p(x)$, where $p(x) =$ $x^8 +$ $x^4 +$ $x^3 +$ $x^2 +$ $1$ is the first primitive polynomial of degree $8$ listed in [19]. The polynomial $p(x)$ was chosen so that $g(x) = x$ is a generator of ${\rm GF}(2^8) \setminus \{0\}$." ...


4

My answer focuses on the AES matrix only. In general, an $A$ matrix with all submatrices having full rank generates an MDS code when concatenated by an identity matrix of the right size to form $[I|A]$, but that's really a coding theory matter. As to the specific question, this is basic linear algebra but you need to work over the field that AES is defined ...


4

Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are: The minimum number of active Sboxes, i.e., the minimum branch number across 2 rounds is $9,$ the minimum weight of the MDS code. MDS codes have a fully known weight distribution, so ...


4

They said that, one goal of MDS matrices is to protect the block ciphers against linear and differential attacks. That would probably depend on the cipher, but in generally, pretty accurate. is constructing the bias table of MDS matrices behavior impossible? Actually, it's trivial; MDS matrices are completely linear, and so they have probability 1 ...


4

Your result is accurate: 25 active S-boxes is the best you can do in a 5-round trail. Here's an example for the 5-bit S-box variant, respecting the S-box constraints (and assuming I read the specification correctly): $$ \begin{bmatrix} \mathtt{19} & \mathtt{00} & \mathtt{1c} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} &...


4

Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we multiply by 2 and add the input. Those two multiplications can be described with 8x8 binary matrices. The easiest way to find the matrices is to think how those ...


4

Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$? The necessary condition is that $k\mid n$ which means $n=km$ for some integer $m$. Now Let $\bf A$ be $km \times km$ binary matrix. The first step is that to consider the matrix $\bf A$ as a block ...


3

Here is a Sage code that creates the MDS matrix over $F_2$. mds = matrix(GF(2), [ [0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0], [0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0], [0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0], [1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,...


3

This question can be used to get what you want. There we use bytes (so expand those to bits) and you have to use extra XOR's (i.e. binary additions) to get the field multiplications.


3

From the article on page 5; Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$. Let $A$ be the almost-MDS matrix. So its branch number is $n$. Using above theorem we have $$n \leq \frac{2n+4}{3} $$ So $n=2,3$ or $4$. The size of matrix is a tool for ...


3

I'm not sure about your definition, so let's take branch number in terms of the byte-wise differential branch number, i.e. the branch number of a function $F(x)$ is $$\mathcal{B}_{F(x)} = \min_{a,b \neq a}\{ w(a \oplus b) + w(F(a) \oplus F(b))\}$$ where $w(x)$ is the number of non-zero bytes in $x$. In this case, the branch number of the Twofish round ...


3

There is book Algebraic Aspects of the Advanced Encryption Standard thats gives a good algebraic description of the AES algorithm. Reading it you'll see that there was some freedom in choosing some parametres to fix a standard. Changing this choices, but keeping the algebric properties should give you an equivalent algorithm. This mainly means you can ...


3

What you are looking to do can be done, but if you expect it to just work, you are mistaken. Performing the calculation of the inverse here is the easy part, the hard part is the choice of affine transform polynomial and vector, as incorrect choice will lead to an insecure s-box. Multiplicative Inverse The most simple method of calculating the inverse is ...


3

The Kalyna paper does contain the elements on page 6, but it is not formatted in the familiar table manner, rather it describes it via mathematical formula and rotations, as the matrix is circulant: $w_{i,j} = (υ \ggg i) ⊗ G_j $ $ υ = (0x01,0x01,0x05,0x01,0x08,0x06,0x07,0x04)$ Where $G$ is the input matrix and $W = (w_{i,j})$ is the output matrix ...


3

Your matrix contains 2 which is not an element of $\operatorname{GF}(2^8)$ unless it means $x$. In this case, we can use SageMath to find the inverse as R.<x> = PolynomialRing(GF(2), 'x') S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1)) S.is_field() S.cardinality() y^8 + y^4 + y^3 + y + 1 A = matrix(S,[[1,y,y],[y,y,1],[y,1,y],]) A.inverse() ...


3

No, for MDS codes used in the way it is used in AES there's no other choice, i.e., an MDS code with these dimension must have all entries nonzero in the $M$ matrix. The MDS matrix $M$ has to be square, mapping 4 bytes to 4 bytes and must have 4 nonzero entries in each row by MDS property. It also means changing each input byte affects each output byte, ...


2

I guess that a single e-mail to Vincent Rijmen might solve this problem, but I would speculate that the new S-box should have been more hardware-friendly compared to that of Rijndael. The recursive structure of $W$ and smaller constants in the MDS matrix may have required another field representation.


2

Let $C$ be $[n,k,d]$ code, where $n$,$k$ and $d$ are length of code words, dimension and minimum distance of code, respectively. Codes with $n-k=d-1$ are called MDS codes. In general case, if a $m\times m$ matrix $M$ is an MDS we can use $[I\mid M]$ as a generator matrix and check if the code produced is MDS code. In this state, produced code $C$ is $[2m,m,...


2

Because: These numbers in the matrix form a Maximum Distance Separable matrix; that is, one where, if you change some bytes of the input, then the total number of bytes of input changed PLUS the total number of bytes of output changed will always be at least 5 (e.g. if you change 2 bytes of input, then you'll always change at least 3 bytes of the output). ...


2

my answer is extension to circulant and recursive. one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the MDS matrix ) , depth (number of stages) and the field size (usually 4 or 8 ) according to this paper MDS Matrices with Lightweight Circuits, the native ...


2

A matrix $M$ of order $n$ is an MDS (Maximum Distance Separable) matrix if and only if every sub-matrix of $M$ is non-singular. Therefore, if you have an $n\times n$ MDS matrix $M$, constructing the $(n-1)\times (n-1)$ MDS matrix $M'$ is so easy. $M'$ can be constructed by choosing an arbitrary $(n-1)\times (n-1)$ sub-matrix of $M$. Here you can find some ...


Only top voted, non community-wiki answers of a minimum length are eligible