Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation

Abstract

We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition). We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption. And we give proofs that CBC and CFB mode are secure if we assume a quantum secure PRF (secure under queries in superposition).

1 Introduction

Block ciphers are one of the most fundamental primitives in cryptography. On its own, however, a block cipher is almost useless because it can only encrypt messages of a fixed (and usually very short) length. Therefore block ciphers are usually used in so-called “modes of operation”: constructions whose goal it is to extend the message space of the block cipher, and possibly add other features or more security in the process. Since most encryption in practice uses at some level a mode of operation, the security of those modes of operation is of paramount importance for the security of many cryptographic systems.

In the light of the possible advent of quantum computers,¹ we have to ask: is existing classical cryptography also secure in the presence of attackers with quantum computers? In particular, does the security of common modes of operation break down?

In this paper, we study a number of common modes of operation, namely those listed in the 2013 ENISA² report on recommended encryption algorithms [9]: CBC, CFB, OFB, CTR, and XTS. We study whether those modes are secure in the quantum setting under comparable assumptions as in the classical setting, and if not, we construct counterexamples.

The aforementioned modes of operation (except ECB and XTS) are known to be IND-CPA secure in the classical setting, under the assumption that the underlying block cipher is a pseudo-random function (PRF).³ ECB is known not to have reasonable security for most applications, while the security of XTS is an open question.

In the quantum case, there are two variants of the IND-CPA notion: “standard IND-CPA” and “IND-qCPA”. While standard IND-CPA lets the quantum adversary perform only classical encryption queries, IND-qCPA (as defined by [6]) allows the adversary to perform quantum encryption queries (i.e., queries which are a superposition of different messages, to get a superposition of different ciphertexts). In other words, IND-qCPA additionally guarantees security when the encryption key is used to encrypt messages in superposition. (See below for a discussion on the relevance of this notion.)

Similarly, there are two variants of the notion of a classical PRF in the quantum setting: standard secure PRF and quantum secure PRF. In the first case, the function cannot be distinguished from a random function when making arbitrary classical queries to that function. In the second case, the function cannot be distinguished from random when making arbitrary quantum queries, i.e., when querying the function on a superposition of many inputs.

We can now ask the question: which variant of quantum PRFs is needed for which variant of IND-CPA. As it turns out, if we merely wish to get standard IND-CPA security, the answer is trivial: CBC, CFB, OFB, and CTR are secure assuming that the underlying block cipher is a standard PRF. In fact, the original security proofs of these schemes can be reused unmodified.⁴ (We hence abstain from reproducing the original proofs in this paper and refer to the classical proofs instead.) And ECB is still trivially insecure, and for XTS we still do not know which security we achieve.

On the other hand, if we ask for IND-qCPA security, the picture changes drastically. OFB and CTR mode can be shown IND-qCPA secure based on a standard secure PRF. (The proof is relatively straightforward.)

In contrast, we prove that CBC and CFB are not IND-qCPA secure based when based on a standard secure PRF. In fact, for CBC and CFB we show that the adversary can even recover the secret key using quantum queries. For XTS, we show that the adversary can recover the second half of a plaintext if he can provide the first half of the plaintext (and the adversary can get half of the key). Although this does not formally contradict IND-qCPA (because IND-qCPA does not allow the challenge query to be performed in superposition), it show that XTS does not satisfy the intuitive notion of CPA security under superposition attacks.

If, however, the block cipher is a quantum secure PRF, then CBC and CFB are IND-qCPA secure. The proof of this fact, however, is quite different from the classical security proof: since the block cipher is invoked in superposition, we are in a situation similar to the analysis of quantum random oracles, which are notoriously difficult to handle in the quantum case. (Note: this refers only to the difficulties encountered in our proof. Our results are in the standard model, not in the random oracle model.)

We summarize the results in Table 1. Our counter-examples are in the quantum random oracle model, but our positive results are in the standard model (no random oracle).

Table 1. Summary of our results. The superscripts refer to the bibliography or to theorem numbers. “No in spirit” means that there is an attack using superposition queries that does not formally violate IND-qCPA.

On the IND-qCPA Security Notion. The IND-qCPA security notion [6] models passive security against adversaries that have access to the encryption of (chosen) plaintexts in superposition. The obvious question is: do we need that?

• The most obvious reason is that in the future, we might want to encrypt messages in superposition for some legitimate purpose. E.g., the encryption scheme is used as part of a quantum protocol. (That is, a protocol that actively uses quantum communication, not just a classical protocol secure against quantum adversaries.)

• A second argument (made in [7]) is that with continuing miniaturization, supposedly classical devices may enter the quantum scale, and thus “accidentally” encrypt messages in superposition. (Personally, we have doubts how realistic this case is, but we mention it for completeness.)

• There is, however, a reason why insecurity under notions such as IND-qCPA may affect the security of a purely classical system in the presence of a quantum attacker. If a classical protocol is proven secure (with respect to a quantum adversary), intermediate games in the security proof may actually contain honest parties that run in superposition. This happens in particular if zero-knowledge proof systems or similar are involved [12, 15]. For example, in [13, Sect. 5], the security proof of a classical protocol did not go through because the signature scheme was not secure under quantum queries (they had to change the protocol considerably instead). Encryption schemes that are not just standard IND-CPA, but IND-qCPA might help in similar situations.

1.1 Our Techniques

We briefly summarize the techniques we use to prove or disprove the security of the various modes of operation.

