Imagine a set of 256 plaintexts. All filled with 0s.

Now imagine that we choose one index in all of these 256 states, and make it take the whole range of a byte.

We'll call such a thing a Λ-set (delta set). And the index taking all of the values an active index.

Now imagine that each plaintext of the Λ-set goes through AES, gets encrypted, goes through the rounds' transformations, etc...

The first thing would be to XOR them with the first round key (pre-whitening):

And here a good observer would notice that the output of the pre-whitening round is still a Λ-set.

Now, more interesting, we'll enter the first round. The first transformation, if you remember, is SubBytes:

And as you can see, magically, the state remains a Λ-set. The second transformation, ShiftRows, will not change this fact:

MixColumns is a bit more tricky. Since the new column is created from a linear combination, it affects all the indexes of the output column. Since only one of the value is active, we can see that the first column entirely becomes active after that. And since the other columns of our Λ-set are "inactive", they will remain inactive after the transformation as well.

At the end of the first round, we now have a Λ-set with 4 active indexes.

Remember, an index is active if it takes all of the different values of a byte in a set of 256 different plaintexts. An index is inactive if it takes the same value in the whole set of plaintext. A state in the diagram above represents the whole Λ-set where the green position is active and the rest inactive.

If we analyze one more round, we can see that we still obtain a Λ-set at the end, with all indexes being active.

Add one more round on top of that (and we're now at 3 rounds) and the MixColumns transformation destroys our nice Λ-set.

But is it really the end of our journey? Not so much. Imagine taking the first unknown byte of every state in our destroyed Λ-set, right after that last MixColumns transformation, and XORing them together:

\[ b_1 \oplus\\ b_2 \oplus\\ \cdots\\ b_{256} \]

Now, let's detail this calculus. Here \( a_{i,j} \) represents the value of the byte at position \( i \) in the state \( j \) (if we were to index states) right before that MixColumns transformation.

\[ \begin{gather*} 2 a_{1, 0} \oplus 3 a_{1, 1} \oplus 1 a_{1, 2} \oplus 1 a_{1, 3}\\ \oplus \\ 2 a_{2, 0} \oplus 3 a_{2, 1} \oplus 1 a_{2, 2} \oplus 1 a_{2, 3}\\ \oplus \\ \cdots\\ \oplus\\ 2 a_{256, 0} \oplus 3 a_{256, 1} \oplus 1 a_{256, 2} \oplus 1 a_{256, 3}\\ \end{gather*} \]

Which simplifies itself to

\[ \begin{gather*} 2 (a_{0, 0} \oplus \cdots \oplus a_{256, 0})\\ \oplus\\ 3 (a_{0, 1} \oplus \cdots \oplus a_{256, 1})\\ \oplus\\ 1 (a_{0, 2} \oplus \cdots \oplus a_{256, 2})\\ \oplus\\ 1(a_{0, 3}\oplus \cdots \oplus a_{256, 3}) \end{gather*} = 2 \times 0 \oplus 3 \times 0 \oplus 1 \times 0 \oplus 1 \times 0 = 0 \]

And this works out because XORing all of the possible value of a byte is indeed \( 0 \) (which is what happened in each line up there).

We now have a relationship between the elements of our Λ-set. The AddRoundKey of this last round will not change anything, while unfortunately the beginning of the next round will. The next SubBytes operation will completely destroys this equality and any semblance of structure.

To check this hypothesis, start by creating a reduced version of AES with only 3 rounds in the encryption process (plus the pre-whitening phase).

If you finished the previous Set 1 on AES, you can clone the encrypt() function to a EncryptWithRounds() one that takes one more argument: the number of rounds. This will be useful as we will attack different reduced versions of AES from now on.

1. Create a function named setup() that takes the main key as argument (use this key: aa) and produces a Λ-set with an active byte in index 0 and the same random value in all the other byte positions. Return the encryption of each elements of that Λ-set with 3-round AES.
2. Verify that the ⊕ (XOR) of all the first bytes from the encrypted Λ-set is equal to zero.
3. Verify this property for all the other byte positions.

This nice structural property of AES allows the Square attack to trivially break 4 rounds of AES. Let's see how that works in the next step!