Why is it not possible to attack an AES by creating a function to model the substitution that occurs in a s-box?

Question

I realise that s boxes are able to make the transformations done in AES non-linear. However I am unsure how this makes AES secure. For instance if we had no s box then it is possible to calculate the key from a set of linear equations:

$C^1=Ax+k$

$C^2=AC^1+k$

...

$y=AC^n+k$

Where A is the linear transformation, k is the key, C as the intermediate ciphertexts, n as the number of rounds of encryption, x as the input and y as final output. However, if we add an S box, then would it not be possible to represent the substitution that it performs as a function of x, f(x), so that now we have:

$C^1=Af(x)+k$

$C^2=Af(C^1)+k$

...

$y=Af(C^n)+k$

Which to me appears to also fall prey to Gaussian elimination(via substituting each equation into the function of the next), although such a function for the substitution that occurs in s boxes may be extremely complicated to derive. Provided we are given a few x values that undergo encryption using the same key, and that the s boxes are publicly known we ought to be able to calculate the key. I realise that in reality this cannot happen otherwise AES would not be used at all, so I would be very grateful for any help in identifying where I have gone wrong/how the S boxes would interfere to prevent such method occurring :)

Answer 1

If I understood correctly, you suggest to treat intermediate values $C^i$ as variables.

The problem is that $f(C^i)$ is nonlinear and contains more monomials than the 128 variables (since nonlinearity comes from the S-box, the number of monomials is at most $256\times16$). Therefore, it is not possible to eliminate it using the equation $C^i = ...$, and $C^i$ is not used anywhere else. Note that if you add more plaintext/ciphertext values, the variables $C^i$ are not the same, so you can not use another pair to eliminate those extra monomials. Instead, more variables are added.

Note that the S-box has a weakness in that there exist quadratic equations (over $GF(2)$) connecting its input and output (instead of direct degree-7 equations of the S-box), which simplifies the system a lot. However, still, nobody managed to show a way to solve such or similar system faster than the AES key bruteforce.

For the record, the source of the quadratic equations is that the S-box is affine-equivalent to the $GF(256)$ inverse function $y=x^{254}$. We have $yx^2=x^{256}=x$ and so $yx^2-x=0$, which is quadratic over $GF(2)$ (splits into 8 equations).