Attacking 4 rounds with the Square attack

Remember what happened to our Λ-set after we've reached the end of 3 rounds

We do not have a Λ-set anymore, but we know that we still have some kind of special structure. If we XOR the bytes of one index from the states of our Λ-set, they will sum up to \( 0 \).

Now what would happen if we added another round on top of that? The next SubBytes transformation destroys our observations. After this, we're in the unknown.

In this section, we'll attack 4-round AES (with 128-bit keys). So you can imagine that this 4th round is the last round of our variant of AES, and as we know, since it's the last round it doesn't have the MixColumns transformation.

You might already have guessed what "good" this unkonwn brings for our cryptanalysis. And this is a theme that we will keep running into in different sorts of cryptanalysis. This unknown allows us to make a guess on the last round key and verify the guess.

There exist several types of results for a cryptanalysis. We're currently looking at a total break, which will obtain us the cipher's secret key. Other weaker results can recover the plaintext without revealing the secret key, or even just allow you to distinguish from a set of ciphertexts what cipher was used to obtain them (here we already know that we're dealing with AES).

Imagine that you make a guess for the first byte of the last round key. You can now reverse the value of the state, from each of your ciphertext (which you know, this is a chosen-plaintext attack) up until the state where we know our observations hold.

There exist several classes of attacks, which are ranked according to how much leway the attacker gets. A chosen-plaintext attack is when the attacker can encrypt any plaintexts he wants, and observe the resulting ciphertexts. A ciphertext-only attack is when an attacker only have access to a set of ciphertexts. The latter one is obviously weaker, but is ranked as a stronger attack. This is because if an attacker can use this little information to break a cipher, then his attack is pretty good :)

At this point, it's enough to XOR all of the reversed bytes at the state right before the last SubBytes to check if they XOR out to \( 0 \). If they do, you might really well have guessed the right byte for the last round key.

The point is then to find the value of the last round key byte-by-byte.

Now it's your turn!

  1. Modify your reduced version of AES to now apply 4 rounds instead of the previous 3. Remember, the last round does not make use of the MixColumns transformation. Your setup() function should now use this 4-round AES.
  2. Create a function named reverseState() that takes a key guess of one byte, the position of that key guess and the encrypted Λ-set returned by the setup() function. It should then reverse the byte at that position on every element of the Λ-set, up until the beginning of the last round. It should then return this set of reversed bytes.
  3. Create a function named checkKeyGuess() that takes the key guess of one byte and the set of byte values returned by the reverseState() function. The function should try to XOR all the given bytes and check if the result equals \(0\). If it is, you might have found a key! Display the byte guessed. Otherwise do nothing.

At this point, make sure that things work. You should test reverseState and checkKeyGuess. Use:

If checkKeyGuess() finds out that the XOR is indeed \(0\), you're good. Otherwise meditate for 5 minutes and correct your code.

You now have enough functions to code your general attack.

What you will do, to find out one byte of the last round key, is to loop through all the 256 possible values of that byte and feed them to your freshly created functions.
But because an invalid guessed key byte might sometimes gives you a false positive, you will want to test all of them before taking a conclusion.

For this, you will have to modify your checkKeyGuess() function to keep track of what guess seem valid or not.

  1. Loop through all the possible byte for a given index and validate each guess. When a valid guess is found, update a list to keep track of what guesses are valid so far.

  2. Create a function that checks if there is more than one valid byte guess in the list. If there is only one valid key guess, then you've found the real key byte of the last round key at this position.
    If you have more than one valid key guess, you need to test the remaining valid bytes of your list with a new encrypted Λ-set. Remember: you can use the setup() function for that: it is supposed to generate a random Λ-set at every call. Do this until only one guess remains in your list.
  3. Now that you have the algorithm working for finding one byte of the last round key, iterate it over all the byte positions of the last round key until you found all of them. The algorithm should be really fast. (On my year old device it runs in one second.)

Make sure to test the values you obtain. The next section will show you how to obtain the main secret key from this last round key.

Next