Design properties of the Rijndael finite field?

Question

So we've already had a question on replacing the Rijndael S-Box. My question is - can we use a different finite field other than the one given by $x^8 + x^4 + x^3 + x + 1$ in $GF(2^8)$. In other words, would any irreducible polynomial over this field do the trick or are the special considerations and properties of that particular reducing polynomial?

If a more general discussion on appropriate fields for cryptographic operations, such as those used in ECC, is necessary, then I'd be happy to hear it. What I'm trying to get to is an understanding of whether there are any important properties in terms of the "randomness" of the operation - for example, are there weak fields to operate over? For example, $x^8 + x^3 + x + 1$ ought to also be irreducible - so would it be suitable? I ask partly because of the Galois/Counter Mode issue with short tags which lead me to think not all fields might hold equal strength. Right? Wrong? Inconsequential?

Answer 1

For security of ECC, the choice of the irreducible polynomial is unimportant, because all finite fields with the same cardinal are isomorphic to each other (and the isomorphisms are easy to compute); this is why we can say "the finite field $GF(2^{163})$" even though there are many irreducible polynomials of degree $163$ over $GF(2)$. So the algebraic structure of an elliptic curve is not impacted by the actual field choice (of course, the curve is described with an equation $Y^2+XY=X^3+aX^2+b$ for two given constants $a$ and $b$, and those constants are represented with a given choice for the field; but using another field and applying the isomorphism on $a$ and $b$ yields another curve with the same structure). In practice, we use polynomials which promote implementation efficiency, i.e. polynomials with very low Hamming weight ($3$ if possible, $5$ otherwise), and where the non-zero coefficients are of the smallest possible degree (to make post-multiplication modular reduction easier).

For the Rijndael S-Box, things are not as simple. In the original Rijndael specification, there are some explanations on the design rationale, which were not copied into the final FIPS 197 standard. The S-Box is treated page 26; the use of an inverse in $GF(2^8)$ comes from a 1994 article by Nyberg, as providing good defense against differential cryptanalysis. To this inverse, Daemen and Rijmen added the so-called "affine mapping" which is meant to mask the algebraic structure of the said multiplicative inverse. All details are not given, so presumably they tried many polynomials (there are 30 irreducible polynomials of degree 8 over $GF(2)$, 16 of which being primitive) and many possible affine mappings, "measured" resistance to differential and linear cryptanalysis, and kept the best candidate.

Daemen and Rijmen published a book on the design of Rijndael (I have not read it).

Answer 2

Actually, the choice of irreducible polynomial is unimportant in AES; for any polynomial representation of $GF(2^8)$, you can modify the affine tranformation (and the MixCollumn) operation to come up with a block cipher that is equivalent to AES (meaning that any break to that can be translated to a break on the original AES).

The key observation here is that, for any two polynomial representations $A$ and $B$ of the same $GF(2^N)$ field, there is a bitwise linear isomorphism $L$ from elements in representation $A$ to elements in representation $B$ which preserves both the field addition and multiplication operations:

$L( X +_A Y ) = L(X) +_B L(Y)$

$L( X \times_A Y) = L(X) \times_B L(Y)$

So, if $A$ is the standard AES polynomial representation ($x^8 + x^4 + x^3 + x +1$), and $B$ is your favorite alternative representation, you can implement AES using your representation, which each internal value being mapped by $L$ compared to the equivalent value in the standard AES operation. The affine operation then becomes:

$Affine'(X) = L( Affine( L^{-1} ( X )))$

which is also affine (because L is linear). In addition, in the MixCollumn operation, instead of multiplying elements by 2 and 3 (in the $A$ representation), you multiply them by $L(2)$ and $L(3)$ (in the $B$ representation).

The result of all this is an alternative cipher that is equivalent to standard AES where all inputs (plaintext, keys) are transformed by a linear operation, and whose output (ciphertext) is also transformed by a linear operation. This linear operation can be publicly computed, and hence cannot impact security.

On another note, you state that $x^8 + x^3 + x + 1$ ought to be irreducible; well, as $x^8 + x^3 + x + 1 = (x+1) \times (x^7 + x^6 + x^5 + x^4 + x^3 + 1)$, that is not the case.