Assessment of the Key-Reuse Resilience of NewHope

Abstract

NewHope is a suite of two efficient Ring-Learning-With-Error based key encapsulation mechanisms (KEMs) that has been proposed to the NIST call for proposals for post-quantum standardization. In this paper, we study the security of NewHope when an active adversary takes part in a key establishment protocol and is given access to an oracle, called key mismatch oracle, which indicates whether her guess of the shared key value derived by the party targeted by the attack is correct or not. This attack model turns out to be relevant in private key reuse situations since an attacker may then be able to access such an oracle repeatedly – either directly or using faults or side channels, depending on the considered instance of NewHope. Following this model we show that, by using NewHope recommended parameters, several thousands of queries are sufficient to recover the full private key with high probability. This result has been experimentally confirmed using Magma CAS implementation. While the presented key mismatch oracle attacks do not break any of the designers’ security claims for the NewHope KEMs, they provide better insight into the resilience of these KEMs against key reuse. In the case of the CPA-KEM instance of NewHope, they confirm that key reuse (e.g. key caching at server side) should be strictly avoided, even for an extremely short duration. In the case of the CCA-KEM instance of NewHope, they allow to point out critical steps inside the CCA transform that should be carefully protected against faults or side channels in case of potential key reuse.

This research has been partially funded by ANRT under the program CIFRE 2016/1583. We acknowledge the support of the French Programme d’Investissement d’Avenir under national project RISQ P141580. This work is also partially supported by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701).

1 Introduction

The insecurity of the main asymmetric cryptosystems (RSA, (EC)DLP) in front of a potential quantum computer has led the crytographic community to investigate new quantum resistant primitives. In 2016, NIST has initiated a process to develop and standardize one or more public-key cryptographic algorithms which are supposed to be quantum safe. Cryptosystems based on lattices represent one of the most promising directions for such systems.

Key Encapsulation Mechanisms (or KEMs) are one of the most important asymmetric cryptographic primitives. The NIST call specifically asks for quantum resistant KEM proposals in order to replace number theory based Diffie-Hellman key establishment protocols, which can be broken in the quantum computation model. Potential candidates for post quantum key establishment include the ones based on the lattice based Ring Learning With Errors Problem (Ring-LWE) introduced in [7, 22]. Recently, Google conducted real life TLS experiments [6] with a Ring-LWE based key exchange scheme: the NewHope-Usenix system [6]. While these experiments show the efficiency of NewHope-Usenix, the specification of the reconciliation step of the system is rather complex. The technicality of this step requires a large fraction of the algorithm description in the original paper [1]. This issue together with possible intellectual property right considerations led the designers to introduce a simplified new variant initially named NewHope-Simple [25] where the reconciliation-based approach of NewHope-Usenix is replaced by an encryption-based approach. Thanks to the combined use of encoding and compression techniques, the performance price to pay for this new version in terms of bandwith overhead is quite marginal. Now NewHope -Simple has been transformed into NewHope, a suite of two candidate KEM mechanisms of the NIST call for proposals [23] named NewHope-CPA-KEM and NewHope-CCA-KEM, in short CPA-KEM and CCA-KEM. Both mechanisms are encryption-based: they rely upon an auxiliary probabilistic public key encryption allowing to encrypt a 256-bit data named CPA-PKE, that is not submitted to the NIST call for proposals as a standalone mechanism.

NewHope-CPA-KEM, that is nearly identical to NewHope-Simple, is only claimed to be a passively secure KEM. It can be viewed as the CPA-PKE encryption of a hashed secret random value $\nu$ followed by hashing $\nu$ on both sides. Unlike CPA-KEM, CCA-KEM is claimed to be secure with respect to adaptively chosen ciphertext attacks. It is derived from CPA-PKE in a less straightforward manner, by applying a variant of the Fujisaki-Okamoto transform [11]. An essential feature of this transform is that the encryption of $\nu$ is derandomized: this allows the decrypting party Alice to re-encrypt the decryption result, check that the result matches the received ciphertext, and use this test to prevent information leakages on the private key in active attacks where “dishonestly” derived ciphertext values are sent by an adversary.

While the specification of CPA-KEM and CCA-KEM does not formally prevent re-using the same CPA-PKE (public key, private key) pair in multiple key establishments, the design rationale section of the NewHope specification requires that such key pairs be never cached and that a fresh key pair be generated at each key establishment¹. In the case of CPA-KEM, one of the main reasons for this requirement is that, unlike the classical Diffie-Hellman key establishment, the original Ring-LWE based KEM with reconciliation is known to be vulnerable to a practical active attack in a key reuse situation as shown in [10]. Despite not being based on the reconciliation paradigm, CPA-KEM shares sufficiently many features with its predecessor for being conjectured also vulnerable to similar attacks. In the case of CCA-KEM, this requirement to reuse private keys could be justified by the fact that no real perfect forward privacy can be offered if private keys are not ephemeral².

Motivation

With its strong performance and its Ring-LWE based security, NewHope is a high profile candidate of the NIST competition. There is a good chance for it to be implemented in the future for Internet protocols. So, studying its security under several attacker models is important.

In this paper, we investigate the resilience of the CPA-KEM and CCA-KEM versions of NewHope in a misuse situation where the same key pair is reused for multiple key establishment by the private key owner – who will be referred to as Alice in the sequel. Note that Alice is also the party who initiates the two-round key establishment in both schemes. We use the generic name of key mismatch oracle to refer to the private key recovery attack models we are considering, that are closely inspired from the adversary model considered in [10]. While slightly less powerful than a CCA attack against an encryption based KEM where a decryption oracle is available, attacks using a key mismatch oracle still belong to the active attack category. Their common feature is that the adversary is assumed to be able: (1) to actively interact with Alice by performing multiple KEM establishment where Alice uses the same key pair, (2) to produce each time a guess on the resulting secret key derived by Alice and (3) to access a binary oracle that indicates whether this guess is valid or not.

