One round of AES-128

Question

Maybe it’s a silly question, I’m interested in the best known/chosen plaintext attack on only one round of AES-128. More specifically, what is the smallest number of known/chosen plaintext/ciphertext pairs which allow us to recover the key with high probability? What’s the relationship between how time scales with the number of pairs?

Answer 1

Let $(m,c)$ be a couple of a plaintext and its ciphertext, and $k_0=\{k_{0,1},\ldots, k_{0,16}\}$ and $k_1=\{k_{1,1}, \ldots, k_{1,16} \}$ are the two unknowns subkeys ($k_0$ is in fact the master key).

Including the MixColumns step, then the encryption is $$ c = \mathrm{MC}(\mathrm{SR}(\mathrm{SB}(m \oplus k_0))) \oplus k_1 $$

If we apply the inverse of MC and SR, then it becomes $$ \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c)) = \mathrm{SB}(m \oplus k_0) \oplus \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1)) $$ For ease of notation, let $c' = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(c))$ and $k'_1 = \mathrm{SR}^{-1}(\mathrm{MC}^{-1}(k_1))$, then we have $$ c' = \mathrm{SB}(m \oplus k_0) \oplus k'_1 $$

Suppose you know two plaintexts $m_1$ and $m_2$ and their respective ciphertexts $c_1$ and $c_2$. To get the byte $k_{0,i}$, you make a guess $\tilde{k}_{0,i}$ and compute $$ \tilde{k}'_{1,i} = c'_{1,i} \oplus \mathrm{SB}(m_{1,i} \oplus \tilde{k}_{0,i}) $$ You do the same by replacing with $m_2$ and $c'_2$ ($m_1$ and $m_2$ should differ on every bytes) and if the obtained values $\tilde{k}'_{1,i}$ coincide, then the guess might be correct and $\tilde{k}_{0,i}$ is a candidate for $k_{0,i}$.

Other plaintexts/ciphertexts can be used to filter the candidates until one remains for each byte, or concluding with an exhaustive search.

Answer 2

UPDATE: improved attack to $2^{40}$, previous version of this answer had attack complexity $2^{48}$

I will try to improve the answer by @poncho for a single plaintext-ciphertext pair. My attack recovers the key by guessing 5 bytes and determining the others, thus the effort close to $2^{40}$ times a few operations.

Let $k_0, k_1,k_2,k_3$ denote the columns of the master key, and let $k'_0,k'_1,k'_2,k'_3$ denote the columns of $MC^{-1}$ applied to the second subkey. Also let $ct' = MC^{-1}(ct)$. In this way, we get $ct' = SR(SB(pt + k)) + k'$. Here is adapted KS picture:

We have three kinds of relations:

1. columns of $k$ related to columns of $k'$ through KS:
   • $MC(k'_2 + k'_3) = k_3;$
   • $MC(k'_1 + k'_2) = k_2;$
   • $MC(k'_0 + k'_1) = k_1;$
   • $MC(k'_0) = k_0 + w$, where $w=SubWord(RotWord(k_3))+(1,0,0,0)$ is a KS internal value;
2. bytes of $k$ related to bytes of $k'$ through $SR\circ SB$ and plaintext-ciphertext bytes (note that a column of $k'$ corresponds to a diagonal of $k$):
   • $ct_{(j-i)\mod{4}}[i] + k'_{(j-i)\mod{4}}[i] = S(pt_j[i] + k_j[i])$;