IND-qCPA Security of OFB and CTR Mode Using a Standard PRF. Both OFB and CTR mode are stream ciphers. That is, in both cases, encryption can be represented as $\mathsf {Enc}_k(M)=G_k(|M|;r)\oplus M$, where $G_k$ is a pseudorandom generator with key k for some randomness r. Thus, to encrypt a superposition $\sum _i \alpha _i{\left| {M_i}\right\rangle }$ of messages of length $\ell$, all we need to do is to compute $c:=\mathsf {Enc}_k(0)=G_k(\ell ;r)$, and then to compute $\sum _i\alpha _i{\left| {\mathsf {Enc}_k(M_i;r)}\right\rangle }=\sum _i\alpha _i{\left| {M_i\oplus c}\right\rangle }$. Since computing $\mathsf {Enc}_k(0)$ can be done using a classical encryption query, it follows that superposition encryption queries can be simulated using classical encryption queries. Hence the IND-qCPA security of OFB and CTR can be directly reduced to the standard IND-CPA security of the same schemes. And standard IND-CPA security is shown exactly in the same way as in the classical setting.

IND-qCPA Security of CBC and CFB Mode Using a Quantum Secure PRF. To show security of CBC and CFB mode, we cannot directly follow the classical security proof since that one relies inherently on the fact that the block cipher (the PRF) is queried only classically. Instead, we use the following techniques to prove CBC security:

Fig. 1.

(a) CBC mode (using a random function H instead of the block cipher). (b) Modified challenge ciphertext computation ($c_1$ replaced by randomness). We need to prove that replacing $c_2$ by a random value leads to an indistinguishable view.

• Since the block cipher is a PRF, we can assume it to be a truly random function H (to which the adversary has no access, since he does not know the key). CBC encryption is thus performed as sketched in Fig. 1(a).

• We replace the challenge encryption (i.e., the encryption query where the adversary should distinguish between $\mathsf {Enc}(m_0)$ and $\mathsf {Enc}(m_1)$) step by step by randomness. That is, we consider a sequence of hybrid games, and in the i-th game, the first i blocks of the challenge ciphertext are replaced by uniformly random bitstrings. Once all ciphertext blocks are replaced by randomness, the probability of guessing whether $m_0$ or $m_1$ was encrypted is obviously $\frac{1}{2}$. Thus, all we need to show is that replacing one block of the challenge ciphertext by randomness leads to a negligible change in the advantage of the adversary. The situation is depicted in Fig. 1(b).