Our study is motivated by the belief that an in-depth understanding of the security offered by candidate KEM mechanisms submitted to the NIST call for proposals in key reuse situations is a useful part of their cryptanalytic evaluation, even for those candidates for which key reuse is considered as a misuse of the mechanism. Having an accurate estimate of the number of queries to the key mismatch oracle and of the complexity of the private key recovery really helps to assess the possible danger³. We focus here on a case study of the NewHope candidate KEMs. An advantage of this choice is that previous work on reconciliation-based Ring-LWE schemes such as [10] can be partly leveraged. However, as will be seen in the sequel, the fact that the NewHope suite is encryption-based and is using encoding techniques induces substantial differences and non-trivially complicates the cryptanalysis. To the best of our knowledge, no investigation of attacks against a scheme without reconciliation in a key mismatch oracle model was published so far.

Previous Work

The danger of accessing a key mismatch oracle within some key agreement protocols in a key share reuse context has been already exposed several times. Early examples showing the vulnerability of some standardized Diffie-Hellman key agreement protocols in such a context were introduced in [20]. The potential danger of a somewhat related type of attack, namely so-called reaction attacks against PKE schemes [13], where an adversary can submit a chosen ciphertext to the legitimate private key owner and access a binary information about her reaction (whether the decryption succeeds or fails for instance), is probably even better known. Bleichenbacher’s attack against RSA PKCS$\#$1 of Crypto’98 [4] can been viewed as an early reaction attack. In 1999, Hall, Goldberg and Schneier presented reactions attacks against several PKE schemes [13]. In the particular case of lattice based cryptography, several notes on the vulnerability of NTRU to reaction attacks and its protection against such attacks were published [14, 15]. In 2003, Howgrave-Graham et al. proposed a reaction attack on NTRUEncrypt that leverages decryption failures [17]. A recent example of reaction attack is Guo et al.’s key recovery attack on the code-based PKE QC-MDPC [12]. It is thus natural that NSA, in 2015, warns NIST Post-Quantum candidates against active attacks [19]. Few times later, the first concrete attacks on a Ring-LWE based key establishment leveraging a key mismatch oracle was proposed by Fluhrer [10] (see also [8, 9]).

These attacks rely on the fact that the reconciliation step can be exploited by an active adversary to retrieve some information on the secret static key. Despite the warnings issued in [19], certain NIST candidates are vulnerable to active attacks. Indeed, it is shown in [3] that the secret key of the NIST candidate HILA5 can be recovered in the key mismatch oracle setting following Fluhrer’s approach. In summary, despite the raising awareness of the cryptography research community that key mismatch oracle attacks threaten many lattice based KEMs in case of key reuse, relatively few examples of such attacks have been published so far.

About the side channel protection of NewHope, no dedicated countermeasure has been proposed for NewHope so far, but in [21] a side channel protection for a similar scheme has been proposed. This paper describes a provably first-order secure masking scheme and its integration into a CCA conversion.

Our Contribution

In the following, we evaluate the security of NewHope when the attacker gets access to a key mismatch oracle. We concretely explain how the attacker can have access to such an oracle in different scenarios with the CPA-KEM and the CCA-KEM. We first introduce a straightforward way to recover such an oracle in the CPA-KEM. The adversary enters a key establishment with Alice, derives from her guess on the shared key produced by Alice a guess on the resulting session key she produces, and attempts to initiate a session with Alice under this guessed session key. The success or failure of this protected communication attempt provides the desired key mismatch oracle⁴.

Then, at the end of the paper, we elaborate other scenarios on the CCA version which require side channels. Indeed, the CCA-KEM version induces major extra differences with formerly analyzed reconciliation-based schemes, that also deserve being analyzed. Because of the CCA transform, a key mismatch oracle cannot be accessed directly. But we show that for unsufficiently protected implementations, simple faults or side channels could bypass this transform and provide the desired key mismatch oracle. While unprotected versions of CCA-KEM are extremely efficient, its implementations must be very carefully protected against any key mismatch oracle leakage if key pairs are potentially reused. This might eventually come with a cost in terms of performance. This study may help the developers to protect the algorithms against a possible key mismatch oracle leakage.

The core of this work is the description of a new attack on NewHope using the key mismatch oracle. Even if the existence of previous work attacks (see [8, 10]) casts suspicion on the resistance of NewHope CPA-KEM against active attacks in the same key-reuse setting, one has to take into account substantial differences between the reconciliation-based paradigm of the original NewHope and the encryption-based paradigm of CPA-KEM. Because of these differences, the detail of Fluhrer’s attack [10] is not really inspiring for mounting an attack and any direct transposition attempt would be hopeless. Finding an efficient way of deriving information on the secret key from the key mismatch oracle with a low number of queries induces several issues. The main difficulty is to retrieve enough leakages after the application of the encoding and compression functions. We investigated how to leverage these functions in order to find a simple way to instantiate the oracle and identified precise elements in the polynomial ring that can be used by the adversary to recover the secret. Finally, we had to take into account the fact that NewHope coefficients are in $[-8,8]$.

We experimented our attack with a Magma CAS proof of concept. Under NewHope parameters, we were able to recover exactly the secret $\mathbf S$ with on average 16, 700 queries for NewHope1024 which corroborates the expected performance of the model.

Paper Outline

In Sect. 2 we introduce some notation and describe the NewHope CPA scheme. In Sect. 3, we describe the notion of key mismatch oracle and how practical it can be for the CPA-KEM. In Sect. 4, we detail our attack using the key mismatch oracle. In Sect. 4.4, we present our experiments. In Sect. 5, we show how the key mismatch oracle can be retrieved with side channels with the CCA-KEM. Finally, in Sect. 6, we summarize our results and discuss future research.

2 Preliminaries

2.1 Notations

