Gabrielle De Micheli

Rémi Piau

Cécile Pierrot

A Tale of Three Signatures: practical attack of ECDSA with wNAF

Keywords: Public key cryptography, ECDSA, Side channel attack, windowed Non-Adjacent Form, Lattice techniques

Attacking ECDSA with wNAF implementation for the scalar multiplication first requires some side channel analysis to collect information, then lattice based methods to recover the secret key. In this paper, we reinvestigate the construction of the lattice used in one of these methods, the Extended Hidden Number Problem (EHNP). We find the secret key with only 3 signatures, thus reaching a known theoretical bound, whereas best previous methods required at least 4 signatures in practice. Given a specific leakage model, our attack is more efficient than previous attacks, and for most cases, has better probability of success. To obtain such results, we perform a detailed analysis of the parameters used in the attack and introduce a preprocessing method which reduces by a factor up to 7 the total time to recover the secret key for some parameters. We perform an error resilience analysis which has never been done before in the setup of EHNP. Our construction find the secret key with a small amount of erroneous traces, up to 2% of false digits, and 4% with a specific type of error.

Introduction

The Elliptic Curve Digital Signature Algorithm (ECDSA) [START_REF] Johnson | The elliptic curve digital signature rithm (ECDSA)[END_REF], first proposed in 1992 by Scott Vanstone [START_REF] Vanstone | Responses to NIST's proposals[END_REF], is a standard public key signature protocol widely deployed. ECDSA is used in the latest library TLS 1.3, email standard OpenPGP and smart cards. It is also implemented in the library OpenSSL, and can be found in cryptocurrencies such as Bitcoin, Ethereum and Ripple. It benefits from a high security based on the hardness of the elliptic curve discrete logarithm problem and a fast signing algorithm due to its small key size. Hence, it is recognized as a standard signature algorithm by institutes such as ISO since 1998, ANSI since 1999, and IEEE and NIST since 2000.

The ECDSA signing algorithm requires scalar multiplications of a point P on an elliptic curve by an ephemeral key k. Since this operation is time-consuming and often the most time-consuming part of the protocol, it is necessary to use an efficient algorithm. The Non Adjacent Form (NAF) and its windowed variant (wNAF) were introduced as an alternative to the binary representation of the nonce k to reduce the execution time of the scalar multiplication. Indeed, the NAF representation does not allow two non-zero digits to be consecutive, thus reducing the Hamming weight of the representation of the scalar. This improves on the time of execution as the latter is dependent on the number of non-zero digits. The wNAF representation is present in implementations such as in Bitcoin, as well as in the libraries Cryptlib, BouncyCastle and Apple's Common-Crypto. Moreover, until very recently (May 2019), wNAF was present in all three branches of OpenSSL.

However, implementing the scalar multiplication using wNAF representation and no added layer of security makes the protocol vulnerable to side-channel attacks. Side-channel attacks were first introduced about two decades ago by Kocher et al [START_REF] Kocher | Differential power analysis[END_REF], and have since been used to break many implementations, and in particular some cryptographic primitives such as AES, RSA, and ECDSA. They allow to recover secret information throughout observable leakage. In our case, this leakage corresponds to differences in the execution time of a part of the signing algorithm, observable by monitoring the cache.

For ECDSA, cache side-channel attacks such as Flush&Reload [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF]35] have been used to recover information about either the sequence of operations used to execute the scalar multiplication, or for example in [START_REF] García | Constant-time callees with variable-time callers[END_REF] the modular inversion. For the scalar multiplication, these operations are either a multiplication or an addition depending on the bits of k. This information is usually referred to as a double-and-add chain or the trace of k. A trace is created when a signature is produced by ECDSA and thus we talk about signatures and traces in an equivalent sense. At this point, we ask how many traces need to be collected to successfully recover the secret key. Indeed, from an attacker's perspective, the least traces necessary, the more efficient the attack is. This quantity depends on how much information can be extracted from a single trace and how combining information of multiple traces is used to recover the key. We work on the latter to minimize the number of traces needed.

The nature of the information obtained from the side channel attack allows to determine what kind of method should be carried out to recover the secret key. Attacks on ECDSA are inspired by attacks on a similar cryptosystem, DSA. In 2001, Howgrave-Graham and Smart [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF] showed how knowing partial information of the nonce k in DSA can lead to a full secret key recovery. Later, Nguyen and Shparlinski [START_REF] Nguyen | The insecurity of the elliptic curve digital signature algorithm with partially known nonces[END_REF] gave a polynomial time algorithm that recovers the secret key in ECDSA as soon as some consecutive bits of the ephemeral key are known. They showed that using the information leaked by the side channel attack, one can recover the secret key by constructing an instance of the Hidden Number Problem (HNP) [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[END_REF]. The basic structure of the attack algorithm is to construct a lattice which contains the knowledge of consecutive bits of the epheremal keys, and by solving CVP or SVP, to recover the secret key. This type of attack has been done in [START_REF] Benger | ooh aah... just a little bit": A small amount of side channel can go a long way[END_REF][START_REF] Van De Pol | Just a little bit more[END_REF][START_REF] Wang | Attacking OpenSSL ECDSA with a small amount of sidechannel information[END_REF][START_REF] García | Constant-time callees with variable-time callers[END_REF]. However, these results considered perfect traces, but obtaining traces without any misreadings is very rare. In 2018, Dall et al. [START_REF] Dall | Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks[END_REF] included an error-resilience analysis to their attack: they showed that key recovery with HNP is still possible even in the presence of erroneous traces.

In 2016, Fan, Wang and Cheng [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] used another lattice-based method to attack ECDSA: the Extended Hidden Number Problem (EHNP) [START_REF] Hlavác | Extended hidden number problem and its cryptanalytic applications[END_REF]. EHNP mostly differs from HNP by the nature of the information given as input. Indeed, the information required to construct an instance of EHNP is not sequences of consecutive bits, but the positions of the non-zero coefficients in any representation of some integers. This model, which we consider in this article as well, is relevant when describing information coming from Flush&Reload or Prime&Probe attacks for example, the latter giving a more generic scenario with no shared data between the attacker and the victim. In [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the authors are able to extract 105.8 bits of information per signature on average, and thus require in theory only 3 signatures to recover a 256-bit secret key. In practice, they were able to recover the secret key using 4 error-free traces.

In order to optimize an attack on ECDSA various aspects should be considered. By minimizing the number of signatures required in the lattice construction, one minimizes the number of traces needed to be collected during the side-channel attack. Moreover, reducing the time of the lattice part of the attack, and improving the probability of success of key recovery allows to reduce the overall time of the attack. In this paper, we improve on all three of these aspects. Furthermore, we propose the first error-resilience analysis for EHNP and show that key recovery is still possible with erroneous traces too.

Contributions:

In this work, we reinvestigate the attack against ECDSA with wNAF representation for the scalar multiplication using EHNP. We focus on the lattice part of the attack, i.e., the exploitation of the information gathered by the side-channel attack. We first assume we obtain a set of error-free traces from a side-channel analysis. We preselect some of these traces to optimize the attack. The main idea of the lattice part is then to use the ECDSA equation and the knowledge gained from the selected traces to construct a set of modular equations which include the secret key as an unknown. These modular equations are then incorporated into a lattice basis similar to the one given in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], and a short vector in it will contain the necessary information to reconstruct the secret key. We call "experiment" one run of this algorithm. An experiment succeeds if the algorithm recovers the secret key.

A new preprocessing method. The idea of selecting good traces beforehand has already been explored in [START_REF] Wang | Attacking OpenSSL ECDSA with a small amount of sidechannel information[END_REF]. The authors suggest three rules to select traces that improve the attack on the lattice part. Given a certain (large) amount of traces available, the lattice is usually built with a much smaller subset of these traces. Trying to identify beforehand the traces that would result in a better attack is a clever option. The aim of our new preprocessing -that completely differs from [START_REF] Wang | Attacking OpenSSL ECDSA with a small amount of sidechannel information[END_REF] -is to regulate the size of the coefficients in the lattice, and this results in a better lattice reduction time. For instance, with 3 signatures, we were able to reduce the total time of the attack by a factor of 7.

Analyzing the attack. Several parameters intervene while building and reducing the lattice. We analyze the performance of the attack with respect to these parameters and present the best parameters that optimize either the total time or the probability of success.

First, we focus on the attack time. Note that when talking about the overall time of the attack, we consider the average time of a single experiment multiplied by the number of trials necessary to recover the secret key. We compare 3 our times with the numbers reported in [7, Table 3] with method C. Indeed, methods A and B in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] use extra information that comes from choices in the implementation which we choose to ignore as we want our analysis to remain as general as possible. The comparison is justified as we consider the same leakage model, and compare timings when running experiments on similar machines. For 4 signatures, our attack is slightly slower 4 than timings in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. However, when considering more than 4 signatures, our attack is faster. We experiment up to 8 signatures to further improve our overall time. In this case, our attack runs at best in 2 minutes and 25 seconds. Timings for 8 signatures are not reported in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], and the case of 3 signatures was never reached before our work. In Table 1, we compare our times with the fastest times reported by [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. We choose their fastest times but concerning our results we choose to report experiments which are faster (not the fastest) with, if possible, better probability than theirs. The overall time of the attack is also dependent on the success probability of key recovery. From Table 2, one can see that our success probability is higher than [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], except for 7 signatures. They have 68% of success with their best parameters whereas we only reach 45% in this case.

For the sake of completeness, we mention that in [START_REF] Van De Pol | Just a little bit more[END_REF], the authors use HNP to recover the secret key using 13 signatures. Their success probability in this case is around 54 % and their overall time is close to 20 seconds, hence much 3 In order to have a fair comparison with our methodology, the times reported in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] with which we compare ourselves have to be multiplied by the number of trials necessary for their attack succeed, thus increasing their total time by a lot. Using 5 signatures, their best total time would be around 15 hours instead of 18 minutes. 4 For 4 signatures, no times are reported without method A. Thus, we have no other choice than to compare our times with theirs, using A. Yet their time for 4 signatures without A should at least be the time they report with it.