3. (given that $k'_0$ is known) bytes of $k_0$ related to bytes of $k_3$ (the fourth relation from 1. becoming bytewise).

We guess $k_0'$ and $k'_3[0]$. Now we determine all the rest.

1. Since $k_0'$ is guessed, we can use 3rd kind of relations. Together with 2nd kind, we learn a lot!

   

2. (Main trick) Let $x=k'_3[1]$ and $y=k_3[2]$ be yet unknown bytes. By chaining relations of 2nd and 3rd kinds, we connect $x$ and $y$: $$ S^{-1}(x + ct'_3[1]) + pt_0[1] = S(y) + (k_0[1] + MC(k'_0)[1]). $$ At the same time, we can connect $x$ and $y$ by a linear relation using the KS relation $MC(k'_2 + k'_3) = k_3$, where 3 bytes of $k_3$ are known: $$ x + k'_2[1] + 11 \otimes y = 9\otimes x_3[0] +14 \otimes x_3[1] + 13\otimes x_3[3]. $$ This small system with two unknowns and two equations has two constants that depend on guessed bytes. By a precomputation with complexity $2^{16}$, all solutions can be stored (indexed by the two constants). As a result, during the 5-byte guess we learn $x,y$ (a few candidates possibly) in a constant time. We propagate bytewise again.

   

3. Use $MC(k'_2 + k'_3) = k_3$ (we now know $k_3$) to learn two more bytes and propagate bytewise.

   

4. Consider the equation $MC(k'_1 + k'_2) = k_2$. We know two input and two output bytes of MC, which allows us to learn everything else, due to MC being MDS. Propagate bytewise.

   

5. The two leftover bytes can be recovered from known $k'_2 + k'_3$ and byte propagation.

6. It is left to check all the relations to dismiss occasional false positives.

SageMath code for the attack

Answer 3

corpsfini gave an efficient method for rederiving the key if you're given two plaintext/ciphertext pairs; I will look at an inefficient method that tries to rederive the key given only one such pair.

The general strategy is to guess selected key bytes within the second subkey, and then use the know relations, both from the know plaintext/ciphertext pair, and from the AES-128 key scheduling, to deduce all the bytes of the first subkey (which is the key we're looking for).

Notation I will use: $k_{a,b}^c$ will be the subkey byte from subkey $c$ (0 will be the initial, 1 will be the final) in the $a$th row and $b$th column.

So, the attack is that we initially guess the subkey bytes $k_{0,0}^1, k_{0,3}^1,k_{1,2}^1, k_{1,3}^1, k_{2,1}^1, k_{2,2}^1, k_{2,3}^1, k_{3,1}^1, k_{3,2}^1, k_{3,3}^1$. This consists of 10 bytes (and hence 80 bits).

We now proceed to check this guess (and deduce the rest of the key) in constant time (hence the total attack takes $O(2^{80})$ time)

We first note (assuming our guess is correct) we have all the second round subkey bytes for column 3; we consider AES in decryption mode on this column; we can compute the AddRoundKey and the InvMixColumns. The InvShiftRows will move the internal state bytes we know into positions $(0,3), (1,2), (2,1), (3,0)$. Then, can compute the InvSubBytes for these positions, and what we have left is known plaintext xor'ed with unknown key bytes to give us known state bytes. This allows us to deduce the values of $k_{0,3}^0,k_{1,2}^0,k_{2,1}^0,k_{3,0}^0$.

Then, if we look at the AES-128 key scheduling logic, we see that $k_{0,3}^1 = k_{0,2}^1 \oplus k_{0,3}^0$; we know $k_{0,3}^1$ and $k_{0,3}^0$, so we can deduce $k_{0,2}^1$.

Now, we know all the second round subkey bytes for column 2; similar logic gives us the first subkey bytes $k_{0,2}^0,k_{1,1}^0,k_{2,0}^0,k_{3,3}^0$, which allows us to deduce $k_{0,1}^1$ and $k_{1,1}^1$

That gives us all the second round subkey bytes for column 1; repeating this gives us the first subkey bytes $k_{0,1}^0,k_{1,0}^0,k_{2,3}^0,k_{3,2}^0$, which allows us to deduce $k_{0,0}^1, k_{1,0}^1, k_{2,0}^1$.

Along with $k_{3,3}^1$, that's the entire second round subkey; from that, it's easy to derive the first round subkey (actually, we've deduce most of the bytes from that already), and validate our guess.

Obviously, this attack can be optimized, and I have this nagging feeling that it would be possible to guess one less byte; however this is what I have at the moment.

Answer 4

There is a paper called Low Data Complexity Attacks on AES by Bouillaget et al. It describes best attacks on 1-4 rounds of AES with only 1-9 known/chosen plaintexts:

So, to answer your question: 1 round can be attacked in $2^{32}$ time with 1 known plaintext, and in $2^{12}$ time with 2 known plaintexts.