Grover algorithm for AES in CBC mode

Question

Hello,
I was wondering whether it is theoretically possible to use Grover alrogithm to break AES in CBC mode. Assume that I have ~1000 plaintext/ciphertext pairs and key length is 128 bits. I thought about it this way:

1. For each pair of plaintext and ciphertext use only first 16 bytes of plaintext and first 16 bytes of ciphertext. (They will be labeled as P_n, C_n where n is n-th pair)
2. Write down set of equations with one unknown variable - key. (Key is labeled as K)
   AES-128_d(C₁, K) ⊕ AES-128_d(C₂, K) = P1 ⊕ P2
   AES-128_d(C₃, K) ⊕ AES-128_d(C₄, K) = P3 ⊕ P4
   AES-128_d(C₅, K) ⊕ AES-128_d(C₆, K) = P5 ⊕ P6
   ...
   AES-128_d is AES-128 decryption function
   ⊕ is XOR
3. Use Grover algorithm to find K from the equations given above. If key is found determining IV is easy by using this equation:
   AES-128_d(C₁, K) = P1 ⊕ IV

Can Grover algorithm be used to invert set of equations from step 2? How many plaintext/ciphertext pairs would I need to uniquely dertermine key and IV for keylengths of 128, 192 and 256 bits?

Answer 1

Grover's algorithm would work against CBC. Do you mean you have several thousand plaintext/ciphertext messages, each with their own IV?

I'm not sure what you're doing in step 2. I think generally the IV is considered part of the ciphertext, so if you have the ciphertext, you have the IV, and then you end up with equations like:

AES-128$_d$(C$_1$, K) = IV $\oplus$ P$_1$

AES-128$_d$(C$_2$, K) = C$_1 \oplus$ P$_2$

etc.

For Grover's algorithm, since you know the right-hand side, and you know the input to the AES decryption, you could search over the space of K and, for the oracle, use a circuit to perform AES decryption of C$_1$, C$_2$, etc. and compare to the value on the right-hand side.

For near certainty that the returned value K is correct, you will need only 2 blocks for AES-128 (i.e., just C$_1$ and C$_2$ of one message), 2 blocks for AES-192, and 3 blocks for AES-256. Generally, if you use $r$ blocks, each with $n$ bits and with a key of $k$ bits, the probability that Grover's search will find the correct key is about $e^{-2^{k-rn}}$. So if $k < rn$, you're basically guaranteed the correct result (see the "Spurious keys" section on page 4 of this paper for a derivation).

Answer 2

$\text{AES-128}_d(C_1, K) \oplus \text{AES-128}_d(C_2, K) = P_1 \oplus P_2$

Doesn't that assume that the two ciphertexts share the same IV? Typically, they don't.

In any case, even if you don't know any of the IVs, then a simpler method would be if you have a known two block message with plaintext $(P_a, P_b)$ and a corresponding ciphertext $(C_a, C_b)$, then

$$\text{AES-128}_e(P_b \oplus C_a, K) = C_b$$

This holds no matter what IV was used.

Can Grover algorithm be used to invert set of equations from step 2?

I suppose. However, if all you have is a series of single block messages, you have to assume that all IVs are the same. If they are unknown and random, then you can't deduce anything.