faster. However, as their leakage model is different, we do not further mention their work.

Finding the key with only three signatures. Overall, combining a new preprocessing method, a modified lattice construction and a careful choice of parameters allows us to mount an attack which works in practice with only 3 signatures. However, the probability of success in this case is very low. We were able to recover the secret key only once with BKZ-35 over 5000 experiments. This result is difficult to quantify as a probability but we note that finding the key a single time over 5000 experiments is still much better than randomly finding a 256-bit integer. If we assume the probability is around 0.02%, as each trial costs 200 seconds in average, we can expect to find the secret key after 12 days using a single core. Note that this time can be greatly reduced when parallelizing the process, i.e., each trial can be run on a separate core. On the other hand, if we use our preprocessing method, with 3 signatures we obtain a probability of success of 0.2% and a total time of key recovery of 39 hours, thus the factor 7 of improvement mentioned above. Despite the low probability of success, this result remains interesting nonetheless. Indeed, the authors in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] reported that in practice, the key couldn't be recovered using less than 4 signatures and we improve on their result. Resilience to errors. We also investigate the resilience to errors of our attack. Such an analysis has not yet been done in the setup of EHNP. It is important to underline that collecting traces without any errors using any side-channel attack is very hard. Previous works used perfect traces to mount the lattice attack. Thus, it required collecting more traces. As pointed out in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], more or less twice as many signatures are needed if errors are considered. In practice, this led [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] to gather in average 8 signatures to be able to find the key with 4 perfect traces.

We experimentally show that we are still able to recover the secret key even in the presence of faulty traces. In particular, we find the key using only 4 faulty traces, but with a very low probability of success. As the percentage of incorrect digits in the trace grows, the probability of success decreases and thus more signatures are required to successfully recover the secret key. For instance, if 2% of the digits are wrong among all the digits of a given set of traces, it is still possible to recover the key with 6 signatures. This result is valid if errors are uniformly distributed over the digits. However, we have a better probability to recover the key if errors consist in 0-digit faulty readings, i.e., 0 digits read as non-zero. In other words, the attack could work with a higher percentage of errors, around 4%, if we could ensure from the side channel attack and some preprocessing methods that none of the non-zero digits have been flipped to 0.

Looking at Coppersmith. Finally, as the EHNP setup consists of a system of modular equations for which we look for integer roots, we investigate the use of Coppersmith's method for finding small roots of integer polynomials, as an alternative to EHNP. Albeit our attempts to apply Coppersmith's method were not successful as some bound on the unknowns is not satisfied, we briefly sketch our ideas hoping it could lead to further improvements.

Organization: In Section 2, we introduce some background on ECDSA and the wNAF representation. Moreover, we give details on lattices and well known reduction algorithms. In Section 3, we explain how the Extended Hidden Number problem can be transformed into a lattice problem. We explicit the lattice basis and give some analysis on the length of the short vectors found in the reduced basis. In Section 4, we introduce our preprocessing method which allows us to reduce the overall time of our attack. In Section 5, we give experimental results which shows the performance of our attack as a function of the various parameters that are being considered. In Section 6, we analyze the resilience of our attack to erroneous traces. Finally in Section 7, we describe our attempt to use Coppersmith's method instead of EHNP.

Preliminaries

Elliptic Curves Digital Signature Algorithm

The Elliptic Curves Digital Signature Algorithm is a variant of the Digital Signature Algorithm, DSA, [21] which uses elliptic curves instead of finite fields. The parameters used in the ECDSA algorithm are an elliptic curve E over a finite field, a generator G of prime order q and a hash function H. The private key is an integer α such that 1 < α < q -1 and the public key is

p k = [α]G, the scalar multiplication of G by α.
To sign a message m using the private key α, randomly select an ephemeral key k ← R Z q and compute [k]G. Let r be the x-coordinate of [k]G. If r = 0, select a new nonce k. Then, compute s = k -1 (H(m) + αr) mod q and again if s = 0, select a new nonce k. Finally, the signature is given by the pair (r, s).

In order to verify a signature, first check if r, s ∈ Z q , otherwise the signature is not valid. Then, compute

v 1 = H(m) • s -1 mod q, v 2 = r • s -1 mod q and (x, y) = [v 1 ]G + [v 2 ]p k . Finally, the signature is valid if x ≡ r (mod q).
Remark 1. In this paper, we consider a 128 bit level of security and thus α, q and k are all 256-bit integers.

wNAF representation

The ECDSA algorithm presented above requires the computation of [k]G which corresponds to a scalar multiplication. In [START_REF] Gordon | A survey of fast exponentiation methods[END_REF], various methods to compute fast exponentiation are presented. One family of such methods is called window methods and comes from NAF representation. Indeed, the NAF representation does not allow two non-zero digits to be consecutive, thus reducing the Hamming weight of the representation of the scalar. The basic idea of a window method is to consider chunks of w bits in the representation of the scalar k, compute powers in the window bit by bit, square w times and then multiply by the power in the next window. The window methods can be combined with the NAF representation of k, as we will explain now. For any k ∈ Z, a representation

k = ∞ j=0 k j 2 j
is called a NAF if k j ∈ {0, ±1} and k j k j+1 = 0 for all j ≥ 0. Moreover, every k has a unique NAF representation. The NAF representation minimizes the number of non-zero digits k j . It is presented in Algorithm 1.

