Thomas Espitau
email: tespitau@ens-cachan.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@univ-rennes1.fr

Benoît Gérard
email: benoit.gerard@irisa.fr

Mehdi Tibouchi
email: tibouchi.mehdi@lab.ntt.co.jp

Loop abort Faults on Lattice-Based Fiat-Shamir & Hash'n Sign signatures

Keywords: Fault Attacks, Digital Signatures, Postquantum Cryptography, Lattices, BLISS

As the advent of general-purpose quantum computers appears to be drawing closer, agencies and advisory bodies have started recommending that we prepare the transition away from factoring and discrete logarithm-based cryptography, and towards postquantum secure constructions, such as lattice-based schemes. Almost all primitives of classical cryptography (and more!) can be realized with lattices, and the efficiency of primitives like encryption and signatures has gradually improved to the point that key sizes are competitive with RSA at similar security levels, and fast performance can be achieved both in software and hardware. However, little research has been conducted on physical attacks targeting concrete implementations of postquantum cryptography in general and lattice-based schemes in particular, and such research is essential if lattices are going to replace RSA and elliptic curves in our devices and smart cards. In this paper, we look in particular at fault attacks against some instances of the Fiat-Shamir family of signature scheme on lattices (BLISS, GLP, TESLA and PASSSign) and on the GPV scheme, member of the Hash'n Sign family. Some of these schemes have achieved record-setting efficiency in software and hardware. We present several possible fault attacks, one of which allows a full key recovery with as little as a single faulty signature, and discuss possible countermeasures to mitigate these attacks.

Introduction

Recent progress in quantum computation [DBI + 15], the NSA advisory memorandum recommending the transition away from Suite B and to postquantum cryptography [NSA16], as well as the announcement of the NIST standardization process for postquantum cryptography [CJL + 16] all suggest that research on postquantum schemes, which is already plentiful but mostly focused on theoretical constructions and asymptotic security, should increasingly take into account real world implementation issues.

Among all postquantum directions, lattice-based cryptography occupies a position of particular interest, as it relies on well-studied problems and comes with uniquely strong security guarantees, such as worst-case to average-case reductions [Pei15]. A number of works have also focused on improving the performance of lattice-based schemes, and actual implementation results suggest that properly optimized schemes may be competitive with, or even outperform, classical factoring-and discrete logarithm-based cryptography.

Among the possible signatures schemes, one can devise schemes provable in the random oracle model into two categories. One the one hand the ones constructed using the Full Domain Hash (FDH) approach, and on the other hand schemes built with the Fiat-Shamir technique. This work focuses on the study of the effect of Loop abort faults type for both of the construction types, in the general framework of lattice-based cryptography. More precisely, we get interested in four instances of the Fiat-Shamir family: BLISS, PASSSign, GLP and TESLA, and one instance of the Hash'n Sign family: GPV. BLISS (Bimodal Lattice Signature Scheme) is a lattice-based signature scheme that incorporates many of the performance improvements geared towards reducing parameter sizes without security compromises, by careful analysis of the hardness of the underlying problems and of the statistical properties of the randomness distributions involved. It has been proposed by Ducas et al. in [DDLL13], building upon the previous signature scheme of Lyubashesky [Lyu12], and it has been implemented in hardware by Pöppelmann et al. in a paper presented at CHES 2014 [PDG14]. The Lyubashevsky signature scheme had also been implemented in hardware at CHES 2012 by Güneysu et al. [GLP12]. Both signature schemes are interesting targets for the cryptanalyst, since they are actually designed with real world practicality in mind, and have been the subject of concrete implementation efforts. PASSSign is signature scheme developed as a variant of the PASS and PASS-2 signatures, introduced by Hoffstein et al. in 2014 ACNS paper [HPS + 14]. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. Eventually, TESLA was introduced by Alkim et al. in [ABBD15] as a tightly secure scheme based on the learning with errors (LWE) problem.

The literature on the underlying number-theoretic problems of lattice-based cryptography is extensive (even though concrete bit security is not nearly as well understood as for factoring and discrete logarithms; in addition, ring-based schemes have recently been subjected to new families of attacks that might eventually reduce their security, especially in the postquantum setting). On the other hand, there is currently a distinct lack of cryptanalytic results on the physical security of implementations of lattice-based schemes (or in fact, postquantum schemes in general! [TE15]). It is well-known that physical attacks, particularly against public-key schemes, are often simpler, easier to mount and more devastating than attacks targeting underlying hardness assumptions: it is often the case that a few bits of leakage or a few fault injections can reveal an entire secret key (the well-known attacks from [BDL01,BMM00] are typical examples). We therefore deem it important to investigate how fault attacks may be leveraged to recover secret keys in the lattice-based setting, particularly against some Lattice-Based signatures.

Our contributions. In this work, we initiate the study of fault attacks against lattice-based signature schemes. Early lattice-based signature schemes with heuristic security have been broken using standard attacks [GJSS01,GS02,NR09] but recent signature schemes [GPV08, Lyu09,Lyu12,DDLL13] are provably secure, and cryptanalysis probably requires a more powerful attack model. We therefore look at fault attacks. To the best of our knowledge, the only previous work in that direction is a fault attack against NTRUSign [HHP + 03], due to Kamal and Youssef [KY12]. It is, however, of limited interest since NTRUSign is known to be broken [NR09,DN12]; it also suffers from a very low probability of success.

In this work, we consider faults against implementations of the Fiat-Shamir representents, both on the software [Lyu12,DDLL13] and hardware [GLP12,PDG14], and a single fault attack on the GPV scheme of the Hash'n Sign family. For both families, we present new fault attacks, the main idea of which is that some polynomials are generated coefficient by coefficient, and thus, we may use faults to abort the generation loop early. Similar fault attacks have been described on DSA [NNTW05] or pairing computations [PV06]. Using such faults, our first attack uses LLL to solve a closest vector problem in a lattice, and using a single successful faulty signature makes it possible to recover the entire secret key. The second attack on [GLP12] uses only a single fault and also relies on lattice reduction techniques to exploit this fault. We then take a closer look at the concrete software and hardware implementations, discuss how we can inject the required faults in practice, and propose countermeasures.

