How can I calculate the Rijndael SBox?

Question

I would like to implement the Rijndael subBytes() operation using calculation instead of tables, because I like to play with this on different wordsizes, as an academical exercice, to see what the table would look like.

The first part is a multiplicative inverse in the polynomial binary finite field, isn't it?
The $g: a \rightarrow b = a^{-1} \in \frac{\mathbb{F}_{2^8}[z]}{m(z)}$, right?

I can use Sage to calculate it, but I prefer to implement it by myself. I've tried with section 4.3.2 of the Rijndael's design book and I've look with others like cohen's book (its about curves but the binary field maths are explained), but I'm not finding something that convinces me because play with different word sizes would decay in an ugly set of if statements in the first case or my background is too pour to really get the others in the right way.

• What would be the best way to attack an implementation of this?

I have another question with in this subBytes() and it's about the parameters in the affine transformation. In this sub-operation

$f: a \rightarrow b = r\times a+s$

where $r$ is a rotation matrix representation of the polynomial $z^7+z^6+z^5+z^4+1$ (that I'm not getting what's behind this matrix, or why/how this MDS (Maximum Separable Distance) are coming to the scene), and $s$ looks to be a vector representation of the polynomial $z^6+z^5+z+1$. I'm also confused because the book and the amended version 2 from 1999 uses different values on what I've called $r$ and $s$.

• How were those $r$ and $s$ chosen?

To undo this $f$, $f^{-1}$ is using an $r^{-1}$ and $s^{-1}$ that, if I didn't made a mistake, are not the inverses calculated using the first operation.

• Any clue about how they are calculated?

Answer 1

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 to build tables. You need to start by building antilog and log tables for the given field size and reduction polynomial.

The antilog table is built like this:

$Antilog(0) = 1$
$Log(0) = 0$

$Antilog(i) = g \times Antilog(i-1)$
$Log(Antilog(i)) = i$

for $i = 1$ to $2^{n-1}$, where $g$ is the generator of the table for a given $m$ (reduction polynomial), and addition and multiplication are done in $GF(2^n)$

The multiplicative inverse is then done using a lookup in these tables:

$b^{-1}(x)=Antilog(2^{n-1} - Log(b(x)))$

where $b(x)$ is the byte representation of the polynomial you want inverted, and subtraction is not in the field. $0^{-1}$ is mapped to $0$.

For Rijndael, $n$ is 8, $m$ is 0x11B, the smallest $g$ is 3.

Once the log and antilog tables are generated, you can either build a separate table for the inverse, or perform the double lookup to get it.

Affine Transformation

For the affine transform matrix multiplication, see my answer here for an implementation example. The bit indexes of the new affine transformation polynomial need to be placed into the correct locations of the rotational matrix.

The bit indexes of 0x1F do not match those of the polynomial representation, which is actually the right most row top to bottom. The 0x1F representation makes a software algorithm a little easier to write and debug, since the column index now matches a successive division by 2 of the input and taking the LSB. This could be done in the correct order using multiplication, but requires steps to prevent an overflow with specific data types (byte) in numerous programming languages. Creating a table for transformations by $r$ will be the quickest for testing.

The 0x1F representation is also used in many papers describing the Rijndael s-box or when presenting alternatives, so I tend to use it by default, while keeping in mind the polynomial is different.

The $r$ and $s$ values used in Rijndael do not seem to be optimal for avalanche properties, and seem to have been chosen without detailed analysis. $r^{-1}$ is the inverse of $r$, details here. $s^{-1} = r^{-1} \times s$.

Testing

When changing the width of the s-box, there are several important things at this point that need to be kept in mind. The choice of affine polynomial determines the avalanche properties of the s-box, and the vector determines if there are any fixed points. Avalanche properties are also determined by initial choice of $m$. See this paper for the effects of changing these:

S-boxes generated using Affine Transformation giving Maximum Avalanche Effect

Upon generation of a candidate s-box it needs to be tested to make sure it meets all relevant cryptographic properties. Test for avalanche first (with the first functional vector), and once you have found the best affine transform, run through all vectors. Additional testing should then be performed on the remaining s-boxes. Note the lack of vector testing in the first s-box generated in the above paper (table 4) which has a fixed point at 0x10. The Rijndael design criteria requires that fixed points do not exist; this restriction was imposed despite the fact no attacks which exploit fixed points were known.

For every 1 bit increase in $n$, the workload goes up substantially. Each s-box takes 2 to 3 times longer to generate, and you have have 4 times as many affine/vector combinations to test, and up to 8 times the workload for avalanche testing per combination. Additionally, if you test all choices of $m$ for best avalanche effect, that's another doubling on average. Memory required to store the tables also more than doubles.