1
$\begingroup$

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 :)

$\endgroup$
4
  • 2
    $\begingroup$ You have to deal with degree 128 monomials ( on average 127) and a huge number of monomials to deal with. Courtois claimed to break AES ( meaning the complexity is less than 128-bit search) but that was highly speculative. This already has the name SAT solving. See Bard's book for samples. $\endgroup$
    – kelalaka
    Jun 19, 2021 at 7:21
  • 1
    $\begingroup$ @kelalaka SAT solving is only one method to solve such systems. What Ahmed suggests is simply linearization (which is a basic component of more advanced methods based on Gröbner basis, eXtended linearization, ElimLin, etc.). $\endgroup$
    – Fractalice
    Jun 19, 2021 at 8:35
  • $\begingroup$ @Fractalice I've used the SAT as the big term ( I see now using SAT solving causes a miss direction). GB,XL,XLS, RL, EL are all means to solve our SAT problem, especially in Cryptography. Bard already covers most of them in their book. The answer of this Q is just some papers $\endgroup$
    – kelalaka
    Jun 19, 2021 at 8:48
  • 3
    $\begingroup$ n 2003, Murphy and Robshaw discovered an alternative description of AES, embedding it in a larger cipher called "BES", use very simple operations over a single field, GF(28). An XSL attack yields a simpler set of equations that would break AES with ~2^100 comp., if the Courtois et. al analysis is correct. In 2005 Cid. et al gave evidence that, in its proposed form, the XSL algorithm does not provide an efficient method for solving the AES system of equations; however Courtois disputed their findings. At FSE 2007, Chu-Wee Lim and Khoongming Khoo showed that it cannot possibly work as presented $\endgroup$
    – kelalaka
    Jun 19, 2021 at 8:50

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.