Organization of the paper. In Section 2, we give a basic description of the five schemes attacked (GLP, BLISS, PASSSign, TESLA on the one hand, and GPV on the other). In Section 3, we present all our fault attacks on these latter schemes and in Section 4 we explain how we can inject the required faults in the concrete implementations. Finally, Section 5 is devoted to possible countermeasures.

2 Description of the considered Lattice-Based Signatures 2.1 Notation, Gaussian distributions and hardness assumptions For any integer q, we represent the ring Z q by [-q/2, q/2) ∩ Z. For any ring R, we denote its quotient ring by R q as the ring R/(qR). The BLISS signature scheme uses two quotient rings R q = Z q [x]/(x n + 1) and R 2q = Z 2q [x]/(x n + 1) where n is a power of two and q is a prime such that q = 1 (mod 2n). The elements of R q can be represented by polynomials of degree n -1 with coefficients in the range Z q . We define B = {0, 1} and B n w the set of binary vectors of length n and Hamming weight w (i.e. vectors with exactly w out of n non-zero bits). Vectors are considered as column vectors and will be written in bold lower case letters and matrices with upper case letters. By default, we will use the 2 Euclidean norm,

v 2 = ( i v 2 i ) 1/2 and ∞ -norm as v ∞ = max i |v i |. The Gaussian distribution with standard deviation σ ∈ R and center c ∈ R at x ∈ R, is defined by ρ c,σ (x) = exp -(x-c) 2 2σ 2
and more generally by ρ c,σ (x) = exp -(x-c) 2 2σ 2 and when c = 0, by ρ σ (x). The discrete Gaussian distribution over Z centered at 0 is defined by D σ (x) = ρ σ (x)/ρ σ (Z) (or D Z,σ ) and more generally over Z m by D m σ (x) = ρ σ (x)/ρ σ (Z m ). All the constructions in this paper are based on the hardness of the generalized SIS (Short Integer Solution) problem, which is connected to hard lattices problems.

Definition 1. (R -SIS K q,n,m,β problem).
Let R be some ring and K be some distribution over R n×m q , where R q is the quotient ring R/(qR). Given a random A ∈ R n×m q drawn according to the distribution K, find a non-zero v ∈ R m q such that Av = 0 and v 2 ≤ β. If R = Z and K be the uniform distribution, then the resulting problem is the classical SIS problem first defined by Ajtai in his seminal paper [Ajt96] showing connections between worst-case lattice problems and the average-case SIS problem. If β ≥ √ mq n/m , the SIS instances are guaranteed to have a solution. In [LM08], Lyubashevsky and Micciancio show that if R = Z q [x]/(x n + 1) with n a power of 2, then the R -SIS K q,n,m,β problem is as hard as the Õ( √ nβ) -SVP problem in all lattices that are ideal in R (where K is the uniform distribution over R 1×m q ). Another hardness assumption used in the security reduction of some of the schemes presented in this paper is the LWE (learning with errors) problem. We first start by defining the LED which is the probability distribution used in the definition of the LWE problem. Definition 2. (LWE q,n,m,ξ distribution). Let n, m, q > 0 integers and ξ a distribution over Z. We define by D s,ξ LWE distribution which outputs (a, a, s + e) ∈ Z n q × Z q , where a is drawn uniformly at random in Z n q and e under ξ.

We are now able to define the LWE problem -in its decisional version since it will be the only one used in the security reduction -. Definition 3. (LWE q,n,m,ξ problem) Let n, m, q > 0 be integers and ξ be a distribution over Z. Moreover, define O ξ to be an oracle, which upon input vector s ∈ Z n q returns samples from the distribution D s,ξ . The decisional learning with errors problem LW E n,m,q,ξ is (t, )-hard if for any algorithm A, running in time t and making at most m queries to its oracle, we have

Pr[A O ξ (s) (•) = 1] -Pr[A U (Z n q ×Zq) (•) = 1] ≤
where the probabilities are taken over s ← U(Z n q ) and the random choice of the distribution D s,ξ , as well as the random coins of A.

Description of the Lyubashevsky signature scheme

In [Lyu12], Lyubashevsky describes a signature scheme proved secure in the random-oracle model which is an alternative to hash-and-sign methodology of Gentry et al. in [GPV08]. Gentry, Peikert and Vaikuntanathan were the first to propose a signature scheme whose security is based on the hardness of worstcase lattice problems, while Lyubashevsky and Micciancio present a one-time signature scheme based on the hardness of worst-case ideal lattice problems [LM08]. Lyubashevsky propose a Fiat-Shamir framework [FS86] using rejection sampling technique in [Lyu09]. Both signature schemes are inefficient in practice: [GPV08] requires megabytes long signature and [Lyu09] needs 60,000 bits for reasonable parameters.

Many previous lattice-based signature schemes have been broken since information about the secret key leaks in every signature [GJSS01,GS02,NR09,DN12]. Consequently, the basic idea of the Lyubashevsky and BLISS signature schemes is to use the rejection sampling so that the distribution output is independent of the secret key. This signature scheme is proved secure on the hardness of the ring version of 2 -SIS q,n,m,β .

In the following, we describe the version of Güneysu et al. in [GLP12] which is a particular instantiation of the ring version of Lyubashevsky signature as presented in Section 7 in [Lyu12]. We denote by R q,k the subset of R q that consists of all polynomials with integer coefficients in the interval [-k; k]. The hardness assumption of [GLP12] is that (a, t) ∈ R q × R q where a is chosen uniformly in R q and t = as 1 + s 2 with s 1 and s 2 uniformly chosen in R q,k is indistinguishable from (a, t) uniformly chosen in R q × R q . When √ q < k, the solution (s 1 , s 2 ) is not unique and finding one of them is as hard as worst-case lattice problems in ideal lattices [LM06,PR06]. In [LPR13], it was shown that if s i are chosen according a Gaussian distribution instead of a uniform one, then recovering the s i given (a, t) is as hard as solving worst-case lattice problems using a quantum computer. In the following our attacks do not take into account the way the secret key is generated and work in all cases.