• Say we want to show that $c_2=H(m_2\oplus c_1)$ is indistinguishable from random (the situation in Fig. 1(b). At a first glance, this seems simple: $m_2\oplus c_1$ is uniformly random, so the probability that it collides with other H-queries is negligible, hence $H(m_2\oplus c_1)$ is uniformly random. However, this argument does not hold in the quantum setting: since some encryption queries are performed in superposition, it can be that H was queries on all inputs simultaneously, hence we cannot say that H was not queried at $m_2\oplus c_1$ before. Fortunately, we can use the “One-way to Hiding (O2H) Lemma” from [14] here. This lemma basically says: for a uniformly random x, to show that H(x) is indistinguishable from random, we need to show: when running the adversary, and aborting at a randomly chosen H-query, and measuring the input to that query (disturbing the superposition), then the probability that the outcome is x is negligible.

  In the present setting this means: if we measure a random H-query during the execution of the IND-qCPA game, the probability that the argument equals $m_2\oplus c_1$ is negligible. For example, the probability that one of the h-queries before the challenge encryption equals $m_2\oplus c_1$ is trivially negligible, because $c_1$ has not yet been chosen at that point.

• For the H-queries performed during the challenge query, we use the fact that H is indistinguishable from a random permutation [18]. In that case, the H-query inputs are uniformly random due to the fact that $c_2$ is chosen uniformly at random (remember that we replaced $c_2$ by a random value), hence they collide with $m_2\oplus c_1$ only with negligible probability.

• For the H-queries performed after the challenge query, we cannot use the same argument, because those queries can be performed in superposition. However: if we only care whether the chosen H-query has input $m_2\oplus c_1$, then, instead of just measuring the H-query input, we can measure in the computational basis all registers involved in the encryption. Then we observe that measuring all registers commutes with the operations performed during encryption, so equivalently we can assume that that measurement happens at the beginning of the encryption (and in particular measures the plaintext). And that means, for the purposes of bounding the probability of measuring H-query input $m_2\oplus c_1$, we can assume that we encrypt a classical plaintext. From here, the argument from the previous item applies.

• Altogether, the probability of measuring $m_2\oplus c_1$ in any H-query is negligible. Then the O2H lemma implies that the $H(m_2\oplus c_1)$ is indistinguishable from random. And by iterating this indistinguishably, we can replace the whole challenge ciphertext by randomness. And then the adversary has only probability $\frac{1}{2}$ of guessing which challenge plaintext was encrypted.

This shows that CBC mode is IND-qCPA secure if the block cipher is a quantum secure PRF. The security of CFB mode is shown very similarly.

Insecurity of CBC and CFB Mode Using a Standard Secure PRF. To show that CBC and CFB mode are insecure using a standard secure PRF, we first construct a specific block cipher $\mathsf {BC}$ as follows:

where E is a standard secure PRF and H refers to a random oracle. (This construction is not really a block cipher because it is not infective and hence not decrypt able. The definition of $\mathsf {BC}_k$ can be refined to make it decryptable, we omit this technicality in this proof overview, see Sect. 3.1.) This block cipher has the special property of being $k\Vert 1$-periodic: $\mathsf {BC}_k(x)=\mathsf {BC}_k(x\oplus (k\Vert 1))$. In particular, this it cannot be a quantum secure PRF, even if E is. Namely, given superposition access to $\mathsf {BC}_k$, Simon’s algorithm [11] allows us to recover $k\Vert 1$ given quantum oracle access to $\mathsf {BC}_k$.⁵ This idea also allows us to break CBC mode when CBC mode uses $\mathsf {BC}_k$ as its underlying blockcipher. If we encrypt a single block message m using CBC, we get the ciphertext $(c_0,\mathsf {BC}_k(c_0\oplus m))$. Although the message m is XORed with the random IV $c_0$, the period remains the same, namely $k\Vert 1$. Thus, using what is basically Simon’s algorithm, using superposition queries to CBC mode, we get $k\Vert 1$ (more precisely, one bit of information about it for each superposition query). This reveals the key k completely and in particular shows that CBC is not IND-qCPA secure.

The question of course is whether $\mathsf {BC}_k$ is indeed a standard secure PRF. Even though the adversary has only classical access to $\mathsf {BC}_k$, the proof cannot be purely classical: we use a random oracle H that the adversary can query in superposition. Instead, we use again the O2H lemma [14] mentioned above. This allows us to replace H(k) by a random key y in the definition of $\mathsf {BC}_k$. Now the analysis of $\mathsf {BC}_k$ becomes purely classical and basically amount to showing that the adversary cannot guess two inputs to $\mathsf {BC}_k$ that lead to the same input for $E_y$. (Using the actual, decryptable construction of $\mathsf {BC}_k$, this proof becomes technically a bit more complex, but still follows the same ideas.)

In the case of CFB mode, the attack is similar, except that here we need to encrypt two-block messages in order to get a ciphertext that depends in a $k\Vert 1$-periodic way on the plaintext. (Since the first message block is not fed through the block cipher in CFB mode.)

Insecurity of XTS Mode Using a Standard Secure PRF. To attack XTS, we use the same basic idea as for CBC and CFB. However, there are some additional complications. In XTS, two keys $k_1,k_2$ are used. Each ciphertext block is computed as $c_i:=\alpha ^{i-1}L \oplus \mathsf {BC}_{k_2}(\alpha ^{i-1}L\oplus m_i)$. Here $L:=\mathsf {BC}_{k_1}(I)$ is a secret value that is derived from a nonce I (thus L stays fixed throughout one encryption operation, but changes from ciphertext to ciphertext). If we use the block cipher constructed above (when breaking CBC), we can easily derive $k_2$: since $\mathsf {BC}_{k_2}$ is $k_2$-periodic, so is $\mathsf {BC}_{k_2}(\alpha ^{i-1}L\oplus m_i)$. Thus with one single block encryption we would be able to retrieve one bit of $k_2$ using Simon’s algorithm. However, retrieving $k_2$ does not help us in decrypting XTS mode, since we do not know $k_1$, and hence cannot compute the value L. Also, the fact that $\mathsf {BC}_{k_1}(I)$ is $k_1$-periodic does not help us to retrieve $k_1$ since we do not have any control over I. Instead, we use the following trick. We construct

where $f_k$ is a suitable function depending on k (with the property that $\mathsf {lastbit}($ $f_k(\cdot ))$ $=1$). (We interpret message blocks are pairs x, y by splitting them in the middle.) Again we ignore in this proof overview that $\mathsf {BC}_k$ cannot be decrypted, the more involved construction given in the full version [2] avoids this problem.

Now $\mathsf {BC}_k$ is k-periodic in x, and $f_k(x)$-periodic in y for fixed first input x. Using this block cipher, we can first use the attack technique described for CBC mode to recover $k_2$ (by encrypting a number of one block messages). The main difference is that now we create a plaintext that is a superposition in the first half of the block (x), and fixes the second block ($y:=0$). Now, instead of recovering $k_1$ (which seems impossible), we can recover the message L used during a given encryption query: We encrypt a message where the x-part of each block is 0, and the y-part of each block is the superposition of all messages. Since $\mathsf {BC}_{k_2}$ is invoked with $\alpha ^{i-1}L\oplus m_i$ when encrypting $m_i$, we have that the first half of the input to $\mathsf {BC}_{k_2}$ is the first half of $\alpha ^{i-1}L$. Thus $\mathsf {BC}_{k_2}$ is $f_{k_2}( firsthalf (\alpha ^{i-1}L))$-periodic. Thus from message block i, using Simon’s algorithm, we get one bit of $f_{k_2}( firsthalf (\alpha ^{i-1}L))$. Since we know $k_2$, this reveals one bit of information about $\alpha ^{i-1}L$. Thus we get a bit each about many different $\alpha ^{i-1}L$ (for different i), and this allows us to compute L. If our ciphertext, in addition to the superposition-message-blocks contains parts that are unknown, we can then decrypt those using our knowledge of L and $k_2$. (Note that we cannot use this knowledge to decrypt another ciphertext, since each ciphertext uses a different L.) Thus, we can decrypt ciphertexts whose plaintexts are partially under our control (and in superposition), and partially unknown.

1.2 Related Work

Boneh et al. [4] have argued the requirement of quantum-accessible random oracle model to prove post-quantum of BR encryption scheme introduced in [3]. They have proved the CCA security of hybrid encryption scheme introduced in [3] in the quantum random oracle model. Ebrahimi and Unruh in [8] prove the CCA security of Fujisaki-Okamoto transform in the quantum random oracle model. In [5] Boneh and Zhandry construct the first message authentication codes (MACs) that are existentially unforgeable against a quantum chosen message attack and show that quantum-secure PRF leads to quantum-secure MACs. In [7], Damgård et al. study secret sharing scheme and multiparty computation where the adversary make ask superposition queries. They also examine the zero knowledge protocols and use the secret sharing results to design zero knowledge proofs for all of NP in the common reference string model.

1.3 Organisation

In Sect. 2 we provide the various security definitions and lemmas used throughout the paper. Section 2.1 contains the definition of all the modes of operations discussed. In Sect. 3.1, we provide the a standard-secure construction of a PRF used in CBC the and CFB attack. Section 3 describes the attack on the CBC mode of operation based on that standard-secure PRF. (The insecurity of CFB and XTS are deferred to the full version [2].) Finally, in Sect. 4 we show how to achieve the IND-qCPA security for OFB, CTR, CBC, and CFB modes of operation.

2 Notation and Tools

Notation. By $x\leftarrow A(y)$ we denote an algorithm A that takes an input y outputs a value that is assigned to x. We write $x\leftarrow A^H(y)$ if A has access to an oracle H. By $(A\leftarrow B)$ we refer to the set of all functions from A to B. $x\xleftarrow {\$}A$ represents an x which is uniformly randomly chosen from the set A. $\{0,1\}^n$ represents the bit-strings of length n and $a\Vert b$ for strings a and b represents the concatenation of two strings. For two vectors a and b, $a\odot b$ denotes the dot product between two vectors. We use $\eta (t)$ to denote a function with a security parameter t. If we say a quantity is negligible(denoted negl.) we mean that it is in $o(\eta ^c)$ or $1 - o(\eta ^c)$ for all $c > 0$. We use the notation $A\approx B$ to say that quantity A has negl. difference with quantity B. For an $n-$bit string a and binary variable b, $a\cdot b = a$ if $b = 1$ otherwise $a\cdot b = 0^n$. For a string $x=x_1x_2x_3\cdots x_n$ where $x_i$ is the $i-th$ bit we use functions $\mathsf {lastbit}$ and $\mathsf {droplastbit}$ such that $\mathsf {lastbit}(x)=x_n$ and $\mathsf {droplastbit}(x)=x_ix_2\cdots x_{n-1}$.

Definition 1

(IND-CPA). A symmetric encryption scheme $\varPi = (\mathsf {Gen},\mathsf {Enc},$ $\mathsf {Dec})$ is indistinguishable under chosen message attack (IND-CPA secure) if no classical poly-time adversary $\mathcal {A}$ can win in the $PrivK^{CPA}_{\mathcal {A},\varPi }(t)$ game, except with probability at most 1/2 + negl:

• $\pmb {PrivK}^{\pmb {CPA}}_{\pmb {\mathcal {A},\varPi }}(t)$ game:

  • Key Gen: The challenger picks a random key $k\leftarrow \mathsf {Gen}$ and a random bit b.

  • Query: Adversary $\mathcal {A}$ chooses two messages $m_{0},m_{1}$ and sends them to the challenger. Challenger chooses $r\xleftarrow {\$}\{0,1\}^{*}$ and responds with $c^{*} = \mathsf {Enc}_{k}(m_{b};r)$.

  • Guess: Adversary $\mathcal {A}$ produces a bit $b'$, and wins if b = $b'$.

Definition 2

(IND-qCPA [6]). A symmetric encryption scheme $\varPi$ = (Gen,Enc, Dec) is indistinguishable under quantum chosen message attack (IND-qCPA secure) if no efficient adversary $\mathcal {A}$ can win in the $PrivK^{qCPA}_{\mathcal {A},\varPi }(t)$ game, except with probability at most 1/2 + negl:

• $\pmb {PrivK}^{\pmb {qCPA}}_{\pmb {\mathcal {A},\varPi }}(t)$ game:

  • Key Gen: The challenger picks a random key k and a random bit b.

  • Queries

    • - Challenge Queries: $\mathcal {A}$ sends two messages $m_{0},m_{1}$ to which the challenger responds with $c^{*} = \mathsf {Enc}_{k}(m_{b};r)$.

    • - Encryption Queries: For each such query, the challenger chooses randomness r, and encrypts each message in the superposition using r as randomness:

      

  • Guess: $\mathcal {A}$ produces a bit $b^{'}$, and wins if b = $b^{'}$.

Definition 3

(Standard-Security [17]). A function PRF is a standard-secure PRF if no efficient quantum adversary $\mathcal {A}$ making classical queries can distinguish between a truly random function and a function $\textsf {PRF}_{k}$ for a random k. That is, for every such $\mathcal {A}$, there exists a negligible function $\epsilon = \epsilon (t)$ such that

Definition 4

(Quantum-Security [17]). A function PRF is a quantum secure PRF if no poly-time quantum adversary $\mathcal {A}$ making quantum queries can distinguish between truly random function and the function PRF $_{k}$ for a random k.

Lemma 1

(One Way to Hiding (O2H) [14]). Let $H: \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ be a random oracle. Consider an oracle algorithm $A_{O2H}$ that makes at most $q_{o2h}$ queries to H. Let B be an oracle algorithm that on input x does the following: pick $i\xleftarrow {\$}\{1,\ldots ,q_{o2h}\}$ and $y\xleftarrow {\$}\{0,1\}^{t}$, run $A_{O2H}^{H}(x,y)$ until (just before) the $i-th$ query, measure the argument of the query in the computational basis, output the measurement outcome. (When $A_{O2H}$ makes less than i queries, B outputs $\bot \notin \{0,1\}^{t}$.) Let,

Then,

2.1 Modes of Operation

Definition 5

(ECB Scheme). For a given permutation $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{ECB}= (\mathsf {Gen},\mathsf {Enc}, \mathsf {Dec})$ as follows:

$\mathsf {Gen}$: Pick a random key $k\xleftarrow {\$}\mathcal {K}$.

$\mathsf {Enc}$: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\mathsf {Enc}_{k}(M) := c_{1}\cdots c_{n}$, where $c_{i} = E(k,m_{i})$ for $0<i\le n$.

$\mathsf {Dec}$: For a given cipher-text $C = c_{1}\cdots c_{n}$ and key k; $\hat{m_{i}}:= E^{-1}(k,c_{i})$ for $0<i\le n$.

Definition 6

(CBC Scheme). For a given permutation $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{CBC}=(\textsf {Gen,Enc,Dec})$ as follows:

Gen: Pick a random key $k\xleftarrow {\$}\mathcal {K}$.

Enc: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\textsf {Enc}_{k}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{0}\xleftarrow {\$}\{0,1\}^{t}$ and $c_{i} = E(k,m_{i}\oplus c_{i-1})$ for $0<i\le ~n$.

Dec: For a given cipher-text $C = c_{0}c_{1}\cdots c_{n}$ and key k; $\hat{m_{i}}:= E^{-1}(k,c_{i})\oplus c_{i-1}$ for $0<i\le n$.

Definition 7

(CFB Scheme). For a given function $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{CFB}=(\mathsf {Gen},\mathsf {Enc},\mathsf {Dec})$ as follows:

$\mathsf {Gen}$: Pick a random key $k\xleftarrow {\$}\mathcal {K}$.

$\mathsf {Enc}$: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\mathsf {Enc}_{k}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{0}\xleftarrow {\$}\{0,1\}^{t}$ and $c_{i} = E(k,c_{i-1})\oplus m_{i}$ for $0<i\le ~n$.

$\mathsf {Dec}$: For a given cipher-text $C = c_{0}c_{1}\cdots c_{n}$ and key k; $\hat{m_{i}}:= E(k,c_{i-1})\oplus c_{i}$ for $0<i\le n$.

Definition 8

(OFB Scheme). For a given function $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{OFB}=(\mathsf {Gen},\mathsf {Enc},\mathsf {Dec})$ as follows:

$\mathsf {Gen}$: Pick a random key $k\xleftarrow {\$}\mathcal {K}$.

$\mathsf {Enc}$: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\mathsf {Enc}_{k}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{0}=r_0 \xleftarrow {\$}\{0,1\}^{t}$, $r_i=E(k,r_{i-1})$ and $c_{i} = r_i\oplus m_{i}$ for $0<i\le n$.

$\mathsf {Dec}$: For a given cipher-text $C = c_{0}c_{1}\cdots c_{n}$ and key k; $\hat{m_{i}}:= E(k,c_{i-1})\oplus c_{i}$ for $0<i\le n$.

Definition 9

(CTR Scheme). For a given function $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{CTR}=(\mathsf {Gen},\mathsf {Enc},\mathsf {Dec})$ as follows:

$\mathsf {Gen}$: Pick a random key $k\xleftarrow {\$}\mathcal {K}$.

$\mathsf {Enc}$: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\mathsf {Enc}_{k}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{0}\xleftarrow {\$}\{0,1\}^{t}$ and $c_{i} = E(k,c_{0}+i)\oplus m_{i}$ for $0<i\le n$.

$\mathsf {Dec}$: For a given cipher-text $C = c_{0}c_{1}\cdots c_{n}$ and key k; $\hat{m_{i}}:= E(k,c_{0}+i)\oplus c_{i}$ for $0<i\le n$.

Definition 10

(XTS Scheme). For a given permutation $E: \mathcal {K}\times \{0,1\}^{t}\rightarrow \{0,1\}^{t}$ we define the symmetric encryption scheme $\varPi _{XTS}=(\mathsf {Gen},\mathsf {Enc},\mathsf {Dec})$ as follows:

$\mathsf {Gen}$: Pick random keys $k_1$ and $k_2$ i.e., $k_1\xleftarrow {\$}\mathcal {K}$ and $k_2\xleftarrow {\$}\mathcal {K}$.

$\mathsf {Enc}$: For a given message $M = m_{1}m_{2}\cdots m_{n}$, where n is a polynomial in t; $\mathsf {Enc}_{k}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{i} = E(k_{1},m_{i}\oplus \varDelta _{i})\oplus \varDelta _{i}$ for $0<i\le n$, $\varDelta = \alpha ^{i-1}L$, $L=E(k_{2},I)$ and $\alpha$ is the primitive element of the field $\mathbb {F}^{n}_{2}$. Here I is a publicly known nonce that is agreed upon out of band (but that is different in different ciphertexts).

$\mathsf {Dec}$: For a given cipher-text $C = c_{1}\cdots c_{n}$; and key k; $\hat{m_{i}}:= E(k,c_{i}\oplus \varDelta _i)\oplus \varDelta _i$ for $0<i\le n$.

3 Quantum Attacks on CBC, CFB, and XTS Based on Standard Secure PRF

We show that CBC and CFB mode are not IND-qCPA secure in general when the underlying block cipher is only a standard secure PRF, and that XTS has a chosen-plaintext attack using superposition queries. For this, in Sect. 3.1 we first construct a block cipher that is a standard secure PRF (but are intentionally not quantum secure). Then, in Sect. 3.2 we show how to break CBC and CFB, respectively, when using that block cipher.

3.1 Construction of the Block Cipher for CBC

To show that a standard secure PRF is not sufficient for IND-qCPA security of CBC and XTS modes of operation we need a block cipher that is standard secure PRF but not quantum secure. Our first step is to construct such a block cipher and prove it to be standard secure. In this section we provide two such constructions of block cipher that would be later used to show insecurity of CBC and XTS against a quantum adversary respectively.

Construction 1:

where, $E:\{0,1\}^{n-1}\times \{0,1\}^{n-1}\rightarrow \{0,1\}^{n-1}$ is a standard secure PRF, $t:\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}$ is a standard secure PRF, $H:\{0,1\}^n\rightarrow \{0,1\}^n\times \{0,1\}^n$ is a random oracle and the key $k\xleftarrow {\$}\{0,1\}^{n-1}$.

