Join Log in
Score:0
pajacol avatar Crypto

Grover algorithm for AES in CBC mode

in flag
pajacol

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?

99
0 + 0
aes
cbc
Score:0
Sam Jaques avatar Crypto
us flag
Sam Jaques

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

0 + 0
pajacol avatar
in flag
pajacol
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.
0
Reply
Sam Jaques avatar
us flag
Sam Jaques
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.
0
Reply
Score:0
poncho avatar Crypto
my flag
poncho

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

0 + 0
pajacol avatar
in flag
pajacol
I should clarify that I meant that IVs are indeed the same and I only know the first 16 bytes of each plaintext.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.