Description of BLISS

The BLISS signature scheme is a more efficient version of Lyubashevsky signature scheme. The rejection sampling has been optimized so that the number of times we need to reject is diminished using a bimodal distribution. The key generation has also been updated to generate the s i using NTRU ideas. We do not define the parameter N κ (S) (the interested reader can read it in [DDLL13]), used only in the key generation algorithm, which is a technical parameter that is not important in our attacks. Finally, the z 2 is compressed in z † 2 in BLISS, but since our attack does not involve this value, we do not describe how the compression works. The value ζ is defined as ζ • (q -2) = 1 mod 2q. The only modification important for us is that H as now range {v : v ∈ B n , v 1 ≤ κ}.

Description of the PASSSign signature scheme

PASSSign is a signature scheme introduced by Hoffstein et al. in [HPS + 14]. This scheme is a variant of the PASS and PASS-2 scheme from the same authors, adding the rejection sampling technique of Lyubashevsky from 2009. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation.

We follow in its description the original presentation and notation of [HPS + 14]. Computations are made in the ring Z q [x]/(x N -1). On that ring, we define B ∞ q the subset of polynomials whose coefficients lie in [-k, k]. Given g a primitive N -th root of unity in Z q , Ω a subset of {g i |1 ≤ i ≤ N -1}, we define the mapping

F Ω : Z q [x]/(x N -1) → Z |Ω| q
consisting on the multi-evaluation of a polynomial on the elements of Ω. The image a a polynomial f by F Ω will be simply denoted by f | Ω . The function FormatC maps the set of bitstrings output by the Hash function H into a set of sparse polynomials. Once again, since its details are not mandatory when mounting the attack, we let the interested reader to refer to the original paper for an in-depth description.

Signing Key: s1, s2 ∈ Rq,1 where each coefficient of every si is chosen uniformly and independently from {-1, 0, 1} Verification Key: (a, t) where a ← Rq and t = as1 + s2 Random Oracle:

H : {0, 1} * → {v : v ∈ {-1, 0, 1} n , v 1 ≤ κ} with κ = 32 1: function Sign(µ, a, s1, s2) 2: y1, y2 ← R q,k 3: c = H(ay1 + y2, µ) 4: z1 = s1c + y1, z2 = s2c + y2 5:
If z1 or z2 ∈ R q,k-32 , goto 1 6:

return (z1, z2, c) 7: end function 1: function Verify(µ, z1, z2, c, a, t) 2:

Accept iff z1 and z2 ∈ R q,k-32 and c = H(az1 + z2 -tc, µ) 3: end function Fig. 1. Lyubashevsky or [GLP12] signature scheme based on Ring 2 -SIS q,n,m,β .Two sets of parameters for (n, q, k) are given for estimated security of 100 and 256 bits: Set I (512, 8383489, 2 14 ) for a 8,950-bit signature, 1620-bit secret key and 11800-bit public key and Set II (1024, 16760833, 2 15 ) for a 18800-bit signature, 3250-bit secret key and 25000-bit public key.

1: function KeyGen() 2:

Choose f , g as uniform polynomials with exactly d1 = δ1n entries in {±1} and d2 = δ2n entries in {±2} 3:

S = (s1, s2) T ← (f , 2g + 1) T 4: If Nκ(S) ≥ C 2 • 5 • ( δ1n + 4 δ2n ) • κ then restart 5: aq = (2g + 1)/f mod q (restart if f is not invertible) 6:
return (pk = A, sk = S) where A = (a1 = 2aq, q -2) mod 2q 7: end function Public Parameters: g a primitive N -th root of unity in Zq, Ω a subset of {g i |1 ≤ i ≤ N -1}, t its cardinal, k the infinity norm of noise polynomials, and b the 1-norm of challenge polynomials. Signing Key: Secret