Theorem 1

Construction 1 is a standard secure PRF for any quantum adversary $\mathcal {D}$ given classical access to $\mathsf {BC}_{k}$ and quantum access to the random oracle H.

We give the proof in the full version [2].

Thus, we have proved that the given construction is pseudo-random and hence a standard secure PRF.

3.2 Attack on CBC Mode of Operation

We choose a block cipher $\mathsf {BC}$ as in Construction 1 in Sect. 3.1 for the construction of the $\varPi _{ CBC }$ scheme (Definition 6). As proved, this block cipher is a standard secure PRF (i.e., if the quantum adversary has only classical access to it).

Lemma 2

There exists a standard secure pseudo-random function such that $\varPi _{ CBC }$ is not IND-qCPA secure (in the quantum random oracle model).

Proof

Let the $\varPi _{ CBC }$ scheme use the block cipher $\mathsf {BC}$, we use one block message to attack the $\varPi _{ CBC }$ scheme. We know that the adversary has quantum access to the $\varPi _{ CBC }$ scheme, hence a quantum adversary can query the superposition of all messages of size equal to the block length of $\mathsf {BC}$ (i.e., n). The adversary prepares the quantum registers M and C to store quantum messages and receive quantum cipher-texts respectively. The adversary then stores the superposition of all the messages in M (i.e., $\sum _{m}2^{-n/2}|m\rangle$) of size equal to block size of $\mathsf {BC}$ and string $|0^{2n-1}\rangle |+\rangle$ in C equal to twice the block size of $\mathsf {BC}$ respectively, and makes an encryption query. The corresponding reply is then stored in the quantum register C. The attack has been sketched in Fig. 2.