Input : k ∈ Z + Output: NAF representation of k i = 0; while k > 0 do if k (mod 2) = 1 then ki = 2 -(k (mod 4)); k = k -ki; else ki = 0; end k = k/2; i = i + 1; end return ki-1, ki-2, . . . , k1, k0
Algorithm 1: NAF algorithm

The NAF representation can be combined with a sliding window method to further improve the execution time. For instance, in OpenSSL (up to the latest versions using wNAF 1.1.1b for example), the window size usually chosen was w = 3. The scalar k is converted into wNAF form using Algorithm 2. Note that in Algorithm 2, the sequence of digits m i belongs to the set {0, ±1, ±3, . . . , ±(2 w -

Input: k ∈ Z + , w ∈ N Output: (m0, m1, . . . , mn), i.e., k in its wNAF representation i = 0; while k > 0 do if k (mod 2) = 1 then mi = k (mod 2 w+1 ); if mi ≥ 2 w then mi = mi -2 w+1 ; end k = k -mi; else mi = 0; end k = k/2; i = i + 1; end
Algorithm 2: wNAF representation 1)}. We can rewrite k as a sum of its non-zero digits, which we rename k i . More precisely, we get

k = j=1 k j 2 λj ,
where is the number of non-zero digits, and λ j represents the position of the digit k j in the wNAF representation.

Example 1. In binary, we can write

23 = 2 4 + 2 2 + 2 1 + 2 0 = (1, 0, 1, 1, 1)
whereas in NAF-representation, we have

23 = 2 5 -2 3 -2 0 = (1, 0, -1, 0, 0, -1).
Using a window size w = 3, the wNAF representation gives

23 = 2 4 + 7 × 2 0 = (1, 0, 0, 0, 7).
There exists a modified wNAF representation used in OpenSSL for example. In the non-modified wNAF representation, at most one of any w + 1 consecutive digits is non-zero and in the modified version, this also stands with the exception that the most significant digit may be only w -1 zeros away from that next nonzero digit.

Lattice reduction algorithms

A lattice is a discrete additive subgroup of R n . It is usually specified by giving a basis matrix B ∈ Z n×n . The lattice L(B) generated by B consists of all integer combinations of the row vectors in B. The determinant of a lattice is the absolute value of the determinant of a basis matrix: det L(B) = | det B|. The discreteness property ensures that there is some λ 1 > 0 such that the length of one of the shortest non-zero vectors v 1 in the lattice satisfies ||v 1 || = λ 1 . Let λ i be the i th successive minimum of the lattice. The LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] takes as an input a lattice basis, and returns in polynomial time in the lattice dimension n a reduced lattice basis whose vectors b i satisfy the worst-case approximation bound ||b i || 2 ≤ 2 (n-1)/2 λ i . In practice, for random lattices, LLL obtains approximation factors such that b 1 ≤ 1.02 n λ 1 as noted by Nguyen and Stehlé [START_REF] Nguyen | LLL on the average[END_REF]. Moreover, for random lattices, we note that the Gaussian heuristic implies that

λ 1 ≈ n/(2πe) det(L) 1/n . (1)
The BKZ algorithm [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF][START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF] is exponential in some given block-size β and polynomial in the lattice dimension n. It outputs a reduced lattice basis whose vectors b i satisfy the approximation [START_REF] Schnorr | Block reduced lattice bases and successive minima[END_REF], where γ β is the Hermite constant. In practice, Chen and Nguyen [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF] observed that BKZ returns vectors such that b 1 ≤ (1 + β ) n λ 1 where β depends on the block-size β. For random lattices, they get 1 + β = 1.01 for a block-size β = 85.

||b i || 2 ≤ iγ (n-i)/(k-1) β λ i

Attacking ECDSA using lattices

Using some side-channel attack, one can recover information about the wNAF representation of the nonce k. In particular, it allows us to know the positions of the non-zero coefficients in the representation of k. However, the value of these coefficients are unknown. This information can be used in the setup of the Extended Hidden Number Problem (EHNP) to recover the secret key. For many messages m, we use ECDSA to produce signatures (r, s) and each run of the signing algorithm produces a nonce k. We assume we have the corresponding trace of the nonce, that is, the equivalent of the double-and-add chain of kG using wNAF. The goal of the attack is to recover the secret α while optimizing either the number of signatures required or the total time of the attack.

The Extended Hidden Number Problem

The Hidden Number Problem (HNP), introduced in 1996 [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[END_REF], allows to recover a secret element α ∈ Z q if some information about the most significant bits of random multiples of α (mod q) are known for some prime q. Boneh and Venkatesan show how to recover α in polynomial time with probability greater than 1/2. In [START_REF] Hlaváč | Extended hidden number problem and its cryptanalytic applications[END_REF], the authors extend the HNP and present a polynomial time algorithm for solving the instances of this extended problem. The Extended Hidden Number Problem is defined as follows. Given u congruences of the form

a i α + i j=1 b i,j k i,j ≡ c i (mod q), (2)
where the secret α and 0 k i,j 2 ηij are unknown, and the values η ij , a i , b i,j , c i , i are all known for 1 i u (see [START_REF] Hlaváč | Extended hidden number problem and its cryptanalytic applications[END_REF], Definition 3), one has to recover α in polynomial time. Similarly to the HNP, the EHNP can be transformed into a lattice problem and one can recover the secret α by solving a short vector problem in a given lattice.

Using EHNP to attack ECDSA

From the ECDSA algorithm, we know that given a message m, the algorithm outputs a signature (r, s) such that

αr = sk -H(m) (mod q). (3)
The value H(m) is just some hash of the message m. We consider a set of u signature pairs (r i , s i ) with corresponding message m i that satisfies Equation (3).

For each signature pair, we have a nonce k. Using the wNAF representation of k, we write k = j=1 k j 2 λj , with k j ∈ {±1, ±3, . . . , ±(2 w -1)} and the choice of w depends on the implementation. Note that the coefficients k j are unknown, however, the positions λ j are supposed to be known via some sidechannel leakage. It is then possible to represent the ephemeral key k as the sum of a known part, and an unknown part. As the value of k j is odd, one can write k j = 2k j + 1, where -2 w-1 k j 2 w-1 -1. Using the same notations as in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], set d j = k j + 2 w-1 , where 0 ≤ d j ≤ 2 w -1. In the rest of the paper, we will denote by µ j the window-size of d j . Note that here, µ j = w but this window-size will be modified later. This allows to rewrite the value of k as

k = j=1 k j 2 λj = k + j=1 d j 2 λj +1 , (4)
with k = j=1 2 λj -j=1 2 λj +w . The expression of k represents the known part of k. By substituting k in Equation ( 4), we obtain a system of modular equations of the form

αr i - i j=1 2 λi,j +1 s i d i,j -(s i ki -H(m i )) ≡ 0 (mod q) ( 5
)
where the unknowns are α and the d i,j . The known values are the i which is the number of non-zero digits in k for the i th sample, λ i,j , which is the position of the j th non-zero digit in k for the i th sample and k defined above. We can then use Equation ( 5) as input to the Extended Hidden Number Problem, following the method explained in [START_REF] Hlaváč | Extended hidden number problem and its cryptanalytic applications[END_REF]. The problem of finding the secret key is then reduced to solving the short vector problem in a given lattice which we give in the following section.

Constructing the lattice

Before giving the lattice basis construction, we redefine Equation ( 5) to reduce the number of unknown variables in the system. This will allow us to construct a lattice of smaller dimension. Again, we use the same notations as in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF].

Eliminating one variable. One straightforward way to reduce the lattice dimension is to eliminate a variable from the system. In this case, one can eliminate α from Equation [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]. Let E i denote the i th equation of the system. Then by computing r 1 E i -r i E 1 , we get the following new modular equations