1: function Sign(µ, pk = A, sk = S) 2: y1, y2 ← D n Z,σ 3: u = ζ • a1 • y1 + y2 mod 2q 4: c ← H( u d mod p, µ) 5: Choose a random bit b 6: z1 ← y1 + (-1) b s1c 7: z2 ← y2 + (-1) b s2c 8: Continue with probability 1/ M exp(-Sc /(2σ 2 )) cosh( z, Sc /σ 2 other- wise restart 9: z † 2 ← ( u d -u -z2 d ) mod p 10: return (z1, z † 2 , c) 11: end function 1: function Verify(µ, A, (z1, z † 2 , c)) 2: If (z1|2 d • z † 2 ) 2 > B2 then Reject 3: If (z1|2 d • z † 2 ) ∞ > B∞ then Reject 4: Accept iff c = H( ζ • a1 • z1 + ζ • q • c d + z † 2 mod p, µ) 5: end function
f ∈ Zq[X]/(X n -1) of small norm. t = as1 + s2 Random Oracle: H : Z t q × {0, 1} * → {0, 1} l 1: function Sign(µ, f ) 2: y ← B ∞ k 3: h = H(y|Ω, µ) 4: c = FormatC(h) 5: If z ∈ B ∞ k-b , goto 1 6:
return (c, z, µ) 7: end function

1: function Verify(µ, c, z, c, f |Ω) 2: Accept iff z2 ∈ B ∞ k-b and c = FormatC(H(z|Ω - f • c|Ω, µ))
3: end function Fig. 3. PASSSign signature. Two sets of parameters for (n, q, k) are given for estimated security of 100 and 128 bits: Set I (769, 1047379, 2 15 -1) for a 12624-bit signature, 1600-bit secret key and 7720-bit public key and Set II (1152, 968521, 2 15 -1) for a 18800-bit signature, 2000-bit secret key and 12000-bit public key.

Description of the TESLA signature scheme

The TESLA scheme is a variation of the BG scheme presented in [Ben14], initially modified by Dagdelen et al. in [DBG + 14] at LATINCRYPT 14, allowing to get rid of the forking lemma in their security analysis.

On the contrary of the two previous presented schemes, the TESLA signatures works directly on vectors -and no more on the additional algebraic structure provided by the use of polynomials -. The matrix A used in the scheme is publicly known and can be seen as a global constant shared by arbitrary many users. The CheckE function is fully described in the original paper from Dagdelen et al [DBG + 14] and ensures mandatory properties to preserves that the signature remains short. Once again, we do not fully describe it here since its details are irrelevant for our attacks. We conclude this presentation by noting that the security proof uses the hardness of the LWE problem. Its specificity is to avoid the use of the Forking Lemma proposed by Pointcheval and Stern in [PS96].

GPV Signature Scheme

This signature is described in [DLP14] by Ducas, Lyubashevsky and Prest and derived from an IBE scheme.

We denote here by

f = f 0 - n-1 i=1 f n-i x i where f = n-1 i=0 f i x i and by B the matrix B = M g -M f M G -M F ,
where F and G are defined by fG -gF = q and M a represents the matrix of the multiplication in R by the element a, which is anticirculant of dimension n. return (pk = T, sk = (S, E)) where T = (AS + E mod q 6: end function 1: function Sign(µ, pk = A, sk = S) 2:

y ← $ [-B; B] n 3: v = Ay mod q 4: c ← H( v d , µ) 5: c ← F (c) 6: z ← y + sc 7: w ← v -Ec mod q 8: If |[w i ] 2 d | > 2 d-1 -L or z ∞ > B -U then Restart. 9:
return (z, c) 10: end function

1: function Verify(µ, A, (z1, z † 2 , c)) 2: c ← F (c) 3: w ← Az -Tc mod q 4: c ← H( w d , µ) Accept iff c = c and z ∞ ≤ B -U 5: end function

Description of our attacks

In this section we describe two different fault attacks against the previously described signature schemes. The first attack on all the schemes consists in reducing the polynomial y 1 to only a few monomials (say 64 or 128 among 512) and allows to recover s 1 with an efficient lattice attack. The second fault attack is aimed against the GPV scheme, targeting the vector s of the signature with an early abort of a generation loop.

Both of our attacks have been validated using a proof-of-concept implementation in Sage [Dev16]. The implementation is attached to this paper as supporting material for the reviewers' perusal.

Attack on y 1

Due to the obvious similarities between the four instances of the Fiat-Shamir family that we choose to attack, we only give details of the attack on the BLISS scheme.

The first fault attack that we consider, which is also the more devastating one, targets the generation of the random "commitment" element y 1 , in both the original Lyubashevsky signature scheme and in BLISS. For simplicity's sake, we introduce the attack against BLISS in particular, but it works against other variants of Lyubashevsky signatures with almost no changes.

Intuitively, y 1 should mask the secret key element s 1 in the relation z 1 = ±s 1 c + y 1 , and therefore modifying the distribution of y 1 should cause some information about s to leak in signatures. The actual picture in the Fiat-Shamir with aborts paradigm is in fact slightly different (namely, rejection sampling ensures that the distribution of z 1 is independent of s 1 , but only does so under the assumption that y 1 follows the correct distribution), but the end result is the same: perturbing the generation of y 1 should lead to secret key leakage.

Basis: B ∈ Z n×n of a n-dimensional lattice L, standard deviation σ > 0, center c ∈ Z n v sampled in DL,σ,c 1: function GaussianSampler(B, σ, c) 2: vn ← 0 3: cn ← c 4:
for i ← {n, . . . , 1} do 5:

c i ← ci, bi /|| bi|| 2 6: σ i ← σ/|| bi|| 7: zi ← SampleZ(σ i , c i ) 8:
ci-1 ← zibi and vi-1 ← vi + zibi 9:

end for 10: return v0 11: end function 1: function KeyGen(n, q) 2: σ f = 1.17 q/(2n)

3: f , g ← Dn,σ f 4: Norm ← max (g, -f ) , ( q f f f +gḡ , qḡ f f +gḡ ) ) 5:
if Norm> 1.17 √ q, go to step 3 6:

Using extended euclidean algo, compute

ρ f , ρg ∈ R and R f , Rg ∈ Z s.t. -ρ f • f = R f mod (x n + 1) -ρg • g = Rg mod (x n + 1) 7: if gcd(R f , Rg) = 1 or gcd(R f , q) = 1, go to step 3 8: Using extended euclidean algorithm, compute u, v ∈ Z s.t. u • R f + v • Rg = 1 9: F ← qvρg, G ← -quρ f 10: while k = 0 do 11: k = F• f +G• f f f +gḡ ∈ R 12: Reduce F and G: F ← F -k • f , G ← G -k • g 13:
end while 14:

h = g • f -1 mod q 15:
return sk = (f , g, F, G), pk = h s.t. f • h = g mod q and fG -gF = q 16: end function Signing Key: f , g ∈ Rq,1 where each coefficient is chosen uniformly and independently from {-1,0,1} Verification Key: h ∈ Rq where g = fh mod q Random Oracle:

H : {0, 1} * → Z n q 1: function Sign(µ, B) 2: c ← H(µ) ∈ Z n q 3: (z1, z2) ← (c, 0) -GaussianSampler(B, σ, (c, 0)) z1 + z2 • h = t 4:
return (z1, z2, c) 5: end function 1: function Verify(µ, z1, z2, c, h) 2:

Accept iff z1 + z2 • h = H(µ) and ||(z1, z2)|| ≤ 1.17 √ q 3: end function Concretely speaking, in BLISS, y 1 ∈ R q is a ring element generated according to a discrete Gaussian distribution 5 , and that generation is typically carried out coefficient by coefficient in the polynomial rep-resentation. Therefore, if we can use faults to cause an early termination of that generation process, we should obtain signatures in which the element y 1 is actually a low-degree polynomial. If the degree is low enough, we will see that this reveals the whole secret key right away, from a single faulty signature! Indeed, suppose that we can obtain a faulty signature generated from an element y 1 of degree m n. We get in particular the pair (c, z 1 ) with z 1 = (-1) b s 1 c + y 1 . Without loss of generality, we may assume that b = 0 (we will recover the whole secret key only up to sign, but in BLISS, (s 1 , s 2 ) and (-s 1 , -s 2 ) are clearly equivalent secret keys). Moreover, with high probability, c is invertible: if we heuristically assume that c behaves like a random element of the ring from that standpoint, we expect it to be the case with probability about (1-1/q) n , which is over 95% for all proposed BLISS parameters. We thus get an equation of the form:

c -1 z 1 -s 1 ≡ c -1 y 1 ≡ m i=0 y 1,i c -1 x i (mod q)
(1)

Thus, the vector v = c -1 z 1 is very close to the sublattice of Z n generated by w i = c -1 x i mod q for i = 0, . . . , m and qZ n , and the difference should be s 1 .

The previous lattice is of full rank in Z n , so the dimension is too large to apply lattice reduction directly. However, the relation given by equation ( 1) also holds for all subsets of indices. More precisely, let I be a subset of {0, . . . , n -1}, and ϕ I : Z n → Z I be the projection (u i ) 0≤i<n → (u i ) i∈I . Then we also have that ϕ I (z 1 ) is a close vector to the sublattice L I of Z I generated by qZ I and the images under ϕ I of the w i 's; and the difference should be ϕ(s 1 ).

Equivalently, using Babai's nearest plane approach to the closest vector problem, we hope to show that ϕ I (s 1 ), B , for a suitably chosen positive constant B, is the shortest vector in the sublattice L I of Z I × Z generated by ϕ I (v), B as well as the vectors ϕ I (w i ), 0 and qZ I × {0}.

The volume of L I is given by:

vol(L I ) = B • vol(L I ) = B • vol(qZ I ) [L I : qZ I ] = Bq -r
where is the cardinality of I and r is the rank of the family ϕ I (w 0 ), . . . , ϕ I (w m ) in Z I q , which is at most m + 1. Hence vol(L I ) ≥ Bq -(m+1) , and the Gaussian heuristic predicts that the shortest vector should be of norm: +1) .