After application of encryption algorithm $\mathsf {Enc}$ of $\varPi _{ CBC }$ the message and cipher-text registers contain the following data

The adversary now XORs $c_0$ to the message register by using a CNOT gate. Hence, the quantum bits of the system changes to⁶

Using $y= m\oplus c_{0}$ we have,

Also, we have that

Hence,

We now apply n Hadamard gate ($i.e.,H^{\otimes n}$) giving us the state

As $(-1)^{(y\odot z)}$ = 1 or $-$1 and doesn’t affect the outcome of register (except in phase) we can remove y. Therefore, we have

Hence, if $z\odot (k\Vert 1) = 0$ we have (up to normalization)

otherwise the superposition collapses to zero string. Now if the $n-$bits of message register is measured one gets a vector z such that $z\odot (k\Vert 1) =0$. Hence, to retrieve k we can repeat the same attack again and again until we get $n-1$ independent vectors $v_i$’s (we know that the last bit of $(k\Vert 1)$ is 1). Now using the gaussian elimination one can retrieve the $n-1$ bits of k, thereby breaking the $\varPi _{ CBC }$ scheme.

Fig. 2.

Attack on 1 block CBC using Simon’s algorithm

A very similar attack also breaks CBC mode:

Lemma 3

There exists a standard secure pseudo-random function such that $\varPi _{ CFB }$ is not IND-qCPA secure (in the quantum random oracle model).

