8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ My guess would be that you can probably get away with 2 plaintext-ciphertext pairs, perhaps you need like 10. Computational effort should be around $16\cdot 2^{16}=2^{20}$ operations. $\endgroup$ – SEJPM May 17 at 14:38
  • $\begingroup$ What’s the intuition behind 2 pairs? $\endgroup$ – zz7948 May 17 at 15:19
  • $\begingroup$ That you need to identify two subkeys. Hmm thinking about it perhaps the key schedule gives enough constraints to drop it to one. $\endgroup$ – SEJPM May 17 at 15:30
  • 1
    $\begingroup$ Are two subkeys involved or only one? That is, do we assume there's an AddRoundKey after the round? If not, obviously one plaintext-ciphertext pair would suffice (and the attack is obvious). If there is, then you'd need two (and the attack is nearly as trivial; circa $2^{12}$ work effort) $\endgroup$ – poncho May 17 at 15:58
  • $\begingroup$ So, something like express plaintext and ciphertext in terms of equation involving subkeys, use key schedule to express 1st round key in terms of key, this gives equation for key. Solving this equation is about 2^(20)? $\endgroup$ – zz7948 May 17 at 16:02
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ There needs to be some clean-up in the end; sometimes, there will be multiple possible solutions for $\tilde{k}_{0,i}, \tilde{k}_{1,i}$ (or worse yet, the two plaintext have the same byte in position $i$, in which case there are 256 possible solutions. Generally, it should be fairly easy to derive the correct one based on the key scheduling (the round 1 subkeys are a simple function of the round 0 subkeys); but that step generally will need to be done... $\endgroup$ – poncho May 17 at 18:44
  • $\begingroup$ Yes you are right, there might be some false positives, and $m_1$ and $m_2$ should differ on every bytes. $\endgroup$ – corpsfini May 17 at 18:52
  • $\begingroup$ Thanks, nice answer. So the fast time relies on being able to guess and verify bytes one by one? If it were possible to guess and verify bits one by one, we could do faster? $\endgroup$ – zz7948 May 18 at 3:57
  • $\begingroup$ @zz7948 Yes, we can target the bytes one by one independantly from the others since one round doesn't mix things enough. You can do similar things up to a few rounds: look for ``square attacks'' on AES. I don't think you can do bits one by one since an S-box applies on the whole byte. $\endgroup$ – corpsfini May 18 at 11:07
4
$\begingroup$

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:

Key Schedule Round

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.

Initial guess

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

    Propagated bytes

  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.

    Magic system

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

    Simple linear

  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.

    Linear magic

  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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Very good; my solution missed the part in step 3; where you get to deduce 4 subkey bytes... $\endgroup$ – poncho Aug 26 at 14:20
  • $\begingroup$ @poncho managed to reduce it to 5 bytes guess, by precomputing solutions to a simple relation pair. pastebin.com/wWi3mRi3 $\endgroup$ – Fractalic Aug 26 at 17:28
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Have you thrown it at a SAT solver? $\endgroup$ – fgrieu May 18 at 14:50
  • 1
    $\begingroup$ @fgrieu: no, on the other hand, given the complexity of an sbox (expressed as a binary circuit), I wouldn't be that optimistic. On the other hand, if you express the problem in terms of known relationships ("if you know these 4 bytes of key, you learn these other 2"), possibly a computerized search would find something more efficient $\endgroup$ – poncho May 18 at 17:49
  • $\begingroup$ @poncho, great Thanks for this. Just checking I understand whats going on: we construct a Number of equations with variables corresponding to the key and coefficients with known plaintext/ciphertext. By xoring combinations of these equations with each other we try to remove variables and end up with a small Number of equations in a small Number of variables. We then guess key bytes to remove more variables until we can recover a solution quickly? $\endgroup$ – zz7948 May 20 at 10:37
  • $\begingroup$ @zz7948: well, no, that's not how I'd express it. Instead, we have the case where is we know some of the subkey bytes, we can deduce others (I don't want to express them as "equations" as some of the relations go through an sbox and are hence nonlinear, that is, not amenable to solving as equations). What I show is a group of 10 bytes that, through a series of deductions, gives us all 32 (and hence the key). We still end up guessing all 10 $\endgroup$ – poncho May 20 at 12:10
  • $\begingroup$ @poncho Okay, but in principle as an equation. Since SBox is modular inverse, once we have a relation between between all these things we can multiply by certain key bytes to clear all modular inverses which gives some polynomial equations over a field of size 256. $\endgroup$ – zz7948 May 20 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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