λ I ≈ + 1 2πe • vol(L I ) 1/( +1) + 1 2πe • B 1/( +1) q 1-(m+2)/(
Thus, we expect that ϕ I (s 1 ), B will actually be the shortest vector of L I provided that its norm is significantly smaller than this bound λ I . Now ϕ I (s 1 ) has roughly δ 1 entries equal to ±1, δ 2 entries equal to ±2 and the rest are zeroes; therefore, the norm of ϕ I (s 1 ), B is around (δ 1 + 4δ 2 ) + B 2 . Let us choose B = √ δ 1 + 4δ 2 . The condition for s 1 to be the shortest vector L I can thus be written as: +1) or equivalently:

(δ 1 + 4δ 2 ) • ( + 1) + 1 2πe • B 1/( +1) q 1-(m+2)/(
+ 1 m + 2 + log √ δ1+4δ2 log q 1 - log √ 2πe(δ1+4δ2) log q
.

(2)

The denominator of the right-hand side of (2) ranges from about 0.91 for the BLISS-I and BLISS-II parameter sets down to about 0.87 for BLISS-IV. In all cases, we thus expect to recover ϕ I (s 1 ) if we can solve the shortest vector problem in a lattice of dimension slightly larger than m. This is quite feasible with the LLL algorithm for m up to about 50 or 60, and with BKZ for m up to 100 or so.

To complete the attack, it suffices to apply the above to a family of subsets I of {0, . . . , n -1} covering the whole set of indices, which reveals the entire vector s 1 . The second component of the secret key is then obtained as s 2 = a 1 s 1 /2 mod q.

Remark 1. A variant of that attack which is possibly slightly simpler consists in observing that ϕ I (s 1 ) should be the shortest vector in the lattice generated by L I and ϕ I (v). The bound on the lattice dimension becomes essentially the same as (2). The drawback of that approach, however, is that we obtain each ϕ I (s 1 ) up to sign, and so one needs to use overlapping subsets I to ensure the consistency of those signs.

Remark 2. Note that a single faulty signature is enough to recover the entire secret key with this attack, a successful key recovery may require several fault injections. This is due to rejection sampling: after a faulty y 1 is generated, the whole signature may be thrown away in the rejection step. On average, the fault attacker may thus need to inject the same number of faults as the repetition rate of the scheme, which is a small constant ranging from 1.6 to 7.4 depending on chosen parameters [DDLL13], and even smaller with the improved analysis of BLISS-B [Duc14].

Remark 3. Finally, we note that in certain hardware settings, fault injection may yield a faulty value of y 1 in which all coefficients upwards of a certain degree bound are non zero but equal to a common constant (see the discussion in Section 6.3). Our attack adapts to that setting in a straightforward way: that simply means that y 1 is a linear combination of the x i for small i and of the all-one vector (1, . . . , 1), so it suffices to add that vector to the set of lattice generators.

Attack on the GPV scheme

Our second attack targets the practical hash-and-sign signature scheme of Ducas, Lyubashevsky and Prest [SI14], which is based on GPV-style lattice trapdoors. More precisely, the faults we consider are again early loop aborts, this time in the lattice-point Gaussian sampling routine used in signature generation.

Description of the attack

The attack can be described as follows. A correctly generated signature element is of the form z

= R • f + r • F ∈ Z[x]/(x n + 1)
, where the short polynomials f and F are components of the secret key, and r, R are short random polynomials sampled in such a way that z follows a suitable Gaussian distribution. In fact, r, R are generated coefficient by coefficient, in a single loop with 2n iterations, going from the top-degree coefficient of r down to the constant coefficient of R.

Therefore, if we inject a fault aborting the loop after m ≤ n iterations (in the first half of the loop), the resulting signature simply has the form:

z = r 0 x n-1 F + r 1 x n-2 F + • • • + r m-1 x n-m F.
Any such faulty signature is, in particular, in the lattice L of rank m generated by the vectors

x m-i F, i = 1, . . . , m, in Z[x]/(x n + 1).
Suppose then that we obtain several signatures z (1) , . . . , z ( ) of the previous form. If is large enough (slightly more than m is sufficient; see §5.2 below for an analysis of success probability depending on ), the corresponding vectors will then generate the lattice L. Assuming the lattice dimension is not too large, we should then be able to use lattice reduction to recover a shortest vector in L, which is expected to be one of the signed shifts ±x m-i F, i = 1, . . . , m, since the polynomial F is constructed in a such a way as to make it quite short relative to the Gram-Schmidt norm of the ideal lattice it generates. Hence, we can recover F among a small set of at most 2m candidates.

And recovering F is actually sufficient to reconstruct the entire secret key (f , g, F, G), and hence completely break the scheme. This is due to the particular structure of the NTRU lattice. On the one of the schemes. The point here is to show that the fault attacks presented in this paper are relevant based on the analysis of freely available and published implementations to put forward the need of dedicated protections against faults attacks (when attackers have such abilities).

Classical fault models

Faults during a computation may be induced by different means as a laser beam shot, electromagnetic injection, under-powering, clock/power glitches. . . These faults are mainly characterized by their range: impacting a single bit or many bits (e.g. register or memory word); effect: typically target chunk is set to a chosen value, random value or all-zero (resp. all-one) value; persistence: a fault may only modify the target for a short period or it may be definitive.

Obviously, some fault models are close from being purely theoretical: it is very unlikely to be able to set a 32-bit register to 0xbad00dad during precisely 2 cycles. Nevertheless many recent works have been published showing that some faults models that seemed overdone are actually obtained during lab experiments. One example is the work of Ordas et al. at CARDIS 2014 [OGT + 14] showing that with finely tuned EM probes it is possible to induce a single-bit fault (bit-set or bit-reset).

In the next subsections we discuss which fault models6 may lead to faulty signatures relevant with respect to the attacks presented in this paper. We did not investigate clock glitches or under-powering which induce violation of the setup time and which actual side-effects are implementation and compilationdependent (with large ranges of possible parameters to test). Nevertheless, they may not be overseen in the evaluation of a chip since they may also lead to the generation of relevant faulty signatures.

Fault attacks on software implementations

Polynomial y 1 can be generated using a loop over the n coefficients. This is, again, how the implementation in [DL] is made: a loop is constructing polynomials y 1 and y 2 one coefficient at a time using a Gaussian sampler (function Sign::signMessage).

The condition To perform the attack rather few restrictive since we only require y 1 to have at most (roughly) a quarter of unknown coefficients. Such result can be obtain by going out the loop after a few iterations. Again, a random fault on the loop counter or skipping the jump operation will lead to such result.

Notice here that it is less trivial here to decide whether a faulty signature will be helpful or not. Hopefully, the timing precision is much less important here since the attack will succeed even with 50 unknown coefficients out of 512. This means that the time-window for the fault to occur is composed of decades of loop iterations. Moreover, we may use side-channel analysis to detect the loop iteration pattern to trigger the fault injection. Such pattern is likely to be detected after much less than 50 iterations and thus it seems that the synchronization here will be relatively easy.

To conclude, this attack also seems to be a real threat and even more than the attack on c since synchronization is ease in this case by the loose condition on the number of known coefficients in y 1 .

Fault attacks on hardware implementations

Generation of polynomial y 1 requires n random coefficients. It is very unlikely that all these coefficient are obtained at the same time (n is too large) thus y 1 generation will be sequential. This is the case in the implementation we took as example where the super memory is linked to the sampler through a 14-bit port. We may fault a flag or a state register to fool the control logic (here the bliss processor) and keep part of the BRAM cells to their initial state. If this initial state is known then we know all the corresponding coefficients and hopefully the number of unknown ones will be small enough for the attack to work. The large number of unknown coefficients handled by the attack again helps the attacker by providing a large time window for the fault to occur. The feasibility of the attack will mostly depend on the precise flag/state implementation and the knowledge of memory cells previous/initial value.

There is a second way of performing the fault injection here. The value of y 1 has to be stored somehow until the computation of z 1 (close to the end of the signature generation). In the example implementation a BRAM is used. We may fault BRAM access to fix some coefficients to a known value. A possible fault would be to set the rstram or rstreg signal to one (Xilinx's nomenclature). Indeed, when set to one, this will set the output latches (resp. register) of the RAM block to some fixed value SRVAL defined by the designer. We may notice two points to understand why this kind of fault enables the proposed attack.

(i) The value of y 1 used to compute u will not be the faulted one but this has no impact on the attack. (ii) If we do not know the default value for the output register, all coefficients are unknown but we know that a big part of them are equal to the same unknown default value. In that case, the attack is still applicable by adding one generator to the constructed lattice: see Remark 3 in Section 4.

Again a large time window is given to the attacker due to sequential read induced by the size of y 1 .

The BRAM storage of y 1 helps here the attacker since a single bit-set fault may have effects on many coefficients. The only difficulty seems to be able to perform a single-bit fault -which seems to be possible according to [OGT + 14] -and the rstram signal localization7 .

Conclusion and possible countermeasures

We have shown that unprotected implementations of the four lattice-based signature schemes that we considered are vulnerable to fault attacks, in certain fault models that our analysis suggests are quite realistic: the faulty signatures required by our attacks can be obtained on actual implementations. As a result, countermeasures should be added in applications where such a physical attacker is relevant to the threat model.

Simple countermeasures exist to thwart the single fault attacks proposed here since they rely on processing signatures computed from polynomials that are too sparse. Let investigate the in-depth described attack on BLISS, and the generation of y 1 . The number of non-zero coefficients in that polynomial is not fixed by the sampling algorithm, and it can take several distinct values with non-negligible probability. Therefore, requiring that y 1 has a specified number of non-zero coefficients affects the distribution of z 1 and could thus cause invalidate the security of the scheme. One could, on the other hand, check that the top ε • n coefficients of y 1 are not all zero for some small constant ε > 0, say ε = 1/16; indeed, the probability that they all vanish is roughly:

1 σ √ 2π
εn which is exponentially small. Thus, the resulting distribution of y 1 after this check is statistically indistinguishable from the original distribution, and security is therefore preserved. Moreover, the lattice dimension required to mount our fault attack is greater than (1 -ε)n, which makes it impractical. Another possible countermeasure is to generate the coefficients of y 1 in random order instead of iterating from low to high degree or some other fixed pattern. This prevents our attack since, even if a faults causes the loop to terminate early, the attacker no longer knows which subset of the c -1 x i the vector c -1 z 1 -s 1 is a linear combination of.

A Listings of POC code 1 from sage . stats . distributions . d i s c r e t e _ ga u s s i a n _ i n t e g e r \ import D i s c r e t e G a u s s i a n D i s t r i b u t i o n I n t e g e r S a m p l e r 3 # BLISS -II parameters 5 q =12289 n =512

Fig. 2 .

 2 Fig.2. BLISS Signature Scheme. Four different sets of parameters are proposed with security levels at least 128 bits. The interesting parameters for us are: n = 512, q = 12289, σ ∈ {215, 107, 250, 271}, (δ1, δ2) ∈ {(0.3, 0), (0.42, 0.03), (0.45, 0.06)} and κ ∈ {23, 30, 39}, resulting in signature size around 5kb, secret key size around 2kb and 3kb and public key size of 7kb.

  Public parameters: A ∈ Z m×n q , m, n ∈ Z. Encoding Function: F : {0, 1} κ → Bn,ω, space of vectors length n and weight ω. Random Oracle: H : {0, 1} * → {0, 1} κ .

Fig. 4 .

 4 Fig. 4. TESLA Signature Scheme. A set of parameters are proposed with security level at least 128 bits. The interesting parameters for us are: κ = 128, n = 416, m = 800, q = 2 27 -39, σ = 114, U = 7138, d = 24, ω = 20, L = 6042. The resulting signature size around 10.24kb, secret key size around 1Mb and public key size of 1.33Mb.

Fig. 5 .

 5 Fig. 5. The function SampleZ(σ , c ) samples a 1-dimensional Gaussian D Z,σ ,c .

Fig. 6 .

 6 Fig. 6. IBE Sign [DLP14] signature scheme.

  xx >= QuotientRing ( ZZ [ x ] , ZZ [ x ]. ideal ( x ^n +1) ) 13 Rq . < xxx >= QuotientRing ( GF ( q ) [ x ] , GF ( q ) [ x ]. ideal ( x ^n +1) ) 15 sampler = D i s c r e t e G a u s s i a n D i s t r i b u t i o n I n t e g e r S a m p l e r ( sigma = sigma , algorithm = ' uniform + table ') [ s1vec [ i ] * xx ^i for i in range ( n ) ]) 35 37 def faultyz1gen ( s1 , d ) : # y1 should be generated with gaussian coefficients , but let 's do it 39 # uniformly for now # y1 = sum ([ randint ( -2 * sigma ,2 * sigma ) * xx ^i for i in range ( d ) ]) 41 y1 = sum ([ sampler () * xx ^i for i in range ( d ) ])

In the scheme of [GLP12], the distribution of each coefficient is uniform in some interval, but this doesn't affect our attack strategy at all.

We only focus on single fault attacks here.

Since y1 is not directly outputted checking if the attack actually worked is a bit more tricky. Again side-channel collision analysis may help here. We may also notice that if the faulty y1 is sparse (that is known coefficients have been set to zero) then the number of non-zero coefficients in the corresponding z1 should be significantly smaller then for a z1 corresponding to a dense y1.

hand, G is linked to F via the public key polynomial h: G = F • h mod q, so we obtain it directly. On the other hand, the basis completion algorithm of Hoffstein et al. [HHP + 03] allows to recover the pair (f , g) from (F, G) via the defining relation f • Gg • F = q. This is actually used in the opposite direction in the key generation algorithm of the scheme of Ducas et al. (i.e. they construct (F, G) from (f , g)), but applying [HHP + 03, Theorem 1], the technique is easily seen to work in both ways.

Moreover, if we start from a polynomial of the form ζF where ζ is of the form ±x α , then applying the previous steps yields the quadruple (ζf , ζg, ζF, ζG), which is also a valid secret key equivalent to (f , g, F, G), in the sense that signing with either keys produces signatures with exactly the same distributions. Thus, we don't even need to carry out an exhaustive search on several possible values of F after the lattice reduction step: it suffices to use the first vector of the reduced basis directly.

How many faults do we need?

Let us analyze the probability of success of the attack depending on the iteration m at which the iteration is inserted and the number > m of faulty signatures z (i) available. As we have seen, a sufficient condition for the attack to succeed (provided that our lattice reduction algorithm actually finds a shortest vector) is that the faulty signatures generate the rank-m lattice L defined above. This is not actually necessary (the attack works as soon as one of the shifts of F is in sub-lattice generated by the signatures, rather than all of them), but we will be content with a lower bound on the probability of success. Now, that condition is equivalent to saying that the random vectors (r

m-1 ) ∈ Z m (sampled according to the distribution given by the GPV algorithm) that define the faulty signatures:

generate the whole integer lattice Z m . But the probability that > m random vectors generate Z m has been computed by Maze, Rosenthal and Wagner [MRW11] (see also [FW14]), and is asymptotically equal to k= -m+1 ζ(k) -1 . In particular, if = m + d for some integer d, it is bounded below by:

.

Thus, if we take = m + 1 (resp. = m + 2, = m + 3), we expect the attack to succeed with probability at least p 1 ≈ 43% (resp. p 2 ≈ 71%, p 3 ≈ 86%).

Implementation of the faults

Once afain, due to the obvious similarities between the four instances of the Fiat-Shamir family that we choose to attack, we only give details of the attack on the BLISS scheme. Even though the second attack on the GPV scheme looks different in its exploitation, the underlying fault introduced is strictly identical and as such we let the reader refers to the following description.

In this section we investigate how an attacker may obtain helpful faulty signatures for the proposed attacks. We base our discussion on two available implementations of BLISS signature namely the software implementation from Ducas and Lepoint [DL] and the FPGA implementation by Pöppelmann et al. [PDG14]. The former one is based on /dev/urandom and sha 512 while the later performs sampling based on Trivium instances and uses Keccak hash function as random oracle. Notice that discussion on the hardware implementation is also valid for the implementation of [GLP12] since both share some common components and architecture that we exploit (for instance BRAM storage).

We emphasize the fact that those implementations were not supposed to have any resilience with respect to fault attacks and were only developed as proofs of concept to illustrate the efficiency properties n =256 8 sigmaf =1.17 * sqrt ( q /(2 * n ) ) sigma =1.17 * sqrt ( q )

Rq . < xxx >= QuotientRing ( Integers ( q ) [ x ] , Integers ( q ) [ x ]. ideal ( x ^n +1) )


Erwan Donal

Elena Galli

Arnaud Hubert

Guillaume Bouzille

New indices of Left ventricular function. Let's move from ejection fraction to more physiological parameters

Correspondance

The assessment of myocardial function in the context of valvular heart disease (VHD) remains highly challenging. [START_REF] Galli | LV mechanics in mitral and aortic valve diseases: value of functional assessment beyond ejection fraction[END_REF] The myocardium deforms simultaneously in three-dimensions, and global left ventricular (LV) function parameters such as volume and ejection fraction (EF) may remain compensated despite alterations in myocardial deformation properties. [START_REF] Galli | LV mechanics in mitral and aortic valve diseases: value of functional assessment beyond ejection fraction[END_REF] In VHD, the decline in myocardial deformation parameters precedes the onset of symptoms and portends a poor outcome. Nevertheless, it has not been demonstrated that LV global longitudinal strain (GLS) has independent prognostic value in patients with VHD 2 and GLS does not figure in current recommendations for the management of these patients. [START_REF] Surgery ; Vahanian | Management of Valvular Heart Disease of the European Society of European Association for[END_REF][START_REF] Nishimura | AHA/ACC guideline for the management of patients with valvular heart disease: executive summary. A report of the American College of Cardiology/American Heart Association Task Force on Practice Guidelines[END_REF] The advent of novel tissue-tracking echocardiography techniques offers new opportunities for clinical identification of early abnormalities in LV-function. In this issue of the Journal of Physiology, Hulshof et al. [START_REF] Hulshof | Exploratory assessment of left ventricular strain-volume loops in severe aortic valve diseases[END_REF] propose a new noninvasive measure of LV performance based on electrocardiographic estimates of simultaneous LV longitudinal deformation and volume. They present strain-volume loops evaluated throughout the cardiac cycle and have tested the value of this elegant index of LV-function in 27 patients with aortic valve stenosis (AS) or aortic regurgitation (AR). These volume-strain loops were able to distinguish the hemodynamic cardiac impact of AS and AR. As yet, these results are preliminary only and much work remains to be done in order to demonstrate the advantages of this new approach over the assessment of LV longitudinal strain on its own. 5; 6 LV pressure-strain loops (PSLs) are another interesting and closely related approach. Clinical use of the PSL has been limited by the need for instantaneous LV pressure recordings. However, nonvasive methods for acquiring these data have been developed. 6; 7 The reliability of PLS as an index of LV function has been validated in animal models and confirmed in preliminary studies conducted in CRT candidates and in patients with ischemic heart disease. [START_REF] Russell | Assessment of wasted myocardial work: a novel method to quantify energy loss due to uncoordinated left ventricular contractions[END_REF][START_REF] Boe | Noninvasive myocardial work index identifies acute coronary occlusion in patients with non-STsegment elevation-acute coronary syndrome[END_REF][START_REF] Russell | A novel clinical method for quantification of regional left ventricular pressure-strain loop area: a noninvasive index of myocardial work[END_REF][START_REF] Urheim | Regional myocardial work by strain Doppler echocardiography and LV pressure: a new method for quantifying myocardial function[END_REF] An advantage of LV pressure-strain analysis is that it allows the estimation of regional and global LV work (quantified by calculating the rate of segmental shortening (strain rate) and multiplying it by instantaneous LV-pressure). During LV ejection, work performed during segmental elongation represents energy loss, defined as negative work (NW), while work performed during segmental shortening represents positive work (PW). The dispersion of cardiac work may be expressed as a work wasted ratio (WWR) and calculated as NW/PW. Work efficiency (WE) evaluates the proportion of total work dissipated during systole and can be estimated as: (1-NW)/(PW+NW))*100%. 6; 8 This simple index of LV mechanical dispersion which is highly reproducible and have already been tested in several conditions. 10; 11 We have recently completed a preliminary assessment of PLS as an index of LV myocardial in patients with severe AS and preserved LVEF undergoing aortic valve replacement (AVR) using echocardiographic data recorded at baseline and 1 year after the aortic valve replacement. LV pressure was estimated from an empiric, normalized reference curve adjusted according to the duration of the isovolumic and ejection phases, defined by mitral and aortic valve opening and closure times. Our preliminary results are consistent with those presented here by Hulshof et al. [START_REF] Hulshof | Exploratory assessment of left ventricular strain-volume loops in severe aortic valve diseases[END_REF] In marked contrast to LVEF, both strain-volume and strain-pressure-derived parameters distinguish the LV systolic properties of AS and AR patients clearly, and describe the changes of LV performances before and after AVR.

Heart failure (HF) with preserved ejection fraction (a condition frequently in patients who remain breathless following AVR) may be another interesting field of application of these newly introduced parameters. GLS alone has not proved to be an effective prognostic index in HF in HF with preserved ejection fraction, 12; 13 but it seems probable that strain-volume loops and/or pressure-volume loops could better describe intrinsic myocardial function in this setting.

The findings presented here 4 are very preliminary, but they encourage further research to determine the extent to which these promising new indices can be translated to everyday clinical practice.

Acknowledgments

Erwan DONAL receive a research grant from General Electric Healthcare