1 j=1 (2 λ1,j +1 s 1 r i ) :=τj,i d 1,j + i j=1 (-2 λi,j +1 s i r 1 ) :=σi,j d i,j -r 1 (s i ki -H(m i )) + r i (s 1 k1 -H(m 1 )) :=γi ≡ 0 (mod q).
(6) Again, using the same notations as in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], we define τ j,i = 2 λ1,j +1 s 1 r i , σ i,j = -2 λi,j +1 s i r 1 and

γ i = r 1 (s i ki -H(m i )) + r i (s 1 k1 -H(m 1 )) for 2 i u, 1 j i .
Even if α is eliminated from the equations, if we are able to recover some d i,j values from a short vector in the lattice, we can recover α using any equation in the modular system [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF]. We will now use Equation ( 6) to construct the lattice basis. From a modular system to a lattice basis. Let L be the lattice constructed for the attack, and we have L = L(B) where the lattice basis B is given below. Let m = max i,j µ ij for 1 j i and 2 i u. We set a scaling factor ∆ ∈ N to be defined later. The lattice basis is given by

B = Eq (6), i = 2 . . . Eq (6), i = u                                                               ∆2 m q 0 0 0 0 . . . . . . 0 • • • ∆2 m q 0 ∆2 m τ 1,2 . . . ∆2 m τ 1,u 2 m-µ1,1 . . . . . . 0 . . . ∆2 m τ 1,2 . . . ∆2 m τ 1 ,u 2 m-µ1, 1 ∆2 m σ 2,1 0 0 2 m-µ2,1 . . . . . . . . . ∆2 m σ 2, 2 . . . 2 m-µ2, 2 0 . . . 0 . . . . . . . . . ∆2 m σ u,1 2 m-µu,1 . . . . . . . . . 0 0 ∆2 m σ u, u 0 2 m-µu, u ∆2 m γ 2 . . . ∆2 m γ u 2 m-1 . . . 2 m-1 2 m-1
Let n = (u -1) + T + 1 = T + u, with T = u i=1 i , be the dimension of the lattice. The u -1 first columns correspond to Equation (6) for 2 ≤ i ≤ u.

Each of the remaining columns, except the last one, corresponds to a d ij , and contains coefficients that allow to regulate the size of the d ij . The determinant of L is given by

det L = q u-1 (∆2 m ) u-1 2 i,j (m-µi,j ) 2 m-1 .
The lattice is built such that there exists w ∈ L which contains the unkowns d i,j . To find it, we know there exists some values t 2 , t 2 , . . . , t u such that if v = (t 2 , . . . , t u , d 1,1 , . . . , d u, u , -1), we get

w = vB, (7)
and

w = (0, . . . , 0, d 1,1 2 m-µ1,1 -2 m-1 , . . . , d u, u 2 m-µ u, u -2 m-1 , -2 m-1
).

If we are able to find w in the lattice, then we can reconstruct the secret key α. In order to find w, we estimate its norm and make sure w appears in the reduced basis. After reducing the basis, we look for vectors of the correct shape, i.e., with sufficiently many zeros at the beginning and the correct last coefficient, and attempt to recover α for each of these.

How the size of ∆ affects the norms of the short vectors. In order to find the vector w in the lattice, we reduce B using LLL or BKZ. For w to appear in the reduced basis, one should at least set ∆ such that

||w|| 2 (1.02) n (det L) 1/n . (8)
The vector w we expect to find has norm ||w|| 2 2 m-1 √ T + 1. From Equation [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], one can deduce the value of ∆ needed to find w in the reduced lattice, which is given by the expression

∆ (T + 1) (T +u)/(2(u-1)) 2 1+ µ i,j -(u+T ) u-1 q(1.02) (T +u) 2 u-1 := ∆ th
In our experiments, the average value of i for 1 i u is ˜ = 26, and thus T = u × ˜ on average. Moreover, the average value of µ ij is 7 and so on average

µ ij = 7 × u × ˜ .
Hence, if we compute ∆ th for u = 3, . . . , 8, with these values, we obtain ∆ th 1, which does not help us to set this parameter. In practice, we verify that setting ∆ = 1 allows us to recover the secret key.

In our experiments, we vary the bitsize of ∆ to see whether a slightly larger value affects the probability of success. This comment will be adressed in Section 5.

Too many small vectors. While running BKZ on B, we note that for some specific sets of parameters the reduced basis contains some undesired short vectors, i.e., vectors that are shorter than w. This can be explained by looking at two consecutive rows in the lattice basis given above, say the j th row and the (j +1) th row. For example, one can look at rows which correspond to the σ i,j values but the same argument is valid for the rows concerning the τ j,i . From the definitions of the σ values we have

σ i,j+1 = -2 λi,j+1+1 • s i r 1 = -2 λi,j+1+1 • ( σi,j -2 λ i,j+1 +1 ) = 2 λi,j+1-λi,j • σ i,j
Thus the linear combination given by the (j + 1) th row minus 2 λi,j+1-λi,j times the j th row gives a vector

(0 , • • • , 0 , -2 λi,j+1-λi,j +m-µi,j , 2 m-µi,j+1 , 0 , • • • , 0). ( 9
)
Yet, this vector is expected to have smaller norm than w. Some experimental observations are detailed in Section 5.

Remark 2. It would be of interest to understand how one can modify the lattice construction to always find w as the shortest vector of the reduced basis. Indeed, by reducing the number of vectors shorter than w we expect to increase the probability of success of our attack. This would lower the chances of w being a linear combination of short vectors and thus not appearing in the reduced basis.

Differences with the lattice construction given in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. Let B be the lattice basis constructed in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. Our basis B is a rescaled version of B such that B = 2 m ∆B . This rescaling allows us to ensure that all the coefficients in our lattice basis are integer values. Note that [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] have a value δ in their construction which corresonds to 1/∆. In this work, we give a precise analysis of the value of ∆, both theoretically and experimentally in Section 5, which is missing in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF].

4 Improving the lattice attack

Reducing the lattice dimension: the merging technique