And for XTS mode we get (using a more complex attack):

Lemma 4

There exists a standard-secure pseudo-random function (in the random oracle model) such that $\varPi _{XTS}$ admits an attack of the following form: The adversary first performs a number of superposition encryption queries. Then the adversary performs a superposition encryption query where the first half of the plaintext is an adversary chosen superposition of messages, and the second half is a bitstring m unknown to the adversary. Then the adversary can compute m.

Details and proofs are given in the full version [2].

4 IND-qCPA Security of OFB and CTR Modes of Operation

In this section, we analyze the quantum security of OFB and CTR modes of operation. Our motive is to prove the security of these schemes against the quantum adversary based on IND-qCPA definition (Definition 2) in Sect. 2. These two modes of operation are similar in working thence similar proofs.

We provide a generic proof for any cryptographic-system with encryption function which XOR’s the message with a random pad based on the length of message and random key. This proof shows that IND-qCPA security of the scheme reduces to the fact that it is IND-CPA secure.

Lemma 5

Let $\varPi = (\mathsf {Gen},\mathsf {Enc},\mathsf {Dec})$ be an encryption scheme with encryption algorithm as $\mathsf {Enc}_{k}(M) = G_{k}(|M|;r)\oplus M$, for randomness r, given message M and key $k\leftarrow \mathsf {Gen}$. If $\varPi$ is IND-CPA secure then it is IND-qCPA secure.

Proof

Let $\Pr [ PrivK ^{qCPA}_{\mathcal {A}_{q},\varPi }(t)=1]=\varepsilon (t) + \frac{1}{2}$, for a poly-time quantum adversary $\mathcal {A}_{q}$. We construct an efficient quantum adversary $\mathcal {A}$ such that $\Pr [ PrivK ^{CPA}_{\mathcal {A},\varPi }(t)=1] = \varepsilon (t)+\frac{1}{2}$. Adversary $\mathcal {A}^{\mathsf {Enc}_{k}}(1^{t})$ works as follows:

• 1. $\mathcal {A}$ prepares two quantum registers M and C being message and ciphertext registers respectively.

• 2. Runs $\mathcal {A}_{q}$, whenever $\mathcal {A}_{q}$ queries encryption oracle on superposition of messages answer the queries in the following way:

  • the quantum message and are stored in M and C respectively,

  • query $s:= \mathsf {Enc}_{k}(0^{|M|}) = G_{k}(|M|;r)$, where r is the randomness.

  • apply unitary operator Uto quantum register M and C where .

  • send the register to the adversary $\mathcal {A}_{q}$.