Let q be a prime number in $\mathbb {N}$ and let $\mathbb {Z}_{q}$ denote the ring elements $\mathbb {Z}/q\mathbb {Z}$. Depending on the context, the elements in $\mathbb {Z}_{q}$ can be equivalently represented as integers in $\{0,\ldots ,q-1\}$ or in $\{-(\frac{q-1}{2}),\ldots ,(\frac{q-1}{2})\}$. In the following, the notation $\mathcal {R}$ refers to the polynomial ring $\mathbb {Z}_{q}[x] / (x^N +1)$ with N a power of 2. If $\mathbf P$ belongs to $\mathcal {R}$, it is a polynomial of degree $(N-1)$ with coefficients $\mathbf P [i]$ belonging to the set $\mathbb {Z}_{q}$. Such elements can also be represented as vectors whose i-th coordinate is the coefficient related to $x^i$. In the sequel we use either the polynomial notation or the vectorial one. For readability, bold capital letters are used to refer to elements in $\mathcal {R}$ and bold lowercase letters will refer to compressed elements, i.e. elements in $\mathcal {R}$ with small coefficients.

Let us define $\mathcal {G}_{a}$ as the centered Gaussian distribution of standard deviation $a$ and $\psi _{k}$ the centered binomial distribution of parameter $k$. Its standard deviation is $\sqrt{k/2}$. One may sample from $\psi _{k}$ for integer $k> 0$ by computing $\sum _{i=1}^{k}b_i - b'_i$, where the $b_i$,$b'_i \in \{0, 1\}$ are uniform independent bits.

Property 1

The elements generated according to a centered binomial distribution $\psi _{k}$ of parameter k are in the interval $[-k,k]$. Thus, the coefficients of the small elements drawn from $\mathcal {R}$ in NewHope are in $[-8,8]$.

In the figures and algorithms, the notation $\xleftarrow {\$}\mathcal {D}$ means picking an element in $\mathcal {R}$ having all its coefficients generated at random according to distribution $\mathcal {D}$. The notation $\xleftarrow {coin}\mathcal {D}$ means using a $coin \in \{0,...,255\}^{32}$ as a seed to pick a pseudorandom element in $\mathcal {R}$ having all its coefficients according to distribution $\mathcal {D}$. This is generally done using a hash function like SHAKE-128. In the paper we refer several times to Sign(a) with $a \in \mathbb {Z}$ by using the convention that it is defined as positive when $a \ge 0$ and as negative when $a<0$. If $x \in \mathbb {R}$, the integer $\lfloor x \rceil$ is defined as $\lfloor x + \frac{1}{2} \rfloor \in \mathbb {Z}$.

2.2 NewHope

NewHope [23, 25] is a RING-LWE based key establishment scheme derived from NewHope-Usenix [1], that is simplified because it does not use the reconciliation anymore. In this section, we describe NewHope, where we omit some details (e.g. the so-called NTT transform or the encoding of the messages) to simplify the presentation. This does not imply any loss of generality for our attack. To ease the understanding, we will describe the CPA-KEM version of NewHope in this section as the key mismatch oracle can be easily derived. We will present the CCA-KEM later in Sect. 5 when we present some ways to access a key mismatch oracle.

The polynomial ring $\mathcal {R}$ used in NewHope has the following parameters: $(N,q)= (1024,12289)$ or $(N,q)= (512,12289)$. The coefficients of the small elements drawn from $\mathcal {R}$ follow a centered binomial distribution $\psi _{k}^N$ with $k=8$. The standard deviation is $a=\sqrt{\frac{8}{2}} = 2$. We decided to focus on explaining the attack for $N=1024$. Indeed, for $N=512$ there is twice less redundancy and the attack is easier. Thus, we fix $N=1024$. These elements will be seen as vectors of size N with integer components. We denote $s=1536$ which is such that $q=8s+1$. The aim of the system is to share a key of size 256 bits following the exchange mechanism outlined below and represented in Fig. 1.

Fig. 1.

Simplified NewHope

A public value $\mathbf A \in \mathcal {R}$ is derived from a published seed. Four specific functions are introduced: Encode, Decode, Compress and Decompress. They are described in Algorithms 1, 2, 3 and 4. Note that we partly deviate from the notation of the original specification of these algorithms, since we use the parameter s (the original description is in [25]). The following paragraphs describe these functions.

