0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – pajacol
    Sep 27 at 17:57
  • $\begingroup$ 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. $\endgroup$
    – Sam Jaques
    Sep 27 at 18:22
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I should clarify that I meant that IVs are indeed the same and I only know the first 16 bytes of each plaintext. $\endgroup$
    – pajacol
    Sep 27 at 17: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.