# Choice of multiplication polynomial in Rijndael s-box affine mapping

The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows:

We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the ‘inverse’ mapping. It can be seen as modular polynomial multiplication followed by an addition:

$b(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1)$ $mod$ $x^8 + 1$

The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box( a ) = a ) and no ’opposite fixed points' (S-box( a ) = ā ).

The multiplication polynomial being $x^7 + x^6 + x^5 + x^4 + 1$, which is irreducible and therefore coprime to the modulus $x^8 + 1$. The inverse mapping multiplication is $x^7 + x^5 + x^2$.

However, $x^7 + x + 1$ is also irreducible, and has an even more simple representation. It is the most simple irreducible polynomial of degree 7. It also has a longer affine period (8 vs 4) which is supposedly better. There are many valid choices for the added constant that result in no fixed or opposite fixed points. The inverse mapping multiplication is $x^6 + x^5 + x^3 + x^2 + 1$, which is coprime to the modulus.

Is there some obvious reason the more simple polynomial was not used? The implication in the Rijndael specification is it does not have the simplest description, which does not seem to be the case. My assumption is lack of complexity of the algebraic expression in the resulting s-box or its inverse, but I do not have the means to determine if that is the case.

## update

Thinking that the reason may have been the statistical performance of the s-box with the given affine polynomial, I compared it against $x^7 + x + 1$, the results are below:

                             AES        x^7 + x + 1
SAC Relative Error           12.5%      9.4%            lower is better
SAC Satisfaction %           67.2%      67.2%           higher is better
Distance to SAC              432        432             lower is better
Negative DSAC                176        152             lower is better

2nd order SAC Rel Err        12.5%      12.5%           lower is better
2nd order SAC Sat %          56.7%      61.2%           higher is better
Dist to 2nd order SAC        1664       1424            lower is better
Negative 2nd order DSAC      844        684             lower is better

AVAL Relative Error          3.52%      3.12%           lower is better
Guaranteed Avalanche         339.2      339.2           my own metric

Bit Independence Rel Err     13.412%    12.856%         lower is better
Bit Independence Sat %       56.2%      63.8%           my own metric


It is quite clear that $x^7 + x + 1$ has better results in many s-box performance metrics when compared to the chosen polynomial.

During testing I also found that the Rijndael s-box has a self inverse mapping at 0x73 and 0x8F, where an input to the s-box and the inverse s-box produce the same result. This implies that the additive constant may not have been chosen carefully enough. The optimal constant appears to be 0x15.

-
I just performed an SAC test, the more simple polynomial actually performs better by a slight margin – Richie Frame Jul 2 '14 at 20:23
Do you have any evidence that these metrics have anything to do with the security of AES? Are there any theoretical (reduced round) attacks known against AES that would be foiled by an sbox that is better by these metrics? – poncho Jul 21 '14 at 14:38
@poncho No I do not. They concern differential properties, better performance in these tests generally means more resistance to differential cryptanalysis. The AES s-box is already very good in these respects, what I am saying there is that their choice of affine polynomial was not chosen from a subset of those with statistically better properties, so that is not a potential reason not to use a more simple polynomial. – Richie Frame Jul 21 '14 at 20:25

The affine transformation is a vector space operation $(\mathbb{F}_{2})^8$, and the simplicity comes from the fact that, from the bunch of possible transformations the one used can be also described as a product in a polynomial ring modulo $x^8+1$.