and The function Compress (Algorithm 3) takes as input a vector $\mathbf C$ in $\mathcal {R}$ and applies on each of its component a modulus switching to obtain an element $\mathbf c$ in $\mathbb {Z}_{8}[x]/(x^N +1)$. Compressing a vector C essentially means keeping the 3 most significant bits of each coefficient. The function Decompress (Algorithm 4) shifts the bits of the input $\mathbf c \in [0,8[^N$ to place them among the most significant bits. These functions are not the inverse of each other.

and The Encode function takes a n-bit input $\nu$ where $n=N/4$ and creates an element $\mathbf K \in \mathcal {R}$ which stores 4 times the element $\nu$. The redundancy is used by the function Decode to recover $\nu$ with a noisy $\mathbf K$.

 Key Encapsulation Mechanism. Let us now describe this scheme.

• 1. Setup: Alice generates 2 small secrets $\mathbf S$ and $\mathbf E$ in $\mathcal {R}$. She sends $\mathbf B =\mathbf {AS}+\mathbf E$ to Bob.

• 2. Key Encapsulation: From a random coin acting as a seed, Bob derives 3 small secrets $\mathbf {S'}$, $\mathbf {E'}$ and $\mathbf {E''}$ in $\mathcal {R}$ and a random element $\nu _B$ of size n which will be the encapsulated key. He computes $\mathbf U ={\mathbf {AS'}}+\mathbf {E'}$. He encodes $\nu _B$ into a redundant element $\mathbf K$ of $\mathcal {R}$ using the algorithm Encode (Algorithm 1). Bob uses Compress (Algorithm 3) to compress $\mathbf C ={\mathbf {BS'}}+\mathbf {E''}+\mathbf K$ into an element with very small coefficients as described above. He sends $(\mathbf c =\textsf {Compress}(\mathbf C ),\mathbf U )$ to Alice. He deduces the shared secret as $\mu _B =\textsc {SHAKE-256}(32,\nu _B)$.

• 3. Key Decapsulation: Alice decompresses $\mathbf c$ with Decompress into $\mathbf {C'}$ (Algorithm 4). She computes $\mathbf {C'}-\mathbf {US}$ which is close to

  $$\begin{aligned} \mathbf C -\mathbf {US}= \mathbf {ES'}+\mathbf {E''}+ \mathbf K -\mathbf {E'S}. \end{aligned}$$

  (1)

  Since $\mathbf {ES'}+\mathbf {E''}-\mathbf {E'S}$ is small, she recovers an estimated value $\nu _A$ of $\nu _B$ with a decoding algorithm called Decode(Algorithm 2). From $\nu _A$, she can deduce $\mu _A=\textsc {SHAKE-256}(32,\nu _A)$.

Since $\mathbf S ,\mathbf {S'},\mathbf E ,\mathbf {E'},\mathbf {E''}$ are small, Alice and Bob get the same key $\mu = \mu _B=\mu _A$ with high probability.

Remark 1

This Section presented NewHope-CPA-KEM which is the target Sect. 4’s analysis. However a PKE called NewHope-CPA-PKE has been introduced in [23]. The slim difference lies on the fact that $\nu _B$ becomes the encrypted message. The CCA security of the CCA version, called NewHope-CCA-KEM relies on the CPA security of NewHope-CPA-PKE (see Sect. 5).

3 The Key Mismatch Oracle

This section introduces the notion of key mismatch oracle and a way to access it in the CPA version. We will always consider a malicious active adversary, Eve, who acts as Bob. Her messages, key and intermediate values will be denoted as $m_E,\mu _E$ and $\nu _E$ instead of $m_B,\mu _B$ and $\nu _B$.

Remark 2

One might wonder how a malicious Alice can recover Bob’s secret in a case of key reuse by Bob. In NewHope, this can be done with 2 queries, see the full version of our paper [2].

The goal of the adversary is to recover Alice’s static private keys $\mathbf S$ and $\mathbf E$ by using the following oracle several times. We will focus on recovering the secret S. E can be derived from S with $\mathbf E =\mathbf B -\mathbf {AS}$.

Definition 1

. A key mismatch oracle is an oracle that outputs a bit of information on the possible mismatch at the end of the key encapsulation mechanism.

In the NewHope context, the key mismatch oracle is the oracle that takes any message $m_E$ and any key hypothesis $\mu _E$ as input and outputs the following

(2)

Such an oracle should leak information on secret $\mathbf S$ because its output is clearly correlated to the value of $\mathbf S$. However, this oracle is less powerful than a CCA decryption oracle against CPA-PKE. Indeed, the only information given is a bit representing the possible key mismatch. The difficulty is to choose appropriate $(m_E,\mu _E)$ to retreive information of a small part of S. In Sect. 4, we present how to recover the secret $\mathbf S$ from such an oracle.

The simplest way to access such an oracle is when the CPA-KEM is implemented with static secrets. In other words, Alice will keep her secrets $\mathbf S$ and $\mathbf E$ for several key establishment requests. We consider that Eve does not necessarily follow the scheme specification. She can “cheat” and generate a message $m_E$ that is not derived from a coin or from random small secrets $\mathbf {S'},\mathbf {E'}$ and $\mathbf {E''}$. By definition, the CPA version of NewHope is passively secure, an attacker using a key mismatch oracle is outside of the security assumptions⁵. This has been well highlighted in paragraph 2.3, Section No key caching of the original paper of NewHope-Usenix. However an implementation of NewHope which allows misuse cases (see [24]) cannot be completely excluded. Thus it is important to precisely evaluate such a threat and consider the following attack model.

Attack Model 1

Alice will accept any syntactically correct message $m_E$ and always try to use the corresponding shared key for communicating. When she derives the shared key, either she is able to decrypt messages exchanged after that with Eve (and thus Eve deduces that the shared key is the same) or she will notify Eve that something went wrong with the key agreement. Eve will then deduce that the key is different. In both cases, Eve gets the desired key mismatch oracle.

In Sect. 5, we show how to get access to such an oracle with side channels in the CCA framework.

4 Attack on NewHope with Key Mismatch Oracle

We assume here that Eve, the attacker, has access to $\mathcal {O}_{1}$, a key mismatch oracle as defined in Sect. 3. Let us now explain how she proceeds to recover Alice’s static secret key $\mathbf S$ following Attack Model 1.

4.1 Rewriting the Key Mismatch Oracle

The use of the key mismatch oracle obviously leaks information on Alice’s secret key $\mathbf S$. But the task of recovering $\mathbf S$ entirely seems much more complicated. Indeed as defined in Sect. 3, the only information provided by the key mismatch oracle is a bit representing the success or mismatch of the key agreement. The difficulty for Eve is to choose appropriate $(m_E,\mu _E)$ pairs to get useful information on small parts of S.

In a first step, Eve simplifies her part of the protocol in such a way that the knowledge of the key mismatch oracle output bit $\mathcal {O}_{1}(m_E,\mu _E)$ can be easily exploited. To do so, she can fix for instance $\mu _E$ such that:

$$\begin{aligned} \nu _E=(1,0,\dots ,0) \text { and thus }\mu _E = \textsc {SHAKE-256}(32,\nu _E). \end{aligned}$$

(3)

The value of $\nu _E=(1,0,\dots ,0)$ has not been arbitrarily chosen; as we will see later, the 0 in positions 1 to $n-1$ will help the success rate of the attack (see Proposition 3). From now on, the value of $\mu _E$ is fixed according to Eq. (3). Moreover, when replacing $m_E$ by its definition: $m_E =(\mathbf c ,\mathbf U )$, the oracle $\mathcal {O}_1$ can be reformulated using the oracle $\mathcal {O}_2$ defined below.

Definition 2

Let us introduce oracle $\mathcal {O}_{2}$ such that $\mathcal {O}_{2}(\mathbf c ,\mathbf U )= \mathcal {O}_{1}\big ( (\mathbf c ,\mathbf U ),\mu _E \big )$.

With this new definition, Eve can adapt the values of $\mathbf c$ and $\mathbf U$ to leverage Oracle $\mathcal {O}_{2}$ and retrieve information on $\mathbf S$. In other words, since $\mu _E$ is fixed, the inputs $(\mathbf c ,\mathbf U )$ are the degrees of liberty for finding S.

From Alice’s side, the link between $\nu _A$ and $\mathbf S$ passes through the functions Decode, Decompress (see the figures in full version of our paper [2].) and the element $\mathbf {K'}$: $\nu _A = \textsf {Decode}(\mathbf {k'}) = \textsf {Decode}(\mathbf C - \mathbf {US}) = \textsf {Decode}(\textsf {Decompress}(\mathbf c ) - \mathbf {US}).$ Thus, from the definition of the Decode algorithm, the value of $\nu _A[i]$, the i-th component of $\nu _A$, is deduced from the following sign computation:

$$\begin{aligned} Sign\biggm (\sum _{j=0}^{3} \biggm |(\textsf {Decompress}(\mathbf c ) - \mathbf U \cdot \mathbf S )[ i + nj] - 4s \biggm |-q\biggm ) \end{aligned}$$

(4)

We recall here that 0 is positive by convention.

The problem for Eve is that she is unable to know the number of errors that will occur at the end of the decryption computations and the positions in which they appear. Indeed, the key mismatch oracle only gives one bit of information corresponding either to mismatch or success. If there is a mismatch, Eve knows that at least one bit of $\nu _A$ is different from $\nu _E$ but she can not determine which one (or which ones). Therefore, in order to mount an effective attack, Eve needs to restrict all these different possibilities by making the following hypothesis:

Hypothesis 1

For i from 1 to $n-1$, the component $\nu _A[i]$ is equal to 0.

If Hypothesis 1 is verified, any failure in the communication comes from a single error in $\nu _A$ located in the very first component $\nu _A[0]$. Indeed, in that case, the success of the exchange only depends on the first computed value $\nu _A[0]$. In particular, if we assume this hypothesis, the oracle $\mathcal {O}_2$ depends only on the $\nu _A[0]$ and we obtain the following result.

Lemma 1

Under Hypothesis 1, the initial oracle $\mathcal {O}_{2}$ can be rewritten as

$$ \mathcal {O}_{2}(\mathbf c ,\mathbf U ) = Sign\biggm ( \sum _{j=0}^{j=3} \biggm |(\textsf {Decompress}(\mathbf c ) - \mathbf U {} \mathbf S )[0+nj] - 4s \biggm |- q \biggm ) $$

For mounting her attack, Eve has to find pairs $(\mathbf c ,\mathbf U )$ that

• 1. target the smallest number of bits of $\mathbf S$

• 2. verify Hypothesis 1

For item 1, since the Decode algorithm takes coefficients of $\mathbf S$ four by four, the size of the smallest target is a quadruplet of coefficients of $\mathbf S$. Actually, for a given quadruplet of integers $\underline{\ell }=(\ell _0,\ell _1,\ell _2,\ell _3)$ and a target index k (i.e. an index corresponding to the components of $\mathbf S$ that Eve wants to retrieve), by taking

$$\begin{aligned} \mathbf U =sx^{-k} \quad \text { and } \mathbf c = \sum _{j=0}^{3} \Big ((\ell _j + 4) \mod 8 \Big )\cdot x^{nj} \end{aligned}$$

(5)

one can prove (see in Proposition 1) that Eve targets the quadruplet $\big (\mathbf S [k+nj]\big )_{j=0\cdots 3}$. Indeed, the element $x^{-k}$ will “rotate” $\mathbf S$ in order to target $\big (\mathbf S [k+nj]\big )_{j=0\cdots 3}$ and $\mathbf c$ is induced by the quadruplet $\underline{\ell }=(\ell _0,\ell _1,\ell _2,\ell _3)$ that can vary.

About item 2, with this choice of $(\mathbf c ,\mathbf U )$, the Hypothesis 1 has good chances to be verified because the coefficients of $\mathbf c$ outside from the set $\{k+nj |\ j=0\cdots 3\}$ are 0. So, the same coefficients of $\mathbf C -\mathbf {US}$ have good chances to be small. Then, Alice is likely to derive 0 for these coefficients of $\nu _A$. However, it is not always verified and this will impact the attack’s success rate. We will discuss and compute this probability later in Proposition 3.

We can now introduce $\mathcal {O}_{3}$, a reformulation of $\mathcal {O}_2$ depending on target index k and the quadruplet $\underline{\ell }$ (see Eq. 5):

$$ \mathcal {O}_{3}(k,\underline{\ell })=\mathcal {O}_{2}\biggm (sx^{-k} ,\ \sum _{j=0}^{3} \Big ((\ell _j + 4) \mod 8 \Big )\cdot x^{nj} \biggm )$$

This formulation of the key mismatch oracle is more convenient in order to explain how Eve will gather information on $\mathbf S$ from instantiations of $\underline{\ell }$. The following proposition shows a first result in this direction.

Proposition 1

Final oracle. Let us assume that Hypothesis 1 is verified. Let k be a target index ($k \in [0,n-1]$). For a given integer quadruplet $\underline{\ell }$ in $[-4,3]^4$, the $(\mathbf c ,\mathbf U )$ explicited in Eq. 5 is such that

$$ \mathcal {O}_{3}(k,\underline{\ell }) = Sign \biggm (\sum _{j=0}^{j=3} \biggm |\ell _j - \mathbf S [k+nj] \biggm |- 8 \biggm ) $$

Proof

The proof is given in the full version of our paper [2].

In the next section, we explain how to effectively use the form $\mathcal {O}_3$ of the key mismatch oracle to extract the secret $\mathbf S$.

4.2 Recovering Very Small Coefficients of S

Let us recall that the secret $\mathbf S$ is a polynomial in $\mathbb {Z}_{q}[x] / (x^N +1)$ with coefficients in $[-8,8]$, it can be seen as a vector of N components $\mathbf S [i]$. Eve will recover the coefficients of the secret $\mathbf S$ four by four. Let k be the index of the targeted quadruplet $[\mathbf S [k], \mathbf S [k+n], \mathbf S [k+2n],\mathbf S [k+3n] ]$. The index k goes from 0 to $n-1$ and for each fixed k, Eve will call the oracle $\mathcal {O}_{3}(k,\underline{\ell })$ with several appropriate value of $\underline{\ell }$ until she gets the secret values.

For simplicity, let us now fix the index k and denote ${S}_j = \mathbf S [k+nj]$.

The following proposition and corollary describe an algorithm that, when iterated (see Corollary 1), allows to recover $S_j$ for j from 0 to 3.

Proposition 2

Let us fix j in [0, 3]. Under Hypothesis 1, if $S_j$ is in $[-3,2]$ and $(S_i)_{i\ne j} \in [-4,4]$, there exists a probabilistic algorithm $\mathcal {A}$ which recovers the value $S_j$ in 8 queries to oracle $\mathcal {O}_3$ with a success probability depending on the distribution of $(S_i)_{0\le i\le 3}$.

Corollary 1

Under Hypothesis 1, if $S_j$ is in $[-3,2]$ and $(S_i)_{i\ne j} \in [-4,4]$, there exists a probabilistic algorithm $\mathcal {A'}$ which recovers the value $S_j$ with an average number of queries to oracle $\mathcal {O}_3$ depending on the distribution of $(S_i)_{0\le i\le 3}$.

In the sequel of this section, we give the proof of Proposition 2 by first presenting the construction of the algorithm and then by introducing a method to assess the success rate. We refer the reader to the full version of our paper [2] for the proof of Corollary 1.

Proof of Proposition 2

Description of $\mathcal {A}$. Let us prove the proposition by focusing on the secret $S_0$ and by explaining how it can be recovered in 8 queries to oracle $\mathcal {O}_3$. The process will then be exactly the same for the three other values $S_1, S_2$ and $S_3$.

The first step consists in taking the 3 values $\ell _1, \ell _2, \ell _3$ at random inside the interval $[-4,3]$. Knowing that all $S_j$ are fixed, the quantity $\sum _{j=0}^{3}|\ell _j - S_j| - 8$ can thus be expressed by $f_v(\ell _0)=\big |\ell _0 - S_0\big | + v - 8$ with $v=\sum _{i=1}^3 |{\ell _j-S_j}|$ a fixed unknown constant (since all $S_j$ are unknown). Let us now see how $f_v(\ell _0)$ behaves when $\ell _0$ varies, see Fig. 2 for an illustration.

We now assume that one makes 8 queries to the oracle $\mathcal {O}_3$: one for each value of $\ell _0$ varying inside $[-4,3]$. Such queries imply having access to $Sign\Big ( f_v(\ell _0)\Big )$ $\forall \ell _0 \in [-4,3]$. The analysis can thus be split in 2 cases:

• 1. If $(v-8) \ge 0$ then all queries to oracle 1 obviously lead to “positive signs”. It is quite clear when one looks at Fig. 2.

• 2. If $(v-8)<0$, two subcases occur

  • In some cases, there exists two possible values $\tau _1 < \tau _2$ such that the function $|\ell _0 - S_0| + (v - 8)$ goes from a positive value to a negative one at point $\tau _1$ and then from a negative value to a positive one at point $\tau _2$. We call this case the favorable case. Figure 3 provides a good illustration.

    

  • If $(v-8)<0$ and $v\ll 8$, only one change of sign will occur in the interval $[-4,3]$. Figure 4 provides a good illustration.

Fig. 2.

If $v-8\ge 0$

Fig. 3.

If $v-8>0$

Fig. 4.

If $v-8\gg 0$

Figure 3 illustrated what happens in the favorable case. Around $S_0$, the trace has a slope equal to + or $-1$. Because of the symmetry, the value $S_0$ can simply be recovered by:

$$\begin{aligned} S_0 = \frac{\tau _2+\tau _1}{2}. \end{aligned}$$

(6)

If we are not in the favorable case, two such values $\tau _1$ and $\tau _2$ do not exist. This means that the constant v is not appropriate.

Termination of $\mathcal {A}$. For any $S_0\in [-3,2]$, $\mathcal {A}$ has a non zero success probability. Indeed, no matter the values of $(S_1, S_2,S_3)$ in $[-4,4]^3$, the 3-uple $(\ell _1,\ell _2,\ell _3) \in [-4,3]^3$ defined by

$$ \biggm (\ell _1 = S_1-2\cdot Sign(S_1), \ \ \ell _2=S_2-2\cdot Sign(S_2),\ \ \ell _3=S_3-3\cdot Sign(S_3)\biggm ) $$

is at least one of the choices inducing a favorable case. Actually, one can check that this choice implies that $v = 7$. Thus $v-8 = -1$ which always gives a favorable case for finding $S_0\in [-3,2]$.

Table 1. Success probability of $\mathcal {A}$ for $(S_j)_{1 \le j\le 3}$ following $\psi _4$ distribution

Success Probability. A precise probabilistic study on the $(S_j)_{1 \le j\le 3}$ to assess the success rate of algorithm $\mathcal {A}$ is detailed in the full version of our paper [2]. In Table 1, one can find the probability of success assuming that $S_1, S_2, S_3$ follow a binomial distribution $\psi _4$. The expected number of iterations is the average amount of tries before recovering the secret.    $\square$

Example 1

Let us suppose that $S_i = [0,-2,1,-1]$. For $(\ell _1,\ell _2,\ell _3) = (2,-2,-1)$, $\sum _{j=0}^{3}|\ell _j - S_j| - 8 = |\ell _0 - S_0| -2$. If we query the sign of the latter for $\ell _0=-4, -3, -2, -1, 0, 1, 2, 3$, we get: +, +, +, -, -, -, +, +. We can conclude that $S_0=\frac{1-1}{2}=0$. Whereas, for $(\ell _1,\ell _2,\ell _3) = (-2,0,1)$, $\sum _{j=0}^{3}|\ell _j - S_j| - 8 = |\ell _0 - S_0| -5$. The sign for $\ell _0=-4,-3,-2,-1,0,1,2,3$ becomes: -, -, -,-, -, -, -, -. We cannot conclude anything on $S_0$.

At the end of this section, with Corollary 1, we know that if $\mathbf S$ is generated with coefficients following the $\psi _4$ distribution and if Hypothesis 1 is verified, there exist an algorithm that recovers each coefficient of $\mathbf S$ that is in $[-3,2]$ (i.e. almost $96\%$ of the coefficients). If a coefficient of $\mathbf S$ is not in $[-3,2]$, no favorable case will appear and the coefficient will not be found. In the next section, we adapt this method for NewHope.

4.3 Recovering S for NewHope Parameters

In this section, we describe a way to recover S for NewHope parameters, i.e. when the binomial parameter is 8. According to Property 1, the coefficients of S[k] are in $[-8,8]$. This is outside from the hypothesis made in Proposition 2. Indeed, the coefficients S[k] should lie in $[-3,2]$. One can make the following change in order to fit with Proposition 2 hypothesis: $\mathbf {S}^{1}= \frac{\mathbf {S}}{2}$. In order to target $\mathbf S ^1$ instead of $\mathbf S$, one can change $\mathbf U$ from Eq. 5 to be the following $\mathbf U =\frac{s}{2} x^{-k}$.

Let us wrap up the attack into the following Proposition.

Proposition 3

There exists a probabilistic algorithm $\mathcal {B}$ which recovers NewHope secret $\mathbf S$ with high probability using an average of 18, 500 queries for $N=1024$.

Proof

Let $k\in [0,n-1]$. The distribution of probabilities for $\mathbf S [k]$ is in Table 2.

Table 2. Distribution $\psi _8$ (note that the probability is the same for negative values)

Case 1: $\mathbf {S}\varvec{[k]}$ belongs to $\varvec{\{-8,-7,5,6,7,8\}.}$ The probability of this case is around 1%. In that case, at most one change of sign will always happen. Then, only the sign of $\mathbf S [k]$ can be recovered and a brute force should be done at the end of the attack to distinguish among the possible values. For $N=1024$, on average 10 coefficients out of 1024 will not be found. When a positive value is not found, it has 8/10 chances to be a 5. At the end of the attack, a bruteforce step evaluating $\mathbf B -\mathbf {AS}$ and taking account of the probabilities can be done.

Case 2: $\mathbf {S}\varvec{[k]}$ belongs to $\varvec{\{-6,...,4\}.}$ In that case, $\mathbf S ^1[k]$ belongs in the interval $[-3,2]$. The attack is the one from Proposition 2 with a different secret $\mathbf {S}^1[k]$=$\frac{\mathbf {S}[k]}{2}$. However, the results will not be as accurate as before. We will show that there is a subtelty that allows Eve to recover the exact value of $\mathbf S [k]$.

There are 2 possible results depending on $\mathbf S [k]\text { mod }2$:

• If $\mathbf S [k]\text { mod }2 = 0$, then $\mathbf S ^1[k]\in \{-3,-2,-1,0,1,2\}$. Proposition 2 allows Eve to recover $\mathbf S ^1$. In other words, Eve will recover a succession of signs where an odd number of $(-)$ occurs (see Fig. 5). She will then be able to recover $\frac{\mathbf {S}[k]}{2} = \frac{\tau _1+\tau _2}{2}$ and then $\mathbf S [k]$.

• If $\mathbf S [k]\text { mod }2 = 1$ then $\mathbf S ^1[k]\in \{-2.5,-1.5,-0.5,0.5,1.5\}$. In a favorable case of Proposition 2, the situation will be different. As in Fig. 6, the number of $(-)$ is then even.

Fig. 5.

When $\mathbf S [k]\text { mod }2 = 0$

Fig. 6.

When $\mathbf S [k]\text { mod }3 = 1$

Wrap Up. Here is a procedure to recover $\mathbf S [k]$.

• Case 1. If the number of $(-)$ is odd, then $\mathbf S [k]$ is even and $\mathbf S [k]=2\frac{\tau _1+\tau _2}{2}=\tau _1+\tau _2$

• Case 2. If the number of $(-)$ is even, then $\mathbf S [k]=2 \Big \lfloor \frac{\tau _1+\tau _2}{2}\Big \rfloor +1$

• Case 3. If at most one change of sign occur, the procedure is restarted.

If the number of restarts is too large (say, $\ge M$), the procedure is stopped and the coefficient, placed in a bruteforce set, is found at the end of the attack.

Table 3. Average number of queries

Number of Queries. The amount of queries is derived with the same technique as in the full version of our paper [2]. See Table 3 for the average number of queries. Let us set the threshold M to 50, to get the total average number of queries, we compute the expected number of queries for $\mathbf S [k]$ (${\approx }18$) and multiply it by $N=1024$.

Success Probability. The success probability depends only on Hypothesis 1 with $\mathbf S ^1$, which becomes the following for $\mathbf S$.

Hypothesis 2

$\forall i,k \in [1,n-1]\ \sum _{j=0}^{j=3} \biggm |\frac{\mathbf {S}[k+i+nj \mod N ]}{2} + 4 \biggm |\ge 8$

Hypothesis 2 is true with a probability 94.6% for $N = 1024$. Indeed, to compute this probability, one can check whether each quadruplet verifies it. Only a few unlikely quadruplet (e.g. [8, 8, 8, 8]) do not verify the hypothesis.    $\square$

4.4 Experimental Results

We implemented a proof of concept with Magma CAS [5]⁶. We coded NewHope according to its parameters and used the key mismatch oracle for the attack. We worked on a basic optimization of the number of queries. We ran 1000 experiments and recovered more than $95\%$ of the secret keys in an average time of 30 minutes per key and 16,700 queries. We still think that the number of queries and the time can be better optimized.

5 Accessing the Key Mismatch Oracle with the CCA Version of NewHope

In order to be protected against active attacks, the CPA-KEM of NewHope has been transformed according to the Hofheinz, Hövelmanns and Kiltz CCA transformation [16] which is a variant of the Fujisaki-Okamoto transformation [11]. The CCA security is then based on the CPA security of the PKE. The CCA transformation of the algorithms defining this version of NewHope is detailed in Algorithms 5, 6 and 7. These algorithms use the underlying CPA-PKE of NewHope as defined in Sect. 1.2.1 of [23].

One can note the main security measure in Algorithm 7 where the instruction in red corresponds to a double encryption to check if the message $m_B$ has been honestly generated.

More precisely, in the key mismatch oracle, the message $m_B$ can be adjusted by the attacker but with this CCA version of NewHope, Eve must follow the protocol and generate $m_E$ according to a seed called $coin'$ that is derived from $\mu _E$ and another seed called coin (a 32-byte random integer). Then, Alice will derive $coin'$ to check if $\mu _E$ was computed following the protocol. Then, a key mismatch will come from the following oracle

(7)

This oracle is less convenient than $\mathcal {O}_{1}$ because with an honest behaviour, the error probability is claimed to be lower than $2^{-213}$ in the NIST specification (paragraph 4.2.7 of [23]). In the sequel, we point at critical steps inside the CCA transform that let Eve access oracle $\mathcal {O}_{1}$ using side channel or fault attacks.

On Using Side Channel or Fault Attack

When the attacker has access to a device implementing Alice’s side of the exchange, the attack model should take into account situations where some algorithmic security measures may be bypassed by using hardware attacks.

Power Analysis. Here we consider that Eve is able to make a power analysis during the verification step of Alice decapsulation algorithm.

Attack Model 2

We assume that Alice has done the CCA key generation. Eve sends messages $m_E$ with a wrong coin. Alice will then reject any messages $m_e$ because the verification is never passed. Eve, the attacker, is able to make a power analysis during the verification step of Alice’s decapsulation algorithm.

With a power analysis, Eve can easily get the desired key mismatch oracle with a low number of traces.

A first idea would be to target the computation of $d = d'$ with differential power analysis. The following code corresponds to NewHope-CCA-KEM verification step where $a=(c,d)$, $b =($ NewHope-CPA-PKE.Encrypt($pk,\mu ';coin''),d')$ and $len = 17/8\cdot N+32$.

This naive method actually works well in practice for an unprotected scheme because when $d=d'$, r is ored with 0 during $17/8\cdot N$ iterations and when $d\ne d'$, r is ored with arbitrary values during $17/8\cdot N$ iterations. With a single trace analysis, the equality $d=d'$ can be verified. One would argue reasonably that unprotected schemes are always vulnerable. The main aim of [21] is to propose a countermeasure to such an attack for a similar scheme which uses the CCA transform. It is an open problem, in this protected context, to extend this approach to a second order power analysis attack. A more realistic model relies on an invasive attack, this is what we present in the sequel.

Single Fault Attack. We consider inserting a fault during the computation of the verification step which cancels the CCA transform. The attack model becomes:

Attack Model 3

We assume that Alice has done the CCA key generation. Eve, the attacker, is able to set the value r to 0 in the verification step of Alice’s decapsulation algorithm.

If Eve is able to set the value r to 0 anytime during the check $d=d'$, she can bypass the reencryption and the mismatch will appear only if $d \ne d'$. Then oracle $\mathcal {O}_1$ becomes accessible. Indeed, Eve can thus send any message $m_E$. Alice derives a wrong $coin'$ but the verification is skipped with the fault. If $d = d'$, Alice derives the shared key for initiating a communication. If $d \ne d'$, Alice will notice Eve that the key agreement failed. Eve will then deduce that the key is different. This vulnerability has been underlined in Sect. 3.6 of [21] for a similar scheme. But no countermeasure has been added to protect against this single fault attack, which can practically be induced by a laser. Countermeasures should have thus to be considered (see [18]), what may impact the efficiency of the verification.

6 Conclusion

The resilience of NIST post-quantum candidate algorithms in misuse situations is worth being investigated. It will help developers to propose implementations with countermeasures tightly designed to ensure the security in extreme contexts (e.g. smart card, IoT) without decreasing too much the efficiency. In this paper, we describe an active attack against NewHope-CPA-KEM with (public, private) key pair reuse. This clearly confirms that if the designers’ caveat against any private key reuse (e.g. temporary caching) is not strictly followed, this results in a practical, low complexity, key recovery attack. Our study indeed indicates that setting an upper limit of a few hundreds on the number of authorized key reuses would not be conservative enough, and already expose private keys to significant information leakages. While unprotected versions of CCA-KEM are extremely efficient, implementations of this scheme must be very carefully protected against any key mismatch oracle leakage if key pairs are potentially reused. As explained in this paper, this is particularly true for countermeasures against fault attacks. This might eventually come with a cost in terms of performance. This consideration may become even more important if one considers second order side channel or combined attacks, which could be a sequel of this work.