# Grover algorithm for AES in CBC mode

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 Pn, Cn where n is n-th pair)
2. Write down set of equations with one unknown variable - key. (Key is labeled as K)
AES-128d(C1, K) ⊕ AES-128d(C2, K) = P1 ⊕ P2
AES-128d(C3, K) ⊕ AES-128d(C4, K) = P3 ⊕ P4
AES-128d(C5, K) ⊕ AES-128d(C6, K) = P5 ⊕ P6
...
AES-128d 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-128d(C1, 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?

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).

• I meant that IVs are the same and I know only the first 16 bytes of each plaintext but the number of these 16 byte pairs is around 1000. Commented Sep 27, 2021 at 17:57
• Ah, so you would only be able to check AES-128$_d$(C$_1$, K)=IV$\oplus$ P$_1$ for each message. I think my answer would be the same, but you would use the C$_1$/P$_1$ from 2 or 3 of the 16-byte pairs. Commented Sep 27, 2021 at 18:22

$$\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.

• I should clarify that I meant that IVs are indeed the same and I only know the first 16 bytes of each plaintext. Commented Sep 27, 2021 at 17:48