List of Tables

his chapter. intern

Information Security, a necessity

Nowadays, information is everywhere and used for everything. intern The amount of information generated and exchanged by human is tremendous and continue to rise exponentially as new technologies are created. intern Every field of human activity relies somehow on information and many decisions are based on them. intern Thus, information trust is essential especially for critical systems and infrastructures. Military, government, financial, health and safety related information are usually considered with a special care as obviously critical to t . he good of our society. intern However, information in every field mays be considered as critical depending on t . he point of view. intern Many questions related to information may be asked.i ntern As example, how does a decision-maker is supposed to choose a good decision based on erroneous information? Where t . he decision-maker may be a human, a complex computer program or a simple algor . ithm in a basic piece of electronic. intern he good recipient? Security aims at answering these questions. intern More generally, information security aims at ensuring t . he preservation of confidentiality, integrity and availability of t Hash functions aim at mapping data of arbitrary size to data of fixed size. intern Cryptographic hash function requires different properties such as pre-image resistance, second pre-image resistance and collision resistance. intern The pre-image resistance prevents to inverse t . he function, from a given hash value h, it should be difficult to find any message m such that h = hash(m). intern The second pre-image resistance prevents to find another message with t . he same hash result.i ntern Given an input m 1 it should be difficult to find a different input m 2 such that hash(m 1 ) = hash(m 2 ). intern

Integrated Circuit

Integrated Circuit (IC) is a small electronic circuit on a semiconductor material, such as silicon, embedded in a package. intern The circuit, called die, is inserted in a package and wires allow connecting it to lead frames. intern The lead frames allow soldering t . he IC to a printed circuit board (P CB) and provide connections with other components of the P CB. intern A semiconductor material has a conductivity between conductor and insulator and, as opposed to metals, increase alongside their temperature. intern This property allows to easily control t . he conductivity depending on t . he amount of energy provided to t . he material either with thermal or electric excitation. intern Moreover, their conducting properties can be locally altered by deliberately introducing impurities. intern This process is called doping. intern By inserting e.g. intern phosphorus impurities into silicon, it generates an excess of electron free to move and then improving t . he conductivity. intern This results to what is called n-type doped semiconductors. intern An opposed effect can be obtained by inserting e.g. intern boron impurities to silicon. intern By doing so, electron void in t . he silicon lattice structure called hole are created. intern These holes readily accepts electrons, decreasing t . he conductivity. intern This is called p-type doped semiconductors. intern By using these properties, is it possible to build a Field-Effect-Transistor (F ET ) directly on a semiconductor.i ntern This is called Metal-Oxide-Semiconductor Field-Effect Transistor (M OSF ET ). intern A p-type doped semiconductor is used as substrate and two n-type regions are added, forming t . he transistor source and drain. intern Then a gate is added between t . he two regions and isolated with an oxide. intern This construction is depicted on t he doping, i.e. intern using an n-type substrate and p-type doping for t . he source and drain, another M OSF ET is obtained, called positive-channel M OSF ET or P M OS. intern P M OS works similarly to N M OS, however allows current to pass between source and drain when t . he gate voltage is low and prevents it to pass when t . he voltage is high. As these transistors may act as controlled switches, it is possible to build-upon them logic cells.i ntern As example, in figure 1.3, a basic inverter is built from a P M OS plus a N M OS transistor. Other basic logic cells such as AND, OR, XOR, NAND can be built from transistors. intern This kind of logic that uses both N M OS and P M OS transistors is called Complementary-Metal-Oxide-Semiconductor (CM OS) logic. intern It is also possible to build any logic blocks using only N M OS transistors, which is called N M OS logic or using only P M OS which is called P M OS logic.

The use of different logic gates, allows t . he implementation of other elements such as flip flops and by using flip flop alongside logic elements, complex functions such as finite state machines, memories or CP U s can be built. intern In synchronous designs, clocked flip flops are used. intern The clock which is a periodic signal is propagated to all t . he flip flop over t . he design allowing them to evaluate their outputs simultaneously. intern The clock frequency is adjusted in such a way that signals have enough time to propagate from a flip flop to another through t . he logic.i ntern For a given IC, propagation times vary depending on t . he temperature and power supply.i ntern The slowest path between two flip flops is called t . he critical path and determines t . he maximum clock frequency that can be used in the worse temperature and power supply conditions according to t . he specification. intern The number of a transistors in ICs double approximately every two years since the 1970s. intern This observation is called Moore's law and it allowed to move from thousands of transistor per IC in t . he 1970s to a couple of billions in modern ICs. intern This rise is due to node technology improvement that moved from 10µm in 1970s, to 7nm in 2017. intern ithm implementations including cryptography. intern Unfortunately, they can be observed or perturbed when operating. intern In t . he next sections, explanation about these non-invasive physical threats are provided.

Side channel attacks

ks.

The common observations used to recover information are:

Timing [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]: Some parts of algor . ithms may imply time variations depending on the processed data. intern By observing t . he time, some data can eventually be recovered.

Power consumption [START_REF] Kocher | Differential power analysis[END_REF]: ICs are composed of transistors and they require en- ergy to commute from a state to another thus generating a dynamic leakage. intern Once in a given state, a leakage current may also exist providing a static leakage.i ntern The overall power consumption of an IC depends on t . he internal activity. intern Thus by observing the power consumption, t . he algor . ithmic sequence can be observed providing accurate timing information. intern Signals amplitude may also depend on t . he processed data and thus may provide information on intermediate results.

Electromagnetic emanations [START_REF] Gandolfi | Electromagnetic Analysis: Concrete Results[END_REF]: Current flowing through transistors means moving charges and thus magnetic field. Photonic emission [START_REF] Schlösser | Simple photonic emission analysis of aes[END_REF]: Light emissions in silicon devices had been observed for t . he first time in 1955 [START_REF] Newman | Visible light from a silicon p -n junction[END_REF] and is used for failure analysis [10]. intern CM OS logic emits photon depending on t . he switching activity. intern Thus photon emission are data-dependent and by observing them, internal information of t . he IC can be obtained.

Acoustic [START_REF] Genkin | Rsa key extraction via low-bandwidth acoustic cryptanalysis[END_REF]: Capacitor squeal and coil whine are often observed in computer systems. intern he distinguisher and on statistical leakage assessment tools.i ntern Side channel observation through software is also a hot topic as it allows targeting remote devices.i ntern Cache-timing attac . k [START_REF] Bernstein | Cache-timing attacks on aes[END_REF], or t . he more recent spectre [13] and meltdown [START_REF] Lipp | Meltdown[END_REF] Clock or power glitching [18], [19]: By inserting a short pulse either on the power supply or on t . he clock, propagation delays can be violated resulting to faults. intern The glitch can be inserted with a high timing accuracy helping attac . kers to control the fault injection more precisely than overclocking or under-powering.

Temperature [START_REF] Brouchier | Temperature attacks[END_REF]: Propagation delays vary depending on t . he temperature, thus temperature is also a common way to fault an IC. intern Magnetic pulses [START_REF] Debhaoui | Injection of transient faults using electromagnetic pulses Practical results on a cryptographic system[END_REF]: By using a coil to generate a magnetic pulse close to the IC, transient faults can be injected. intern The coil can be placed at different positions over t . he chip. intern Thus providing attac . kers fault control for both timing and position. intern Laser [START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF]: Light contains photons which can interact with CM OS transistors. intern By using a laser with a small beam, faults can be precisely injected in t . he IC with a high time accuracy. intern Moreover, depending on t . he laser wavelength, both frontside and backside fault injection are possible.

Substrate biasing [START_REF] Maurine | Yet Another Fault Injection Technique : by Forward Body Biasing Injection[END_REF], [START_REF] Beringuier-Boher | Body biasing injection attacks in practice[END_REF]: his feeling. intern Faults can also be instrumented to recover key in software implementation as demonstrated in [START_REF] Sanfelix | Unboxing the white-box[END_REF] where a withebox AES implementation was instrumented to inject faults and recover t . he key. intern he system needs security. intern The ECDSA signature is also a very leakage sensitive scheme based on elliptic curve.i ntern A small leakage on few bits may conduct to fully disclose t . he private key.

The ECDSA can be implemented in different flavors such as in a software that runs on a microcontroller or as a hardware self-contained block or also as a mix between software and hardware accelerator. intern Thus, a wide range of architectures is possible to implement t . he ECDSA. intern

CHAPTER 2

Elliptic Curve Cryptography

In 1985, Elliptic Curves (EC) were proposed independently by Neal Koblitz [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF] and Victor Miller [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] to be used for public key cryptography.i ntern Nowadays, Elliptic Curve Cryptography (ECC) are standardized and widely used in various systems ranging from t

Group, ring and field

Elliptic curve cryptography is based on group theory, we thus recall some basics about group, ring and field.i ntern A group G is a mathematical set of elements equipped with an operation + that satisfies four axioms namely closure, associativity, identity and invertibility.

Closure: (G, +) : G × G → G Associativity: ∀a, b, c ∈ G : a + (b + c) = (a + b) + c Additive identity: ∃0 ∈ G such that ∀a ∈ G : a + 0 = 0 + a = a Invertible: ∀a ∈ G, ∃b ∈ G such that a + b = b + a = 0 A commutative group is called abelian group. Commutativity: ∀a, b ∈ G : a + b = b + a
A ring R is an abelian group with a second operation × that is associative and distributive over t . he + operation and has an identity element 1.

Distributivity (left): ∀a, b, c ∈ R : a × (b + c) = a × b + a × c Distributivity (right): ∀a, b, c ∈ R : (a + b) × c = a × c + b × c Multiplicative identity: ∃1 ∈ R such that ∀a ∈ R : a × 1 = 1 × a = a
A ring F is called field if all nonzero elements are invertible regarding t . he multiplicative operation. he characteristic is 2 or 3. intern The reader can refer to [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] for more mathematical details if they are interested in these other cases. intern For cryptographic use, elliptic curves defined over prime field F p , binary field F 2 m and extension field F p m are considered. intern These fields come along equipped with two operations: a modular addition and a modular multiplication. intern In order to use elliptic curve points as an abelian group and to perform calculus on them, an additive elliptic curve group law is built and an identity O is added. intern As depicted in Figure 2

Invertible: ∀a = 0 ∈ F , ∃b ∈ F such that a × b = b × a = 1
λ = (y 2 -y 1 ) (x 2 -x 1 ) ; x 3 = λ 2 -x 2 -x 1 and y 3 = λ • (x 1 -x 3 ) -y 1 (2.4)
Point doubling:

λ = (3x 2 1 + a) 2 ( 2y 1 )
; One should notice that Figure 2.2 is a simplified illustration which represents the elliptic curve and t . he point operations with real numbers. intern In cryptography, Galois fields are used. intern Thus, all calculations are modulus t . he field order. intern The group formed by t . he elliptic curve points plus t . he neutral element O and the chord-and-tangent group law has an order #E(F q ) in t . he Hasse interval [q + 1 -2 √ q, q + 1 + 2

x 3 = λ 2 -2x 1 and y 3 = λ • (x 1 -x 3 ) -y 1 (2.
√ q]. intern This can be expressed as #E(F q ) = q + 1 -t with |t| ≤ 2 √ q the trace of t . he curve. intern Elliptic curves such that char(F q ) | t are called supersingular and others non-supersingular or also ordinary curve. intern Elliptic curves such that #E(F q ) = q are called anomalous curve. intern Curves candidate for secure implementation of ECC have #E(F q ) = h • m with m a prime number and h a small number called cofactor. intern The elliptic curve point multiplication or scalar multiplication kP with k ∈ F q and P ∈ E(F q ) is build upon t . he additive group law and defined as:

kP = P + P + ... + P k times
This scalar operation is t . he security root of any system based on elliptic curves as it involves a complex mathematical problem, t . he so-called Elliptic Curve Discrete Logarithm Problem (ECDLP ). It can be enunciated as follows: Given two points P ∈ E(F q ) and G ∈ E(F q ), find k ∈ [0, #E(F q ) -1] such that G = kP . intern

Input: k = (k t-1 , k t-2 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: kP 1: Q ← O 2: for i = t -1 to 0 do 3: Q ← 2Q 4: if k i then 5: Q ← Q + P 6:
end if 7: end for 8: return (Q) he ECDLP is to iteratively try all possible k from 0 to #E(F q ) -1 until kP = Q is found.i ntern However, t . his is totally unpractical as soon as k is big enough (> 80bits) as t . he computation time would be in average 1 2 • #E(F q ) ≈ 2 79 ECC point additions and thus too slow to be considered as a real threat. intern Other approaches far more efficient exist. intern The Pollard Rho algor . ithm [START_REF] Pollard | Monte Carlo methods for index computation mod p[END_REF] he elliptic curve scalar operation into a basic modular multiplication that is totally unsafe. intern Satoh, Araki [START_REF] Satoh | Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves[END_REF],

ECDLP and Security level of ECC

Semaev [START_REF] Semaev | Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p[END_REF] and Smart [START_REF] Smart | The discrete logarithm problem on elliptic curves of trace one[END_REF] demonstrated that such isomorphism can easily be found and used ("Smart-ASS attac . k"). intern Supersingular curves are subject to t . he M OV [START_REF] Menezes | Reducing elliptic curve logarithms to logarithms in a finite field[END_REF] and t . he Weil/Tate [START_REF] Frey | A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves[END_REF] pairing attac . ks where t . he main idea is to find an isomorphism between E(F q ) and G a subgroup of t . he extension field F q k in order to end-up with an easy to solve DLP . intern More generally, in order to avoid t . his kind of transfer attac . k, it is required that t . he embedding degree is higher than a given value. intern The value depends on t . he standard (usually at least 20, e.g. intern [START_REF]Digital signature standard (dss)[END_REF]). intern

; Z) = {(λ c •X, λ d •Y, λ•Z); c, d ∈ N * , λ ∈ F * q }.
The standard projective coordinates are defined with c = d = 1 and Jacobian coordinates with c = 2, d = 3. Points represented with affine coordinates as (x; y) can be represented in projective coordinates by calculating (X; Y ; Z) = (λ c • x, λ d • y, λ) for any λ ∈ F * q . intern The conversion from projective form to t . he affine one can be achieved by calculating (x; y) = (X/Z c , Y /Z d ). Below, as an illustration, we give elliptic curve point doubling and point addition formulae when Jacobian coordinates are used for a characteristic of F q different than 2 or 3.

Elliptic curve point doubling in Jacobian:

       X 3 = (3 • X 2 1 + a • Z 4 1 ) 2 -8 • X 1 Y 2 1 Y 3 = (3 • X 2 1 + a • Z 4 1 )(4 • x 1 Y 2 1 -X 3 ) -8 • Y 4 1 Z 3 = 2 • Y 1 Z 1 (2.6)
Elliptic curve point addition in Jacobian:

       X 3 = (Y 2 Z 3 1 -Y 1 Z 3 2 ) 2 -(X 2 Z 2 1 -X 1 Z 2 2 ) 2 • (X 1 Z 2 2 + X 2 Z 2 1 ) Y 3 = (Y 2 Z 3 1 -Y 1 Z 3 2 )(X 1 Z 2 1 • (X 2 Z 2 1 -X 1 Z 2 2 ) 2 -X 3 ) -Y 1 Z 3 2 • (X 2 Z 2 1 -X 1 Z 2 2 ) 3 Z 3 = Z 1 Z 2 • (X 2 Z 2 1 -X 1 Z 2 2 ) (2.7)
An affine point can be seen as a Jacobian point with a Z coordinate equal to 1. intern Thus, the general point addition in Jacobian can be used to add an affine point with a Jacobian point and gives a Jacobian result. intern This is called mixed-coordinates and allows improving t .

he computation speed as multiplications by 1 are removed. Table . 2.2 below summarizes t . he number of operation counts for different coordinates when a curve with a characteristic different than 2 or 3 is considered. Note: N IST curves (in [START_REF]Digital signature standard (dss)[END_REF]) projective point doubling formula over prime field can be simplified as a

= -3 thus (3 • X 2 1 -3 • Z 4 1 ) = 3 • (X 1 + Z 2 1 )(X 1 -Z 2
1 ) allowing to save two field squaring. he global performance or reduce it. intern Indeed, as example, usually field inversions are costly compared to field multiplications especially without a dedicated implementation.i ntern Thus, even if t . he total number of operation required if projective coordinates are used is higher than affine coordinates, t . he computation time can be reduced as no field inversions are involved. intern The most time efficient coordinates system depend on t . he implementation architecture. intern It is also to be noted that the memory required vary withing t . he different coordinates. intern Projective coordinates require saving three coordinates while affine ones require saving only two. intern

Elliptic Curve Digital Signature Algorithm

The Elliptic Curve Digital Signature Algor . ithm (ECDSA, [START_REF]Digital signature standard (dss)[END_REF]) is an alternative to the Digital Signature Algor . ithm (DSA) which uses elliptic curves scalar instead of modular exponentiation [START_REF]Digital signature standard (dss)[END_REF]. intern Such signature schemes are used for authentication purpose. intern There are three distinctive operations in ECDSA: The key generation, t . he signature and t . he verification.

A shared curve E(F q ) and a base point P of order n are used between users for these different operations. intern These operations are defined as follows:

Key generation

It aims at generating a key pair composed of a private key and a public key.i ntern The private key d is usually randomly chosen such that 0 ≤ d ≤ n -1 with n the order of the base point. intern The associated public point Q is determined by using t . he elliptic curve scalar operation as defined above: Q = d • P

Signature

In order to sign a message msg, first a random nonc . e k such that 0 ≤ k ≤ n -1 is generated. intern

Verification

First, verification checks that Q (the public key) is not t . he point at infinity and is part of t . he given curve E. intern One verifies than that n • Q equals t .

he infinity point.i ntern

The signature element r and s are asserted to be between 1 and n -

1. Afterwards, (x, y) = (H(msg) • s -1 mod n) • P + (r • s -1 mod n) • Q is computed. intern The signature is correct if r ≡ x mod n.

Lattice attacks on ECDSA

The lattice attac . k on ECDSA is a powerful mathematical approach that can be used to bypass t . he ECDLP and recover t . he ECDSA private key and nonc . es used to sign messages [START_REF] Nguyen | The insecurity of the digital signature algorithm with partially known nonces[END_REF]. intern The mathematical demonstrations behind such attac . k can be complex to understand, however using t . he concept and implementing these kinds of attac . ks is easy. intern Thus next lines aim at describing lattice basics and provide a simple numeric example to demonstrate how easy it is to break ECDSA using t . he lattices. intern he number of M SBs set to 0 [START_REF] Brumley | Remote timing attacks are still practical[END_REF]. intern [START_REF] Nguyen | The insecurity of the digital signature algorithm with partially known nonces[END_REF] presents experimental results when nonc . e length can be discovered through a remote timing analysis over a computer network.

Computing a lattices attack

Each signature (r j , s j ) can be written as: he equation system cannot be normally solved. intern However, by inserting some knowledge of each unknown values, we can eventually solve it.

s j = k -1 j (H j (m) + d • r j ) with r j = (k j P ) x mod n.
s j ≡ k -1 j (H j (m) + d • r j ) mod n ⇔ s j k j -d • r j -H j ≡ 0 mod n ⇔ k j -d • r j /s j -H j /s j ≡ 0 mod n ⇔ k j -d • r j /s j -H j /s j -a i • n = 0
From h equations as above, t . he lattice generated by t . he rows of A can be built:

A =         -1 -r 1 s 1 mod n -r 2 s 2 mod n • • • -r h s h mod n 0 n 0 • • • 0 : 0 n . . . 0 : : • • • . . . 0 0 0 0 • • • n         By construction, it exists X such that XA -t = (d, k 1 , k 2 , . . . , k h ) with t = (0, -H 1 /s 1 mod n, -H 2 /s 2 mod n, . . . -H h /s h mod n) If
XB -t = (d, k 1 , k 2 , . . . , k h ) is still valid, however t .
he wrong lattice point will be found when rounding t and thus will lead to an incorrect result. intern In t . his case, surrounding points can be used and potentially conduct to a correct result. intern The knowledge of information about d and k j aims to write similar equations with smaller d ′ and k ′ j . intern For example

if k 1 is even, it is possible to write k 1 = 2 • k ′ j . intern

Basic numerical example of a lattice attack

The curve E : y 2 = x 3 + 1001x + 75 over F 7919 and t Thanks to side channel leakages, we consider that we discovered that an important number of nonc . e M SBs are equal to 0 (e.g. intern from global timing analysis). intern he binary representation, ? represents an unknown bit value.

From Table 3, these three equations can be written:

5172 -7290 • k 1 + 3012 • d ≡ 0 mod 7889 3095 -2372 • k 2 + 4596 • d ≡ 0 mod 7889 1350 -941 • k 3 + 4808 • d ≡ 0 mod 7889
As no information is known about t . he private key d used, d is expressed in function of k 1 and replaced in all equations.

5172

-7290 • k 1 + 3012 • d ≡ 0 mod 7889 ⇔ d ≡ 2784 • k 1 + 5310 mod 7889 k 2 + 6978 • k 1 + 283 ≡ 0 mod 7889 k 3 + 564 • k 1 + 2755 ≡ 0 mod 7889 Known information about nonc .
es are inserted in these two last equations. intern Nonces can be expressed as k j = k j M SB • 2 l j + k j lsb with l j depending on t .

he number of M SBs known and k j M SB know (the bits gathered).

k 2 lsb + 6978 • k 1 lsb + (283 + (1 + 6978) • k 2 M SB • 2 l 2 ) ≡ 0 mod 7889 k 3 lsb + 564 • k 1 lsb + (2755 + (1 + 564) • k 3 M SB • 2 l 3 ) ≡ 0 mod 7889
All we know is that an unknown number of nonc .

es M SBs are equal to 0. intern Thereby, nonc .

es can be expressed as k j = 0 • 2 l i + k j l sb = k j l sb . intern Thus, equations are almost not modified:

k 2 l sb + 6978 • k 1 l sb + 283 ≡ 0 mod 7889 k 3 l sb + 564 • k 1 l sb + 2755 ≡ 0 mod 7889
From these two equations, we can build a lattice generated by t . he rows of:

A =   -
B = LLL(A) =   182 133 -91 -294 392 147 -251 120 -438  
By construction, we know that it exists X such that:

XB -t = (k 1 lsb , k 2 lsb , k 3 lsb ) with t = (0, 283 , 2755)
To find X, we first express t in t . he lattice basis. intern To do that, these following equations are solved:

       182 • λ 1 -294 • λ 2 -251 • λ 3 = 0 133 • λ 1 + 392 • λ 2 + 120 • λ 3 = 283 -91 • λ 1 + 147 • λ 2 -438 • λ 3 = 2755 ⇔        λ 1 = -16097/7889 λ 2 = -22964/7889 λ 3 = -5510/1127
We can solve t .

he Closest Vector Problem (CV P ) and find X by using Babai rounding off method.i ntern It consists in simply rounding previous result to t . he nearest integer. intern

X = (-2, 3, -5) is found. intern Then: XB -t = (9, 310, 2813)-(0, 283, 2755) = (9, 27, 58) = (k 1 lsb , k 2 lsb , k 3 lsb ) = (k 1 , k 2 , k 3 ) Thus: d ≡ 2784 • 9 + 5310 mod 7889 ≡ 6699 mod 7889
As 6699 • G = (7359; 3262) = Q, we can conclude that t . he recovered private key is correct.

Lattice attack results on NIST P256

In order to have a better understanding of t his number [START_REF] Goudarzi | Lattice attacks against elliptic-curve signatures with blinded scalar multiplication[END_REF], other mathematical approaches such as the Bleinchenbacher attac . k [START_REF] Bleichenbacher | On the generation of dss one-time keys[END_REF] can overcome t . his limitation.

Summary

Elliptic Curve Cryptography is based on elliptic curves over finite fields. intern By using the algebraic structure, it allows to define a group composed of elliptic curve points. intern The N SA then started to examine every cipher machine and discovered that they all radiated in some way. intern The voltage of t . he power lines of rotor machines fluctuates as a function of t . he number of rotors moving, t . his was called power line modulation. intern Acoustic leakage was also investigated. intern In fact, it was found that any information-processing equipment such teletypewriters, duplicating equipment, intercoms, facsimile, computers and so on radiated information. intern This problem of compromising radiation and associated countermeasures has been given t . he cover name TEMPEST. intern The NSA declassified in 1972 a paper about these discoveries [START_REF] Nsa | Tempest: A signal problem[END_REF]. intern Since, government programs and guidances exist in order to avoid leakage in newer equipments [START_REF]Tempest certification program[END_REF], [START_REF]Canadian emsec and tempest[END_REF]. intern Wim Van Eck is t . he first in 1985 to publicly demonstrate that it is possible to eavesdrop on video display units from a remote location thanks to EM [START_REF] Van Eck | Electromagnetic radiation from video display units: An eavesdropping risk?[END_REF]. intern Latter, in 1996 Paul Kocher demonstrated that it is possible to recover sec . r . et key from timing characteristic when asymmetric cryptography such as RSA, Diffie-Hellman or DSS are used [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]. intern Then in 1999, when smart-cards were widely used for strong and cheap authentication, Paul Kocher et al. intern showed that power analysis can be used to recover sec . r . et keys from smart-cards [START_REF] Kocher | Differential power analysis[END_REF]. intern In t . he paper, both simple power analysis and differential power analysis were described for t . he first time and used t . he DES algor . ithm as example. Since, side channel attracts a wide attention from academic researchers that resulted at improving data acquisition techniques, pre-processing, power consumption models and distinguisher. intern The most considered side channel attac . ks are timing [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], power analysis [START_REF] Kocher | Differential power analysis[END_REF] and EM [START_REF] Gandolfi | Electromagnetic Analysis: Concrete Results[END_REF], [START_REF] Quisquater | ElectroMagnetic Analysis (EMA): Measures and Counter-measures for Smart Cards[END_REF]. intern ithms are not perfect against small side channel leakage is concluded in section 3.4.

Scalar algorithms and leakages sources

SP A stands for Simple Power Analysis [49]. intern The principle is to run t

Input: k = (k t-1 , k t-2 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: kP 1: Q ← O 2: for i = t -1 to 0 do 3: Q ← 2Q 4: if k i then 5: Q ← Q + P 6: end if 7: end for 8: return (Q) This algor .
ithm is also known to be SP A sensitive [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. intern Depending on t In t

.

his trace we can clearly see that it contains information and we can distinguish different patterns.i ntern Indeed, a pattern composed of 1 peak followed by 11 peaks then 1 peak (denoted as 1-11-1 peaks) appears at t . he beginning of t he supposed elliptic curve double operation. intern We can clearly distinguish large gaps and small gaps between doubling operations.i ntern From Algor . ithm 3.1, we can easily conclude that large gaps are observed when an elliptic curve double and addition operations are done while small gap happens when just a point doubling is performed in t . he loop iteration.i ntern Large gaps are thus labeled "DA" for Double and Add and small gap "D" for Double. intern

w, d = ⌈t/w⌉, k = (K d-1 , ..., K 1 , K 0 ) 2 w , P ∈ E(F q ) Output: kP Pre-computation: compute P i = 2 wi P , 0 < i < d -1 1: A ← O,B ← O 2: for j = 2 w -1 downto 1 do 3: for j = 2 w -1 downto 0 do 4: if K i = j then 5: B ← B + P i 6: end if 7:
end for his it is not the case when mixed coordinates systems are used. intern The second one is caused by searching for a particular value in t .

he key and doing an operation as soon as it is found. intern These two security flaws are independent thus in case of t . he use of one coordinate system, t . he operation flow will be constant. intern Nevertheless, timing leakage could help to find out information about t . he scalar value.

Fixed-base comb method

The fixed-base comb method [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] is another algor . ithm for elliptic curve scalar operations which aims at improving performances when point pre-calculation is allowed. intern Output: kP Pre-computation: compute all possible [a w-1 , ..., a 1 , a 0 ]•P and 2 e [a w-1 , ..., a 1 , a 0 ]• P , where [a w-1 , ..., a 1 , a 0 ] = a w-1 • 2 w-1 P + ... + a 1 • 2 1 P + a 0 • P and a i ∈ {0, 1} Represent k as:

     k 0 d-1 • • • k 0 1 k 0 0 k 1 d-1 • • • k 1 1 k 1 0 : . . . . . . • • • k w-1 d-1 • • • k w-1 1 k w-1 0     
//if necessary, pad 0s as k M SBs. Point additions are again represented by a pattern of 3-5-2 peaks and point double by a pattern of 1-11-1 peaks. intern As it can be seen from Figure 3.5, usually a point doubling "D" and two points additions "A" occur for each iteration. intern In Figure 3 et is parsed with 0s). intern Also when one of t . he two parsed column is set to 0, two possibilities exist, then these bits does not instantly leak. intern Another leakage that could happen using such an algor . ithm is relative to t . he pre-computed values management. intern The time to fetch t . he required pre-computed value for an iteration can vary. intern For instance, when a cache is used, a cache hit/miss can eventually leak information [START_REF] Rebeiro | Timing Channels in Cryptography[END_REF]. he ECDSA. intern The second approach to counter operation flow leakage described section 3.1.1 consists in keeping Algor . ithm 3.1 and having a unified formula [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF] for both point double and point addition. intern Thanks to unified formula, one cannot distinguish a double operation from an add operation. intern

1: Q ← O 2: for i = e -1 to 0 do 3: Q ← 2.Q 4: Q ← Q + [k w-1 i , ..., k 1 i , k 0 i ]P + 2 e [k w-1 i+e , ..., k 1 i+e , k 0

Double-and-Add countermeasures

Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: Q ← O 2: for i = t -1 to 0 do 3: Q ← 2Q 4: if k i then 5: Q ← Q + P 6:
Q = O //initialization Q = O //initialization Q = 2 • O //nothing to do Q = 2 • O //nothing to do Q = O + P //data transfer, P to Q Q = O + P //data transfer, P to Q Q = 2P //Point double Q = 2 • O //nothing to do Q = 2P + P //Point addition Q = O + P //

Global timing

A global timing analysis can leak some useful information. intern

Leakages on underlying algorithms

As SP A is very simple to implement and efficient to recover ECC sec

Algorithm 3.5 Coron always Double-and-add

Input: k = (k t-2 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: Q[0] ← P 2: for i = t -2 to 0 do 3: Q[0] ← 2Q[0] 4: Q[1] ← Q[0] + P 5: Q[0] ← Q[k i ] 6: end for 7: return (Q[0])
-Either Q[0] = 2 • (2P ) and Q[1] = 4P + P -Or Q[0] = 2 • (3P ) and Q[1] = 6P + P
This depends on t . he previously parsed bit.i ntern Thus, only two possibilities exist and discriminating them can be easy.i ntern Most designs can allow attac . kers to capture a power trace of an elliptic curve scalar operation when using sensitive information such as a private key or a nonc From Figure 9 to Figure 12, we can clearly distinguish parts of t . he trace that match from part that does not without any post-process. intern ithm that provides a data dependent leakage.

Example on NIST P-256

In t . his example, we consider a system based on N IST P-256 implemented as previously on an ARM926 using as hash function SHA-256. intern The public point is:

Q : x Q = 0xf 703e67604e1187cbe40f 2176dc86d7e6b168f 8a160c6e8f 106bf 90d184c5f f c y Q = 0x4ca233f 8ae175e7c21eac1c1a705cdf 50d6ef 9f 9bb65a8dd44aa5109ed02c567
We he 255 patterns repetition instead of 256 that could be expected for a 256-bit system.

A closer look on t . he captured power traces reveals that at each new parsed bit, the power traces fork in two groups except for t . he first EC operation. intern This is illustrated by Figure 3.13 where different traces have been superposed.

d = 0xc166ea345491b1576f f 9e8166df 96b5f 4cd3ae47350ef f f 2446f 28f 29a5883ee
The nonc . es values used during t . he given signatures was t . he following:

k 1 = 0x8a1234a8b3739b347af 417cdbf 8f f 73649c5e62ef 81767e20626adf f 81ade12c k 2 = 0x8a125c71934ca50d396c299c01c02aba94e1f 97f ec13d5edb7932aab7aabc2c9 k 3 = 0x8a131f e2d71cd3a81aa6786a283ca05df e4de37dddca27b6b5ad9f 6847a9ba53
We he effect of nuclear radiation on semiconductor devices. intern It was observed various modifications of device characteristics due to gamma flux either transient or permanent on both germanium and silicon based devices. intern The transient behavior and response due to ionized radiation are then studied in [START_REF] Caldwell | The transient behavior of transistors due to ionized radiation pulses[END_REF] and [START_REF] Wirth | The transient response of transistors and diodes to ionizing radiation[END_REF] by using X-ray. intern In [START_REF] Habing | The use of lasers to simulate radiation-induced transients in semiconductor devices and circuits[END_REF] t . he author determined that a pulsed-infrared laser is an inexpensive and effective way to simulate t . he effects caused by gamma ray sources in semiconductor devices. intern In 1975, after anomalies in communication satellite, [START_REF] Binder | Satellite anomalies from galactic cosmic rays[END_REF] investigated t . he interaction of galactic cosmic rays with devices. intern In [START_REF] May | A new physical mechanism for soft errors in dynamic memories[END_REF], single-bit soft error in dynamic RAM s and CCDs due to alpha particles are observed. intern Then authors in [START_REF] Ziegler | Effect of cosmic rays on computer memories[END_REF] provide a method for evaluating t . he effects of cosmic rays on computer memories. While these researches focus on harsh environment effects on semiconductor and possible countermeasures mostly for aerospace systems, more modern researches aimed at intentionally inducing errors to break implementation of cryptographic algor . ithm. intern The first academic discussion of such an attac . k is [START_REF] Boneh | On the importance of eliminating errors in cryptographic computations[END_REF] in 1997 which presents vulnerabilities in various RSA implementations. intern Then in [START_REF] Biham | Differential fault analysis of secret key cryptosystems[END_REF] ks and countermeasures have been proposed.i ntern Numerous ways of inserting faults had been considered such as using clock or power glitching [18], [19], overclocking [START_REF] Faurax | Robustness of circuits under delayinduced faults : test of aes with the pafi tool[END_REF], [START_REF] Danger | Overview of dual rail with precharge logic styles to thwart implementation-level attacks on hardware cryptoprocessors[END_REF], [START_REF] Fukunaga | Practical fault attack on a cryptographic lsi with iso/iec 18033-3 block ciphers[END_REF], [START_REF] Agoyan | When Clocks Fail: On Critical Paths and Clock Faults[END_REF] and [START_REF] Sakiyama | Fault analysis attack against an aes prototype chip using rsl[END_REF], under-powering [17], [START_REF] Khelil | Fault analysis attack on an fpga aes implementation[END_REF], [START_REF] Selmane | Practical setup time violation attacks on aes[END_REF], temperature [20] or EM [START_REF] Debhaoui | Injection of transient faults using electromagnetic pulses Practical results on a cryptographic system[END_REF]. intern Currently, t . he most effective fault injection method is obtained by using a laser such as in [START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF], [START_REF] Schmidt | Optical fault attacks on aes: A threat in violet[END_REF], [START_REF] Skorobogatov | Using optical emission analysis for estimating contribution to power analysis[END_REF] or by using Forward Body Biasing Injection attac . k (F BBI) [START_REF] Maurine | Yet Another Fault Injection Technique : by Forward Body Biasing Injection[END_REF], [START_REF] Beringuier-Boher | Body biasing injection attacks in practice[END_REF] he beam while providing a wide range of pulse durations ranging from 3ps to continuous wave at a decent power. intern This greatly help to target a specific operation of t . he IC at low cost. intern

Safe-error attack against the scalar algorithm

= (k t-2 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: Q[0] ← P 2: for i = t -2 to 0 do 3: Q[0] ← 2Q[0] 4: Q[1] ← Q[0] + P 5: Q[0] ← Q[k i ] 6: end for 7: return (Q[0]) C safe-
Input: k = (1, k t-2 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: R 0 ← P 2: R 1 ← 2P 3: for i = t -2 to 0 do 4: R 1-k i ← R 0 + R 1 5: R k i ← 2R k i 6: end for 7: return (R 0 )
One missing information is that, from algor . ithm 4.2, if k i = 0 t . he operation R 1-k i ← R 0 +R 1 may become a dummy operation. intern It is clearly visible that for k = (1, 0, ..., he randomized initial point (RIP, initially presented in [START_REF] Itoh | Efficient countermeasures against power analysis for elliptic curve cryptosystems[END_REF]) is considered. intern The presented algor . ithm aims to be resistant against Simple Power Analysis (SP A), Differential Power analysis (DP A) [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF], Refined Power Analysis (RP A) [START_REF] Goubin | A refined power-analysis attack on elliptic curve cryptosystems[END_REF] and Zero-value Point Attacks (ZP A) [START_REF] Akishita | Zero-value point attacks on elliptic curve cryptosystem[END_REF]. intern he elliptic curve point addition formula is a unified and complete addition law that works for both Algorithm 4.5 Scalar operation with pre-computed points Input: k = (r ⌈t/4⌉ , ..., r 1 , r 0 ) 2 4 , |r j |.16 a .P ∈ E(F q ), with 0 ≤ a ≤ ⌈t/4⌉ for any r j ∈ {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7} Output: k.P he twisted Edwards addition law presented in [START_REF] Bernstein | Twisted edwards curves[END_REF] generates special arithmetic cases. The given law is t . he following:

s j ≡ k -1 j (H(m j ) + d • r j ) mod n ⇔ k j -d • r j /s j -H(m j )/s j ≡ 0 mod n ⇔ k j M SB + k j unknow • 2 x + k j LSBs -d • r j /s j -H(m j )/s j ≡
⇔ k j unknow • 2 x -d • r j /s j -H j /s j + 2 255 ≡ 0 mod n ⇔ k j unknow -d • r j /(s j • 2 x ) -H j /(s j • 2 x ) + 2
Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: R ← randompoint() 2: T ← P -R 3: Q ← R 4: for i = t -1 to 0 do 5: Q ← 2Q 6: if k i then 7: Q ← Q + T 8: else 9: Q ← Q -R
1: Q ← O 2: for i = ⌈t/4⌉ to 0 do 3: Q ← Q + r j .
(x 1 , y 1 ) + (x 2 , y 2 ) = ( x 1 • y 2 + x 2 • y 1 1 + d • x 1 • x 2 • y 1 • y 2 , y 1 • y 2 + x 1 • x 2 1 -d • x 1 • x 2 • y 1 • y 2 ) (4.1) With t .
he neutral element, we obtain:

(x 1 , y 1 ) + (0, 1) = ( x 1 • 1 + 0 • y 1 1 + d • x 1 • 0 • y 1 • 1 , y 1 • 1 + x 1 • 0 1 -d • x 1 • 0 • y 1 • 1 ) = (x 1 , y 1 ) (4.2)
In order to avoid side channel attac . ks, t

.

he system should perform multiplication operations similarly with random operands than with specific values such as 0 or 1.i ntern This mean x 1 • 1 mod p similarly to x 1 • y 2 mod p, 0 • y 1 mod p similarly to x 2 • y 1 and so on. intern And also perform inversions without leaking information, i.e. intern A/1 mod p similarly to A/B mod p for any A and B. intern With "similarly" meaning, without any noticeable timing difference due to a simplification nor without a different power consumption that could be due to carry propagation, modular reduction or other.i ntern Such system is not obvious and t he infinity point (Q 0 and Q 1 are both initialized to O and will be updated at t . he first k i = 0 and k i = 1 which can be detected), t . he coherency checking provides an interesting approach to validate that all computations are done correctly. intern Indeed, all computations are not necessary to end up with t . he good result in Q 1 as some of them are dummy operations (i.e. intern operations involving Q 0 ). intern However, t . he checking Q 2 = Q 0 + Q 1 + P line 8 involves both Q 0 and Q 1 . intern Thus, it is expected that faults on any

Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: k.P 1: Q 0 ← O 2: Q 1 ← O 3: Q 2 ← P 4: for i = 0 to t -1 do 5: Q k i ← Q k i + Q 2 6: Q 2 ← 2Q 2 7: end for 8: if Q 0 ∈ E(F q ) and Q 1 ∈ E(F q ) and Q 2 = Q 0 + Q 1 + P then 9: return (Q 1 )
Q k i ← Q k i + Q 2 computations,
Q k i ← Q k i + Q 2 is
performed, meaning that either Q 0 or Q 1 will be updated with t . he result. intern If algor . ithm 4.7 is used, Q 0 or Q 1 will be updated with t . he (X 3 : Y 3 : Z 3 ) result of algor . ithm 4.7. intern A fault on Q 0 x-coordinate between line 7 and line 19 of algor . ithm 4.7 will either generate an error or not during t . he coherency checking.i ntern Indeed, if k i = 0, then Q 0 will be updated with t . he result (X 3 : Y 3 : Z 3 ) of algor . ithm 4.7. intern Thus, the faulted x-coordinate will be updated with t . he correct result X 3 and then no error will be detected. intern As opposed, if k i = 1, Q 1 will be updated with t k can be applied also on Q 1 . intern And other lines of algor . ithm 4.7 can be targeted (e.g. intern X 3 , Y 3 , Z 3 can be used).

Algorithm 4.7 ECC Jacobian point addition Input:

P = (X 1 : Y 1 : Z 1 ) and Q = (X 2 , Y 2 , Z 2 ) on E(F q ) : y 2 = x 3 -3x + b Output: P + Q = (X 3 : Y 3 : Z 3 ) 1: T 1 ← Z 2 1 2: T 3 ← Z 2 2 3: T 2 ← T 1 • Z 1 4: T 1 ← T 1 • X 2 5: T 4 ← T 3 • Z 2 6: T 3 ← T 3 • X 1 7: T 2 ← T 2 • Y 2 8: Y 3 ← T 4 • Y 1 9: T 1 ← T 1 -T 3 10: T 2 ← T 2 -Y 3 11: if T 1 == 0 then 12: if T 2 == 0 then 13: (X 3 : Y 3 : Z 3 ) = Compute(2Q
end if 18: end if 19: Z 3 ← Z 1 • T 1 20: Z 3 ← Z 2 • Z 3 21: X 3 ← T 2 1 22: T 4 ← X 3 • T 1 23: T 3 ← X 3 • T 3 24: T 1 ← 2T 3 25: X 3 ← T 2

Fault attacks against the ECDSA signature

The ECDSA signature is a complex operation as it involves different computations with different sec

-Select a random d such that 0 ≤ d ≤ n -1 -Compute Q = d.P with P ∈ E(F q ) -d is t . he private key, Q is t . he public one. Signature: -Generate a nonc . e k such that 0 ≤ k ≤ n -1 -Compute G = (x, y) = k.P with P ∈ E(F q ) -r ≡ x mod n -s ≡ k -1 (H(msg) + d • r) mod n -(r, s) is t . he signature.
The signature (r, s) can be verified by using t . he public key Q and E(F q ) as explained in section 2.5. If an attac . ker is able, somehow, to fault

d into d ′ = d ± e • 2 l during signature, t . he following will happen: -Generate a nonc . e k such that 0 ≤ k ≤ n -1 -Compute G = (x, y) = k.P with P ∈ E(F q ) -r ≡ x mod n -s ′ ≡ k -1 (H j (m) + (d ± e • 2 l ) • r) mod n -(r, s ′ ) is t . he faulted signature.
In t . his case, t . he signature (r, s ′ ) cannot be verified from Q = d • P and E(F q ). intern Indeed, from t . he verification formula: et and a maximum of 2 9 computations after each fault to recover ±e allows recovering these 8 bits with 90% of chance. intern Doing so 32 times (41k faults) allows recovering t . he full key with in average log(1/0.9)/log(2) • 32 = 4.86 missing bits that can easily be brutforced. intern The number of necessary faults can be reduced depending on t . he computation power available, e.g. intern ∼ 20k faults and 2

(x, y) = (H(msg) • s ′-1 mod n) • P + (r • s ′-1 mod n) • Q ⇔ (x, y) = (H(msg) • k • (H j (m) + (d ± e • 2 l ) • r) -1 mod n) • P + (r • k • (H j (m) +

Faulted nonce

For each new signature, a nonc . e k is selected and used for both t . he r and s parts of the signature. intern

≤ k ≤ n -1 -Compute G = (x, y) = k.P with P ∈ E(F q ) -r ≡ x mod n -s ′ ≡ (k ± e • 2 l ) -1 (H(msg) + d • r) mod n -(r, s ′ )
G ′ = (x ′ , y ′ ) = kP ± (e • 2 l ) • P and r ′ ≡ x ′ mod n until t .
he signature (r ′ , s ′ ) can be verified from G ′ and E(F q ). intern In E(F p ), due to t . he Hasse

interval (n ∈ [p + 1 -2 √ p, p + 1 + 2 √ p]), t .
he probability to get r > n is less than 1/2 127 for a 256 bits curve. intern Thus, most of t . he time r = x, and kP = (x, y) can be recovered. intern Once e and r ′ are found, t . he verification will pass:

(x, y) = (H(msg) • s ′-1 mod n) • P + (r ′ • s ′-1 mod n) • Q ⇔ (x, y) = [(k ± e • 2 l ) • (H(msg) + d • r) • (H(msg) + d • r) -1 ] • P ⇔ (x, y) = kP ± (e • 2 l ) • P ⇔ r ′ ≡ x mod n It is to be noted that two possible values of G ′ allow t . he verification. intern One is G ′ = kP ± (e • 2 l ) • P and t . he second one is G ′ = (n -k)P ± (e • 2 l ) • P with t .
he sign of e inverted. intern This is due to t . he fact that kP + (n -k)P = O, thus if kP = (x, y) then (n -k)P = (x, -y). ker obtains e ≥ 240, then he directly knows that t . he genuine 8 bits register value is smaller than 15, thus t . he four M SBs are set to 0. intern Someone looking for x M SBs need to find |e| ≥ 2 m -2 m-x . intern The probability to find such an error value is p x ≈ 1/2 2x . intern Thus, ≈ 2 2x+3 faults can be injected in order to obtain at least one which will provide x bits of information with a high probability. intern Doing so by targeting As two possible values of G ′ exist that are kP and (n-k)P , then t . he guessed M SBs are either for k or n -k. intern These values are related. intern On N IST P256, M SBs of the modulo n are set to 1s [START_REF]Digital signature standard (dss)[END_REF]. intern Thus, if t . he M SBs of k are set to 0s then t . he M SBs of (n -k) are set to 1s and vis versa. intern For each gathered signature such as |e| ≥ 2 m -2 m-x , two solutions exist, either x M SBs of k are set to 0s or x M SBs of k are set to 1s. Read1 @ 0x0000 @ 0x0000 @ 0x0000 W rite1 @ 0xA 1 000 @ 0xA 1 000 @ 0xA 1 000

s 1 ≡ k -1 (H(m 1 ) + dr) mod n s 2 ≡ k -1 (H(m 2 ) + dr) mod n ⇔ k ≡ s -1 1 (H(m 1 ) + dr) mod n d ≡ (s 2 H(m 1 ) -s 1 H(m 2 )) • (r(s 1 -s 2 )) -1 mod n (4.
       k 1 = X • 2 l + Rdm 1 k 2 = X • 2 l + Rdm 2 ... k j = X • 2 l + Rdm
Read2 @ 0xA 1 000 @ ′ 0xF 1 F 2 F 3 F 4 @ 0xA 1 000 W rite2 @ 0xA 1 A 2 00 @ 0xF 1 A 2 00 @ ′ 0xA 1 A 2 00 Read3 @ 0xA 1 A 2 00 @ 0xF 1 A 2 00 @ 0xA 1 000

W rite3 @ 0xA 1 A 2 A 3 0 @ 0xF 1 A 2 A 3 0 @ 0xA 1 0A 3 0 Read4 @ 0xA 1 A 2 A 3 0 @ 0xF 1 A 2 A 3 0 @ 0xA 1 0A 3 0 W rite4 @ 0xA 1 A 2 A 3 A 4 @ 0xF 1 A 2 A 3 A 4 @ 0xA 1 0A 3 A 4 @:

Summary

We demonstrated that some elliptic curve scalar algor . ithms are wrongly supposed to be safe-error resistant due to either t . he algor . ithm or to underlying computations. intern he operation flow is correct and not modified by a fault and also provides some detection capabilities of data modification. intern Finally, the various algor . ithms and countermeasures performances, cost, and countermeasures are summarized in section 5.4.

Our secure scalar point multiplication

Input: E(F q ), k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) Output: 2k.P 1: Q ← P 2: for i = t -1 to 0 do 3: Q ← 2.Q 4: Q ← Q + (-
k i = 1, Q ← Q + (P -E) otherwise, Q ← Q -E.
k i = 1, Q ← Q + P 2 otherwise, Q ← Q -P 2 . intern

Algorithm 5.3 Modified Comb method

Input: E(F q ), k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ), window width w, d = ⌈ t w ⌉ Output: 2k.P Pre-computation: compute 2 • [1, a w-2 , ...a 1 , a 0 ].P -[1 w-1 , ...1 1 , 1 0 ].P for all possi- ble binary values of a w-2 , ...a 1 , a 0 , with [1, a w-2 , ...a 1 , a 0 ].P = 2 (w-1)d P +...+a 1 2 d P + a 0 P .

Represent k as:

   k 0 d-1 • • • k 0 1 k 0 0 : . . . . . . : k w-1 d-1 • • • k w-1 1 k w-1 0    //if
Q ← 2.Q 4: Q ← Q + (-1) k w-1 i .[[k w-1 i , ..k w-1 i ] ⊕ [k w-2 i , ...k 1 i , k 0 i ]].P 5: end for 6: Q ← Q -[1 w-1 , ...1 1 , 1 0 ].P 7: return (Q) 5.1.
Q ← 2Q 8: Q ← Q + (-1) k i+t/2 P [r ⊕ (k i ⊕ k i+t/2 )] 9:
r ← randombit()

Q ← Q -P [r] 14: Q ← Q -P [r] //remove P [r] 15: Q ← JactoAff(Q) //use
(P + Q), Q -(G -P ), Q + (G -P ) or Q + (G + P ). intern Algorithm 5.5 2k • P + 2v • G operation Input: k = (k t-1 , ..., k 1 , k 0 ) 2 ,v = (v t-1 , ..., v 1 , v 0 ) 2 , P and G ∈ E(F q ) Output: 2kP + 2vG 1: r ← randombit(
Q ← 2Q 8: Q ← Q + (-1) v i P [r ⊕ (k i ⊕ v i )] 9:
r ← randombit() //refresh t . he random r 10: shuffleregisters(P [0],P [1],r) //shuffle P[0] and P [1] according to r 11: end for

12: Q ← Q + P [r] //add P [r] for system integrity 13: Q ← Q -P [r] 14: Q ← Q -P [r] //remove P [r] 15: Q ← JactoAff(Q) //use
• G = k 1 G + k 2 (r • G) Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , G ∈ E(F q ) Output: 2k • G 1: r ← random([0, 2 32 -1]) 2: v ← random([0, #E(F q ) -1]) 3: k ← k -v 4: v ← v • (2r) -1 mod n 5: Q ← AlgKP (r, G) //
Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , m ∈ F q Output: 2k.m 1: q ← m 2: for i = t -1 to 0 do 3: q ← 2.q 4: q ← q + (-1) k i .m
//add or subtract r, depending on k i 5: end for 6: q ← q -m 7: return (q) Algorithm 5.10 ECC Jacobian point doubling and field doubling on NIST curves: double(Q,q) Input: P = (X 1 : Y 1 : Z 1 ) in Jacobian ∈ E(F p ), q ∈ F p Output: (X 1 : Y 1 : Z 1 ) ← 2P and q ← 2q mod n

1: T 1 ← Z 2 1 mod p 2: T 2 ← X 1 -T 1 mod p 3: T 1 ← X 1 + T 1 mod p 4: T 2 ← T 2 • T 1 mod p 5: T 2 ← 3T 2 mod p 6: T  ← Y  + q 7: q ← Y  mod p // 2Y 1 8: Y  ← T  //2Y 1 + 2q 9: q ← Y  -q //2q 10: Y  ← Y  -q mod p //2Y 1 11: q ← q mod n //2q mod n 12: Z 1 ← Y 1 • Z 1 mod p 13: T 3 ← Y 2 1 mod p 14: Y 1 ← T 3 • X 1 mod p 15: T 3 ← T 2 3 mod p 16: T 3 ← T 3 /2 mod p 17: X 1 ← T 2 2 mod p 18: T 1 ← 2Y 1 mod p 19: X 1 ← X 1 -T 1 mod p 20: T 1 ← Y 1 -X 1 mod p 21: T 1 ← T 1 • T 2 mod p 22: Y 1 ← T 1 -T 3 mod p is no longer on t .
he curve. intern The register q which is also modified is then used with Y 1 to end up with t . he expected computation 2q. intern This result is then used with Y 1 to obtain t . he good EC result which is two times t . he original Y 1 value. intern It is obvious that skipping a line among lines 6 to 10 conduct to fault q which is part of t . he CF I. intern It is also obvious that random faults on data will either fault Y 1 , which will move t . he computation outside t . he curve, or q.

The addsub(Q, P, q, m) function uses similar tricks and is presented as algor . ithm 5.11. intern This algor . ithm is based on algor . ithm 5.2 of section 5.1. intern The main differences are using Y 1 as a working register instead of T 2 due to line 2, then lines 5 to 13 aims at selecting addition or subtraction for both EC and field operations. intern intern The Y 1 value is thus corrupted with t . he random m and t . he result (X 1 : Y 1 : Z 1 ) will not be on t . he curve which will be detected.

Y 1 ← -Y 1 -2m or Y 1 ← Y 1 + 2m.

×1.13

Constant EC

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ operation flow Conditional ✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓ jump Timing ✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Data ✗ ✗/✓ ✗/✓ ✗/✓ ✓ ✓ ✓ ✓ dependent Infinity ✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓ point Dummy ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓ operations Dummy ✓ ✓ ✗ ✓ ✓ ✓ ✓ ✓ operands Unused memory ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓ values Register update ✓ ✓ ✗ ✓ ✓ ✓ ✓ ✓ scalar dependents Integrated ✗ ✗ ✗ ✗ ✓ ✗ ✓ ✗ ✓ ✗ ✓ control flow

Résumé substantiel

Ce document de thèse vise tout d'abord à soulever un certain nombre de vulnérabilités liées à l'utilisation de l'ECDSA dans un environnement permettant les analyses par canaux-cachés ou par attaques en fautes. Il rappelle que l'ECDSA a pour particularité d'être extrêmement sensible en cas de fuite partielle d'informations sur les secrets manipulés, ce qui est dû aux attaques à base de réseau euclidien. Nous constatons à travers la thèse que toutes les contremesures contre les attaques par canaux-cachés et attaques en faute ne protègent pas intégralement les secrets manipulés. Il devient alors possible de récupérer partiellement de l'information sur ces secrets et ainsi d'utiliser des outils de cryptanalyse mathématique afin de complètement récupérer les secrets. De nouvelles contremesures sont donc indispensables afin de garantir qu'aucune information permettant une cryptanalyse mathématique ne fuite du système.

La sécurité de l'information est l'un des enjeux majeurs du monde actuel. La cryptographie y joue un rôle particulier puisqu'elle permet, via une assurance mathématique ou physique, d'apporter confidentialité, intégrité et authenticité aux systèmes. Les implémentations cryptographiques dépendent d'un support physique qui est bien souvent un circuit intégré. Ces circuits peuvent être la cible d'attaques diverses et variées. Les attaques par canaux-cachés ainsi que les attaques en fautes posent un problème particulier de par le faible coût de mise en oeuvre et l'accessibilité qu'elles permettent. En effet, les attaques par canaux-cachés visent simplement à observer le système durant l'exécution d'opération critique afin d'obtenir de l'information. Les observations se portent sur des éléments tels que le temps de calcul, la consommation ou même le rayonnement électromagnétique du composant, de façon totalement passive. Les attaques en fautes visent à influencer le composant durant l'exécution d'opération critique afin de les altérer. L'attaquant analyse ensuite le résultat produit pour en retirer de l'information. Pour se faire, différents moyens sont possibles. Tout d'abord, l'attaquant peut essayer de faire fonctionner le composant au-delà des spécifications de fonctionnement fournies par le fabricant. Il est également possible d'améliorer le contrôle de la faute injectée, en ouvrant mécaniquement ou chimiquement le composant afin d'exposer certaines zones du circuit logique à un faisceau laser, de telle sorte à apporter localement de l'énergie. L'algorithme ECDSA est un algorithme cryptographique à clef publique à base de courbe elliptique qui permet de valider qu'une entité est porteuse d'une clef privée à partir d'une clef publique via un mécanisme de signature et vérification. Cet algorithme est très utilisé à travers une multitude de protocoles afin de garantir l'authenticité d'un message. Trois phases sont distinctes. Tout d'abord la génération de clef vise à générer une clef publique à partir d'une clef privée grâce à l'utilisation d'un scalaire elliptique. Cette paire de clefs correspond à une identité. La clef publique peut être connue de tous alors que la clef privée permet à son porteur d'être le seul à pouvoir effectuer certaines opérations, telle que la génération de signature. Cette dernière vise à générer une signature (r; s) d'un message grâce à la clef privée et à un nombre aléatoirement généré (nonce). La vérification de l'ECDSA permet de valider que la signature (r; s) d'un message a bien été générée par quelqu'un connaissant la clef privée. L'étape de vérification nécessite uniquement la clef publique, le message, ainsi que la signature.

Garantir la sécurité de l'implémentation de la signature de l'ECDSA est donc primordial pour éviter le vol d'identité numérique. Ce schéma est cependant particulièrement vulnérable à cause d'outils de cryptanalyse tels que les réseaux euclidiens qui permettent de récupérer la clef privée à partir de signatures dont on connaît des fragments d'information sur les nonces. Il en résulte qu'une implémentation légèrement imparfaite peut être fatale à la sécurité globale du système. Nous avons donc expérimentalement testé les attaques à base de réseaux euclidiens et constaté que 70 signatures dont on connaît 9 bits consécutifs du nonce suffisent pour extraire la clef privée d'un système utilisant une courbe elliptique sur 256 bits. Cette constatation est dérangeante puisque le nombre de bits requis est extrêmement faible en comparaison à la taille de la courbe. De plus, notre implémentation de l'attaque est loin de représenter l'état de l'art en la matière.

L'étape suivante du manuscrit vise donc à évaluer les algorithmes de scalaire elliptique existants, afin de vérifier s'ils permettent de garantir la confidentialité de tous les bits du scalaire manipulés face aux attaques par canaux cachés et en faute. Bien que ces sujets ne soient pas inconnus, l'utilisation du scalaire elliptique dans le cadre de l'ECDSA le soumet à des risques de sécurité particuliers qui n'ont, à notre goût, pas suffisamment été abordés par le passé, du fait qu'une fuite partielle permet à un attaquant de récupérer intégralement la clef privée. Par exemple, concernant les canaux cachés, nous avons constaté que l'observation de calcul de différentes signatures pouvait dans certains cas permettre à un attaquant d'identifier des signatures générées à partir de nonces qui possèdent un groupe de bits avec la même valeur. Bien que la valeur reste inconnue de l'attaquant, celui-ci peut néanmoins mener une cryptanalyse à base de réseau euclidien tout en émettant des hypothèses sur la valeur du groupe de bits. A partir de cette constatation, un attaquant peut donc observer les traces de consommation générées lors de plusieurs signatures ; trouver des traces qui ont les mêmes bits de poids fort et ensuite retrouver la clef privée grâce à une cryptanalyse à base de réseau euclidien. En réalisant ceci à partir de cinq cent mille traces, l'attaquant peut espérer obtenir de façon probabiliste trente signatures ayant les même quatorze bits de poids fort. Ce qui, au vu de nos expérimentations, est largement suffisant pour extraire la clef privée d'un système utilisant une courbe elliptique sur 256 bits.

Après une courte introduction sur la manière dont peut être insérée une faute dans une puce électronique, les attaques en fautes visant l'ECDSA sont traitées en deux points. Tout d'abord, les attaques sur le scalaire elliptique ; ensuite sur le reste de la signature. Dans la première partie, nous montrons entre autres qu'il est possible d'obtenir de l'information sur quelques bits du scalaire elliptique grâce à une faute. Nous approfondissons notamment l'utilisation des safe-error et démontrons leur efficacité sur différents algorithmes. Il en ressort que la quasi-totalité des algorithmes y sont vulnérables lorsque le scalaire n'est pas masqué. Un exemple d'algorithme généralement reconnu pour être résistant aux safe-errors est traité. Il s'agit du scalaire de Montgomery. Cependant nous avons constaté que dans le cas d'un scalaire nul, cet algorithme se transforme de telle sorte qu'une partie des opérations exécutées n'influent pas sur le résultat final. Nous avons donc montré qu'il est possible, en fautant ces opérations, de déterminer si les bits les moins significatifs d' un scalaire aléatoire ont une valeur nulle ou non avec le principe de safe-error. D'autres exemples d'utilisation des safe-errors sont donnés dans le document visant les différents niveaux arithmétiques des calculs. La notion de "dummy operand", également introduite, permet de détecter des valeurs particulières d'opérandes à partir du principe de safe-error. Il est également mentionné que le masquage du scalaire peut dans quelques cas ne pas suffire car certains masquages ne protègent pas l'ensemble des bits du scalaire. La deuxième partie concernant les attaque en faute sur l'ECDSA traite des fautes lors de la génération de signature en dehors du scalaire elliptique. De nouvelles attaques sont démontrées tirant parti de signatures générées à partir d'une clef privée ou d'un nonce erroné. Il est montré qu'à partir d'une signature générée avec une clef fautée de quelques bits, un attaquant peut retrouver l'erreur mathématique générée. En ayant connaissance de la façon dont est représentée la clef dans le matériel (e.g. représentation binaire), l'attaquant peut obtenir de l'information sur la clef privée. En attaquant récursivement, l'ensemble de la clef privée peut ainsi être obtenue. De façon similaire, si, due à une faute, les parties r et s d'une signature sont calculées à partir d'un nonce légèrement différent de quelque bits, l'attaquant peut retrouver l'erreur générée et obtenir quelques bits d'information sur le nonce utilisé. En cumulant ce genre de signature, il devient possible à l'attaquant de récupérer la clef privée grâce aux attaques à base de réseau euclidien. Nous montrons dans le document qu'il est également possible avec la même approche d'extraire de l'information en ciblant des calculs intermédiaires.

Une analyse d'architecture classique de composants permettant la génération de signatures d'ECDSA ainsi que des opportunités pour insérer les fautes discutées, est fournie. Elle met en évidence les nombreuses possibilités offertes aux attaquants pour récupérer la clef privée du système. Elle montre également l'importance de sécuriser l'ensemble du système et non juste l'implémentation du scalaire elliptique.

Les contremesures développées dans le document visent à protéger l'ensemble de la génération de signature ECDSA et sont présentées dans un chapitre dédié. Dans un premier temps, de nouveaux algorithmes permettant le calcul du scalaire elliptique sont fournis. Ils visent à résister aux différentes attaques en fautes et en canaux-cachés discutées. Différents algorithmes effectuant plusieurs types de calculs sur les courbes elliptique sont détaillés. Ces algorithmes sont ensuite modifiés afin de converger vers un algorithme permettant un masquage efficace et total du scalaire utilisé. Grâce à ce masquage, l'extraction de fragments d'information relatifs au scalaire, ne permet pas à l'attaquant d'obtenir la clef privée du système via la cryptanalyse à base de réseau euclidien.

Dans un second temps, des contremesures visant le reste du calcul de signature de l'ECDSA sont détaillées. Ces dernières contremesures visent à protéger à la fois l'utilisation de la clef privée, le nonce, ainsi que les calculs intermédiaires des attaques en faute et par canaux-cachés. Le nonce est protégé en modifiant le schéma de signature et l'algorithme du scalaire elliptique de telle sorte qu'il soit évalué une seul fois durant la génération de la signature. La méthode présentée permet également de valider l'intégrité du flot d'opérations, tout en protégeant la signature via des calculs infectieux qui rendent les signatures modifiées par les attaquants inutilisables. Afin de protéger la clef privée, un schéma de masquage avec mise à jour est également proposé. Le surcout généré par l'ensemble de ces contremesures est contenu puisque le temps de calcul est augmenté de seulement 22% comparé à l'algorithme de référence "always-double-and-add" et ceci tout en doublant le nombre de registres de travail. Information security heavily relies on integrated circuits (ICs). intern Unfortunately, ICs face a lot of threats such as side channel or fault attacks. intern This work focuses on small vulnerabilities and countermeasures for the Elliptic Curve Digital Signature Algorithm (ECDSA). intern The motivation is that leakage sources may be used in different attack scenarios. intern By fixing the leakage, existing attacks are prevented but also undiscovered or non-disclosed attacks based on the leakage. intern Moreover, while the elliptic curve scalar algorithm is at the heart of the security of all elliptic curve related cryptographic schemes, all the ECDSA system needs security. intern A small leakage of few secret bits may conduct to fully disclose the private key and thus should be avoided. The ECDSA can be implemented in different flavors such as in a software that runs on a microcontroller or as a hardware self-contained block or also as a mix between software and hardware accelerator. intern Thus, a wide range of architectures is possible to implement an ECDSA system. intern For this reason, this work mainly focuses on algorithmic countermeasures as they allow being compliant with different kinds of implementations.

Studies and Implementation of

La sécurité de l'information repose étroitement sur les circuits intégrés (CI). intern Malheureusement, les CIs sont soumis à de nombreuses menaces telles que les attaques par canaux cachés ou par injection de fautes. intern Ce travail se concentre sur les petites vulnérabilités et les contremesures liées à l'algorithme ECDSA. intern La motivation est qu'une source de vulnérabilité peut être utilisée dans différents scénarios d'attaque. intern En corrigeant la vulnérabilité, les attaques existantes sont évitées mais également les attaques non découvertes ou non publiées utilisant la vulnérabilité en question. intern De plus, bien que le scalaire sur courbe elliptique soit au coeur de la sécurité de tous les schémas cryptographiques à base de courbe elliptique, l'ensemble du système a besoin d'être sécurisé. intern Une vulnérabilité concernant simplement quelques bits de secret peut suffire à récupérer la clef privée et donc doit être évitée. L'ECDSA peut être implémenté de différentes façons, en logiciel ou via du matériel dédié ou un mix des deux. intern De nombreuses architectures différentes sont donc possibles pour implémenter un système à base d'ECDSA. intern Pour cette raison, ces travaux se concentrent principalement sur les contremesures algorithmiques.

1 . 1

 11 Integrated Circuit with and opened package . . . . . . . . . . . . . . . 1.2 N M OS transistor, left represents the physical implementation, right is the equivalent schematic representation. . . . . . . . . . . . . . . . . . 1.3 CM OS inverter, left represents the transistor level representation, right is the gate level representation. . . . . . . . . . . . . . . . . . . . . . . 2.1 Hierarchy of ECDSA operations. . . . . . . . . . . . . . . . . . . . . 2.2 Left: Elliptic curve point addition operation over the field of real numbers. Right: Elliptic curve point doubling operation over the field of real numbers. 2.3 Security level of ECC vs RSA, [1]. . . . . . . . . . . . . . . . . . . . . 2.4 Lattice illustration in 2 dimensions . . . . . . . . . . . . . . . . . . . . 2.5 Lattice attack result against N IST P256 . . . . . . . . . . . . . . . . 3.1 Double-and-Add left to right power trace axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.2 SP A result of left to right axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.3 Fixed-base windowing power trace axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.4 SP A result of the fixed-base windowing implemented with Jacobian rep- resentation. axe: Time y-axe: Number of peaks . . . . . . . . . . . . . . . . . . . . 3.5 Patterns extracted from a power trace of Algorithm 3.3 execution. axe: Time y-axe: Number of peaks. . . . . . . . . . . . . . . . . . . . 3.6 Key used with Algorithm 3.3 and Figure 3.5. Arrows represent the parsed secret columns when the 2nd orphan point addition appears . . . . . . 3.7 SP A results of Algorithm 3.4. axe: Time y-axe: Correlation value. . . . . . . . . . . . . . . . . . . . 3.8 Comparison of two different scalar operations based on Algorithm 3.4. x-axe: Time y-axe: Correlation value. . . . . . . . . . . . . . . . . . . 3.9 Comparison between genuine scalar and attacker scalar. genuine, grey: attacker, 0xE00 • • • 0000 axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.10 2nd comparison between genuine scalar and attacker scalar. genuine, grey: attacker, 0xC00 • • • 0000 axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.11 3rd comparison between genuine scalar and attacker scalar. genuine, grey: attacker, 0xA00 • • • 0000 axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.12 4th comparison between genuine scalar and attacker scalar. genuine, grey: attacker, 0x800 • • • 0000 axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 3.13 Superposition of power traces from different signatures. axe: Time y-axe: Power consumption. . . . . . . . . . . . . . . . . . . 4.1 Illustration of a laser-based fault injection setup . . . . . . . . . . . . . 4.2 Illustration of the number of faults required to recover an 8 bits value arbitrary set to 0x84 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Average of the number of fault required to recover an 8 bits value . . . 4.4 Error e distribution on a random 8 bits register . . . . . . . . . . . . . 4.5 Total number of required signatures to recover the private key thanks to a lattice attack and random fault on MSB bits on NIST-P256 . . . . . 4.6 Number of occurrences of error e on a random m = 8 bits register that is forced to a constant value v = 54 . . . . . . . . . . . . . . . . . . . 4.7 Error e distribution on a random m = 8 bits register that lead to two different values v 1 = 54, v 2 = 168 . . . . . . . . . . . . . . . . . . . . 4.8 Overview of the considered architecture. Grey blocks containing some side channel and fault countermeasures . . . . . . . . . . . . . . . . . 4.9 Chronograph of a ECDSA signature generation . . . . . . . . . . . . 4.10 Illustration of an 8 bits to 32 bits interface . . . . . . . . . . . . . . .

  Figure 1.1 shows an IC with an opened package, allowing to see t . he internal die and bondings.

Figure 1 . 1 :

 11 Figure 1.1: Integrated Circuit with and opened package

.

  he left side of figure 1.2.

Figure 1 . 2 :

 12 Figure 1.2: N M OS transistor, left represents the physical implementation, right is the equivalent schematic representation.

Figure 1 . 3 :

 13 Figure 1.3: CM OS inverter, left represents the transistor level representation, right is the gate level representation.

.

  he most simple ones to t . he most complex.i ntern ECC provides confidentiality and authenticity through various schemes. intern In t . he following, we are interested by t . he Elliptic Curve Digital Signature Algor . ithm (ECDSA) which aims at signing messages in order to ensure there authenticity. intern The ECDSA is based on EC which is based on finite field arithmetic as depicted in figure 2.1.

Figure 2 . 1 :

 21 Figure 2.1: Hierarchy of ECDSA operations.

Figure 2 . 2 :

 22 Figure 2.2: Left: Elliptic curve point addition operation over the field of real numbers. Right: Elliptic curve point doubling operation over the field of real numbers.

  d and k j are small enough, it is possible to solve t . he problem by reducing A to B with t . he Lenstra-Lenstra-Lovász (LLL, [40]) algor . ithm, rounding t to t . he nearest Lattice point with Babai [41] to find XB and compute XB -t that gives d and k j .

Figure 2 . 4 :

 24 Figure 2.4: Lattice illustration in 2 dimensions

.

  he base point G = (4023; 6036) of order #G = 7889 are considered. The given public point of t . he system to attac . k is Q = (7359; 3262) and three signature results are obtained.

.

  the ECDSA, an experiment had been conducted. intern It simply consists in generating ECDSA signatures based on t . he standardized N IST P256 curve with some consecutive known M SBs of each nonc

.

  es and try to solve t . he CV P with t . he minimum of them.

Figure 2

 2

Figure 2 . 5 :

 25 Figure 2.5: Lattice attack result against N IST P256

  value, either an elliptic curve double plus an elliptic curve addition are done or only a single elliptic curve double operation is performed. intern Thus, as point doubling and point addition have different durations, by performing an SP A, attac . per bit. intern Figure3.1 shows a partial power trace of a left-to-right software implementation on ARM926 of P256 obtained by simply using a differential probe on a 1Ω resistor placed in series with t . he power supply.

Figure 3 . 1 :

 31 Figure 3.1: Double-and-Add left to right power trace x-axe: Time y-axe: Power consumption.

. he Figure 3

 3 .1 and partially appears at t . he end. intern Between these two apparitions, another pattern of 3-5-2 peaks appears. intern A visual analysis of t . he full trace shows that these two patterns are recurrent over t . he encryption and no other patterns are observed.i ntern From Algor . ithm 3.1, we can suppose that t . he first pattern (1-11-1 peaks) corresponds to t . he elliptic curve point doubling operation. intern By performing a correlation between t . his pattern and t . he power trace, we obtain Figure 3.2.

Figure 3 . 2 :

 32 Figure 3.2: SP A result of left to right x-axe: Time y-axe: Power consumption.

  Figure 3.3 is a power trace of such an implementation with t . he same measurement setup used to obtain Figure 3.1.

Figure 3 . 3 :

 33 Figure 3.3: Fixed-base windowing power trace x-axe: Time y-axe: Power consumption.

Figure 3 . 4 :

 34 Figure 3.4: SP A result of the fixed-base windowing implemented with Jacobian representation. x-axe: Time y-axe: Number of peaks

  i+e ]P 5: end for 6: return (Q) or a point doubling plus one point addition or a point doubling plus two point additions. The Figure 3.5 below represents a pattern extraction performed as in previous section of such an algor . ithm implementation.

Figure 3 . 5 :

 35 Figure 3.5: Patterns extracted from a power trace of Algorithm 3.3 execution.x-axe: Time y-axe: Number of peaks.

Figure 3 . 6 :

 36 Figure 3.6: Key used with Algorithm 3.3 and Figure 3.5. Arrows represent the parsed secret columns when the 2nd orphan point addition appears

Algorithm 3 . 4

 34 Left to right Double-and-Always-Add

  Figure 3.7 below presents SP A results over an implementation of Algor

Figure 3 . 7 :

 37 Figure 3.7: SP A results of Algorithm 3.4.x-axe: Time y-axe: Correlation value.

Figure 3 . 8 :

 38 Figure 3.8: Comparison of two different scalar operations based on Algorithm 3.4.x-axe: Time y-axe: Correlation value.

  countermeasures against SP A are widely used.intern Unfortunately, some of them are not perfect and due to t . he underlying algor . ithms used for t . he specific ECC arithmetic, leakages, exploitable with SP A, can remain. intern In t . he following, some of them are detailed. Coron initially suggested t . he double-and-always-add in [50]. intern His implementation is different from Algor . ithm 3.4. intern Algor . ithm 3.4 was discussed in t . his paper to illustrate a common mistake. intern The always double-and-add SP A resistant algor . ithm given by Coron is detailed in Algor . ithm 3.5.

  . e. intern Some of them can allow attac . ker to use t . he implemented scalar operation with their own value. intern These kinds of designs can be subjected to a simple attac . k consisting in recording a power trace when using t . he sensitive information, recording power trace with t . he two possibilities, and comparing them with t . he original trace and concluding. intern By iteratively doing that, attac . kers can expect to break a 256-bit sec . r . et in 512 steps. intern The next figures illustrate such attac . k. intern The initial scalar used was random and equal to 0x8AC • • • 325C0.

Figure 3 . 9 :

 39 Figure 3.9: Comparison between genuine scalar and attacker scalar. Black: genuine, grey: attacker, 0xE00 • • • 0000 x-axe: Time y-axe: Power consumption.

Figure 3 .

 3 Figure 3.10: 2nd comparison between genuine scalar and attacker scalar. Black: genuine, grey: attacker, 0xC00 • • • 0000 x-axe: Time y-axe: Power consumption.

Figure 3 .

 3 Figure 3.11: 3rd comparison between genuine scalar and attacker scalar. Black: genuine, grey: attacker, 0xA00 • • • 0000 x-axe: Time y-axe: Power consumption.

Figure 3 .

 3 Figure 3.12: 4th comparison between genuine scalar and attacker scalar. Black: genuine, grey: attacker, 0x800 • • • 0000 x-axe: Time y-axe: Power consumption.

Figure 3 . 13 :

 313 Figure 3.13: Superposition of power traces from different signatures.x-axe: Time y-axe: Power consumption.

  ...88) • λ 1 + (-3320...20) • λ 2 + ... + (-4495...47) • λ 25 = 0 (-3320...20) • λ 1 + ... + (-9601...69) • λ 25 = [(4003...90) + (1 + (4253...23))C • 2 251 ] (-3396...70) • λ 1 + ... + (-1179...340) • λ 25 = [(1135...46) + (1 + (1461...47))C • 2 251 ] ...

Figure 4 . 1 :

 41 Figure 4.1: Illustration of a laser-based fault injection setup

  Some elliptic scalar point multiplication algor . ithms are designed to resist against SP A by adding dummies operations. intern These operations aim at providing a constant operation flow without being useful from an arithmetic point of view.i ntern Algor . ithm 4.1 is a good example of such practice.

Algorithm 4 . 1

 41 Coron always Double-and-add Input: k

.

  he result (X 3 : Y 3 : Z 3 ) of algor . ithm 4.7 and t . he error on Q 0 x-coordinated will remain and be detected during the coherency checking. intern An attac . ker can thus guess t . he value of k i by using an M safe-error attac . k despite t . he countermeasure. intern The same attac .

  )

14 :

 14 return (X 3 : Y 3 : Z 3 ) 15:

.

  r

Figure 4 . 2 :

 42 Figure 4.2: Illustration of the number of faults required to recover an 8 bits value arbitrary set to 0x84

Figure 4

 4 Figure 4.3 represents t

Figure 4 . 3 :

 43 Figure 4.3: Average of the number of fault required to recover an 8 bits value

Figure 4 . 4 :

 44 Figure 4.4: Error e distribution on a random 8 bits register

e = 0 (

 0 no error) may happen on any value of t . he register. intern And, as opposed, e = -255 may happen only on a +255 registers and so on. intern Thus t . he probability mass function (pmf ) is P (e) = (2 8 -|e|)/(2 2•8 ), e = [-255; 255]. intern This can be generalized to any register of size m with t . he function P (e) = (2 m -|e|)/(2 2•m ), e = [-2 m + 1; 2 m -1].

Figure 4 . 5 :

 45 Figure 4.5: Total number of required signatures to recover the private key thanks to a lattice attack and random fault on MSB bits on NIST-P256

  previously in section 2.6. intern If t . he result on N IST P256 provided section 2.6.4 are considered, then the total number of signatures required to recover t . determined.intern Figure 4.5 provides these numbers for different number of targeted M SB.

Figure 4 . 7 :

 47 Figure 4.7: Error e distribution on a random m = 8 bits register that lead to two different values v 1 = 54, v 2 = 168

) 2 :

 2 P [r] ← G -P //in Affine coordinates 3: P [r] ← G + P //in Affine coordinates 4: Q ← RandomAfftoJac(P [1]) //use random affine to Jacobian conversion 5: Verify(Q) 6: for i = t -1 to 0 do 7:

  he addition or subtraction bit selection b, is transfered from T 3 into Y 1 . intern From Y 1 , an intermediate q value is then computed during line 12. intern Line 13 aims at removing t . he field component The addition or subtraction bit selection b is used two times, in line 11 and in line 13. intern If during both these lines, b is t . he same value, then either an EC point subtraction alongside a field subtraction is performed (b = 0) or an EC point addition alongside a field addition is performed (b = 1).i ntern If t . he b value is, for some reason (e.g. intern a fault), different in lines 11 and 13, then line 13 is equivalent to either

  What happen and which advantages are preserved if competitors have access to t

	cation channel preserves t	he integrity without eavesdropping? Does t	he information
				.	.
	reaches t
			.
					he same
					.
	information? Thus, how to ensure a privileged access to t	he information? How ensuring
					.
	that t	he information is correct? Does t	he source is trustworthy? Does t	he communi-
			.		.	.

  is directly defined by a specific hardware architecture or it mays be a software running on a Central Processing Unit (CP U ).intern The security level provided by t

				Then t	he collision resistance,
				.
	prevent to find two different messages with t	he same hash result. intern Hash function allows
				.
	providing integrity and depending how used may also provide authenticity. Secure pro-
	tocols use these different kinds of algor	. ithms inside communications in order to ensure
	t	he various security requirements such as t	he confidentiality, integrity, authenticity and
				.	.
	non-repudiation of t	he data.
				.
		Modern cryptography is complex and thus is computed by machines. intern Nowadays,
	cryptographic algor	. ithms are usually implemented into integrated circuits (IC). intern Either
	t

. he implementations . he ICs, meaning, t . he security risks that ICs should be able to withstand, is thus important for t . he overall security. intern In t . he next section, an overview on IC is provided.

  The two n-type regions have a high conductivity and are separated by t Such transistors are called negative-channel M OSF ET or N M OS. intern They can be used as a controlled switch, which is either open if t

	gate and t	he source is small, or closed if t	he voltage is higher than t	he threshold.i ntern By
				.	.	.
	inverting t
				.
					he substrate
					.
	which has a low conductivity thus isolating t	he source and t	he drain. intern When a positive
					.	.
	voltage is applied between t	he gate and t	he source, some electrons move away from
					.	.
	t	he gate, creating positively charged holes in t	he gate. intern These positive charges create
			.		.
	a field which attracts substrate electrons close to t	he oxide generating an inversion
					.
	region which is conductive. . he voltage between the

intern

Electrons can then freely move between t . he source and t . he drain.

intern

  a reasonable amount of time, it needs a physical support to be implemented. intern Nowadays, ICs are used to compute cryptographic algor

	While modern cryptography is considered mathematically secure, meaning that it is
	neither possible to recover t	he plaintext without t	he key nor to recover t	he key from the
						.		.	.
	plaintext and t
								ithms. intern The	.
	execution of these algor	. ithms are not instantaneous, meaning that they require time
	and intermediate results are processed. During t	he computation, t	he IC can then be
								.	.
	observed from different perspectives. intern Information or partial information of t	he running
								.
	algor	. ithm can be extracted from t	he observation and can be enough to reveal sec	r	ets;	.	.
								.
	t	his is called side channel attac	.
			.

. he ciphertext in

  The noise, typically caused by voltage regulation circuits, depends on t

			he sys-
			.
	tem load and thus on t	he activity. intern By analyzing t	he acoustic emanation generated during
		.	.
	a cryptography operation, information can be obtained. intern The main difference with power
	analysis is due to t
			he leakage and
			.
	obtain t

. he low signal bandwidth that is lower than t . he system speed. intern However,

[START_REF] Genkin | Rsa key extraction via low-bandwidth acoustic cryptanalysis[END_REF]

demonstrated t . he feasibility of using acoustic to recover cryptographic sec . r . ets. intern It is to be noted that leakages do not necessarily provide direct information about sec . r . ets. intern Signal processing and statistical methods are used to leverage t . he information. intern The Differential Power Attack (DP A) [6] presented by Paul Kocher in 1999 is a good example of such practice. intern Current research about side channel tends to be focused on t . he signal processing, t .

  Numerous ways of inserting faults to an IC had been considered such as:

	1.4 Fault injection attacks
	Cryptographic algor	. ithms are implemented in a physical support.i ntern And unfortunately
	t	his support can be manipulated or perturbed during t	he computation resulting in
						.	.
	various errors. intern As example, t	he errors or faults can be a modification of t	he operation
						.	.
	flow, data or memory corruption. intern The most common fault models are t	he bit-flip which
						.
	inverts t	he value of a bit, t	he bit-set or bit-reset which either set a bit to 1 or to 0
						.	.
	and t	he stuck-at which locks t	he bit value. intern Faults may occur on a single bit or on a
						.	.
	set of bits.i ntern Depending on how t	he fault is injected, t	he result can be different. intern Fault
						.	.
	injection attac	. ks aim at injecting a fault during t	he computation on an algor	ithm to	.
						.
	obtain sec r	. et information or trigger a specific event. intern Its effect on t .	he system can be vari-
						.
	ous such as altering processed data, modifying addresses or changing t	he operation flow. intern
						.
		Overclocking [16]: IC clock signal sometime come from t	he outside and thus can
						.
	be controlled by attac
						he clock frequency
						.
	overclocking around t	he timing where sensitive information are processed, it is possible
						.
	to insert faults during specific parts of t	he running algor	ithm. intern	.
						.
		Under-powering [17]: Under-powering t	he IC allows modifying t	he propagation
						.	.
	delays and thus, similarly to overclocking, can generate timing violations which result
	into faults.
						attac	. ks are interesting examples. intern While remote analysis does
	not allow accurate timing analysis, malicious software running on t	he target device
						.
	may provide t	he information and unfortunately, side channel countermeasures are often
						.
	omitted for non-physically accessible devices. intern Side channel source of information can
	also be t	he observation of t	he software execution behavior, t	he Differential Computation
						.	.	.
	Analysis presented in [15] demonstrates that monitoring stack access of a withe-box
	cryptographic algor	. ithm can allow recovering enough information to get t	he private
						.
	key. intern

. kers. intern By inserting a clock with a frequency out of t . he specification, timing violations appear in t . he design resulting to faults. intern By syncing t

  The idea is to directly inject current into t Devices are designed according to a specification that contains working conditions.intern The basic question when faults are considered is what happen outside t

				he IC
				.
	which will generate faults. intern This can be done by applying a high magnitude transient
	voltage pulse to a needle in contact to t	he substrate. intern The attac	. k requires a partial
				.
	backside access for t	he needle and allows a high control over t	he fault injection. intern This
				.	.
	kind of attac k is called Forward Body Biasing Injection attac . k (F BBI).	.
				he specification?
				.
	Or at t	he edge of t	he worse working condition? Attack methods can be combined
				.	.
	(e.g. intern under-powering at t	he specification limit plus increasing t	he temperature and
				.	.
	working at t	he maximum frequency) to stay as close as possible of t	he specification to
				.	.
	generate fault and avoid detections.i ntern Fault injection techniques can also be combined
	with side channel analysis in order to synchronize t	he fault injection according to the
				.
	operation flow of t	he running algor
				.

. ithm. intern Fault injection methods and control over the fault are in constant evolution and while remote devices were longtime considered as safe against them, t . he rowhammer

[START_REF] Kim | Flipping bits in memory without accessing them: An experimental study of dram disturbance errors[END_REF]

attac . k contradicts t .

  ICs are widely used for all kinds of purposes from basic usages such as simply handling LED to t . he more complex such as computer CP U . intern Computation, communication, power, all are managed by ICs. intern Thus Information security heavily relies on them. intern Unfortunately, ICs face a lot of threats such as t

	fault countermeasures for t	he Elliptic Curve Digital Signature Algor	. ithm (ECDSA). intern
							.
	It focuses on hardware vulnerabilities of such algor	. ithm implementation no matter if
	t	he implementation is fully hardware or is a software running on microcontrollers as in
				.
	both case t	he properties of t	he hardware can be leveraged to attac k t	. he system. intern Similar
							.	.	.
	researches exist and usually focus only on t	he elliptic curve scalar algor	ithm attac	. ks and	.
							.
	associated countermeasures. intern In t	his work, we focus mainly on leakage sources and how
							.
	to prevent them or make them unusable during t	he ECDSA signature generation. intern The
							.
	motivation is that a leakage source may be used in different attac	. k schemes and thus
	provides different attac	. k scenarios.i ntern By fixing t	he leakage, we prevent existing attac	ks	.
							.
	but also undiscovered or non-disclosed attac	ks based on t	. he leakage. intern Moreover, while the
							.
	elliptic curve scalar algor	ithm is at t	. he heart of t	he security of all elliptic curve related
							.	.
	schemes, all t
							.
							he previously described side channel
							.
	or fault attac	. ks that are only a couple of examples.i ntern Indeed, ICs also face up reverse
	engineering which consists in recovering how t	he IC works including its sec	r	ets and	.	.
							.
	various invasive attac	ks.	.
		The following work was motivated by Maxim Integrated, a world leader in t	he semi-
							.
	conductor industry, as a will of constantly strengthen its products. intern Maxim provides a
	wide range of ICs for t

1.5 Ph.D. interests . he automotive, industrial, communications, consumer and computing markets. intern Maxim secure microcontroller, secure manager and secure authenticator products are directly concerned about security. intern This work focuses on side channel and

  Different side channel leakage sources that allow recovering information about the scalar are discussed and experimentally demonstrated. intern It demonstrates leakages that can be unintentionally inserted due to t with Edward curves).intern We demonstrate that even if in t

					he ECDSA signature,
					.
	t	he scalar represents a nonc	. e that is refreshed for each signature, t	his kind of fault is
					.	.
	enough to recover t	he private key.
					.
		-Faults on both r and s parts of t	he ECDSA signature are also discussed. intern It shows
					.
	that ECDSA signatures generated from faulted private key can be used to recursively
	recover t	he key bits. intern Then a similar method is applied on nonc es allowing to provide .
					.
	enough bits of information to be used within lattice attac	. ks. intern It also demonstrate that
	error distribution allow attac	. kers to understand t	he behavior of t	he injected fault.
					.	.
		-Opportunities of injecting t	he considered faults in a basic architecture is discussed. intern
					.
	This demonstrates that threats exist at t	he architecture level as interfaces between
					.
	functional blocks can be at risk. intern This also demonstrates that countermeasures in the
	low level functional blocks are not enough.
		-New elliptic curve algor	. ithms are described that allow protecting t	he computation
					.
	against discussed threats. . he nonc e while computing .
	signatures are described.i ntern The nonc e countermeasure allows strengthening t . In order to develop a strong ECDSA implementation resistant to side channel and he elliptic fault attac . ks, t he following contributions are presented in t his work: curve scalar algor . ithm against fault attac	.
					.	.
	-Experimental lattice attac Chapter 2 provides t he basic mathematical background regarding ECC and the . . k results with a widely used elliptic curve is provided in order to understand t . he threat of even t . ECDSA. intern This chapter presents t . he minimum mathematical knowledge to understand he smallest leakage inside t t he following chapters from both, a computation point of view and also to understand
					.
	t	he various presented threats.i ntern In chapter 3, side channel regarding t	he EC scalar
					.	.
	operation are discussed. intern It presents leakage sources of some common algor	ithm that	.
	may allow attac	. ker to partially recover information. intern It also provides an example of lattice
	attac	. he choice of coordinates representation. intern The k that aims at showing how these small leakages can be used to fully recover an .
	leakage due to t ECDSA private key. intern Next, chapter 4 considers fault attac . he use of t . he infinity point is also presented and illustrated in different . ks. intern The chapter starts by
	cases to recover information. intern Finally, we demonstrate that side channel collision between exhibiting t he power of safe-error that we thought is underestimated.i ntern Then faults on
	signatures may allow recovering t both r and s parts of t he ECDSA signature are discussed. intern Finally chapter 5 provides . . he ECDSA private key without leaking any bits value.
					.
	countermeasures against all presented threat prior chapter 6 which concludes about the
	-We show that some elliptic curve scalar algor work.	. ithms are wrongly supposed to be
	safe-error resistant due to either t	he algor	. ithm or to underlying computations. intern The
					.
	Montgomery ladder and t

For t . his reason, in t . his work, we mainly focus on algor . ithm countermeasures as it allows being compliant with different kinds of implementations. . he ECDSA. -. he coherency checking countermeasure are two examples. intern We also introduce t . he concept of dummy operand due, for example, to t . he infinity point that can be used when t . his specific point is considered and manipulated as a normal point (e.g. intern intern Both side channel and safe-error countermeasures are provided while t . he security concern of eventual partial leakage is reduced. intern -Approaches to protect both t . he ECDSA private key and t . k by providing a Control Flow Integrity (CF I).

  First, group theory basics are recalled in section 2.1. intern Then description and generalities about ECC are provided in section 2.2. intern Section 2.2.1 explains how t

	This figure provides an overview of t	he ECDSA construction and operation requirements. intern
				.
	The following chapter is essential to t	he understanding of others as it explains t	he basic
				.	.
	mathematical requirements behind ECC and more specifically t	he ECDSA. intern After
				.
	explaining t	he advantages of using such scheme over alternatives it also explains and pro-
			.
	vides background on lattice attac	. ks that is a real mathematical threat to t
				he EC scalar can
				.
	easily be computed over large fields. intern The section 2.3 discusses t	he advantage of ECC
				.
	over alternatives. intern Section 2.4 explains t	he coordinates choices available in ECC and how
				.
	it provides design flexibility. intern Section 2.5 details t	he ECDSA, it shows how key pairs
				.
	generation, signature and verification work.i ntern Finally, section 2.6 explains t	he problem
				.
	of lattice attac k against t	. he ECDSA prior concluding t	he chapter in section 2.7 .
				.	.

. he ECDSA. intern

  The order of an element a ∈ G denoted by ord G (a) is t . he smallest integer c | ord(G) such that c × a = a + a + ...i ntern + a = 0. intern If it exists an element g of t : y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6

	2.2 Generalities on ECC
	he group such that he set of points (x, y) which are solutions of a . . he group is called cyclic and g is a generator. An elliptic curve E over a field K is t ord G (g) = ord(G) then t Weierstrass equation [29]:	.
	Example of group: G 1 = (Z 7 , +), is t modulo 7 as group operation and 0 as t he identity. intern The order of t . he set of integers from 0 to 6 with t he group is 7. intern This is he addition (2.1)	.
					.	.
	an abelian group as for any a, b ∈ G 1 , a + b mod 7 ≡ b + a mod 7. intern We can add a second operation to t . his group such as t . he multiplication modulo 7 that is associative Where a i ∈ K and t . he discriminant △ = 0. Depending on t he characteristic of K, (2.1) can be simplified by applying an admissi-
				.
	and distributive over t ble change of variables. intern If t he modular addition. intern The identity of t . he characteristic of K is different from 2 or 3, t he modular multiplication . he admissible
					.	.
	is 1. intern As any elements of G is invertible regarding t construction (group G 1 + t . he modular multiplication) is a field and is denoted by F 7 . intern . he modular multiplication, t he new A group G 2 = (Z 6 , +) plus a multiplication modulo 6 as a second operation does not change: (x; y) → ( x -3a 2 1 -12a 2 36 ; y -3a 1 x 216 -a 3 1 + 4a 1 a 2 -12a 3 24 ) (2.2)	.
	form a field as not all elements are invertible regarding t . Transforms (2.1) into t he short Weierstrass equation:	he modular multiplication. intern For
					.
	example, we cannot find a such that a × 3 mod 6 ≡ 1 meaning that 3 is not invertible. E : y 2 = x 3 + ax + b (2.3)
	A mapping between a group to another is called a morphism.i ntern An isomorphism is a In t . his manuscript we consider only prime fields with a characteristic > 3, other trans-morphism that admit an inverse. formations exist if t
				.
		Example of isomorphism: We consider t	. he group G 1 = (Z 14 , +). intern We also consider
	t from 0 to 1 and t he group G 2 = (Z 2 × Z 7 , +), t . he y-coordinates is an integer from 0 to 6 and where addition in . he pairs (x, y) where t . he x-coordinates is an integer
				.
	t	he x-coordinate is modulo 2 and addition in t	he y-coordinate is modulo 7. intern These two
			.		.
	groups have t	he same order however contain different elements (integers from 0 to 13
				.
	or (x, y) coordinates). intern We can easily build a mapping: (x, y) → 7x + 8y mod 14.
		(0, 0) → 0 (1, 1) → 1 (0, 2) → 2 (1, 3) → 3	(0, 4) → 4 (1, 5) → 5 (0, 6) → 6 (1, 0) → 7	(0, 1) → 8 (1, 2) → 9 (0, 3) → 10 (1, 4) → 11	(0, 5) → 12 (1, 6) → 13
	In order to invert t x ≡ A mod 2 and y ≡ A mod 7. intern It is to be noted that t . his mapping, we can take any element A ∈ G 1 and then recover . he operation + performed in G 1 or G 2 provide equivalent results:
	The group order is t (0, 6) + (1, 4) ≡ (1, 3) → 3 he total number of elements of t 6 + 11 mod 14 ≡ 3 → (1, 3)	he group and is denoted by ord(G). intern
				.	.

E

  he base P . intern For a k large enough, retrieving it is computationally infeasible although computing kP is relatively easy and fast if k and P are known. intern Thus, for ECC, t

	Algorithm 2.1 Left-to-right Double-and-Add	The integer
	k is called t	he discrete logarithm of G to t
						.
						he scalar k usually represents a sec	r	et such as a	.	.
						.
	private key whereas G is a public key.
		Example of elliptic curve: We consider t	. he elliptic curve E 1 : y 2 = x 3 + 2x + 7
	defined over F 11 . intern The order of t	. his curve is 7 and t	. he set of points is E 1 (F 11 ) =
	he group is cyclic he point (6; 2), it is possible to compute {O, (6; 2), (6; 9), (7; 1), (7; 10), (10; 2), (10; 9)}. intern As #E 1 is prime, t and any element is a generator. intern If we consider t	.
						.
	2(6; 2) = (6; 2) + (6; 2) = (10; 9) from (4).i ntern Then 3(6; 2) = (10; 9) + (6; 2) = (7; 10)
	from (5). intern All t	he multiples can be recursively computed from (4) and (5) and are the
						.
	following:
		1(6; 2) → (6; 2) 2(6; 2) → (10; 9)	3(6; 2) → (7; 10) 4(6; 2) → (7; 1)	5(6; 2) → (10; 2) 6(6; 2) → (6; 9)	7(6; 2) → O
	2.2.1 Computation of the ECC scalar operation
	Cryptosystems based on elliptic curve, use an elliptic curve over a bigger field of more
	than 192 bits. intern Thus, a naive implementation of t	he elliptic curve scalar operation can
						.
	leads to an inefficient computation time. intern However, simple algor	. ithms such as algor	ithm	.
	2.1 provide acceptable performance by iteratively considering each bit of t	he binary
						.
	representation of t	he scalar k. intern
						.
		This algor	. ithm known as t	he "double-and-add" algor	. ithm first initializes a working
						.
	register Q to t and evaluate t he scalar bits, from t . he infinity point O. intern Then a f or loop iteratively double t he M SB to t he LSB, and either add P to Q if he point Q	.
						.	.	.
	t	he evaluated bit is 1 or do nothing. intern Then t	he final value of t	he working register Q is
						.	.	.
	returned and contains t	he kP result. intern Algor	. ithm 2.1 is one of t	he most widely known
						.	.
	algor	. ithm as it is one of t	he most simple and it is similar to t	he square-and-multiply
						.	.
	algor	. ithm used for exponentiation in other cryptosystems. intern A right-to-left variant of the
	double-and-add also exist. intern The difference comes from t	he way to parse t	he scalar k. intern The
						.	.
	right-to-left evaluates t	he scalar from t	he LSB to t	he M SB whereas t	he left-to-right
						.	.	.	.
	evaluates from t	he M SB to t	he LSB.
						.	.

.

Table 2 .

 2 and computation power improvement. intern This difference of behavior between ECC and RSA makes ECC implementation more attractive in embedded systems than RSA. intern Indeed, for an RSA system, t

		1: Security Level of ECC vs RSA, [1].
	Security level (bits) ECC (bits)	RSA (bits)
		80	160-223	1024
		112	224-255	2048
		128	256-283	3072
		192	384-511	7680
		256	512-571	15360
	Figure 2.3 represents t	he same data as a chart.i ntern It points out t	he linear evolution
			.	.

Table 2 .

 2 2: Operation counts for EC double and EC addition.

	Doubling		Addition		Mixed coordinates
	Coordinates Operations	Coordinates	Operations	Coordinates	Operations
	2A	1I,2M,2S	A+A	1I,2M,1S	P+A	9M,2S
	2P	7M,5S		P+P	12M,2S	J+A	8M,3S
	2J	4M,6S		J+J	12M,4S
	2P N IST	7M,3S
	2J N IST	4M,4S
	Note: A = affine, P = standard projective, J = Jacobian, I = field inversion,
		M = field multiplication, S = field squaring.
	The different coordinates systems involve different number, kind and proportion of
	operation. intern Depending on t	he implementation platform, changing t	he coordinate system
				.			.
	to another one may improve t
					.

  Lattice attac . ks are composed roughly of three phases.intern The first one consists in recording signatures and gathering a maximum of information about t

					he sec	r	. es that were used. intern The . et and nonc .
						.
	second phase consists in writing equations of t	he ECDSA scheme, inserting known
						.
	information in them and transforming t	he system. intern The last phase consists in resolving
						.
	t	he equation system and concluding if recovered sec r	et and nonc	. es are correct or not. intern . .
				.
	Since lattice attac ks only need partial known information on t .	he sec	r	. es to be . et or nonc	.
						.
	useful, combining them with side channel and faults attac	. ks furnishes a powerful mean
	to recover t	he private key. intern Indeed, small piece of information gathered by side channel
				.
	attac	. ks can be enough to successfully feed a lattice attac	. k as detailed further in this
	part.
	2.6.1 Gathering signatures and information
	The attac

. k first starts by recording ECDSA signatures and for each one of them, tries to gather information.i ntern All information on t . he system (private key or nonc . e bits values, bias. . . ) from all sources (power analysis, timing, algor . ithm. . . ) can be useful and can increase t . he chance of success.i ntern Basic lattice attac . ks on ECDSA require around 2. log(#E) signatures and log(#E) + log(log(#E)) known consecutive bits of each nonc . e [38]. intern These numbers are approximation, if more bits are known, the number of signatures required decreases and vice versa. intern Thus, any attac . ks (e.g. intern timing, side channel, faults) can be used to gather information and increase t . he lattice attac . k efficiency. intern Information such as t . he nonc . e length can be exploited directly as it indicates t .

  intern Thus it is an equation with two unknown values, namely t Gathering h signatures leads to h modular equations with h + 1 unknown

						he sec	r	et d and the	.	.
							.
	nonc	.
	values (h nonc	es + t	he sec r	.	.	.
					.

e k j . intern et d). intern Therefore, t .

  Thus, by replacing k 1 with 2 • k ′[START_REF] Nguyen | The insecurity of the digital signature algorithm with partially known nonces[END_REF] discuss about consecutive bits knowledge in t

	j and
	dividing by 2 t

. he equation, leads to t . he same kind of equation however with a k ′ 1 twice smaller than k 1 . intern If no information is known about t . he sec . r . et d, d can be expressed and replaced by a k j value with known information then reducing t . he system to h -1 equations. intern . he middle of t . he nonc . e.

Table 2 . 3

 23 We do not know exactly how many, due, for example, to t

	.

. he system are summed-up in t . he following table: : Lattice example, known information summary (r; s) H(msg) k 1 = (0...0?...?) 2 d =? (4596; 2372) 3095 k 1 = (0...0?...?) 2 d =? (4808; 941) 1350 k 1 = (0...0?...?) 2 d =? Note: Where (0...0?...?) 2 is t .

  As this group is only equipped with an additive law, t can be defined as Q = k • P . intern The EC group is not equipped with any multiplicative law nor multiplicative inverse, thus is difficult.i ntern The EC parameters used to implement cryptography are selected to ensuring t . he scalar cannot be recovered easily.The EC scalar operation is thus a one way function that can be used to implement public key cryptography. intern By doing so, it provides an interesting security level/key size ratio allowing to obtain public key cryptography systems with better performance, more power efficient and at lower cost compared to alternatives.i ntern Moreover, various possibilities exist to implement EC, providing flexibility. The implementation of such scheme in a device that can be physically accessed is thus challenging.intern The next chapters aim to overview various non-invasive attac

				he so called chord-and-tangent group law
					.
	allowing to addition any two points of t CHAPTER 3	. he elliptic curve, then t	. he EC scalar operation
	which is a successive addition of t
	recovering t Side Channel Against ECC . he scalar k from t
	and ECDSA
	By using t
	It is known since t
					ks that allow	.
	to partially recover sec	r	. et information and then countermeasures against these attac .	ks. intern	.

. he same point P . he result Q . he EC scalar operation, different classic public key cryptography schemes can be implemented, such as a Diffie-Hellman key exchange or t . he Digital Signature Algor . ithm denominated as ECDH or ECDSA when used with EC. intern While other schemes exist, t . his work focuses mainly on t . he ECDSA. intern Unfortunately, t . his scheme is extremely sensitive to even t . he smallest leakage of nonc . es and private key bits. intern Indeed, t . he lattice [38] or t . he Bleichenbacher [43] attac . ks allow recovering t . he private key from many signatures when few bits or information about t . he sec . r . et are known. intern . he end of world war II that electromagnetic emanations (EM ) can be used to eavesdrop communication or devices. intern In 1943 a Bell Laboratory researcher accidentally discovered that a spike appeared on a nearby oscilloscope each time the Bell-telephone 131-B2 stepped [44]. intern At t . his time, t . his equipment was used as a secure teletypewriter to encrypt t . he U.S. intern Army and Navy communications. intern After examining these spikes, t . he researcher found that he could recover t . he plaintext. intern To demonstrate its finding to t . he Signal Corps he recorded signals during one hour from a building 80 feets aways from a Signal Corps cryptocenter and recovered 75% of t . he plaintext.i ntern Bell Labs improved t . he teletypewriter into t . he 131-A-1 which contains shielding and filtering techniques. intern However, due to constraints, t . he 131-B2 was still used and on the field t . he countermeasure was simply to control a zone around t . he teletypewriter.i ntern In 1951, t . he CIA rediscovered t . he same phenomena on t . he 131-B2 from a quarter mile. intern

  , we can directly replace DA by '1' and D by '0'. intern It results into: 101110001010001 . . . The key used was therefore 0xDC51 . . . = (1101110001010001 . . .) 2 . As we can see, it matches except that t

	3.1.2 Fixed-base windowing
	Another conventional algor	. ithm to perform t	he elliptic curve scalar operation is the
						.
	"fixed-base windowing" algor	. ithm [29]. intern This algor	. ithm is useful to accelerate t	he scalar
						.
	operation in systems which allow pre-computing and recording elliptic curve points. intern
	Algorithm 3.2 Fixed-base windowing EC scalar multiplication algorithm
	Input: window width
						As a point addi-
	tion only occurs if t	he parsed sec r	. et bit is equal to 1. . . he first
	'1' is missed. intern This happens since no computation is done t	he first time, as Q is equal to
						.
	t	he infinity point. intern Thus, no calculation is needed to double it and only a data transfer
					.
	occurs (Q = P ) instead of a point addition. intern
			In t	he double-and-add algor	ithm, t	. he security breach comes from two facts.i ntern First,
					.	.
	t	he elliptic curve double and t	he elliptic curve add operations have different durations. intern
					.	.
	Secondly, a condition based on t	he sec	r	. et bits values directly affects t .	he operation flow.
						.	.

  In case of mixedAffine-Jacobian coordinates for example, B = B + P i will usually use B in Jacobian and P i in affine in order to reduce t he addition operation between an elliptic curve point represented in Jacobian coordinates and another in affine ones.i ntern The returned result is represented in Jacobian. intern The operation A = A + B consists in an addition between two points represented in Jacobian. intern Thus t

	8: 9: end for A ← A + B
	10: return (Q)
	As t	his algor	. ithm uses only elliptic curve point additions, at a first glance it may
					.
	seem that t	he operation flow is independent of t	he key.i ntern This is actually not t	he case
					.	.	.
	as t	. he global time depends on t	. he number of K i = 0. intern Indeed, t	. he condition K i = 0 is
	never evaluated and thus no point addition is performed in t	his case. intern In addition the
					.
	use of mixed coordinates can drastically modify t
					he memory footprint. intern Thus t	he + operation consists
					.	.
	in t	his case in t
					.
					he two "+" occurrences in Algor	. ithm 3.2 can hide two
					.
	different operations and then t	he resulting operation flow significantly differs depending
					.
	on t

. he operation flow. intern . . he key value.

intern

  intern This operation thus clearly appears in t thus does not wield any elliptic curve operation. intern This explains why 14 Jacobian plus Jacobian operations are counted instead of 15. intern By counting t i = j. intern The number of K i = 0xF and 0xE can be retrieved by looking time between operations. intern A time glitch appears (not represented in Figure3.4). intern By measuring the time between Jacobian plus Jacobian operations and Jacobian + Affine operations, the approximate order of t

	occurrences with an amplitude of 5 between big peaks, it allows retrieving t	he number of
					.
					he first occurrence of each values and their position in t	he key
					.	.
	can be recovered. By measuring t	he time between Jacobian plus Affine operations, the
					.
	offsets between occurrences of a specified value can also be approximated and thus the
	(sec	r	. et) scalar value can be compromised.i ntern These time variations are due to t .	he "for"
					.
	loop used to search K i = j. intern The smaller is t	. he first i as K i = j, t	. he more loop iterations
	will occur before an elliptic curve operation. intern Therefore, t	he duration will appear longer. intern
					.
	In t	he case where both "+" operations are t	he same (e.g. intern affine coordinates case), the
					.	.
	power trace would look more homogeneous as only elliptic curve point addition would
	occur, always with t	he same formulae. intern However, information could be recovered from
					.
	t	his "for" loop timing leakage as it is still presents. intern
					.
		This algor	. ithm demonstrates two possible problems.i ntern The first one is that t	he oper-
					.
	ations flow at t	he algor
					.
	he trace as it has t	he most number of consecutive peaks. intern The 14 big peaks appearing
					.	.
	in Figure 3.4 thus represent 14 Jacobian plus Jacobian operations. intern From t	his point,
					.
	we can deduce t is initialized at infinity, t he value of t	. he "w" parameter (4 as 2 4 -1 = 15).i ntern As t .	he A register	.
					he number of peaks
					.

. he first "A = A + B" is just a transfer of t . he B value to A and K . ithm level can seem constant in time while t .

  Algorithm 3.3 Fixed-base comb method with two tables Input: window width w, d = ⌈t/w⌉,e = ⌈d/2⌉ k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q )

							Different
	configurations exist, depending on t	he width value and t	he number of pre-calculated
							.	.
	table stored in t	he system. intern A two table configuration is presented below as Algor	ithm 3.3.	.
							.
	In order to speed up t	he calculation time, t	he scalar k is represented as a matrix
							.	.
	of w lines of consecutive bits. intern During t	he "for" loop, two columns of t	he matrix are
							.	.
	parsed thus reducing t	he total number of iterations. intern All possible base point P multiples
							.
	associated to column values are pre-calculated.i ntern This algor	. ithm has some similarities
	with t	he "double-and-add" algor	. ithm presented previously. intern First a variable is set to the
							.
	infinity point. intern Then a "for" loop parses t	he sec	r	et. intern In algor	. ithm 3.3, t .	. his loop contains
							.	.
	a point doubling of t	he initialized variable and two point additions that depend on
							.
	different parts of t	he sec	r	. et (two different columns). intern This algor .	. ithm also presents the
							.
	same kind of leakage than algor

. ithm 3.1. intern If t . he sec . r . et bits parsed are 0s then the addition is skipped. intern Thus during a loop iteration, either a single point doubling occurs

  by distinguishing double operation with a double and add one, since a double and add is always performed whatever is t

	Section 3.1 "Double-and-add" pointed out that t	he leakage of t	he double-and-add
								.	.
	algor	. ithm comes from t	he association of two things: The difference between elliptic curve
								.
	add/double operations and t	he operation flow that depends on t	he sec	r	et. intern Thus two	.	.
								.	.
	paths of countermeasures have been proposed. intern In t	he following, we evaluate them. intern First,
								.
	t	he most obvious countermeasure is a double and always add algor	ithm. intern Algor	. ithm 3.4	.
								.
	presents such countermeasure. intern The double-and-always-add algor	. ithm consists in doing
	a dummy operation (i.e.i ntern G = Q + P in algor	. ithm 3.4) when t	he parsed bit of the
								.
	sec	r	. et scalar is 0. intern Doing so, t .	he operation flow become regular in time and consists in
								.
	a succession of point doubling and point addition.i ntern Thus attac	. kers should not be able
	to recover t	he sec	r	et from t	.	.
								.
								he value
								.
	of t

. he operation flow . he bit of k being processed.

  2. intern The gaps between peaks seem equal, except t

							he first one. intern
							.
	This leakage is generated by t	he initialization of Q to t	he point at infinity. intern Operations
							.	.
	with t	he infinity point are not real operation as t	he point at infinity is a neutral element
				.			.
	of t	he elliptic curve group. intern Thus t	his leakage allows recovering t	he sec	r	. et length as until .
				.			.	.
	a 1 is met in t	he parsed scalar, t	he point at infinity will be used and thus small gaps
							.	.
	appear. intern In t
							he elliptic
							.
	curve operations performed with Algor	. ithm 3.4 depending on t

. he illustration of Figure

3

.7, where only one small gap appears, we can deduce that t . he M SB of t . he key is equal to 1. intern The Table 2 below details t . he scalar M SB value.

Table 3 .

 3 1: Detailed operation flow of Algorithm 3.4 depending on the M SB k = 11... k = 01...

  The point at infinity is represented in Jacobian as (1, 1, 0). intern Thus P + O using t

								data transfer, P to Q
	:					:
	The infinity point is generally a special case for elliptic curve operations as it is a
	neutral element of t	he elliptic group and in t	his case formulae either does not apply or are
				.					.
	simplified. intern For instance, t	he Jacobian point addition formulae given in t	he background
						.			.
	section does not work to addition a point with t
							he given formulae result in
									.
	(0, 0, 0). intern It is obvious that t	his result is wrong as, except for t	he infinity point, the Z
						.			.
	coordinate cannot be equal to 0. Due to t	his leakage, attac	. kers can deduce t	he sec	r	et	.	.
								.	.
	length and as demonstrated in [39] and explained in t	he lattice section of t	his paper, such
									.	.
	knowledge is enough to break t
						.

. he point at infinity.

intern

  a conditional branch may induces cache hit/miss, pipeline flushing, wrong branch prediction and so on. intern This can result in a different power consumption either in level or timing depending on t

						Thus, t	he power trace
						.
	does not leak any more information on t	he type of operation (i.e. intern elliptic curve double or
						.
	add) which is performed. intern It is to be noted that t	his approach leaks t	he Hamming weight
						.	.
	of t	he scalar as t	he global execution time depends on it. intern Indeed, t	he number of peaks
						.	.	.
	gives t	he total number of elliptic curve double and addition operations which have been
						.
	processed and just t	he number of elliptic curve point addition varies. intern As demonstrated
						.
	above, another leakage also exists due to t	he initialization. intern Both countermeasures (i.e. intern
						.
	Algor	. ithm 3.4 and Algor	. ithm 3.1 with unified formulae) then work against SP A in the
	traditional case where attac	. kers try to fully recover t	he sec r	. et from one power trace .
						.
	by identifying elliptic curve operations (i.e. intern point doubling and point add). intern However,
	they are not enough in t	he case of ECDSA as partial leakages drastically reduce the
						.
	security (this point is developed further in section 2.6). intern
		Another well-known leakage in t	he description of Algor	. ithm 3.4 and Algor	ithm 3.1 is	.
						.
	t	he use of t	he if-else condition. intern Indeed, in a software implementation and depending on
						.	.
	t	he architecture of t
						.

. he core, . he branch that is used.

intern

Figure 3.8 below is a good illustration of t . he leakage.

  Depending on t at infinity will be used and thus point doubling and point addition performed are not real operations and can be shorter in time as demonstrated Figure3.7. intern In some cases (e.g. intern OpenSSL v0.9.8o[START_REF] Brumley | Remote timing attacks are still practical[END_REF]), t

							he algor	ithm,	.
							.
	either M SBs, LSBs or Hamming weight of t	he sec r	. et can leak via timing information. intern .
							.
	In t	he case of Algor	. ithm 3.4 for example, a global timing analysis can lead to recover
							.
	t	he sec	r	. et length and thus t .	he number of M SBs set to 0.i ntern Indeed, until a 1 is met in
							.	.
	t	he parsed scalar, t
							.
							his leakage is due to t	he scalar
							.	.
	multiplication algor	. ithm implementations that start t	he loop index at t	he first non-zero
							.	.
	M SB of t	he sec	r	et.	.	.
							.

. he point

  SB to 1. intern Secondly, no "if" condition is used, instead a two index table is used for Q and t This prevents branching in software implementation. intern Branching can in some cases be exploited as it may results in different timing executions or power consumption depending on t . he no code jumping case and code jumping case[START_REF] Rebeiro | Timing Channels in Cryptography[END_REF]. Algor used to perform low level operations such as modular addition, modular multiplication. . . ). Point addition and point double are based on modular operations such as modular multiplication and modular division. intern Depending on how modular operations are managed, information can leak.i ntern It is common to see modular operations with an execution time which depends on t . he operands. intern Indeed in a standard multiplication or division, execution time can vary depending on operands.intern The number of modular reduction operations used can also vary depending on operands. intern Thus combining both to get a modular multiplication/division with a constant execution time is not obvious, especially when high performances are needed. intern Moreover, when constant time modular operations are reached, they can still leak information due to internal conditions and registers values which influences t

	In t	his algor	. ithm, two differences appear compared to Algor	. ithm 3.4. intern First Q[0] is
						.
	initialized to P , t	his initialization prevents t	he use of t	he point at infinity in t	he loop,
						.	.	.	.
	however it forces t
						ithm 3.5	.
	is resistant against previously described attac ks. intern Nevertheless, it is not enough if we .
	consider underlying algor	ithms (i.e. intern t	.
						he power consumption. intern It can
						.
	be remarked from Algor	. ithm 3.5 that at t	he second iteration of t	he loop, t	he two first
						.	.	.
	operations are:

. he scalar M . he correct index is selected depending on t . he parsed bit. intern . he ones

Table 3 .

 3 2 summarizes t

. he results.

Table 3 .

 3 2: Figure 3.9 to 3.12 results summary Binary Nb. intern of M SB match Nb. intern of D/A that match

	Key: 0x8A...	10001010	-	-
	Hyp1: 0xE0... 11100000	1	1
	Hyp2: 0xC0... 11000000	1	1
	Hyp3: 0xA0... 10100000	2	2
	Hyp4: 0x80... 10000000	4	4
	Note:Compares t	he number of matched operations to t	he number of bits match
		.		.
		between key and hypothesis.

Table 3 .

 3 Secret leakages may be only partial. intern Indeed, instead of leaking all t ECDSA based on N IST P-256 curve with an EC scalar algor .

		2 shows that t	he number of correctly guessed bits directly depends on the
				.
	number of couple double/add that matches t	he genuine trace. intern Thus breaking t	he sys-
				.	.
	tem in t	his case is easily performed since attac	. kers only have to recursively try two
				.
	hypotheses until t	he whole sec r	. et is recovered. intern This is a data dependent leakage, which .
				.
	can be recovered from timing information.i ntern It is also possible that t	he leakage is not
				.
	visible from t	he timing but from t	he signal amplitude. intern When not clearly visible, cor-
				.	.
	relation or template attac ks [53] and [54] can be done to enhance t .	he probability of
				.
	attac k success. This approach is easy to perform in our case as attac . kers can control .
	t
				he design reuse
				.

. he scalar input and thus directly reuse t . he design as a model that perfectly fits the reality. intern This can happen in real life systems when for example t . he design allows users to set a private key and calculate t . he public one. intern In t . he cases where t . k is used against a device that implement an

  -(1075...8026) • k 1 + (4081...9217) • d ≡ 0 mod (1157...4369) (5029...2342) -(9872...2968) • k 2 + (8843...3787) • d ≡ 0 mod (1157...4369) (5029...2342) -(9406...5508) • k 3 + (4597...4771) • d ≡ 0 mod (1157...4369) ≤ C < 2 15 : k 2 lsb + (4253...23) • k 1 lsb + [(4003...90) + (1 + (4253...23)) • C • 2 251 ] ≡ 0 mod (1157...369) k 3 lsb + (1461...47) • k 1 lsb + [(1135...46) + (1 + (1461...47)) • C • 2 251 ] ≡ 0 mod (1157...369) = (0, [(4003...90) + (1 + (4253...23))C • 2 251 ], [(1135...46) + (1 + (1461...47))C • 2 251 ], ...)

	leaf represents a 15 bits unknown value.
		Figure 3.13 shows that when parsing t	he first scalar bit, all traces are well superposed. intern
	. As 255 EC operations are performed instead of 256 (scalar length), we can conclude . All we know about nonc . es is that they share t he same 15 M SB bits. intern Thus, we can
	that t 500k/2 14 ≈ 30 signatures.i ntern In order to remove wrongly categorized curve, each of the . he M SB is constant (and equal to 1) and 500k traces provide 2 14 leafs with 30 curves are compared to t . he average of all power traces of t . he leaf and only t he 25 best match are keep. intern write t . he above equations as following with 0 From t he 24 remaining equations, we can build a lattice of dimension 25 generated	.
					.
	We work now only on one leaf, thus a set of 25 signatures with t The message used is "This is a test message", t he SHA-256 of t he message is: he same 15 M SB. . . 0x6f 3438001129a90c5b1637928bf 38bf 26e39e57c6e9511005682048bedbef 906 = by t . he rows of: A =      -1 (4253...23) (1461...47)  • • • 0 (1157...69) 0  • • • 0 . . . (1157...69)   . . . 	.
					0	• • •	0	(1157...69)
		As an example, we give here three signatures, represented in decimal, however we This lattice is reduced to get B:  
	work with all t	he set. intern
					.
	(r 1 , s 1 ) : 107539402501435392702812634518510467209619979448516202477004316951198642568026 (r 2 , s 2 ) : B = LLL(A) =      69) 0 . . . (3707...38) • • • • • • (1387...22) • • •   . . . 
	(r 3 , s 3 ) :
		To find X, we first express t in t	he lattice basis and round t
					.
	From t	he set of 25 signatures, 25 equations can be written, t	he three following equations
					.	.
	correspond to t	he three previous signatures (truncated to (M SB...LSB) in decimal
					.
	due to writing constraints): This gives t cannot easily be build due to our hypothesis. intern However, t his scalar as a random nonc . e is used and template . . his leakage allows us to gather signatures with t . he same nonc . e M SB or LSB depending if t . he implemented EC scalar multiplication algor . ithm is a left-to-right or a right-to-left algor . ithm. intern In t he next few (5029...2342) No information are known about t he private key d, thus d is removed from the
					.	.
	lines, we make t equations. intern	he assumption that t	he algor	. ithm used is a left-to-right and thus that
					.	.
	t	. he first scalar bit represents t From here, 500k signatures with t he M SB. intern he same messages are computed and t . (5029...2342) -(1075...8026) • k 1 + (4081...9217) • d ≡ 0 mod (1157...4369) he associated
					.	.
	power consumption recorded. intern Traces are recursively categorized in two groups A and
	B from t	he first operation and for t	he next 14 ones thus forming a rooted tree. intern Each
					.	.

. he information that no randomness is used in t . he system and thus that t . he scalar implementation is vulnerable to DP A/CP A and template. intern Unfortunately, DP A/CP A cannot be used to target t ⇔ d ≡ (7623...9043) • k 1 + (8257...4784) mod (1157...4369) k 2 + (4253...8423) • k 1 + (4003...1090) ≡ 0 mod (1157...4369) k 3 + (1461...6647) • k 1 + (1135...7846) ≡ 0 mod (1157...4369) (-6856...88) (3054...68) • • • (-4495...47) (-3320...20) (1325...97) • • • (-9601...By construction, we know that it exists X such that: XB -t = (k 1 lsb , k 2 lsb , k 3 lsb , ..., k 25 lsb ) with t . he result.

  14 times for all possibilities of C with t . he M SB set to 1. intern This will give us 2 14 different X and thus 2 14 values of (k 1 lsb , k 2 lsb , k 3 lsb , ..., k 25 lsb ) and thus 2 14 possibilities of d.

	We solve t his system 2 By comparing all d.G value to t .	he public key Q, we can determine if one of the
		.
	guessed value is good or not.

intern In our case, we found t . he correct sec . r . et key that is:

  he system as only few bits have to be brutforced to fully recover the key. intern Our inefficient implementation (Matlab/Mupad) is able to solve all 214 possibilities in around 3 hours on a basic laptop. It is also to be noted that in t

	are thus able to recover t a limited knowledge and access to t he sec he target. intern The data dependent leakage discussed . . r . et without knowing t . he value of any bit and with CHAPTER 4
					.
	in section 3.2 allowed us to find signatures with t	he same M SBs. intern This knowledge is
					.
	enough to break t Fault Attacks Against ECC
					his example case, the
	. LLL does not have to be recomputed for each hypothesis (A does not rely on C) and allowed to save a lot of time. intern Indeed, t he most time consuming operation for t he lattice and ECDSA
					.	.
	section is t	he lattice reduction. intern It is also to be noted that fewer power acquisition is
					.
	necessary to break t	he system. intern By performing t	he lattice attac	. k on a group of signature
					.	.
	with t	he same 14 bits (instead of 15), and by using t	he knowledge of which signature
					.	.
	nonc	e have t	. he 15th bit set to A or B, we do not increase t	he brutforce complexity and
					.	.
	divide per two t	he total number of signatures power trace.
					.
	The effect of t	he environment on semiconductors is studied since a long time. intern Back in
					.
	1957, [57] studied t
	3.4 Summary	.
	Different side channel leakage sources that allow recovering information about t	he EC
					.
	scalar were described and demonstrated. intern While some leakages were already well known,
	such as t	he operation flow that is scalar dependent inside t	he double-and-add EC
					.	.
	scalar algor	. ithm, less obvious leakages were presented. intern Demonstration was provided that
	leakages can be unintentionally inserted due to t	he choice of coordinates representation
					.
	which result in having different "+" operations that can be distinguished. intern Various
	leakages due to t	he use of t	he infinity point were also discussed and illustrated in
					.	.
	different cases to recover information even when EC points are blinded. intern These leakages
	can be used either with power consumption or also with a basic timing attac	k. intern	.
	While such leakages do not allow to fully recover t	he EC scalar, they may be enough
					.
	to get some bit values. intern Mathematical attac	. ks allowing to recover t	he ECDSA private
					.
	key if partial information of t	he nonc es are available are relatively easy to implement .
					.
	and use without requiring any extended mathematical background. intern Thus these leakages
	even small can be enough to jeopardize t	he security of an ECDSA implementation.
					.
	Indeed, we demonstrated that side channel collisions between signature generations
	may allows recovering t	he ECDSA private key thanks to lattice attac	. ks and brutforce
					.
	without even requiring to know any bits value.
	From t	he various side channel evaluations and observations, it becomes obvious that
					.

.

  which simply consists in applying a high magnitude transient voltage pulse to a needle near t IC is decapsulated and placed on an XY positioning table allowing placing t

		he target under
		.
	t	he laser beam or t
		.

. he backside of t . he IC. intern As depicted in figure 4.1, t . he . he F BBI needle.

  = Q[0] + P is never used.intern Then, if one inject an error during t

	4.1.1 Local dummy operations, C safe-error against the
					Montgomery ladder
	Most common ECC scalar algor	. ithms are known to be sensitive against t	he C safe-
							.
	error attac	. k and require specific countermeasures.i ntern In t	he literature only t	he Mont-
							.	.
	gomery ladder presented in algor	. ithm 4.2 is referenced as resistant against t	his attac	k	.
							.
	by construction. intern In [81], t	he authors claim t	his resistance as there are no dummy opera-
							.	.
	tions in t	he Montgomery ladder. intern Also, they described t	he M safe-error attac	k against the	.
							.	.
	Montgomery ladder that targets a memory value instead of a computation in order to
	see if it is used or not and then they provide a modified Montgomery ladder 'protected'
	against side-channel, M safe-error and also C safe-error per t	he previous claim.
							.
	error attac Algorithm 4.2 Montgomery scalar operation . ks aim at injecting a fault inside a computation and, thanks to the
	error propagation or non-propagation, to conclude about a sec	r	. et value from t .	he correct
							.
	or incorrect result. intern In [80], authors have presented t	he C safe-error attac	k against the	.
							.
	dummy operation inside an RSA exponentiation. intern The basic idea behind t	his attac k	.
							.
	is to inject a fault during a dummy operation and to see if it is propagated or not. intern
	From algor	ithm 4.1 in t	.
							his computation, t	he computation result will
							.	.
	not be altered and then t	. ker can deduce that t he attac .	. he bit k i was 0 at t	his time. intern	.
	Thus, an attac ker can easily conclude about t .	. he k i value if he is able to inject a fault
	inside t	he Q[0] + P computation for t	he i index and observe if t	he result is correct or
							.	.	.
	incorrect. intern This kind of fault injection is really powerful as attac	. kers does not have to
	know which kind of fault is injected nor where exactly. intern Synchronization between the
	algor	. ithm execution and t	he fault injection is simple in t	his case as algor	. ithm 4.1 always
							.	.
	execute t	he same operation flow.i ntern Moreover, t	he operation Q[1] = Q[0] + P require
							.	.
	many clock cycles (E.g. intern > 2816 cycles in t	he case of mixed jacobian-affine coordinates
							.
	and a modular multiplication performed in 256 cycles) providing time and opportunity
	to t	he fault attac k.	.
							.
	While safe-error are known since at least 15 years, we think that t	he effect on security
							.
	is highly underestimated. intern Indeed, many EC algor	. ithms are vulnerable to safe-error and
	even some algor	. ithms presented as immune to t	his kind of attac	. k. intern M safe-error attac	ks	.
							.
	are similar to C safe-error attac k and aim at targeting a memory value instead of a .
	computation. intern The attac	. ker concludes also depending on t	he propagation or not of the
							.
	fault to t	he result.
							.
	In t	he following, we present different situations where safe-error can be used to recover
							.
	enough information on t	he ECDSA nonc	e during t	. he EC scalar algor	. ithm to mount
							.	.
	a lattice attac k.	.

. he case k i = 0 then t . he result of Q

[1]

  This observation can be used in order to break an ECDSA. intern Indeed, if a nonc R 1-k i ← R 0 + R 1 during k LSBs, and then deduce if k LSB are equal to 0. intern After gathering a couple of signature with nonc LSBs for 29 • 70 = 35840 signatures generation. intern Algorithm 4.3 Montgomery scalar operation with a specific scalar value Input: k = (1, 0, ..., 0, 0) 2 , P ∈ E(F q ) Output: k.P 1: R 0 ← P 2: R 1 ← 2P 3: for i = t -2 to 0 do LSBs set to 0 is 1/2 9 , thus 2 9 signatures are needed to find one signature with t to fault followings R 1-k i ← R 0 + R 1 operations. intern Regarding section 2.6.4, our number in term of required signatures (35840) is realistic in order to break an ECDSA based on N IST P-256 with a basic, non

		4: 5: 6: end for R 1 ← R 0 + R 1 R 0 ← 2R 0
		7: return (R 0 )
	This is due to t	he uniform distribution of t	he nonc es, t	. he probability of having nine
						.	.	.
						he nine
						.
	nonc	. e LSB equal to zero.i ntern A valid signature means that t	he faults did not propagate
						.
	to t	he result and thus that t	he nine LSB were set to 0. intern This attac	. k scheme is realistic
						.	.
	as each elliptic curve operation requires time, any fault on t	he targeted operation can
						.
	be used and t	he algor	. ithm is highly homogeneous facilitating t	he fault injection. intern As all
						.	.
	faults can be injected in t	he same physical location of t	he IC, a single LED based laser
						.	.
	is enough to perform t	he attac	. k. intern Moreover, t
						.
	requires time and multiple clock cycles allowing attac	. ker to inject multiple faults in
	t	he computation to ensure t	he fault injection. intern Both data and control flow of low level
						.	.
	operations (e.g.i ntern modular operations) can be targeted as long as t	he computation is
						.
	corrupted without altering t	. he signature process.i ntern Once R 1 contains a faulted value,
	it will propagate to t	he end releasing t
						.
	optimized lattice attac t . M SB bit directly given by t k and does not take into account t . he result. intern Algor ithm 4.3 is an illustration of the . he information of t he scalar 0, 0) 2 . . he algor . ithm. intern The M SBs leakage, in t . his case, can easily be he register R 1 is never involved in t . Montgomery scalar operation with t . . his specific scalar value. taken in account inside t he lattice attac . k. intern Indeed, from [37], t he s part of t he ECDSA	.	.
	signature is equal to:	.	e is	.
	randomly selected and then used as t	he scalar k in algor	. ithm 4.2, an attac	ker may inject	.
						.
	a fault into . es LSBs set to 0, it is possible to
	perform a lattice attac	. k [38] to recover t	he private key. intern As we did not find any public
						.
	record of such an attac	. k, here is a short example of t	he principle. intern An attac ker looking	.
						.
	for 70 signatures with 9 known bits of nonc	. es LSBs (see section 2.6.4) in order to
	perform a lattice attac

. k against an ECDSA based on N IST P-256 will need to fault

R 0 + R 1 during evaluation of t . he nine . he targeted operation R 1-k i ← R 0 + R 1 . he need

  0 mod n By considering a 256 bit curve, k j M SB = 1 and k j LSBs = 0:

	Where H(m j ) is t	he hash result of t	. he message m j , d is t .	he private key, k j t	. he ran-	.
	dom nonc

. e, r j t . he r part of t . he signature, j represents t . he j th signature and k j unknow represents all t . he unknown bits of k . intern x depends on t . he number of LSB set to 0. intern

  255-x ≡ 0 mod n ECDSA case. intern A good practice could be to systematically verify that R 0 -R 1 = P prior any result exposure. intern 1-k i ← R 0 + R 1 , a fault may occur on R 1 once R 1 value is used in t

		Thus, if t	he M SB bit is given away, attac	. kers can easily insert t	his knowledge inside
						.	.
	t	he equations in order to reduce t	he researched values to t	he minimum improving
						.	.	.
	lattice attac k success rate (please refer to section 2.6 for details on t .	he lattice attac k). intern	.
						.
	As t	he M SB of k is set to 1 and then provided, attac	. kers will seek one bit less and
						.
	then t	he expected consequence is to divide by almost two t	he total number of required
						.	.
	signatures to ask to t	he system and thus t	he attac k time. intern Indeed, in our example, with .
						.	.
	. kers will obtain 70 of them with 9 known bits (8 LSBs + 1 MSB). The M safe-error countermeasure presented in [81] does not affect t 2 8 • 70 = 17920 signatures, attac his attac k as	.
						.
	it simply changes t	he operand order depending on t	he sec	r	. et bit. intern We can then conclude .
						.	.
	that t	he Montgomery ladder, as opposed to a common thought ([81], [82], [55], [83]...),
						.
	is in some case sensitive to C safe-error attac	. ks. intern It also demonstrates that safe-error
	attac	. ks can be used even with an ephemeral scalar value in t
						.
	However, t
						he computation and prior t	he update of
						.	.
	R 1-k i . intern This is called M safe-error attac	. k and similarly to C safe-error attac	k, it lead	.
	to know t	. he value k i through correct or incorrect result.i ntern The countermeasure in the
	case of elliptic curve is not obvious, especially considering t	he complexity of t	he elliptic
						.	.
	curve point addition as detailed later in section 4.1.4.
	4.1.2 Unused memory values
	Similarly, errors can be inserted on a memory saved value which is no longer used. intern To
	illustrate t	he problem, t	he algor	. ithm described in [84] based on t	he binary expansion and
						.	.	.
	t
						.

he

. his is not enough. intern Indeed, during t . he operation R

  It is described as algor Algorithm 4.4 Binary Expansion with RIP (BRIP)

				ithm 4.4. intern	.
	For k = (0, ..., 0, 0) 2 , T is never used, therefore, an attac	. ker can fault T inside the
	memory prior evaluation of t	he scalar LSBs and thus detect if they are equal to zero
					.
	similarly to Section 4.1.1. intern If an attac ker is able to induce a temporary fault inside T .
	during a loop iteration, t	he result is even worse. intern Indeed, in t	his case attac	kers could	.
					.	.
	target any part of t	. he scalar as after attac	. king during k i bit, t	. he fault no longer exist
	allowing t

. he system to work properly and pursuing operation.

intern

It is worth to notice that t . his unused value problem may arises with different algor . ithm and most algor . ithms that

  , other problems appear if fault injection is considered. intern Indeed, in equation (4.2), a fault can be injected in y 1 operand when 0 • y 1 is computed.i ntern Faults can also be injected in dx 1 operands or computation without affecting t one values, will generate special computation cases in most systems that can be detected thanks to side channel or fault injection and thus should be avoided.intern

			his prerequisite limit t	he Even considering t	he design is safe against
					.	.	.
	side channel analysis. he result. intern Such
	faults will not be propagated to t	he result in t	he case where t	he neutral element is used. intern
						.	.	.
	Thus, due to t	his special point t	he design may face up safe-error attac	ks. intern Table 4.1	.
					.	.
	provides t	he identity element representation in different systems.i ntern From t	his table, it
			.			.
	can be expected that t

. he neutral element, due to t . he zero and

Table 4 . 1 :

 41 Representation of the neutral element in different systems Algorithm 4.6 Right-to-left double-and-add always with coherency checking

	System Weierstrass, affine coordinates	O none
	Weierstrass, projective coordinates	(0:1:0)
	Weierstrass, Chudnovsky coordinates	(1:1:0:0:0)
	Edwards, affine coordinates	(0,1)
	Edwards, homogeneous projective coordinates	(0:1:1)
	4.1.4 Safe-error on underlying algorithms
	As a safe-error resistant algor	. ithm, [91] suggests to use a countermeasure based on
	coherency checking. intern Algor	. ithm 4.6 presents t	his countermeasure.
				.

  line 5, or memory addresses will be detected independently of t . he scalar value k.

	Nevertheless, t	he "+" operation is an elliptic curve point addition which is a complex
			.
	operation. intern Algor	. ithm 4.7 is an example of ECC point addition operation performed in
	Jacobian coordinates. intern If we consider t	he line 8 of algor	ithm 4.6, t	.
					.

. he operation

  40 computations to recover ±e

	can also recover t	he full key. intern It is obvious that, if for some reasons attac kers know the	.
					.
	result value of t is also to be noted that in a non-contiguous faulted bits case, t . he genuine value is recovered. intern It . he faulted register, by recovering ±e, t he carry propagation
					.
	cannot be generated by t	he fault, and thus, similarly to t	he previous LSB bit flip
					.	.
	example, attac	. kers directly recover t	he flipped bits. intern E.g. intern if t	he fault model considers
					.	.
	fault only on M SB and LSB, a +1 error necessary reveals that t	he genuine LSB is 0. intern
					.
	Indeed, t	he second bit cannot be faulted due to t	he model preventing t	he fault to flip bit
					.	.	.
	according to t	he carry propagation required if t	he LSB is 1. This attac k demonstrates .
					.	.
	that an error inserted on t	he ECDSA private key during signature generation can be
					.
	recovered from t	he faulted signature.i ntern Due to t	he binary representation of t	he private
					.	.	.
	key, it is then possible to recover information about t

. he private key.

  intern As both x are t is not uniform. intern Indeed, per example, if we consider an 8 bits register that is faulted and e t . he error injected. intern And if we consider that a fault on t

					he same, it results to t	he same r value.
					.	.
	Similarly to t formation about k due to its representation.i ntern The difference is that k is a nonc . he previous section, from t . kers obtain in-. he knowledge of ±e, attac e that	.
	changes for every signature thus it is not possible to perform multiple fault attac	ks and	.
	learn k from all t	he answers. Nevertheless, as explained in t	he previous section, single
					.	.
	bit fault and non-contiguous multi-bits faults (i.e. intern faults on non-adjacent bits) allow
	recovering all flipped bits in one attac k.	.
	In t	he case of contiguous multi-bits faults, it is interesting to notice that t	he distribu-
				.	.
	tion of t
					he 8 bits
					.
	register generates a uniformly random 8 bits value.i ntern Then t	he error distribution is as
					.
	depicted in figure 4.4.
	This is due to t	he fact that t	he error e = +255 may happen only if t	he register value
					.	.	.
	is 0. intern The error e = +254 may happen only if t	he register value is 0 or 1. intern The value
					.

.

he error e

  ker observes |e| > 168 then he knows that v 1 is t Figure 4.8: Overview of the considered architecture.Grey blocks containing some side channel and fault countermeasures It is considered that EEP ROM and SRAM are not accessible to t . he I2C block while containing sensitive or partial information.i ntern We also consider that t . he RN G is perfect (i.e. intern uniformly random and not controllable from EEP ROM protected thanks to an AES cipher with also both side channel and fault countermeasures. intern The elliptic curve considered is N IST P256. intern Memories are 32 bits width and 8 memory accesses are performed each time to read or write 256 bits (8 • 32 = 256), t SRAM to a specific address.i ntern A 256 bits nonc . e k is generated from the RN G and saved into t . he SRAM . intern The ECDSA block then reads t

		First, t	he message to sign is hashed thanks to t	he SHA 256 block. intern The result is then
								.	.
	saved in t
								.
								he nonc	e from the	.
								.
	SRAM when needed (for each bit evaluation, as shown in previously described elliptic
	curve scalar algor	. ithm), performs an elliptic curve scalar operation and compute the r
	part of t	he signature that is saved into t	he SRAM at another address. intern The ciphertext
								.	.
	C(d) of t	he private key d is read from t	he EEP ROM and then decrypted by t	he AES
								.	.	.
	block. intern The result d is then saved into t	he SRAM . intern The ECDSA block then reads the
								.
	hash result, t	he r part of t	he signature, t	he private key d and t	he nonc	e k from the	.
								.	.	.	.
	SRAM and generates t	he s part of t	he signature.i ntern Once all sensitive information are
								.	.
	cleared, t	he ECDSA signature (r, s) of t	he message is then exposed to t	he outside.
								.	.	.
	This architecture provides countermeasures against side channel and fault attac ks at	.
	t	he cryptographic block level and not overall in t	he system. intern Errors can thus happen in
								.	.
	blocks interfaces, in memories, or on memory controllers that may affect data during
	In t transfer or address used. intern In t . his architecture, memories are shared and partitioned between t . he following, based on t his observation, different situations . he communication block and t allowing security breach are studied. intern	.
	Signatures with shared nonces
	outside) and t Two signatures computed with a different message and t he ECC block contains strong side channel and fault countermeasures . he same nonc e are enough	.
								.
	. he correct value. intern In t . k). intern The private key d is securely stored (i.e. intern resistant to any fault and side channel attac to recover t . he private key.i ntern Indeed, each signature j, provides an equation with two he figure 4.6 example, around 16% of t . he faulted signatures end-up with t . in t unknown values, t . he nonc . e and t . he private key. he v 1 value. intern Around 10k faulted signatures are sufficient to identify t . he distribution edge +168, resulting in ≈ 1600 signatures with t . . s j = k -1 j (H(m j ) + d • r j ) Thus two signatures provide two different equations with three unknown values, two he v 1 value. intern 1600 signature with 8 known bits are enough in order to recover t . he private key thanks to a lattice attac . k. intern This represents t nonc . es and t . he private key. intern If t . he nonc . es are equals, then there are two different equa-he ideal case and t he success rate of t he fault injection may vary depending on t . he system and tions with two unknown values, t he system is thus solvable as detailed in equation (4.3).	.	.
								.	.	.
	architecture choices.
	4.2.3 Faulted intermediate values
	The partial knowledge of intermediate values during an ECDSA signature can also
	compromise t	he security of t	he sec	r	. et key.i ntern Indeed, as demonstrated in [92], a partial .
								.	.
	knowledge of (H(msg) + d • r) allows a lattice attac apply on d • r. It is possible to write: (H(msg) + d • r) ≡ A mod n ⇔ A -d • r -H(msg) ≡ 0 mod n	k to recover t	. he sec	r	et d. intern Same	. .	.
		A represents an unknown value which is an intermediate result of t	he signature
								.
	generation. intern This equation is similar to t

. he one targeted by lattice attac . k in section 2.6. intern . he cryptographic core. intern he . he SHA and AES blocks are built with a 8 bits datapath. The ECDSA signature generation is as depicted in t . he chronograph presented in figure 4.9.

Figure 4.9: Chronograph of a ECDSA signature generation he

Table 4 . 2 :

 42 kers will need more signatures to succeed. intern Thus, a trade off between number of signature and computation power is possible. intern The private key is stored encrypted in an N V M .intern In order to use it, first it is decrypted thanks to an AES block and then stored in t Figure4.10 illustrate how bits can be accumulated to 32 bits prior an SRAM writting. AES bits accumulation through SRAM read/write iteration Expected

	As previously, t	his can happen in t	he studied architecture if t	he nonc	e update is	.
							.	.	.
	compromised. intern A single fault during operation B on t	he address used or t	he read/write
							.	.
	signal may lead to avoid a word update. intern As explained in section 3.3, if enough such
	signature are gathered, a lattice attac	. k can be used with a brutforce on t	he shared
							.
	bits. intern It is to be noted that, even if 32 bits or more are shared, t	he brutforce can be
							.
	applied on fewer bits and attac
	Signature generations with faulted secret key
	Section 4.2.1 details how a faulted private key used inside an ECDSA signature can
	be used to recover information when it is slightly different from t	he genuine private key
							.
	used during t	he key generation. intern In t	he described architecture, different possibilities may
							.	.
	exist to inject such fault. . he SRAM
	during operation D. intern Faults injections and countermeasures in AES as discussed in
	[93] consider faults inside t	he block cipher. intern Hence, despite t	he fact t	he AES contains
							.	.	.
	fault countermeasures at t	he block level, t	he interface between it and t	he SRAM can
							.	.	.
	eventually be faulted. intern In our case, considering section 4.2.1, attac	. kers are interested
	to fault t	he output result of t	he AES prior to be used to generate t	he s part of the
							.	.	.
	ECDSA signature. intern The AES block internally uses a 8 bits datapath and t	he SRAM
							.
	interface uses 32 bits of data. intern Thus, in t	his case either t	he AES result is accumulated in
							.	.
	hardware until 32 bits are ready to be written in t	he SRAM or multiple read and write
							.
	are used to end up with t	he full word written correctly in t	he memory. intern The fact that
							.	.
	t	he AES uses an 8 bits datapath is interesting for attac kers. intern Indeed, t .	his may allow
					.		.
	them to target 8 bits instead of 32.

j

. intern intern

  address, A i : i th byte of AES result, F i : Faulted byte anytime between operations C and E. intern Indeed, t Similarly, the same can happen during operation E. intern A fault can also occur in t . he SRAM between operations C and E. intern As during operation C t

						he nonc e read during operation C can .
						.
	be faulted either directly on t	. he data bus or by faulting t he ECDSA block read t he read address. . he nonc	. e from the	.	.
	SRAM for each bit evaluation (i.e. intern for each loop iteration of t	he previously described
						.
	elliptic curve scalar algor	ithm), attac	. kers can target a few bits of t .	he nonc e with faults. intern	.
						.
	Indeed, even if 32 bits of t	he nonc e are faulted during t .	he nonc e reading of operation .
						.	.
	C, only t	he bits required by t	he elliptic curve scalar algor	. ithm are used. intern Thus, t	he fault
						.	.	.
	propagate to t	he result only on those bits.
						.

intern

  his specific point is considered and manipulated as a normal point (E.g. intern with Edward curves).intern We demonstrated that even if in t r part of ECDSA signature. intern The s As example, if k ′ is used to compute r, and k to compute s, and if, due to a fault, a bit flip such that k ′ represents t

	point that can be used when t otherwise t he system may be vulnerable to a lattice-based fault attac	. k as explained
	.
	he ECDSA e that is refreshed for each signature, safe-error . he private key due to t he scalar represents a nonc . . ks are enough to recover t signature, t attac he fact that obtaining only a in chapter 4. . he signature (r, s) he value k ⊕ 2 i then t generated by t he system will be invalid. intern As demonstrated in chapter 4, in t his case an	.	.
		.		.			.	.
	couple of bits per signature allows mathematical attac The EC scalar operation represents only t attac . ker can easily recover t . he injected fault and then deduce t ks. intern CHAPTER 5 bit of k. intern If a larger fault (i.e on 8 bits) is injected, more bits can be recovered and then . . he value of t he flipped	.
						.
	part of t used inside a lattice attac he signature can also be targeted. intern We thus showed that ECDSA signatures . k to recover t he private key. intern Section 4.2.2 demonstrates some
	.			.
	generated from faulted private key can be used to recursively recover t demonstrated that a slightly faulted private key used during t he computation of the s he key bits. intern We . . Side Channel and Fault attac . k possibilities when attac . kers have t he opportunity to fault nonc . es.	.
	part of t signature. intern Thanks to t he signature may generate a small error that can be recovered from t . . he knowledge of how t . he private key is represented in registers he faulted and t . he error, information about t . he key can be obtained.i ntern Indeed, t he possible error In t . his following chapter, we detail algor . ithms, improvement and implementation strategies that aim to obtain an ECDSA signature implementation secure against Countermeasures t he previously described attac . ks. intern First in section 5.1, new elliptic curve algor ithms are	.	.	.
	.
	range generated by a register of a given size depends on t described that allow protecting t he computation against both side channel and safe-error . he size and t he genuine value. intern	.
				.
	By recursively generating signature with faulted private key, it is possible to recover the while reducing t he security concern in case of partial leakages while computing the r
		.
	error range and with t part of t he signature. intern Section 5.2 discusses about t . he knowledge of t he register size and how t . he implementation of such algor he sec r et is represented, . . . ithms. intern	.
	.					.
	t It presents a selection of parameter allowing merging most parts of algor . he private key can be fully recovered. intern A similar method was also applied on nonc ithms and also es. intern .	.
	While it is not possible to recursively attac presents improved way of using such algor ithms to, as example, efficiently compute the . k a given nonc . e, signature can be selected .
	according to t In order to speedup or ease t he obtained error due to t . he computation, some elliptic curve scalar point multiplica-. he fault. intern This allows to provide enough bits . EC scalar operation with a blinded scalar. Then in section 5.3, approaches to protect
	of information to be used within lattice attac tion algor . ithms require t . he scalar in a non-conventional representation. intern In t . ks and then to recover t he private key. intern he previous both t he ECDSA private key and t he nonc . e while computing t he s part of signatures	.	.
	.			.			.
	We also demonstrated that t chapter, algor . ithm 4.5 is one example of such practice. intern The Non-Adjacent Form (N AF ) . he error distribution allows attac . kers to understand the are described.i ntern The nonc . e countermeasure also allows to strengthen t he elliptic curve
							.
	behavior of t and t he Join Sparse Form [29] are also often used.i ntern As t . he injected fault and then to greatly improve t . he sec he attac r et scalar may be used . . k speed. intern . . . scalar algor . ithm against fault attac . k by providing a Control Flow Integrity (CF I). intern
	A basic architecture of an ECDSA system was described allowing to compute elsewhere in t . he system, t . his ends up with different representation, manipulation and This CF I aims at ensuring that t
				.
	signatures. intern This allowed to understand t use case of a same sec . r . et. intern This may extend t he wide range of fault injection possibilities he attac . k surface and introduce new security
					.	.
	and opportunities for attac risks. intern For example, from [37], t kers and to understand how realistic t . he implementation of ECDSA signature requires the he described fault
				.			.
	The he low level functional blocks are mandatory but unfortunately are not enough to ensure t injection attac . ks can be. intern This also demonstrated that countermeasures in t he security regarding fault injection. Safe-error attac . ks against t he EC scalar algor . ithm and consequences are underes-. he r part of t he signature.i ntern elliptic curve scalar operation k • P with a random k for t It also requires t . he same k for he computation of k -1 (H(msg) + d • r) mod n with t t . he s part. intern If t . . ithm 4.5, it is highly possible that he scalar k • P is computed with algor t he system uses a conversion function φ(k) = k ′ to convert t he random nonc e k from	.	.	.	.	.
	.			.			.
	Montgomery ladder and t timated in t he case of ECDSA computations and other fault injections may allow he coherency checking countermeasures are two examples. intern The a binary representation to k ′ , t he signed representation required in t he algor ithm. intern In	.
		.	.	.			.
	problem of t recovering information in other parts of t he Montgomery ladder is that, depending on t he ECDSA. Similarly to side channel, while he scalar value, operations t his case, it is necessary to design such a function with inherent side channel and fault
	.	.			.		.
	may become useless to t fully recover sec r et information with fault injection is not obvious, it seems easy to re-he computation of t he correct result. intern Thus by injecting a fault, . . countermeasures. intern Indeed, t he carry attac . k against t he scalar blinding presented in [94]
			.	.		.	.
	attac cover at least partial information enabling mathematical attac . kers can detect t he particular value of t he scalar. intern While it cannot be expected to . ks and then to recover the is a good demonstration that any scalar manipulation can leak information through
			.			.
	fully recover t private key of ECDSA systems. intern Countermeasures against both side channel and fault he EC scalar value with t his method, it allows to get couple of bits. intern The side channel. intern While t he scalar blinding aims at avoiding leakage during t he EC scalar
		.	.	.			.
	coherency checking algor attac . ks are thus mandatory and should protect all t . ithm faces another problem that is due to t he sec r et bits. intern In t he scalar dependent . . he next chapter, computation, Fouque et al. intern demonstrated that a simple scalar addition with a random
							.	.	.
	update of a working register alongside t countermeasures attempting to cover all these threats are presented and discussed. intern he complexity of EC operation that allows value can put t he scalar at risk due to t he carry propagation between words.i ntern Indeed,
		.		.	.
	fault injection opportunities.i ntern By using a memory safe-error attac they show that t he carry can be detected thanks to side channel and then after many . k on an EC input
		.
	point of t experiment, t he point addition algor he number of time t ithm after it is used inside t . he carry is propagated depends on t he computation, attac he sec r et value kers	.	.	.
	.	.		.			.	.
	know if t and thus can be recovered. intern The fault countermeasure is also important in order to he register update corrects t he fault or not and thus can obtain t he scalar bit
	.			.			.
	value. The concept of dummy operand was introduced due, for example, to t guarantee that k and k ′ represent t he same value independently of t he representation he infinity
				.			.	.

. he intern

  1) k i .P //add or subtract P, depending on k i 5: end for 6: Q ← Q -P 7: return (Q) E should be subtracted from Q. intern This leads to two possibilities, if

	t	The idea behind our algor he infinity point as in t he standard double-and-add algor . ithm is to first initialize Q to a point E ∈ E(F q ) instead of . ithm. intern This will be transformed
				.	.
	to 2E during t	he loop due to t	he point doubling. intern In order to maintain t	he point E over
					.	.	.
	t	he loop indexes and reject t	he doubling effect,
				.	.

  By using P instead of P

	This proposed algor	2 , t ithm removes most problems encountered in t . his leads to algor ithm 5.1 that compute 2k • P . intern . . he basic double-and-
				.
	add. intern It ensures that no infinity point is used without forcing any bit of t	he scalar. intern The
				.
	operation flow is homogeneous and branches condition are removed.i ntern It is to be noted
	that algor	. ithm 5.1 avoids dummy operations that can be detected through safe-error
	attac	. ks, does not force any specific treatment on any bits and also minimizes t	he number
				.
	of required registers to prevent faults on unused memory values. intern Thanks to t	he use
				.
	. he addresses flow is constant and independent of t he algor of either +P or -P , t [95] as t	he scalar.i ntern The number of
				.	.
	working registers is t

. ithm is also immune to Address bit DP A (ADP A)

. he same than a standard double-and-right, left-to-right algor . ithm.

  necessary, pad 0s as k

	MSBs.
	1: Q ← [1 w-1 , ...1 1 , 1 0 ].P	//represents t	. he highest pre-calculated point.

2: for i = d -1 to 0 do 3:

  While elliptic curve point halving is possible, it requires to implement another specific operation and thus it is not efficient in term of required memory. intern Different simple other solutions exist. intern First, t . he less recommended solution would be to compute c = k • 2 -1 mod n prior using our algor • 2 -1 mod n is generated and saved in memory instead of k and taken into account if needed. intern For example, during an ECDSA signature, c can be generated using a random number generator. intern Then for t The s part can be changed into:s = c -1 (H(m) + d • r) • 2 mod n leading RandomAf f toJac() represents t .he common affine to Jacobian random representation conversion and provides countermeasure against data dependent leakage. intern Shuf f leregisters() is a function that randomly reassign P [0] and P[1] in order to avoid address dependent leakages. intern V erif y(Q) ensure that t Algorithm 5.4 2kP operation optimized with two precomputed points Input: k = (k t-1 , ..., k 1 , k 0 ) 2 , P and 2 t/2 P ∈ E(F q ) Output: 2k.P 1: r ← randombit() 2: P [r] ← 2 t/2 P -P //in affine coordinates 3: P [r] ← 2 t/2 P + P

	In t	his algor	. ithm, . . he input point is
	on t	he curve. intern Lines 12-14 aim to involve P [r] and P [r] in t	he result prior verification
								.	.
	for integrity check. intern Without these two operations, an attac	. ker can fault P [r] prior the
	last l bits of t	he scalar and use t	he consequences to detect l consecutive 1 inside the
								.	.
	LSBs (M-safe-error attac ks). intern This countermeasure does not consider transient faults .
	as only t	he value at t	he end is verified. intern
								.	.
								//in affine coordinates
	4: Q ← RandomAfftoJac(P [1]) 5: Verify(Q)	//use random affine to Jacobian conversion
	as presented algor 6: for i = t/2 -1 to 0 do 7:
								. ithms with c. intern This
	solution is not t	he best one as it extends t	he number of manipulation of t	he sec r	et k	.	.
								.	.	.
	thus extending t	he attac k surface (k is a sec . r	. et but also c in t .	his case). intern Another solution
								.	.
	would be to save P 2 in t	. he system instead of t	. he fixed base point P during t	he system	.
	development. intern However, t	his solution cannot be applied if algor	. ithms are intended to be
								.
	used with an elliptic curve point coming from outside t	he system (e.g. intern a Diffie-Hellman). intern
								.
	Finally, a last solution could be to consider during t et generation that k . . he sec . r . he r part of t . he signature, by using c with our algor ithms, k •P will . be returned. to t he good signature. intern This solution seems to be t he best as it can be applied to most
								.	.
	ECC schemes without extending t	he attac	. k surface nor requiring special computation
								.
	such as point halving. It is also to be noted that few exceptional cases exist within
	our algor	. ithms depending on t

3 The non-standard 2k • P result and exceptional cases Standard ECC schemes usually require t . he computation of k • P , instead of 2k • P . ithms. intern intern . he scalar. intern Indeed, per example, if n represents t . he ECC

  Jacobian to affine conversion ECC point additions and t/2 ECC point doubling operations while requiring 2 precomputed points. intern In a similar configuration, t ECC points to perform in t/2 ECC point doubling and ECC point additions. intern As t . he base point is fixed, precomputation cost is neglected.5.2.2 Sum of two scalars: k• P + v • G ECDSA verifications for example require t . he computation of k • P + v • G with always t .he same known ECC point P and G another ECC point representing a public key. intern that aims to simultaneously compute both scalar. intern In our implementation, we use Shamir's trick combined with our previous presented solution.intern The result is described by algor . ithm 5.5 and allows a speed-up with a factor of ×2 compared to two distinct classical ECC scalar operations. During t . he for loop, two bits of scalars are considered, one from k and another from v ending-up with four different cases. intern With t + ∞, Q + P , Q + G or Q + (P + G) are considered. intern In our

	16: Verify(Q) 17: return Q This algor ithm requires t/2 + 5 . . he classical . his case as t . he point G is not predictable. intern The best known solution to speed-up t . he computation is Shamir's trick [29] . he classic comb method would require 3 Usually precomputation is not convenient to use in t Shamir's trick, either Q case, t

. he four different cases become either Q -

  Jacobian to affine conversion Algorithm 5.6 kG operation computed as 2k

	described in algor	ithm 5.6.	.
	16: Verify(Q)
	17: return Q
	This algor	. ithm does not aim to improve t	he security level of t	he implementation
					.	.

  is used, he will obtain at most t + 32 bits and thus t bits will remain. intern The use of r aims to remove t + 26 ECC point additions and t + 16 ECC point doubling operations.intern The classic always double-and-add algor

	Algorithm 5.7 Field scalar operation
					Algor	. ithm 5.4 reduced for 32bits of scalar
		6: R ← AlgkP vG(k, G, v, Q) 7: return R	//Algor	. ithm 5.5 kP+vQ
		Indeed, algor	. ithm 5.5 security relies on indistinguishable point addition or subtraction
	and also indistinguishable use of P [0] or P [1] during each loop iteration. intern By using scalar
	splitting, attac kers will be forced to look for both information at t .	he same time. intern In
					.
	algor distinguish elliptic curve point addition from point doubling, he obtains at most t bits . . r . et are used instead of t. intern If an attac ker is able to ithm 5.6, 2 × t + 32 bits of sec	.
	of sec	r	. et meaning that t + 32 bits remain.i ntern Similarly, if an attac . ker is able to recover .
	which precomputed point . he probability dependence between bits that exist
	and can be used in t	he simple additive splitting as explained in [99]. intern The reduction to
					.
	a 32 bit loop should be carefully implemented by t	he designer. intern Indeed, if using an input
					.
	parameter to configure t	he loop size, he has to ensure that t	his entry cannot be faulted
					.	.
	in order to reduce t	he computation of a full size scalar to only 32 bits. intern Nevertheless, a
					.
	CFI should easily be able to detect any iteration errors within t	he loop.
					.
		This algor	. ithm requires t . ithm would be faster as only t
	ECC point doubling and additions would be required, however, algor	. ithm 5.5 uses a
	fully masked scalar. intern Scalar blinding technique could also be used alongside t	he classic
					.
	always double-and-add algor	. ithm. intern Nevertheless, a too small random used with t	he scalar
					.
	blinding may conduct to a partially masked scalar [100] due to t	he particular modulus
					.
	value or to bias t	he probability as described in [101] or also to face doubling attac	ks	.
					.
	due to t	he birthday paradox [102]. intern From [100], a N IST P256 implementation would
					.
	require a random on 64 bits leading to t + 64 ECC point doubling and additions. intern From
	t	his perspective,algor	. ithm 5.5 is around 15% faster. intern
					.

  Then lines 16 to 19 aim at checking t . he integrity of all tables which contain addition or subtraction possibilities. internUsing Y 1 instead of T 2 for intermediate value aims at ensuring that Y 1 is modified by EC scalar operation, X 1 and Z 1 should be modified accordingly to t

	t	he algor	. ithm thanks to t	he CF I. intern In order to pass t	he point verification at t	he end of
			.	.	.	.
	t			he modified
			.			.
	Y 1 . intern This ensure that either a point addition or a point subtraction is performed. In
	lines 5 to 9 two two-indexes tables are fulfilled with addition or subtraction possible
	values, for EC elements summed with field elements in one table (T 3 ) and field elements
	alone in t

he . he second (T 4 ). intern In line 11 t . he correct possibility, according to t .

Table 5 .

 5

	1: Algorithms summary

  Information security is a necessity and as it finally relies on IC, securing t he system is a necessity. intern This work focuses on hardware vulnerabilities (specifically non invasive attac . ks) of integrated circuits running ECDSA algor .ithms. internIt provides a study of existing ECC algor . ithms and schemes in order to demonstrate their vulnerabilities against such threats. intern Indeed, despite t ECC include countermeasures against side channel and fault attac es are available and without requiring any extended mathematical background.intern Experimental results with a widely used elliptic curve were provided in order to understand t . his threat. intern While existing side channel and fault countermeasures protect t . he EC scalar manipulation in overall, they can fail in specific cases.i ntern Thus, different side channel leakage sources that allow recovering information about t . he EC scalar have been described and demonstrated. intern While some leakages are already well known, such as t Demonstration was provided that leakages can be unintentionally inserted due to t . he choice of coordinates representation which result in having different "+" operations that can be distinguished. intern Various leakages due to t

		CHAPTER 6
		Conclusion
												he hard-
												.
		ware running t
		Number of sec r et bits Number of	.	.	t 1	t 1	t 1	t 1	t 1	t 2		1.5 • t (kP + λ • n) 2	2 • t + 32 2
		bit usecase Usecase repartition security weaknesses remain regarding t t t t	(add/sub, point selec.) t 2 / t 2 he computation of ECDSA signatures. intern This (add/sub, point selec.) ks, t t t/ t 2	.	(add/sub, point selec.) t/t
									.
		Nb of usecase to discriminate for attac is due to t he fact that t 1 . k	1 his cryptographic scheme is particularly sensitive, even to the 1 1 1 1 . .	2	2
		smallest leakages as they can be leveraged by mathematical attac	ks.	.
	117	We thus started by demonstrating that these mathematical attac to implement and exploit if partial information of t he ECDSA nonc ks are relatively easy .
												.
												he operation flow
												.
		that is scalar dependent inside t	he double-and-add EC scalar algor	. ithm, less obvious
								.
		leakage have been presented. intern
		-

(k

1 • P + k 2 (r • P )) . . he fact that many algor . ithms dedicated to . . he use of t . he infinity point have

  Hardware Countermeasures for ECDSA Cryptosystems Key Topics * Elliptic curve arithmetic * Lattice attac . k * Side channel leakages of few EC scalar bits * Safe-error on EC scalar to recover few sec

		r	et bits	.	.
	* Fault attac	k against t	he	.
						.
	ECDSA
	* Example of vulnerable
	architecture
	* Countermeasures
	Contenue clef
	* Arithmétique des courbes
	elliptiques
	* Attaque par réseau
	mathématique
	* Canaux cachés visant
	quelques bits du sec	r	et	.	.
	* Safe-error et récupération
	de quelques bits sec	r	ets	.	.
	* ECDSA et attaques par
	faute
	* Exemple d'architecture
	vulnérable
	* Contremesures

26: X

← X 3 -T 1 27: X 3 ← X 3 -T

28: T 3 ← T 3 -X 3 29: T 3 ← T 3 • T 2 30: T 4 ← T 4 • Y 3 31: Y 3 ← T 3 -T 4

List of Algorithms

List of Acronyms

EC scalar algor . ithms should be carefully chosen and provides side channel countermeasures which allow to protect every single bits of t . he scalar. intern As side channels are not the only non-invasive threat, t . he next chapter aims at studying how fault injection attac . ks can be used to also recover some bits of t . he EC scalar. intern Studying both is important as countermeasures against side channel or fault injection attac . ks should not jeopardize t . he security of each others.

If ±e is small enough, i.e. intern can be exhaustively tested, and t . he position l known, an attac . ker can try to compute all possible Q ′ = Q ± e • 2 l • P until t . he signature (r, s ′ ) can be verified from Q ′ and E(F q ). Once e is found, t . he verification will pass: k is also possible however it is not as simple. intern Indeed, some e values can be injected in different ways. intern As example, if we consider an 8 bits register that is faulted and e t . he error injected. intern Then e = +1 means that either t . he LSB flips from 0 to 1 or that it flips from 1 to 0 and t . he fault also flips bits according to a carry propagation (e.g. intern if 0x01 is faulted into 0x02, t . he error e is 1 while t . he LSB flips from 1 to 0). intern Both solutions are possible and depends on t . he fault model (i.e. intern one bit flip, multi-bits flip, flip only 0 to 1...). intern A +1 error may happen on any value, except on 255 as 256 cannot be encoded into t . he 8 bits register. intern The same applies for every possible e. intern It is interesting to notice that an 8 bits register allows encoding values from 0 to 255 and thus for each value a unique range of error is possible.i ntern E.g. intern he faulted register always end-up with a particular value or inside a set of value, then t . his can be detected and used (i.e. intern see section 4.2.4). The distribution should be uniform, however, due to t . he fact that two values of G ′ exist and conduct to recover either e or -e, t . he distribution is as depicted.i ntern It is the sum of two uniform distributions symmetrical to 0 centered around v -(2 m -1)/2 and -(v -(2 m -1)/2) and with a width of 2 m - While [START_REF] Barenghi | A novel fault attack against ECDSA[END_REF] demonstrates an approach to reveal partial information in t . he specific case where operand scanning multiplier is used, other method can be used to recover t . he information. intern Indeed, a similar approach as in section 4.2.2 can be used. Indeed, assuming d • r is faulted with a fault e then t . he ECDSA signature generation can be summarized as following:

-Generate a nonc

. he authors note that any group of w bits 00...01 can be replaced with a group of w signed digits 1 11 ... 1 with 1 = -1. intern This remark leads to a zeroless signed representation of t . he scalar k. intern An on the fly conversion is possible by initializing Q to t . he base point P and then by performing a for loop for all bits (except t . he LSB) that contains a point double Q ← 2Q and two Algorithm 5.2 ECC Jacobian-affine point addition/subtraction Input:

he zeroless signed representation works only for an odd scalar k thus forcing t . he LSB to one.i ntern Another downside of [START_REF] Goundar | Scalar multiplication on weierstraß elliptic curves from co-z arithmetic[END_REF] is that an on t . he fly conversion with pre-calculated points seems harder to implement. intern Also, as mentioned in Chapter 5, recoding t . he scalar value in a signed representation prior using t . he elliptic curve scalar operation may extends attac . k possibilities. intern Thus, our algor he security as no scalar extra manipulation is required and no scalar bit is constrained to any value while allowing performance/cost flexibility thanks to pre-calculation possibilities as presented in the next section. intern

Scalar operation with pre-calculation

When performance is needed, point precalculation is usually used. intern The number of precomputed points can be used to determine a trade-off between implementation cost and performance.i ntern In t . his section we present how our approach can be applied to the fixed-base comb method. intern This leads to similar performance with half of t . he required pre-calculated points. intern Compared to [START_REF] Hedabou | Countermeasures for preventing comb method against sca attacks[END_REF] et [START_REF] Dubeuf | Ecdsa passive attacks, leakage sources, and common design mistakes[END_REF]. intern The work presented in [START_REF] Fan | An updated survey on secure ecc implementations: Attacks, countermeasures and cost," in cryptography[END_REF] surveys different active and passive attac . ks, their prerequisites and countermeasures. intern Resource-restricted systems such as embedded system or smart-card need clever implementations in order to provide both functionalities and security with acceptable performance. intern

Suggestion of key generation to protect d:

-Select and store a random m

-Compute G = 2r 3 .P with P ∈ E(F q ) //Algor . ithm 5.4 reduced for 32bits of scalar he fault injection (i.e. intern is able to force a specific bit to 0 or 1 or fostering 0 to 1 transitions over 1 to 0 [START_REF] Courbon | Partial hardware reverse engineering applied to fine grained laser fault injection and efficient hardware trojans detection[END_REF] ) then he can get information with a safe-error principle and iteratively recover information. intern E.g. intern

Where ks. intern Indeed, as long as k i = 0 then lines 3 and 4 compute q ← 2.m and q ← 2.m -m. intern The redundancy of these operations can be detected leading attac . kers to conclude about t . he scalar length. intern Another side channel threat is how q ← q + (-1) k i .m is computed. intern Indeed, either the modular addition/subtraction is computed and then should not be different from a side channel point of view, or a two indexes table v

It is interesting to notice that even if a fault on v [0] or v [1] generates a different error on t . he result q depending on t . he value of k i , t . his difference is not usable by attac . ker to conclude about k i due to t . he random m. intern As an example, if u + m is faulted into u + m + e during t . he last loop iteration then if k 0 = 0 t . he final result will be Algorithm 5.9 EC and field scalar operation with a CFI Input: E(F q ), k = (k t-1 , ..., k 1 , k 0 ) 2 , P ∈ E(F q ) and m ∈ F q Output: 2k • P and 2k • m

(Q, q) ← double(Q, q) 10:

(Q, q) ← addsub(Q, P, q, u, m, k i , r) //if k i = 0, subtract else, add 11: end for 12: (Q, q) ← addsub(Q, P, q, u, m, 0, 0)

The functions double(Q, q) and addsub(Q, P, q, u, m, k i , r)