In [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the authors present another way to further reduce the lattice dimension, which they call the merging technique. It aims at reducing the lattice dimension by reducing the number of non-zero digits of k. The lattice dimension depends on the value T = u i=1 i , and thus reducing T reduces the dimension. To understand the attack, it suffices to know that after merging, we obtain some new values corresponding to the new number of non-zero digits and λ j the position of these digits for 1 j . After merging, one can rewrite k = k + j=1 d j 2 λ j +1 , where the new d j have a new window size which we denote µ j , i.e., 0 d j 2 µj -1.

We present here our merging algorithm based on Algorithm 3 given in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. Our algorithm modifies directly the sequence {λ j } j=1 , whereas [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] work on the double-and-add chains. This helped us avoid some implementation issues such as an index outrun present in Algorithm 3 [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], line 7. To facilitate the ease of reading of (our) Algorithm 3, we work with dynamic tables. To do so, we first recall various known methods we use in the algorithm: push back(e) inserts an element e at the end of the table, at(i) outputs the element at index i, and last() returns the last element of the table. We consider tables of integers indexed in [0; S -1], where S is the size of the table.

Input : v λ ,
i < n do dist ← v λ .at(i) -v λ .at(i -1); if dist > w + 1 then vµ.push back(v λ .at(i -1) -v λ .last() + w); v λ .push back(v λ .at(i)); end i ← i + 1; end vµ.push back(v λ .at(n) -v λ .last() + w); return (v λ , vµ)
Algorithm 3: Merging algorithm A useful example of the merging technique is given in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. We give in Table 3 the approximate dimension of the lattices we obtain using the elimination and merging techniques. For the traces we consider, after merging the mean of the i is 26, the minimum being 17 and the maximum 37 with a standard deviation of 3. Remark 3. One could further reduce the lattice dimension by preprocessing traces with small i . However, the standard deviation being small, the difference in the reduction times should not be affected too much.

Preprocessing the traces

The two main pieces of information we can extract and use in our attack are first the number of non-zero digits in the wNAF representation of the nonce k, denoted and the weight of each non-zero digit, denoted µ j for 1 j . Let T be the set of traces we obtained from the side-channel leakage representing the wNAF representation of the nonce k used while producing an ECDSA signature. We consider the subset S a = {t ∈ T | max j µ j a, 1 j }. We choose to preselect traces in a subset S a for small values of a. The idea behind this preprocessing is to regulate the size of the coefficients in the lattice. Indeed, when selecting u traces for the attack, by upper-bounding m = max i,j µ i,j for 2 i u, we force the coefficients to remain smaller than when taking traces at random.

In practice, we work with a set T of 2000 traces such that min t∈T max j µ j = 11 and max t∈T max j µ j = 67. We consider the sets S 11 , S 15 and S 19 in our experiments. In Table 4, we give the proportion of signatures corresponding to the different preprocessing subsets. The effect of preprocessing on the total time of the attack is explained in Section 5.

Performance analysis

Traces from the real world. We work with the elliptic curve secp256k1 but none of the techniques introduced here are limited to this specific elliptic curve. We consider traces from a Flush&Reload attack, executed through hyperthreading, as it can virtually recover the most amount of information. 5To the best of our knowledge, the only information we can recover are the positions of the non-zero digits. We are not able to determine the sign or the value of the digits in the wNAF representation. In [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the authors exploit the fact that the length of the binary string of k is fixed in implementations such as OpenSSL, and thus more information can be recovered by comparing this length to the length of the double-and-add chain. In particular, they were able to recover the MSB of k, and in some cases the sign of the second MSB. We do not consider this extra information as we want our analysis to remain general.

We report calculations ran on error-free traces where we evaluate the total time necessary to recover the secret key and the probability of success of the attack. Our experiments have two possible outputs: either we reconstruct the secret key α and thus consider the experiment a success, or we do not recover the secret key, and the experiment fails. In order to compute the success probability and the average time of one reduction, we run 5000 experiments for some specific sets of parameters using either Sage's default BKZ implementation [START_REF]The FPLLL development team: FPLLL, a lattice reduction library[END_REF] or a more recent implementation of the latest sieving strategies, the General Sieve Kernel (G6K) [START_REF] Albrecht | The general sieve kernel and new records in lattice reduction[END_REF]. The experiments were ran using the cluster Grid'5000 on a single core of an Intel Xeon Gold 6130. The total time is the average time of a single reduction multiplied by the number of trials necessary to recover the key. The number of trials necessary to recover the secret key corresponds the number of experiments ran until we have a success for a given set of parameters. For a fixed number of signatures, we either optimize the total time or the success probability. We report numbers in Tables 5, 6 when using BKZ. 6Comments on G6K: We do not report the full experiments ran with G6K since using this implementation does not lead to the fastest total time of our attack: around 2 minutes using 8 signatures for BKZ and at best 5 minutes for G6K.

However, G6K allows to reduce lattices with much higher block-sizes than BKZ. For comparable probabilities of success, G6K is faster. Considering the highest probability achieved, on one hand, BKZ-35 leads to a probability of success of 45%, and a single reduction takes 133 minutes. On the other hand, to reach around the same probability of success with G6K, we increase the blocksize to 80, and a single reduction is only around 45 minutes on average. This is an improvement by a factor of 3 in the reduction time.

Experimentally, we vary the parameters that are considered in the attack: the bitsize of ∆, the preprocessing subset and the block-size used in BKZ.

Only 3 signatures. Using ∆ ≈ 2 3 and no preprocessing, we were able to recover the secret key using 3 signatures with BKZ-35 only once and three times with BKZ-40. When using pre-processing S 11 , BKZ-35 and ∆ ≈ 2 3 , the probability of success went up to 0.2%. Since all the probabilities remain much less than 1% an extensive analysis would have been too much time consuming to do. For this reason, in the rest of this section, the number of signatures only vary between 4 and 8. However, we want to emphasize that it is precisely this detailed analysis on a slightly higher number of signatures that allowed us to understand the impact of the parameters on the performance of the attack and resulted in finding the right ones allowing to mount the attack with 3 signatures.

Varying the bitsize of ∆. In Figure 1, we analyze the total time to recover the secret key as a function of the bitsize of ∆. We fix the block-size of BKZ to 25 and take traces without any preprocessing. We are able to recover the secret key by setting ∆ = 1, which is the lowest theoretical value one can choose. However, we observed a slight increase in the probability of success by taking a larger ∆. Without any surprise, we note that the total time to recover the secret key increases with the bitsize of ∆ as the coefficients in the lattice basis become larger. Details of the experiments are given in Appendix A.

Analyzing the effect of preprocessing. We also analyze the influence of our preprocessing method on the attack time. We fix BKZ block-size to 25. The effect of preprocessing is influenced by the bitsize of ∆ and we give here an analyze for ∆ ≈ 2 25 since the effect is more noticeable. We report results for ∆ ≈ 2 3 in Appendix B. We still gain time using the preprocessing but less than with ∆ ≈ 2 25 .

Fig. 1: Analyzing the overall time to recover the secret key as a function of the bitsize of ∆. We report the numbers BKZ-25 and no preprocessing. The optimal value for ∆ is around 2 3 except for u = 8 where it is 2 5 .

The effect of preprocessing is difficult to predict since its behavior varies a lot depending on the parameters, having both positive and negative effects. On the one hand, we reduce the size of all the coefficients in the lattice, thus reducing the reduction time. On the other hand, we generate more potential small vectors7 with norms smaller than the norm of w. For this reason, the probability of success of the attack decreases since the vector w is more likely to be a linear combination of vectors already in the reduced basis. For example, with 7 signatures we find in average w to be the third or fourth vector in the reduced basis without preprocessing, whereas with S 11 it is more likely to appear in position 40 on average. The positive effect of preprocessing is most noticeable for u = 4 and u = 5, as shown in Figure 2. For instance, using S 15 and u = 4 lowers the overall time by a factor up to 5.7. For u = 5, we gain a factor close to 3 by using either S 15 or S 19 .

For u > 5, using preprocessed traces is less impactful. For large ∆ such as ∆ ≈ 2 25 , we still note some lower overall times when using S 15 and S 19 , up to a factor 2. When the bitsize gets smaller, reducing the size of the coefficients in the lattice is less impacful. Details are given in Appendix B. Balancing the block-size of BKZ. Finally, we vary the block-size in the BKZ algorithm. We fix ∆ ≈ 2 3 and use no preprocessing. We plot the results in Figure 3 for 6 and 7 signatures. For other values of u, the plot is very similar and we omit them in Figure 3 for ease of lecture. Without any surprise, we see that as we increase the block-size, the probability of success increases, however the reduction time increases significantly as well. This explains the results shown in Table 5 and Table 6: to reach the best probability of success one needs to increase the block-size in BKZ (we did not try any block-size greater than 40), but to get the fastest key recovery attack, the block-size is chosen between 20 and 25, except for 3 signatures where the probability of success is too low with these parameters. Details are given in Appendix C.

Error resilience analysis

It is not unexpected to have errors in the traces collected during the side-channel attack. Obtaining a set of error-free traces requires some amount of work on the signal processing side. Prior to [START_REF] Dall | Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks[END_REF], the presence of errors in traces was either ignored or preprocessing was done on the traces until an error-free sample was found, see [START_REF] Genkin | ECDSA key extraction from mobile devices via nonintrusive physical side channels[END_REF][START_REF] Angel | DSA signing key recovery with noisy side channels and variable error rates[END_REF]. In [START_REF] Dall | Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks[END_REF], it is shown that the lattice attack still successfully recovers the secret key even when some traces contain errors. An error in the setup given in [START_REF] Dall | Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks[END_REF] corresponds to an incorrect bound on the size of the values being collected. In our setup, a trace without errors corresponds to a trace where every single coefficient in the wNAF representation of k has been identified Fig. 3: Analyzing the number of trials to recover the secret key and the reduction time of the lattice as a function of the block-size of BKZ. We consider the cases where u = 6 and u = 7. The dotted lines correspond to the number of trials, and the continued lines to the reduction time in seconds. correctly as either non-zero or not. The probability of having an error in our setup is thus much higher. Side-channel attacks without any errors are very rare. Both [START_REF] Van De Pol | Just a little bit more[END_REF] and [START_REF] Dall | Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks[END_REF] give some analysis of the attacks Flush&Reload and Prime&Probe in real life scenarios.

In [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the results presented in the paper assume the Flush&Reload is implemented perfectly, without any error. In particular, to obtain 4 perfect traces and be able to run their experiment and find the key, one would need to have in average 8 traces from Flush&Reload -the probability to conduct to a perfect reading of the traces being 56 % as pointed out in [START_REF] Van De Pol | Just a little bit more[END_REF]. In our work, we show that it is possible to recover the secret key using only 4, even erroneous, traces. However, the probability of success is very low.

Recall that an error in our case corresponds to a flipped digit in the trace of k. The following Table 7 shows the probability of success of the attack in the presence of errors. We ran experiments for BKZ-25 using ∆ ≈ 2 3 and traces taken from S all . We average over 5000 experiments.

We write 1 when the attack succeeded less than five times over 5000 experiments, thus making it difficult to evaluate the probability of success.

The attack works up to a resilience to 2% of errors, i.e., of flipped digits. Indeed, for u = 6, we were able to recover the secret key with 30 errors, meaning 30 flipped digits over 6 × 257 digits. Different types of errors. There exists two possible types of errors. In the first case, a coefficient which is zero is evaluated as a non-zero coefficient. In theory, this only adds a new variable to the system, i.e., the number of non-zero coefficients is overestimated. This does not affect the probability of success much. Indeed, we just have an overly-constrained system. We can see in Figure 4 that the probability of success of the attack indeed decreases slowly as we add errors of this form. With errors only of this form, we were able to recover the secret key up to nearly 4% of errors, for instance with u = 6, using BKZ-35, see Table 10 in Appendix D.

The other type of errors consists of a non-zero coefficients which is misread as a zero coefficient. In this case, we lose information necessary for the key recovery and thus this type of error affects the probability of success far more importantly as can also be seen in Figure 4. In this setup, we were not able to recover the secret key when more than 3 errors of this type appear in the set of traces considered. More details on the probabilities of success of these two types of errors can be seen in Appendix D.

If the signal processing method is hesitant between a 1 or 0 digit, we would recommend to favor putting 1 instead of 0 to increase the chance of having an error of type 0 → 1, for which the attack is a lot more tolerant.

An attempt at using Coppersmith's methods

Given that the setup of the Extended Hidden Number Problem gives a system of modular equations with the unknowns (α, d 1,1 , • • • , d u,lu ), it is natural to ask whether this system can be solved using Coppersmith's method for finding small modular roots of integer polynomials. Admittedly, α is of the order of magnitude of q so not so small, but by small root we mean that it is sufficient to know a bound on each variable.

Coppersmith's methods in the case of bivariate polynomials can be expressed as the following theorem [START_REF] Galbraith | Mathematics of Public Key Cryptography[END_REF]Theorem 19.2.1]. It states that a small modular root of a bivariate polynomial can be detected as an integer root of other polynomials.

Theorem 1. Let F (x 1 , x 2 ) ∈ Z[x 1 , x 2 ]
be a polynomial of total degree n. Let X 1 , X 2 , q ∈ N be such that X 1 X 2 < q 1/n-for some 0 < < 1/n. Then one can compute in time polynomial in log(q) and 1/ > n two polynomials F 1 (x 1 , x 2 ) and F 2 (x 1 , x 2 ) ∈ Z[x 1 , x 2 ] such that for all (x

(0) 1 , x (0)
2 ) ∈ Z 2 with |x

(0) 1 | < X 1 , |x (0) 2 | < X 2 and F (x (0) 1 , x (0)
2 ) ≡ 0 (mod q), one has F 1 (x

(0) 1 , x (0) 2 ) = F 2 (x (0) 1 , x (0)
2 ) = 0 over Z.

Theorem 1 is generalized to m variables in [START_REF] Jutla | On finding small solutions of modular multivariate polynomial equations[END_REF]. Let |x

(0) i | < X i for i = 1, • • • , m. In this setting, the condition X 1 • X 2 < q 1/n-for some 0 < < 1/n is replaced by X 1 • X 2 • • • X m < q 1/n-.
In our setup. We consider the system of u -1 modular equations after elimination, with T = u i=2 i variables. This allow us to have one less unknown and to avoid having to recover α which would be our largest variable as it is of the same order of magnitude of q whereas d i,j < 2 µi,j .

We have the following equations

F i (d 1,1 , . . . , d 1, 1, , . . . d u,1 , . . . , d u, u ) = 1 j=1 τ j,i d 1,j + i j=1 σ i,j d i,j -γ i ≡ 0 (mod q)
for 2 i u, and where τ ji , σ ij and γ i are defined as in Section 3.3. This system has u -1 equations and T unknowns. Note that F i is a linear polynomial and its total degree is n = 1.

Let D be a bound on the unknowns d ij , i.e., |d ij | < D. The condition in the theorem requires that D T < q 1- which means D < q (1-)/T . When → 1, we get that D < 1, and when → 0, we have D < q 1/T . If we consider the attack scenario where the number of signatures u ∈ [START_REF] Benger | ooh aah... just a little bit": A small amount of side channel can go a long way[END_REF][START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the value of T grows with u. For u = 3, the value T is of the order of 150 on average. This results in the condition D 3. But restricting the bound on the d ij to 3 at best seems too restrictive for the key recovery to be successful. Indeed, it means that the algorithm will miss all the solutions with at least one 3 < d i,j < 2 µi,j .

Remark 4. We also considered the equations without elimination, i.e., keeping the variable α. However, this resulted in an even stronger condition of D (D < 1) due to the size of α.

Remark 5. The theorem mentioned above is one of the many variations of Coppersmith's method. The proof of the theorem relies on the construction of a lattice whose coefficients correspond to the coefficients of the polynomials for which we want to find a modular root. The idea is to use LLL on this lattice to construct new polynomials with small coefficients, small enough so that the expected modular root is in truth a root of these new polynomials over the integers.

We have tested various construction for the lattice basis. In particular, we give our lattice construction in the elimination case in Appendix E. However, none of our constructions have allowed us to successfully recover the secret key.

Conclusion and countermeasures

In the last decades, most implementations of ECDSA have been the target of microarchitectural attacks, and thus existing implementations have either been replaced by more robust algorithms, or layers of security have been added.

For example, one way of minimizing leakage from the scalar multiplication is to use the Montgomery ladder scalar-by-point multiplication [START_REF] Montgomery | Speeding the pollard and elliptic curve methods of factorization[END_REF], much more resilient to side-channel attacks due to the regularity of the operations. However, this does not entirely remove the risk of leakage [34]. Additional countermeasures are necessary.

When looking at common countermeasures, many implementations use blinding or masking techniques [START_REF] Osvik | Cache attacks and countermeasures: The case of AES[END_REF], for example in BouncyCastle implementation of ECDSA. The former consists in blinding the data before doing any operations, and masking techniques randomize all the data-dependent operations by applying random transformations, thus making any leakage inexploitable.

However, it is important to keep in mind these lattices attacks as they can be applied at any level of an implementation that leaks the correct information.

B Preprocessing effect over the key recovery total time

We analyze the effect of the preprocessing. We fix BKZ-25 and ∆ ≈ 2 3 , 2 25 . We average over 5000 experiments.

D Analysis of errors

We analyze the effect of two possible kind of errors on the probability of success of our attack, using BKZ-25, ∆ ≈ 2 3 and no preprocessing. We average over 5000 experiments. We write 1 when the attack succeeded less than five times over 5000 experiments. When considering many errors, the probability of success can be increased by augmenting the block-size in the BKZ algorithm, as can be seen in Table 10.

Dq q

The dimension of this lattice is dim L = T + 1 and the determinant is given by det L = D T q T -u+2 .

Coppersmith's method uses LLL to produce polynomials with integer roots equal to those from the inital modular equations and to do so, the lattice basis must satisfy (1.02) n (det L) 1/n < q, where n = dim L. This implies we need the condition D < q u-1 1.02 (T +1) 2 1/T . Numerically, we get D < 1 for u ∈ [START_REF] Benger | ooh aah... just a little bit": A small amount of side channel can go a long way[END_REF][START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF].

Fig. 2 :

 2 Fig. 2: Analyzing the overall time to recover the secret key as a function of the preprocessing subset for 4 and 5 traces. The other parameters are fixed: ∆ ≈ 2 25 and BKZ-25.

Fig. 4 :

 4 Fig. 4: Probability of success for key recovery with various types of errors when using u = 8, BKZ-25, ∆ ≈ 2 3 , and no preprocessing.

Table 1 :

 1 Comparing attack times with[START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], for 5000 experiments.

	Number of	Our attack		[7]
	signatures	Time	Success (%)	Time	Success (%)
	3	39 hours	0.2	-	-
	4	1 hour 17 minutes	0.5	41 minutes	1.5
	5	8 minutes 20 seconds	6.5	18 minutes	1
	6	≈ 5 minutes	25	18 minutes	22
	7	≈ 3 minutes	17.5	34 minutes	24
	8	≈ 2 minutes	29	-	-

Table 2 :

 2 Comparing success probability with[START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], for 5000 experiments.

	Number of	Our attack		[7]
	signatures	Success (%)	Time	Success (%)	Time
	3	0.2	39 hours	-	-
	4	4	25 hours 28 minutes	1.5	41 minutes
	5	20	2 hours 42 minutes	4	36 minutes
	6	40	1 hour 4 minutes	35	1 hour 43 minutes
	7	45	2 hours 36 minutes	68	3 hours 58 minutes
	8	45	5 hours 2 minutes	-	-

  a table of size n with the positions of non-zero digits in the trace sorted in increasing order and n 1, a window size w. Output: v λ , a table of size n n containing the merged λ values and table vµ of same size n , with the values of the window size µi.

	Initialisation
	i ← 1;
	v λ ← empty array;
	vµ ← empty array;
	Processing
	v λ .push back(v λ .at(0));
	while

Table 3 :

 3 Average dimensions of the lattices after merging.

	Number of signatures	Average dimension
	3	80
	4	110
	5	135
	6	160
	7	190
	8

Table 4 :

 4 Proportion of preprocessing subsets.

	Preprocessing	Proportion (%)
	S11	2
	S15	18
	S19	44

Table 5 :

 5 Fastest key recovery with respect to the number of signatures.

	Number of	Total		Parameters		Probability of
	signatures	time	BKZ Preprocessing	∆	success (%)
	3	39 hours	35	S 11	≈ 2 3	0.2
	4	1 hour 17	25	S 15	≈ 2 3	0.5
	5	8 min 20	25	S 19	≈ 2 3	6.5
	6	3 min 55	20	S all	≈ 2 3	7
	7	2 min 43	20	S all	≈ 2 3	17.5
	8	2 min 25	20	S all	≈ 2 3	29

Table 6 :

 6 Highest probability of success with respect to the number of signatures.

	Number of	Probability of		Parameters		Total
	signatures	success (%)	BKZ Preprocessing	∆	time
	3	0.2	35	S11	≈ 2 3	39 hours
	4	4	35	S all	≈ 2 3	25 hours 28
	5	20	35	S all	≈ 2 3	2 hours 42
	6	40	35	S all	≈ 2 3	1 hour 04
	7	45	35	S all	≈ 2 3	2 hours 36
	8	45	35	S all	≈ 2 3	5 hours 02

Table 7 :

 7 Error analysis using BKZ-25, ∆ ≈ 2 3 and S all .

	Number of		Probability of success (%)
	signatures	0 error 5 errors 10 errors 20 errors 30 errors
	4	0.28	1	0	0	0
	5	4.58	0.86	0.18	1	0
	6	19.52	5.26	1.26	0.14	1
	7	33.54	10.82	3.42	0.32	1
	8	35.14	13.26	4.70	0.58	1

  34. Yarom, Y., Benger, N.: Recovering openssl ecdsa nonces using the flush+reload cache side-channel attack. IACR Cryptology ePrint Archive 2014, 140 (2014)We analyze the effect of the bitsize of ∆. We fix BKZ-25 and use no preprocessing. We average over 5000 experiments.

	35. Yarom, Y., Falkner, K.: FLUSH+RELOAD: A high resolution, low noise, L3 cache side-channel attack. In: Proceedings of the 23rd USENIX Conference on Security Symposium. pp. 719-732. SEC'14, USENIX Association, Berkeley, CA, USA (2014) Parameters Results u BKZ-β Preprocessing ∆ bitsize Probability Time of one Total time to key of success (%) experiment (sec) recovery (min) 4 25 Sall 0 0.14 31 375 4 25 Sall 1 0.16 31 330 4 25 Sall 3 0.28 32 191 4 25 Sall 5 0.22 30 234 4 25 Sall 10 0.24 33 228 4 25 Sall 15 0.16 39 411 4 25 Sall 20 0.20 45 379 4 25 Sall 25 0.20 54 454 4 25 Sall 30 0.10 31 515 5 25 Sall 0 3.74 37 16 5 25 Sall 1 4.60 36 13 5 25 Sall 3 4.58 34 12 5 25 Sall 5 4.38 34 13 5 25 Sall 10 3.92 36 15 5 25 Sall 15 4.62 41 15 5 25 Sall 20 4.60 52 19 5 25 Sall 25 4.52 64 23 5 25 Sall 30 4.18 Results u BKZ-β Preprocessing ∆ bitsize Probability Time of one Total time to key of success (%) experiment (sec) recovery (min) 6 25 Sall 0 15.94 77 8 6 25 Sall 1 19.96 61 5 6 25 Sall 3 19.52 57 5 6 25 Sall 5 20.10 59 5 6 25 Sall 10 19.04 63 5 6 25 Sall 15 20.34 72 6 6 25 Sall 20 20.58 92 7 6 25 Sall 25 20.02 91 7 6 25 Sall 30 19.26 164 14 7 25 Sall 0 28.86 185 10 7 25 Sall 1 33.00 134 7 7 25 Sall 3 33.54 136 6 7 25 Sall 5 33.69 142 7 7 25 Sall 10 33.99 149 7 7 25 Sall 15 33.81 186 9 7 25 Sall 20 34.94 229 11 7 25 Sall 25 31.68 300 15 7 25 Sall 30 32.08 351 18 8 25 Sall 0 32.12 322 16 8 25 Sall 1 36.40 237 101 8 25 Sall 3 35.14 227 10 8 25 Sall 5 36.00 211 9 8 25 Sall 10 34.86 245 11 8 25 Sall 15 36.18 296 13 8 25 Sall 20 35.48 376 17 8 25 Sall 25 36.12 460 21 88 Parameters 8 25 Sall 30 34.54 573 27

A Bitsize of ∆ effect over the key recovery total time

  We analyze the effect of the BKZ block-size. We set ∆ ≈ 2 3 and use no preprocessing. We average over 5000 experiments.

				Parameters Parameters			Results Results
	u u	BKZ-β BKZ-β	Preprocessing Preprocessing	∆ bitsize ∆ bitsize	Probability Probability	Time of one Time of one	Total time to key Total time to key
						of success (%) experiment (sec) recovery (min) of success (%) experiment (sec) recovery (min)
	7 7 5 7 5 7 5 8 5 8 6 8 6 8 6	25 25 20 25 25 25 30 25 35 25 20 25 25 25 30	S11 S15 Sall S19 Sall Sall Sall S11 Sall S15 Sall S19 Sall Sall Sall	25 25 3 25 3 25 3 25 3 25 3 25 3 25 3	3.40 26.20 0.82 43.90 4.58 31.68 11.60 4.50 20.18 32.50 6.96 43.90 19.52 36.12 32.96	55 151 162 300 225 9 34 85 1964 237 16 267 57 460 290	27 9 7 15 31 12 10 21	19 12 32 162 4 5 14
	6		35	Sall	3	39.52	1525		64
	7		20	Sall	3	17.35		28		2
	7		25	Sall	3	33.54		136		6
	7		30	Sall	3	44.20		950		35
	7		35	Sall	3	44.80	4245		158
	8		20	Sall	3	29.40		43		2
	8 8 8	u	25 BKZ-β 30 35	Parameters Sall Preprocessing Sall Sall	3 ∆ bitsize 3 3	35.14 Probability 46.66 of success (%) experiment (sec) recovery (min) 227 10 Results Time of one 1894 68 Total time to key 44.70 8119 302
	4	25	S11	3	0.18	9		89
	4	25	S15	3	0.52	24		77
	4	25	S19	3	0.38	29		130
	4	25	Sall	3	0.28	32		191
	5	25	S11	3	1.18	19		27
	5	25	S15	3	5.90	30		8
	5	25	S19	3	6.50	32		8
	5	25	Sall	3	4.58	34		12
	6	25	S11	3	4.04	40		16
	6	25	S15	3	20.36	78		6
	6	25	S19	3	24.76	72		4
	6	25	Sall	3	19.52	57		5
	7	25	S11	3	4.15	60		24
	7	25	S15	3	27.00	158	9
	7	25	S19	3	35.25	173	8
	7	25	Sall	3	33.54	135	6
	8	25	S11	3	4.40	88		33
	8	25	S15	3	35.20	249	11
	8	25	S19	3	40.70	268	11
	8	25	Sall	3	35.14	227	10
				Parameters			Results
		u	BKZ-β	Preprocessing	∆ bitsize	Probability	Time of one	Total time to key
						of success (%) experiment (sec) recovery (min)
	4	25	S11	25	0.20	9		79
	4	25	S15	25	0.52	24		79
	4	25	S19	25	0.50	29		97
	4	25	Sall	25	0.20	54		454
	5 5 5 u 5	25 25 25 BKZ-β 25	S11 S15 Parameters S19 Preprocessing Sall	25 25 25 ∆ bitsize 25	1.70 5.74 6.28 Probability 4.52 of success (%) experiment (sec) recovery (min) 17 17 29 Results 8 32 Time of one Total time to key 8 64 23
	6 4	25 20	S11 Sall	25 3	3.64 0	38	5	17	0
	6 4	25 25	S15 Sall	25 3	22.12 0.28	77	32	5	191
	6 4	25 30	S19 Sall	25 3	25.12 1.30	77	302	5	387
	6 4	25 35	Sall Sall	25 3	20.02 4.10	91 3763	7	1529

C BKZ block-size effect over the key recovery total time

Table 8 :

 8 Error 0 → 1 analysis using BKZ-25, ∆ ≈ 2 3 and S all .

	Number of				Probability of success (%)
	signatures 0 errors 1 error 5 errors 10 errors 20 errors 30 errors 40 errors 50 errors 60 errors
	4	0.28	0.18	0.10	1	0	0	0	0	0
	5	4.58	3.82	2.70	1.06	0.32	1	0	0	0
	6	19.52 10.79 13.88	7.90	2.94	0.86	0.36	0.10	1
	7	33.54 31.06 26.04	18.36	9.24	4.54	?	1.02	0.50
	8	35.14 34.92 31.94	25.50	16.70	7.96	4.94	2.48	1.22

Table 9 :

 9 Error 1 → 0 analysis using BKZ-25, ∆ ≈ 2 3 and S all .

	Number of	Probability of success (%)
	signatures	0 errors 1 error 2 errors 3 errors
	4	0.28	0	0	0
	5	4.58	0.36	1	0
	6	19.52	2.70	0.36	1
	7	33.54	5.54	1.00	0.12
	8	35.14	8.20	1.36	0.30

Table 10 :

 10 Errors 0 → 1 analysis with ∆ ≈ 23 , S all and increasing block-size. .44 7.[START_REF] Wang | Attacking OpenSSL ECDSA with a small amount of sidechannel information[END_REF] 8.73 1.80 3.54 3.48 4.58 1.02 1.26 1.84 3.26 0.50 0.62 1.20 1.43 8 7.96 10.46 11.78 10.98 4.94 6.12 6.73 7.12 2.48 3.26 3.78 4.64 1.22 1.84 1.89 2.18E Lattice construction for Coppersmith's methodsWe consider u -1 equations given after elimination. We construct the following lattice basisDq . . . D . . . σ u, u σ -1 u,1 D τ 1,u σ -1 u,1 D τ 2,u σ -1 u,1 D . . . τ u ,u σ -1 u,1 D -γ u σ -1u,1 Eq u Dq . . .

	Number of					Probability of success (%)
	signatures	30 errors			40 errors	50 errors			60 errors
		25 30	35	40	25 30 35 40 25 30 35 40 25 30 35 40
	5	1 0.24 0.35 0.75 0	1	1 0.42 0	0	0	0	0	0	0	0
	6	0.86 2.48 3.58 3.97 0.36 0.90 1.18 2.28 0.10 0.36 0.58 0.94	1	1 0.12 0.12
	7	4.54 6

In practice, measurements done during the cache attack depend on the noise in the execution environment, the threat model and the target leaky implementation. For instance, Flush&Reload ran from another core would be noisy. Prime&Probe would give the same information, with a more generic scenario. In an SGX scenario, it would recover the largest amount of information but in a user/user threat model it would be too noisy to lead to practical key recovery.

In[START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the authors use an Intel Core i7-3770 CPU running at 3.40GHz on a single core. In order for the time comparison to be meaningful, we ran experiments with a machine of comparable performance to estimate the timings of a single reduction. As we obtained similar timings with an older machine than used in[START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF], the variations we find when comparing ourselves to them solely come from the lattice construction and the reduction algorithm being used rather than hardware differences.

In the sense of vectors exhibited in[START_REF] Galbraith | Mathematics of Public Key Cryptography[END_REF].

Acknowledgement

We would like to thank Nadia Heninger for discussions about possible lattice constructions, Medhi Tibouchi for answering our side-channel questions, Alenka Zajic and Milos Prvulovic for providing us with traces from OpenSSL that allowed us to confirm our results on a deployed implementation, Daniel Genkin for pointing us towards the Extended Hidden Number Problem, and Pierrick Gaudry for his precious support and reading. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several universities as well as other organizations.