# How does non-linearity (S-box) add security to AES?

I'm trying to understand how AES guarentees security. One of the named points on the web is that AES uses a non-linear step (the SubBytes step). But how exactly does the Rijndael key schedule add security? It sounds like a wide question, but for me, not exactly an expert, it's hard to understand.

Help is appreciated

• The title asks how non-linearity (S-box) adds security. The body of the question adds how the Rijndael key schedule adds security. Please clarify what's asked. Do you understand how, regardless of the key schedule's output, non-linearity is essential for security of AES? – fgrieu Nov 24 '15 at 16:48
• I said that because the non-linearity (S-box) is part of the Rijndael key schedule. No, I don't understand. – Thomas W Nov 24 '15 at 16:49
• The non-linearity is also, and foremost, part of the encryption itself. In the formal specification of AES by NIST, FIPS 197, SubBytes is not even part of the key schedule (the corresponding non-linear operation is called SubWord). Hint to answer your own question without the key schedule part of it: assume that a function $f$ is said to be linear iff $\forall (x,y,z), f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$. What can you say about the composition of linear functions? – fgrieu Nov 24 '15 at 17:13
• @fgrieu Even without the ambiguous context I find the question of how the key schedule adds security to be quite ironical given that the key schedule appears to be the weakest part of AES. – kasperd Apr 10 '16 at 12:53