• 3. When $\mathcal {A}_{q}$ asks the challenge query send it to the challenger and send received result back to $\mathcal {A}_{q}$.

• 4. Continue to answer any encryption oracle query as in step 2.

• 5. $\mathcal {A}_{q}$ outputs the result $b'$, send $b'$ to the challenger.

It is clear that $\Pr [ PrivK ^{CPA}_{\mathcal {A},\varPi }(t)=1] = \Pr [ PrivK ^{qCPA}_{\mathcal {A}_{q},\varPi }(t)=1]= \frac{1}{2}+\varepsilon (t)$ and $\mathcal {A}$ is poly-time.

Theorem 2

If E is a standard secure pseudo-random function then $\varPi _ OFB$ and $\varPi _ CTR$ schemes are IND-qCPA secure.

Proof

$\varPi _{ OFB }$ and $\varPi _{ CTR }$ schemes are IND-CPA secure when E is standard secure pseudo-random function. Thus, result follows from Lemma 5.

5 IND-qCPA Security of CBC and CFB Mode of Operation

IND-qCPA security of CBC and CFB modes of operation are conditional on the existence of quantum secure primitives. We use the One-way to Hiding Lemma [14] (Lemma 1) to prove the bound for any quantum adversary that attacks the system.

We define $\mathsf {Enc}_{ CBC }^{i,H}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{j}\xleftarrow {\$}\{0,1\}^{t}$ for $j\le i$ and $c_{j} = H(m_{j}\oplus c_{j-1})$ for $i<j\le n$. Similarly we define, $\mathsf {Enc}_{ CFB }^{i,H}(M) := c_{0}c_{1}\cdots c_{n}$, where $c_{j}\xleftarrow {\$}\{0,1\}^{t}$ for $j\le i$ and $c_{j} = H(c_{j-1})\oplus m_{j}$ for $i<j\le n$.

In the next lemma we prove that probability of distinguishing the output of CBC $\mathsf {Enc}^{i,H}_{ CBC }$ from $\mathsf {Enc}^{i+1,H}_{ CBC }$ by a quantum adversary having access to oracle $\mathsf {Enc}^{i,H}_{ CBC }$ is negligible in t, where t is the security parameter. As the proof for $\mathsf {Enc}^{i,H}_{ CBC }$ and $\mathsf {Enc}^{i+1,H}_{ CFB }$ is similar we provide the instances for $\mathsf {Enc}^{i,H}_{ CFB }$ in parentheses $\llbracket \rrbracket$ wherever there is a difference. Also, we use $\mathsf {Enc}^{i,H}$ to represent the encryption functions of $\mathsf {Enc}^{i,H}_{ CBC }$ and $\mathsf {Enc}^{i,H}_{ CFB }$ to generalize the proof.

Lemma 6

For any i with $i: 0\le i\le p(t)-1$, and every quantum adversary $\mathcal {A}$ that makes at most $q_{A}$ queries,

where p(t) is the maximum number of blocks in the message M and t is the length of each message block.

Proof

For a given message $M = m_{0}m_{1}\cdots m_{n}$ let $\widetilde{\mathsf {Enc}}^{i}_{H}(M,c_{0},\cdots ,c_{i}):= \hat{c}_{1}\hat{c}_{2}\cdots \hat{c}_{n}$ where

