AES with other SBoxes

Question

I'm not a cryptologist, just an interested engineer (& now retired). I used to design hardware with AES en/decryption blocks & generate test vectors using my own Tcl script using the embedded AES function.

However, I was wondering if modifying AES to use more than 1 SBox (& inverse), it would be "more secure", or is that not the case? I've found 1108 SBoxes that meet the original criteria (out of 256! possible combinations). My view would be to have a short table to indicate which SBox to use for each round of 14 (assuming 256 key). I realise this would complicate h/w a bit, but not be very complicated to modify a C program. Initially just using 2 SBoxes, the original & one other, but easily expandable to use 3,4.. etc in software.

Answer 1

Honestly, it would be more secure, but not by much, and that is assuming you are using finite field inversion s-boxes.

A better use of multiple 8-bit s-boxes would be to make them key dependent, however in software that can have the unfortunate side effect of creating another side channel to leak information about the key.

If you want something based on the AES design but with small modifications that make it more secure, what you want is not more s-boxes, but a better s-box with more algebraic complexity. In terms of round design that is probably the only modification you can make before it strays too much from the original design.

The other place to look is the key schedule, which is very simple and fast. This is both beneficial and detrimental, as it is probably the weakest point of the cipher, but makes applications requiring key changes usable. Think a wifi chip that needs a different key for each connected device and needs to constantly switch keys to communicate with them. It can also "roll" to save memory on embedded systems, but this means that round subkeys can be used to recover the key.

From a software only perspective, security can be improved with changes to the key schedule, slowing it down and generating the subkeys using a one way function with less linearity.

Answer 2

Constructing an octet → octet S-box as per AES $\textit{SubBytes}$ ($ \mathbf{S}=(\mathbf{A} \cdot \mathbf{B}) \oplus \mathbf{O})$, there are $2^{8}$ initial row values (associated polynomials) for the affine (circulant) matrix, $2^{8}$ possible offsets, and 30 irreducible polynomials in $GF(2^{8})$, for a universe of 1,966,080 possible S-boxes. Using Javascript, I generated and tested them all. Application can be found here.

Candidate S-box ($\mathbf{S}$) and corresponding inverse S-box ($\mathbf{S'}$) exclusion criteria:
For all input octets, $b \in \left\{0, 1, 2, ... , 255 \right\}$

$b \rightarrow S[b]$
$b \rightarrow S'[b]$
$b \rightarrow \sim S[b]$, i.e., $\left(b \oplus S[b] = 255\right)$
$b \rightarrow \sim S'[b]$
$S[b] = S'[b]$
$f: \mathbf{B} \rightarrow \mathbf{S}$ is not surjective ($f:\mathbf{S} \rightarrow \mathbf{S'}$ is not bijective)

I get 86899 valid S-boxes, or 4.4 % of potential candidates.

Of course, this is still an infinitesimal subset of the $256!$ possible 8 bit → 8-bit S-boxes (of which suitable candidates can be found by random shuffles at about 1 out of every 12 tries), but then the AES nothing-up-my-sleeve advantage disappears.

Answer 3

There is a nice tool, SBox Generator, which generates SBoxes and inverses from a given irreducible polynomial. GF($2^8$) has 30 so-called characteristic polynomials. Rijndael authors simply took the first one in the list. Think the offset (the first table entry, image of 0x00) is fix 0x63; that would be another parameter to optimize diffusion.