$$\hat{c}_{j} = \left\{ \begin{array}{ll} c_{j} &{} 0\le j\le i \\ H(\hat{c}_{j-1}\oplus m_{j}) \llbracket = H(\hat{c}_{j-1})\oplus m_{j}\rrbracket &{} i< j\le n \end{array} \right. $$

Then we have,

We put $c_{i} := x \oplus m_{b}^{i+1}\llbracket {= x}\rrbracket$ where $m_{b}^{i+1}$ is the $(i+1)^{th}$ block of the message $M_{b}$ and $x\xleftarrow {\$} \{0,1\}^{t}$. This means that $c_{i}$ is uniformly random as x is randomly chosen. Therefore,

By definition of $\widetilde{\mathsf {Enc}}^i_H$, we have $\widetilde{\mathsf {Enc}}_H^i(M_b,c_0,\cdots ,c_i)=\widetilde{\mathsf {Enc}}^{i+1}_H(M_b,c_0, \cdots ,c_{i+1})$ with $c_{i+1}:=H(x) \llbracket :=H(x)\oplus m_b^{i+1}\rrbracket$. Hence,

We define an adversary $A_{O2H}$ that makes oracle queries to random function $H\xleftarrow {\$}(\{0,1\}^{t} \rightarrow \{0,1\}^{t})$. $A_{O2H}$ with given inputs x and y does the following:

We note here that adversary $A_{O2H}$ can answer the adversary $\mathcal {A}$’s query as it has oracle access to H. Let $q_{o2h}$ be the number of H-queries made by $\mathcal {A}_{O2H}$, it is clear that $q_{o2h}\le 3p(t)q_{A}$. Let $q_{1}$, $q_{2}$ and $q_{3}$ denote the number of queries that $A_{O2H}$ makes to H before the challenge query, during challenge query and after challenge query respectively.⁷

It is clear that:

Let B be an oracle algorithm described in the O2H lemma (Lemma 1). Therefore, we have that $\varepsilon (t) \le {2q_{o2h} \sqrt{P_{B}}},$ where we have the probability $P_{B}$ as

$$=\frac{1}{q_{o2h}}\cdot \underbrace{\Pr [x=x': x\xleftarrow {\$}\{0,1\}^{t},H\xleftarrow {\$}(\{0,1\}^{t}\rightarrow \{0,1\}^{t}), x'\leftarrow B^{H}(x,j)]}_{:=P_{B}^j}$$

To evaluate $P^{j}_{B}$ we consider three cases depending whether the j-th H-query is before, during, or after the challenge query.

In this case, the j-th iteration query to the oracle H is computed before the challenge query is done. So adversary $\mathcal {A}$ does not get access to x while queries are done. Therefore, adversary $\mathcal {A}$’s queries are independent of x, as it never executes challenge query and beyond. As the adversary $\mathcal {A}$ never used the x for any query we can therefore say that fixing x to be any string should not affect argument of the query. Therefore, we fix input x as the null string $0^{n}$.

$$P^{j}_{B}=\Pr [x=x': x\xleftarrow {\$}\{0,1\}^{t},H\xleftarrow {\$}(\{0,1\}^{t}\rightarrow \{0,1\}^{t}), x'\leftarrow B^{H}(0,j)]\le 2^{-t}.$$

In this case the j-th iteration query to the oracle H is made during the challenge query (i.e,  $q_{1}< j \le q_{1}+q_{2}$). Therefore, oracle algorithm B can stop adversary $\mathcal {A}$ at any of the following queries:

$$H(m_{b}^{i+2}\oplus y ),H(m_{b}^{i+3}\oplus H(m_{b}^{i+2}\oplus y )),\cdots ,H(m_{b}^{p(t)}\oplus H(m_{b}^{p(t)-1}\oplus \cdots H(m_{b}^{i+2}\oplus y)\cdots ))$$

By using result from Zhandry [18] on distinguishing a random function from a random permutation we have,

$$P^{j^{}}_{B} \le \Pr [x=x' : H\xleftarrow {\$}\textsf {Perm}(), x\xleftarrow {\$}\{0,1\}^{t}, x'\leftarrow B^{H}(x,j)]+O\left( \frac{{j}^{3}}{2^{t}}\right) $$

Note that the argument of the j-th query is $s:= m_{b}^{i+j-q_{1}+1}\oplus H(m_{b}^{i+j-q_{1}}\oplus \cdots \oplus H(m_{b}^{i+2} \oplus y)\cdots )$ $\llbracket s := H(\cdots H(H(y)\oplus m_{b}^{i+2})\cdots \oplus m_{b}^{i+j-q_{1}})\oplus m_{b}^{i+j-q_{1}+1}\rrbracket$. From the definition of O2H lemma we know that y is chosen independently at random from x and H. It is easy to see that for a fixed message $M_b$ s would be assigned an output by a permutation that is independent of x but dependent on y since the input to first call to H is $m_b^{i+2}\oplus y$ $\llbracket y \rrbracket$. Therefore,

$$ P^{j}_{B} \le \Pr [x=x': H\xleftarrow {\$}\textsf {Perm}(), x\xleftarrow {\$} \{0,1\}^{t}, x' = s]+ O(\frac{{j}^{3}}{2^{t}})\le \frac{1}{2^{t}}+O\left( \frac{{j}^{3}}{2^{t}}\right) \approx O\left( \frac{{j}^{3}}{2^{t}}\right) $$

In this case, the j-th iteration query to the oracle H is computed after the challenge query is done. We have $j >q_{1} + q_{2}$. Adversary $\mathcal {A}$ makes many encryption oracle queries and eventually measures the argument of one of the H oracle query and stops. Say it measures in the $k^{th}$ H oracle query of j-th encryption query.

$$\begin{aligned} P^{j}_{B} := \Pr [x = x' : x\xleftarrow {\$}\{0,1\}^{t}, H\xleftarrow {\$}(\{0,1\}^{t}\rightarrow \{0,1\}^{t}), x'\leftarrow B^{H}(x,j)] \end{aligned}$$

Fig. 3.

Composition of Encryption Oracle using H oracle

The circuit diagram in Fig. 3 represents the working of adversary $A_{O2H}$. $A_{O2H}$ answers encryption queries using oracle access to H. Let the quantum message (possibly entangled) to be stored in the quantum register M and the corresponding ciphertext in the quantum register C. The encryption circuit is composed of the quantum gates $U_{IV}, U_{H}, CNOT$ and measurements. Where $U_{IV}|M\rangle = |M\oplus IV\rangle$, $U_{H}|M,C\rangle = |M,C\oplus H(M)\rangle$, $CNOT|M,C\rangle =|M,C\oplus M\rangle$, and the measurements are in the computational basis of the message space. Thus, in each case I,II,III we have $P_{B}^j\in O\left( \frac{q_{o2h}^3}{2^{-t}}\right)$.⁸

The unitary gates used to compose the circuits are diagonal in the computational basis and hence commute with the measurements. Therefore, moving the measurements prior to the unitary operations do not affect the probability distribution of the output. Hence, we can measure the message register M before performing the unitary operations. Thus, it is similar to the Case II where we have a query on a classical message.

Therefore, we have $P^{j}_{B}= O(\frac{j^{3}}{2^{t}}).$

Hence by the definition of $P_B$ we have, $P_{B} \le O( \frac{q_{o2h}^{3}}{2^{t}})$. Therefore, we have that $\varepsilon (t)\le q_{o2h}\sqrt{P_{B}}\le q_{o2h}\sqrt{O(\frac{{q_{o2h}}^{3}}{2^{t}})}= O(\frac{{q_{o2h}}^{3}}{2^{t}})$

Theorem 3

If the function E is a quantum secure PRF then $\varPi _{\textsf {CBC}}$ and $\varPi _{\mathsf {CFB}}$ is IND-qCPA secure.

This follows now easily from Lemma 6 and the fact that $\mathsf {Enc}^{i,H}(M_b)$ is independent of its argument $M_b$ for $i=p(t)$. We give the details in the full version [2].