Damien Jauvart
email: damien.jauvart@univ-amu.fr

Nadia El Mrabet
email: nadia.el-mrabet@emse.fr

Jacques J A Fournier
email: jacques.fournier@cea.fr

Louis Goubin
email: louis.goubin@uvsq.fr

Nadia El Mrabet

Improving side-channel attacks against pairing-based cryptography

Keywords: Side-channel attacks, pairing-based cryptography, collisions attack, countermeasure

Side-channel attacks are a serious threat against secret data involved in cryptographic calculations, as for instance pairing-based cryptography which is a promising tool for the IoT. We focus our work on Correlation Power Analysis (CPA) attack against a pairing implementation. We improve a vertical sidechannel analysis attack and propose the first horizontal attack against a pairing implementation. First, we present a characterization of the multiplication that allows us to reduce by a factor of ten the number of side-channel traces required in order to perform a CPA attack against an implementation of Ate pairing. Secondly, we successfully attack the same implementation with only one trace by using the first horizontal attack path against pairing-based cryptography.

Introduction

The Internet of Things (IoT) is taking more and more importance in our daily life. It corresponds to numerous applications where the users' privacy and confidentiality must be guaranteed. In this IoT context, a major issue is the key generation. In a classical PKI model, the number of keys grows exponentially with the number of users [START_REF] Dumas | Architectures PKI et communications sécurisées[END_REF]. Pairing-based cryptography provides elegant solutions for the key management, through Identitybased cryptography, and also allows very interesting protocols such as short signature schemes or hierarchical encryption [START_REF] Dutta | Pairing-based cryptographic protocols: A survey[END_REF]. We study the resistance of a pairing implementation against side-channel attacks in the context of IoT, namely an implementation of an Identity-based protocol on an embedded system. We try to recover the secret decryption key used in an Identitybased Encryption (IBE) scheme.

Side-channel attacks, which aim at recovering secret data, are a serious threat against cryptographic embedded devices. Indeed, in the case of embedded systems, the attacker can easily gain physical access to the device in order to perform this attacks [START_REF] Coron | Statistics and secret leakage[END_REF][START_REF] Kocher | Differential power analysis[END_REF][START_REF] Mayer-Sommer | Smartly analyzing the simplicity and the power of simple power analysis on smartcards[END_REF].

Such attacks take advantage of physical information leakage during a computation. On a given embedded system, the leakage can be the execution time, the power consumption or the electromagnetic emission [START_REF] Kocher | Differential power analysis[END_REF][START_REF] Quisquater | Electromagnetic analysis (ema): Measures and counter-measures for smart cards[END_REF]. Side-channel attacks use the link between leaked data and the processed values in order to retrieve information about the secret. Besides, we consider that the device is fully under the control of the attacker who can thus run the same computation with many known inputs.

As IBE [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] systems are not immune to these threats, the vulnerability of the pairing computations used in IBE systems should be investigated. In this case, the decryption step is the target of the aforementioned sidechannel attacks.

A pairing is a bilinear map denoted e : G 1 × G 2 → G T , where G 1 , G 2 and G 3 are groups of prime order r. In practice G 1 and G 2 are sub-groups of an elliptic curve, G 3 is a sub-group of a finite field. Let U be the ciphertext, the decryption step during an IBE protocol consists in evaluating e(s, U ) where s ∈ G 1 is the secret key.

This critical operation was recently attacked through Correlation Power Analysis (CPA) [START_REF] Blömer | Improved Side Channel Attacks on Pairing Based Cryptography[END_REF][START_REF] Jauvart | Improving Side-Channel Attacks against Pairing-Based Cryptography[END_REF][START_REF] Unterluggauer | Practical Attack on Bilinear Pairings to Disclose the Secrets of Embedded Devices[END_REF] where the target was a modular multiplication calculation.

Studies on side-channel attacks share at least two important features: the comparison of side-channel leakage models [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] and the detection of points of interest related to the models [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF]. The statistical tests that are used in order to detect points of interest can also be considered as a way of validating the leakage model.

Our approach gives rise to a parametrized attack. Because of the large number of variables, we provide a detailed characterization of how side-channel attacks leak information about critical operations during pairing computations. In order to illustrate the application of our approach in the context of a cryptographic algorithms, we targeted one of the modular multiplications involved in the software implementation of an Ate pairing, the secret to be recovered being one of the two points involved in this pairing calculation.

Compared to the practical attacks against pairing calculations published so far [START_REF] Blömer | Improved Side Channel Attacks on Pairing Based Cryptography[END_REF][START_REF] Unterluggauer | Practical Attack on Bilinear Pairings to Disclose the Secrets of Embedded Devices[END_REF], our results, based on real electromagnetic measurements from the chip of an embedded 32-bit ARM core processor, require significantly less computational time in order to retrieve the secret value.

Our study proposes a generic method for attacking pairing implementations and defines parameters to increase a CPA's efficiency (namely the number of measurement curves needed). We use our method in order to develop, as far as we know, the first horizontal attack against a pairing implementation. Contrary to a classical vertical CPA that exploits several measurements at the same instant in time, a horizontal attack only uses one measurement curve at several instants. We illustrate the weakness of a pairing submitted to an horizontal attack and provide counter-measures in order to secure a pairing implementation. The horizontal approach is based on the fact that critical operations are performed several times during the same execution of the Miller algorithm. Measurements are selected at those moments to perform the attack. We also present the first electromagnetic attack against a protected pairing implementation.

The rest of the paper is organized as follows. Section 2 describes the mathematical background for pairings and an IBE pairing-based protocols. Section 3 contains a state of the art of the side-channel attacks against pairings. Section 4 describes improvements of the CPA attack against an unprotected pairing implementation. In Section 5 we provide an optimized side-channel attack, horizontal attack, against pairings with only one side-channel trace. Then, Section 6 shows different countermeasures from the literature and a collision attack to defeat one of them. Section 7 is devoted for a conclusion and prospect.

Cryptographic pairings

This section is divided into three parts: first the definition of a pairing, then the definition of the Ate pairing and the presentation of classical implementation tricks for pairings. The last part is a description of an Identitybased protocol: the Identity-based Encryption (IBE).

Elliptic curves and pairing definition

Let p be a large prime number. An elliptic curve E over the finite field F p is defined by the reduced Weierstrass equation as follows:

E(F p ) = (x, y) ∈ F 2 p |y 2 = x 3 + ax + b, for a, b ∈ F p ∪{O}, (1)
where O is the point at infinity. The curve E should be smooth. This condition is satisfied if the discriminant ∆(E) = -16(4a 3 + 27b 2 ) is not zero.

Elliptic curves E are used in cryptography because we can define a group law on the set of its points. We can perform the addition of two different points of E and the doubling of a point of E.

For efficiency reasons, we can use a projective representation of the points of an elliptic curve. Indeed, a pairing computation is based on a scalar multiplication over an elliptic curve. In affine coordinates, a scalar multiplication involves several inversions, which are expensive operations. We describe our attack using the Jacobian coordinates as they were proved to allow the most efficient pairing computations [START_REF] Beuchat | High-speed software implementation of the optimal ate pairing over barreto-naehrig curves[END_REF]. Since then, it appears that projective coordinates provide the most efficient pairing implementations [START_REF] Azarderakhsh | Fast software implementations of bilinear pairings[END_REF]. However, our methods and descriptions can easily be applied to any implementation of pairings using any system of coordinates. Indeed, the main ingredient of the attack is the interaction between secret data and public one during a multiplication over F p .

Among the points belonging to a curve E, we will work with points of order r (The order of a given point P is the smallest integer o such that [o]P = O.). The set of points of order r is denoted by E[r] = {P ∈ E|[r]P = O}. In practice we work on E[r] with r a large prime dividing the cardinal of E(F p ). We know that E

[r] ⊂ E(F p k ), for k > 1,
where k is the embedding degree, i.e. the smallest integer such that r divides p k -1.

Ate pairing and implementation

For the description of our physical attacks against pairing implementations, it is not necessary to provide all the theoretical details about the Ate pairing and we refer the reader to [START_REF] Hess | The Eta pairing revisited[END_REF] for a complete presentation. We only recall the definition of the Ate pairing. The sets G 1 and G 2 are sub-groups of order r of the elliptic curve E(F p k ), with r a large prime divisor of #E(F p k ) the cardinal of E(F p k ). The set G T is the multiplicative sub-group of the group of r-th roots of unity in

F p k . τ r : G 1 × G 2 → G T (P, Q) → (f t-1,Q (P )) p k -1 r , (2)
where t = p+1-#E(F p ) is the trace of E. The function f t-1,P is called the Miller function.

Efficient implementations of such pairing computation are achieved through the efficient Miller's function computation and the final exponentiation.

Miller's algorithm

The goal is to build a function f m,Q which can be efficiently computed for the integer m. To solve this problem, a recursive method was described by Miller in [START_REF] Miller | Short Programs for functions on Curves[END_REF], and is presented in Algorithm 1.

Algorithm 1: Miller's algorithm [START_REF] Miller | Short Programs for functions on Curves[END_REF] Input :

An elliptic curve E over F p , m = (m n-1 . . . m 0 ) 2 , P ∈ G 1 and Q ∈ G 2 . Output : f m,Q (P ). 1 f ← 1 ; 2 T ← Q ; 3 for i = n -2 to 0 do 4 f ← f 2 • l T ,T (P ) (tangent at T ); 5 T ← [2]T ; 6 if m i = 1 then 7 f ← f • l T ,Q (P ) (line through T and Q); 8 T ← T + P ; 9 return f ;
Equations of line and tangent in Jacobian coordinates. For efficiency reasons, the points can be represented with mixed affine-Jacobian coordinates for the addition and doubling of points in the elliptic curves. The equation of the line through T (in Jacobian coordinates) and Q (in affine coordinates) evaluated at the point P (also in affine), l T,Q (P ) is given by Equation 3.

l T,Q (P ) = (y P Z 3 T -Y T )(x Q Z 2 T -X T ) -(y Q Z 3 T -Y T )(x P Z 2 T -X T ). (3)
The tangent equation at point T evaluated at P is provided by Equation 4.

l T,T (P ) = 2Y T Z 3 T y P -2Y 2 T -(3X 2 T + aZ 4 T )(x P Z 2 T -X T ). (4)
Those equations provide the targets for our attack.

Final exponentiation

The final exponentiation to the power p k -1 r is generally decomposed into three simpler exponentiations, when k = 2δ:

p k -1 r = p δ -1 p δ + 1 Φ k (p) Φ k (p) r . (5)
where Φ k refers to the k-th cyclotomic polynomial. Computations of the final exponentiation are widely described in [START_REF] Scott | On the Final Exponentiation for Calculating Pairings on Ordinary Elliptic Curves[END_REF]. In this paper we focus only on Miller's algorithm, because the weakness of a pairing implementation against side-channel attacks are localized in this step. Indeed, the secret is directly used during the Miller algorithm. We do not use the final exponentiation in our attack path in consequence of what we do not give any details about its implementation.

Identity-based Encryption

An Identity-based Encryption (IBE) scheme can be used to implement a widely known issue in public key cryptography: the key exchange protocol [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. A Public-Key Infrastructure (PKI) based on IBE is scalable when compared to classical schemes using certificates, because precisely it does not require any certification [START_REF] Desmedt | Identity-based key infrastructures (iki)[END_REF]. The drawback is that the trusted authority must really be trusted and will not spy on the exchanges between Alice and Bob. For instance, the trusted authority can be the bank when Alice is a smart card and Bob a payment terminal.

In an IBE scheme, the public key is the user's identity. The associated private key is generated by the Private Key Generator (PKG) [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF]. All Identity-based protocols share one common feature: at a given time there is a computation of a pairing where one of the parameter is secret.

As illustration, we summarize the Boneh-Franklin IBE scheme [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] which is composed of four steps:

1. Set-up; 2. Extraction; 3. Encryption; 4. Decryption.

During the Set-up step, the PKG generates the public parameters for the pairing:

{r, n, G 1 , G 2 , G T , e, P, P P U B , H 1 , H 2 },
where H 1 and H 2 are two hash functions.

The extraction algorithm provides the user's private key denoted by d B (computed using the identity of Bob and securely transmitted to him by the PKG).

During the encryption step, Alice only uses the public key of Bob. She sends him U ∈ G 1 . Bob's private key is involved during the decryption step in the pairing computation. Bob computes the pairing e(U, d B ). Using this notation, the secret is the second input of the pairing. We will later discuss the influence of the secret position on the success of the attack.

The life cycle of the key When a Side-channel attack is performed, it is usually assumed that the secret is used more than once. We will consider this hypothesis for the classical CPA attack. However, in other scenarios1 , the key is used only once or a smaller number of times, so that the horizontal attack path becomes the only possibility for the attacker. We will show that horizontal CPA attacks are possible against a pairing implementation, even if the key is used only once.

Side-channel attacks against unprotected pairings implementations

In a pairing-based cryptographic protocol, the secret is one of the two points in the pairing's inputs. Attacks against the implementations of the pairing algorithms were first revealed by Page and Vercauteren [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF].

State of the art

Side-channel attacks against cryptographic algorithms have been widely studied for more than two decades [START_REF] Kocher | Differential power analysis[END_REF]. Public-key cryptosystems such as RSA or ECC were demonstrated to be vulnerable when submitted to SPA and different variants of DPA. The objective is to reveal the secret exponent (RSA) or the secret scalar (ECC) used in a signature or decoding cryptosystem [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF].

Several publications describe side-channel attacks against pairings over characteristics 2 or 3 fields. These studies are simply mentioned for reference, given that our implementation relies on large prime fields as described in Section 3.3. Page et al. [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] describe the principle of some physical attacks (passive side-channel and active attacks by injections of faults) on a pairing algorithm. They target the Duursma-Lee's [START_REF] Duursma | Tate Pairing Implementation for Hyperelliptic Curves y 2 = x p -x + d[END_REF] algorithm, which is used to calculate the Tate pairing on an elliptic curve over a finite field of characteristic 3. The manipulation of the data during the Duursma-Lee algorithm involves the product of a secret element with a value derived from the known input point of the pairing. The authors propose a SPA-like attack against modular multiplication algorithms which are implemented with the shift-and-add method. Furthermore, they describe a SPA attack which aims at getting the secret bit by bit. Kim et al. [START_REF] Kim | Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields[END_REF] propose temporal attacks, SPA and DPA to target the arithmetic operations which are involved in a pairing over curves in characteristic 2. In the context of the Eta pairing on binary fields, the targeted operation is a(b + r), where a and b are derived from the secret, and r is derived from the known input. The authors conclude that, in theory, the DPA bit by bit proposed by Page et al. [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] could again recover the secret point used in the pairing computation. Pan and Marnane [START_REF] Pan | A correlation power analysis attack against Tate pairing on FPGA[END_REF] propose a practical CPA attack based on a Hamming distance model against the Eta pairing over fields of characteristic 2 based on supersingular curves.

One of the first articles describing side-channel attacks against pairings of large characteristic field was proposed by Whelan et al. [START_REF] Whelan | Side Channel Analysis of Practical Pairing Implementations: Which Path Is More Secure?[END_REF]. They describe a CPA targeting the arithmetic operations to recover the secret. For the calculation part of their CPA, they propose the following plan: calculations of the correlations between the hypothetical outputs of the arithmetic operation x × k for all the possible keys k and the leakage traces. For every key assumption, there is a correlation curve. The candidate key is the one providing the curve with the highest peak. In the same paper, the authors discuss the use of the words length [START_REF] Brier | Correlation power analysis with a leakage model[END_REF][START_REF] Mrabet | A Practical Differential Power Analysis Attack Against the Miller Algorithm[END_REF][START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] or 64) to represent multiprecision numbers. Indeed, they detail the computations of partial correlations which can be used by a CPA to target a part of the word. Especially, if the target is a 32-bit architecture, the enumeration of sub-keys should be made on 2 32 elements, which is considered as unreasonable today. So, it is necessary to target a part of these 32 bits, for example the least significant bytes, and thus to work with partial correlations. El Mrabet et al. [START_REF] Mrabet | A Practical Differential Power Analysis Attack Against the Miller Algorithm[END_REF] propose a simulation of the attack against the Miller algorithm of the pairing over the field F 251 . The equation of the tangent is targeted because it contains a modular multiplication of a coordinate derived from a public input point by a deterministic value derived from the secret point.

Ghosh et al. [START_REF] Ghosh | Security of prime field pairing cryptoprocessor against differential power attack[END_REF] detail a DPA against the modular subtraction in a Tate pairing implemented on a Barreto-Naehrig [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF] elliptic curve. Blömer et al. [START_REF] Blömer | Improved Side Channel Attacks on Pairing Based Cryptography[END_REF] describe side-channel attacks against the modular additions and multiplications of elements in large prime characteristics. Just as El Mrabet et al. [START_REF] Mrabet | A Practical Differential Power Analysis Attack Against the Miller Algorithm[END_REF], they show that these attacks are possible even if the secret point is used as the first argument of the pairing computation. The authors illustrate their results on simulations. Indeed, they use simulation traces with a Hamming weigh model perturbated by a Gaussian noise. Unterluggauer and Wenger [START_REF] Unterluggauer | Practical Attack on Bilinear Pairings to Disclose the Secrets of Embedded Devices[END_REF] publish the first practical attack against a pairing in large prime characteristic fields. They use a CPA-like approach, as previously described by Whelan et al. [START_REF] Whelan | Side Channel Analysis of Practical Pairing Implementations: Which Path Is More Secure?[END_REF]. The authors target the modular operations during an Ate pairing in order to first find the secret 16 least significant bits and then the 16 most significant bits. They work on a 32-bit architecture and take advantage of the processor working with a 16-bit multiplier. Their configuration require more than 1500 traces to find the secret point. In 2016 the importance of implementing countermeasures is supported by the results of Jauvart et al. [START_REF] Jauvart | Improving Side-Channel Attacks against Pairing-Based Cryptography[END_REF], where attacks are presented in a real world environment. Indeed, Ate pairings implemented on ARM Cortex-M3 have been broken efficiently with CPA attacks with approximatively 150 traces.

Details on classical attacks

We describe the attack principle against Miller's algorithm implemented with the Jacobian coordinates.

Case 1: Q is known and P is secret

The numerator of the tangent equation is

2Y T Z 3 T y P - 2Y 2 T -(3X 2 T + aZ 4 T )(x P Z 2 T -X T ).
The coordinates of the secret point P are involved in 2Y T Z 3 T y P and x P Z 2 T . These coordinates are attacked by a CPA against the modular multiplication. The coordinates of the point T = (X T : Y T : Z T ) are known because they are initialized with those of the known point Q.

Case 2: P is known and Q is secret

In this case, the targeted equation is the same, we consider them at the first iteration of the Miller algorithm. Then, the coordinates of the point T are exactly the coordinates of the point Q, i.e. T = (x Q : y Q : 1). Then the targeted tangent equation is 2Y

T y P -2Y 2 T - (3X 2 T + a)(x P -X T ).
The attacker is able to perform an attack against the modular multiplication Y T y P in order to find Y T = y P . He then uses the equation of the elliptic curve to find x Q . He finds several candidates x 1 , x 2 , x 3 , because of the degree of the equation to be solved, he can test them until he finds the same result of the pairing together with the secret x Q .

Target description

In order to implement some attacks in a real world environment, we use a real embedded device as target.

Pairing implementation under tests. We use our own software implementation of the Ate pairing over Barreto-Naehrig curves [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF]. For such curves we recall that the parameters are p, r and the trace t defined with :

     p(x) = 36x 4 + 36x 3 + 24x 2 + 6x + 1, r(x) = 36x 4 + 36x 3 + 18x 2 + 6x + 1, t(x) = 6x 2 + 1. (6)
We choose to use x = 0x3FC0100000000000 given in hexadecimal form. The elliptic curve is E :

y 2 = x 3 + 5.
The tower field extension uses to build the field F p 12 is:

F p 2 F p [u] /(u 2 -β), F p 6 F p 2 [v] /(v 3 -u), F p 12 F p 6 [w] /(w 2 -v), (7)
where β = -5 is a non quadratic residue in F p , with u a non cubic residue in F p 2 and v a non quadratic residue in F p 6 .

The representation of the points is performed via the following system coordinates:

-P ∈ E (F p ) is in affine coordinates. -Q ∈ E 2 F p 2 is in affine coordinates. -T ∈ E 2 F p 2 is in Jacobian coordinates..
The computations for the doubling and addition of points over the elliptic curve are then performed with the tangent and line evaluation method, in what is called mixed coordinates.

Device under test. The target is a 32-bit microcontroller, implemented in 130 nm CMOS technology. This basic integrated circuit has no physical protections against Side-channela ttacks. This is an ARM Cortex-M3. The processor is clocked at 24 MHz. The sampling frequency of the oscilloscope is 4 giga samples per second. We target the modular multiplications. One multiplication takes 5 ms, then it is sampled over 20 million points.

Remark concerning recent attacks against the discrete logarithm problem. First, the curves implemented over binary and ternary fields are definitively to be avoided for cryptographic uses [START_REF] Joux | The Past , evolving Present and Future of Discrete Logarithm[END_REF]. We have to use large prime characteristics. Recent constraints are published in [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF][START_REF] Kusaka | Solving 114-bit ecdlp for a barreto-naehrig curve[END_REF] and new curve parameters are recommended. In a few words, the size of the parameters (256 bits for p and r and our case) must be expanded to 460-bits at least [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF] for BN curves. For the 128-bit security level, the curves providing the most efficient implementation seem to be the KSS16 family. Nevertheless, the algorithm implementation structure remains identical to our implementation. Mainly, the targeted operation for side-channel attacks, the modular multiplication, can still be computed with the CIOS multiprecision multiplication of Montgomery [START_REF] Koc | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF]. Even if another modular multiplication is implemented, our attack path remains successful. As a consequence, even if the parameters we use are no longer up to date, the success of our attack will be the same using new parameters.

Attacking the modular multiplication

The targeted modular multiplication a × b mod p is the CIOS multiprecision multiplication of Montgomery [START_REF] Koc | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF]. It is often chosen for cryptographic applications, and finally, this choice does not affect the attack strategy. It is necessary to identify the operation which involves both a and b. In the case of the CIOS method, we have the calculation (uv) ← c j + a j b i + u. The choice of the algorithm for the modular multiplication (SOS,CIOS,FIOS,FIPS,CIHS [START_REF] Koc | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF]) does not change the target; it is still the multiplication of two machine words a j b i . The calculation of the intermediate variables, for example c j and u must be adapted. We recall the CIOS method in Algorithm 2. We use the following notations: W is related to the architecture size, W = 2 32 bits in our case. A long integer is represented by N words, in the case of 256-bits integer, we have 256 = 32

1 c ← 0 ; 2 for i = 0 to N -1 do 3 u ← 0 ; 4 for j = 0 to N -1 do 5 (uv) ← c j + a j b i + u ; 6 c j ← v ; 7 (uv) ← c N + u ; 8 c N ← v ; 9 c N +1 ← u ; 10 m ← c 0 p 0 mod W ; 11 (uv) ← c 0 + mp 0 ; 12 for j = 1 to N -1 do 13 (uv) ← c j + mp j + u ; 14 c j-1 ← v ; 15 (uv) ← c N + u ; 16 c N -1 ← v ; 17 c N ← c N +1 + u ; 18 if (c N -1 . . . c 0 ) W < p then 19 c ← (c N -1 . . . c 0 ) W ; 20 else 21 c ← (c N -1 . . . c 0 ) W -p ; 22 return c ;

Attacks against 32-bit multiplications

There are two distinct cases to be studied:

-Either b is known and a is secret.

or a is known and b is secret.

Case 1: b is known and a is secret. The first iteration of the CIOS algorithm corresponds to the indexation i = j = 0. The targeted instruction is (uv) ← a 0 b 0 , the multiplication of two machine words is already attacked in [START_REF] Blömer | Improved Side Channel Attacks on Pairing Based Cryptography[END_REF][START_REF] Mrabet | A Practical Differential Power Analysis Attack Against the Miller Algorithm[END_REF][START_REF] Unterluggauer | Practical Attack on Bilinear Pairings to Disclose the Secrets of Embedded Devices[END_REF][START_REF] Whelan | Side Channel Analysis of Practical Pairing Implementations: Which Path Is More Secure?[END_REF]. It is a CPA where the target is the result of the multiplication of machine words. The predictions of the multiplication between the inputs (one seen as a secret key, the other as a known data) are correlated with the measurements traces. The attack allows to recover a 0 . The targeted word is now a 1 , it is manipulated for i = 0 and j = 1, the targeted instructions (uv) ← a 1 b 0 + u, where u is the carry of the previous operation, i.e. (uv) ← a 0 b 0 , thus u is known. It is then possible to use a CPA in order to find a 1 . Other words of a = (a n-1 . . . a 0 ) 2 32 are recovered in the same way. We have to consider the carry as the information leakage is due to access to memories and more particularly the write-back on the memory.

Case 2: a is known and b is secret. This case targets the words b i , it requires a more thorough study of the algorithm because the index i is the one of the main loop. The first iteration (i = j = 0) produces the operation (uv) ← a 0 b 0 , which allows to find b 0 as previously described. In order to identify the carry u through the iterations, we denote it by u 00 .

The target is the word b 1 . It is involved in the instruction (uv) ← c 0 + a 0 b 1 . The word a 0 is known, we are still left to see if we can predict c 0 .

This word c 0 comes from the instruction c j-1 ← v of the CIOS algorithm for i = 0 and j = 1. At first, there is the calculation (uv) ← c 1 + mp 1 + u, afterwards, the instruction c 0 ← v. Then we have to verify that the words c 1 , m and u are known (p 1 is obviously known since it depends on the modulo p). The Table 1 shows the dependence between the intermediate variables and how we reach in c 1 , m and u.

c 1 a 1 b 0 + u 00 a 1 , b 0 , u 00 - u c 0 + mp 0 - c 0 , m m c 0 p 0 mod 2 32 p 0 c 0 c 0 a 0 b 0 a 0 , b 0 -
4 Reducing the number of traces for CPA against pairings

The state of the art presented below shows how the classical attacks can be used to recover the secret input of a pairing function. However few practical validations of these attacks have been performed up to now. In this section we present the most effective known attack [START_REF] Jauvart | Improving Side-Channel Attacks against Pairing-Based Cryptography[END_REF] and describe the advanced techniques we use to make it powerful. Our method improves the efficiency of the attack as concerns the number of traces (factor 10) and the necessary resources.

Attack scheme

In order to recover the 32 bit of a secret operand κ involved in multiplications x (i) × κ for known κ, we proceed with a divide-and-conquer strategy.

In a first part, we describe the attack path on a word of size 2z. We first attack the z least significant bits, and then the z most significant bits. Figure 1 illustrates this principle. The method is the following:

1. We enumerate the 2 z key hypotheses on z bits (this set is denoted by K 0 ) and apply a CPA attack: for each hypothesis, we compute the intermediate variable (for each plaintext) and the correlation between each predicted intermediate variable and the sidechannel observation. We keep the α best key hypotheses which maximize the correlation. The set of hypotheses is denoted by K 1 = {κ 1,1 , . . . , κ 1,α }. 2. We enumerate the 2 z most significant bits from κ 1,i ∈ K 1 hypothesis, and we apply a CPA. For each i = 1, . . . , α, we compute the 2 z key hypotheses:

κ 2,i,j = (j 7 , . . . , j 0 ) 2 j=0,...,2 z -1 radix 2 κ 1,i .
The hypotheses of L i = {κ 2,i,0 , . . . , κ 2,i,2 z -1 } are on 2z bits: for each of them, we compute the correlation with the measured traces. Thereafter, for i = 1, . . . , α we hold the α best key candidates and store them in L i . 3. The key in ∪ α i=1 L i with the best correlation is the key candidate for the 2z secret bits. First, we compute a CPA-based characterization on 32 bits. Then, we compare two Hamming weight leakage models on 8 bits, and we finish by the CPA attack with the best models against the 32 secret bits. The choice of the model on 8 bits was determined by an exhaustive research. We also tried z = 4, 6, 12 but the attack were not successful.

CPA characterization on 32 bits

For this characterization step, some key hypotheses are randomly chosen on 32 bits, knowing that the secret key is among them. To predict an intermediate step we compute φ(κ, x) the Hamming weight of x and κ, where x is the plaintext and κ is the key hypothesis, the result is a 32-bit integer. Among the different key hypotheses, the correct secret key has the highest correlation. Figure 2 shows the correlation of the good key in bold, it is clearly higher than the other ones.

Hamming weight models

In practice, since it is not possible to enumerate the 2 32 key hypotheses, we start with the z = 8 least significant bits. Then, κ is on z bits, the plaintext can be taken on 32 bits, so the product result is either on z bits or on 2z bits as shown in Figure 3.

Fig. 3: Leakage models

We estimate both leakage models previously introduced by means of the t-test. This statistical test was introduced for the detection of points of interest by Gierlichs et al. [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF] under the name of SOST (Sum Of Squared pairwise T-differences). For that purpose, we use the previous measurements. The key κ is fixed and the messages are changed. We fix z = 8 bits. For each trace, the calculation of φ(κ, x) returns a set. In the end, the size of every set is denoted η φ,i , i = 1, . . . , N φ . In the case of the first model there are N φ1 = 9 sets (9 possible Hamming weights for 8 bits). And for the second model N φ2 = 17. For each set, the average m φi and the variance σ 2 φi are computed. The SOST is then obtained using Equation 8:

SOST φ = N φ i,j=1     m φ,i -m φ,j σ 2 φ,i η φ,i + σ 2 φ,j η φ,j     2 for i ≥ j. ( 8
)
The results of the t-test for both models are provided in Figure 4. For this figure, a zoom is made on the part containing the leakage. The leakage is further highlighted when the second model is used: the peak is more narrower and also higher.

Practical results

We have to analyze the number α of key candidates after each intermediate attack. Unterluggauer and Wenger [START_REF] Unterluggauer | Practical Attack on Bilinear Pairings to Disclose the Secrets of Embedded Devices[END_REF] only tested the values α = 5 and α = 10, which did not show any differences. However, we demonstrate that for a fixed number of traces used for the attack, the success rate increases with α [START_REF] Jauvart | Improving Side-Channel Attacks against Pairing-Based Cryptography[END_REF]. In Figure 5, for example, for a database of 80 traces, with α ≥ 40 the success rate of the attack is above 90%. For 170 traces, the attack has a success rate of 100% as soon as α ≥ 28.

The attack against an operand of the multiplication of machine words is efficient whatever the position of Fig. 5: Attacks results for some values of α the secret. With the results of Section 3.5 we are able to attack a modular multiplication, in particular when it is implemented in CIOS. Since the attack against pairing targets the modular multiplication, this attack is able to effectively recover the secret pairing input point.

Table 2 shows the differences when recovering a 32bits word. "Time" denotes the number of enumerated keys and "Memory" is the number of keys which are temporarily stored.

Horizontal attack against pairings

As presented in Section 3, a classical side-channel attack exploits several traces at the same time. The points of interest are the window corresponding to the targeted operation processed by the integrated circuit. The horizontal approach is the following: a critical operation is performed several times within the same execution of the algorithm. The targeted window is repeated, the traces are then selected at these times in order to make a CPA-like attack (for instance) [START_REF] Bauer | Horizontal and Vertical Side-Channel Attacks against Secure RSA Implementations[END_REF][START_REF] Clavier | ROSETTA for Single Trace Analysis[END_REF]. The structure of the Miller algorithm is asymmetric in P and Q. More precisely, the temporary point T , which is allocated to the value of Q at the beginning of Miller's algorithm, is going to evolve during the iterations. The study of this structure allows us to identify a weakness. This is the first horizontal side-channel attack against a pairing implementation.

Weakness in the Miller algorithm

The computation of the tangent equation, in mixed affine-Jacobian coordinates (Equation 4), involves a multiplication between x P and Z 2

T . An execution of the Miller algorithm comprises n -1 iterations, thus n -1 calculations of tangent, and thus n -1 multiplications

x P × Z 2
T with a fixed x P and different Z T . In case the point P is the secret, each execution of a pairing allows to observe n -1 multiplications which involve x P and a known integer. The attack becomes a classic CPA with n -1 traces.

This weakness only appears when the point P is secret (notation for an Ate pairing e(P, Q)).

If the secret is the point Q, this point is modified at each step of the Miller algorithm. The only operations involving the coordinates of Q occurs during the addition step. Roughly, the number of addition steps is half the number of doubling steps. We will first describe the horizontal attack in the most favorable set-up, i.e. when P is secret. We will later discuss the case where Q is secret.

Practical validation of the horizontal attack

Our target is an Ate pairing, whose structure is similar to the Tate pairing. It is an optimized version, which uses twice less iterations for the Miller loop. The number of iterations is 126 for the used Barreto-Naehrig curves [START_REF] Barreto | Pairing-Friendly Elliptic Curves of Prime Order[END_REF], we thus obtain 126 traces of Montgomery's modular multiplications a × b mod p with b being the secret.

As illustrated in Figure 5 we can see that a small number of traces is sufficient for a successful attack. Namely the number of traces can easily been chosen under 126.

The attack context is the second case of Section 3.5. We choose a small value for α in the first place: α = 8. This small value is among the ones which requires the smallest resources to make the attack successful. As the attack with α = 8 allows to find the secret b, it is thus useless to make other attacks with α > 8.

Figures 6 to 9 show the results of the attacks for the secret word b 0 of b = (b N -1 . . . b 0 ) 2 32 . More precisely, Figure 6 gives the results of the correlations af-ter the first sub-attacks. The bold thick curves represent the correlations for the correct secret sub-key on 8 bits (b 0,7 . . . b 0,0 ) 2 : it is among the best hypotheses. Figure 7 represents the correlations after the second sub-attacks. Then the following attack is exposed in Figure 8. Finally the last sub-attacks are represented by Figure 9. In the last sub-attack (Figure 9) the bold thick curve has the highest amplitude, this provides the corresponding key hypothesis returned by the attack. Thus the attack allows us to recover the secret word b 0 . The results are similar during the attack against the other words b N -1 , . . . , b 1 . Our horizontal attack recovers the entire secret key using only one Ate pairing execution.

Discussion

In the presented attack carried in a real target we recover the secret integer (256 bits) with just one Atepairing execution. This is due to the use of our horizontal attack. This attack exploits the Miller loop's structure composed of 126 iterations. In the case of an Optimal-Ate pairing, the number of iterations is lower (which makes the algorithm more efficient). Let us see whether this optimization prevents our horizontal attack. The Optimal-Ate pairing over BN curves with the same security parameters gives a loop of at least However, recent attacks on the discrete logarithm [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF][START_REF] Kusaka | Solving 114-bit ecdlp for a barreto-naehrig curve[END_REF] indicate that the lengths of the parameters need to be increased. Then, for BN curves, the bitlength of r is now 460 bits instead of 256. The number of iterations in the Miller algorithm to compute the Optimal-Ate pairing is then 460 4 = 115. By putting this value in Figure 5 we see that our CPA attack when P is secret, for α = 64, gives a success rate of 97% for 110 traces. This suggests that it is always possible to make such an horizontal attack. According to the analysis made by the authors in [START_REF] Kim | Extended tower number field sieve: A new complexity for the medium prime case[END_REF], for a 128-bit security level, the curve providing the most efficient implementation should be the KSS16 family. The optimal Ate over this family is performed in 77 iterations. It appears from Figure 5 that with 77 iterations of the Miller algorithm, the success rate of our attack is at most 90%. As a consequence, in order to be sure to recover the correct key, the easy way would be to perform a horizontal attack using 2 measurement curves. Alternatively, we can try to obtain partial results for the key, and use a brute force approach for the remaining 20 bits.

If the secret is the point Q, we only have φ(λ) slots for performing the CPA attack, where λ represents the number of iterations during the Miller algorithm and φ the Hamming weight function. If the key is ephemeral and used η times, the attack would be successful if η ×λ is greater than 110.

Attack against protected implementation

We saw in Sections 4 and 5 that unprotected pairings do not resist to side-channel attacks. First, we illustrated how to reduce the number of traces needed to successfully complete an attack, and then we showed the efficiency of a horizontal attack scheme. It is therefore more important than ever to protect such implementations. We recall existing countermeasures and demonstrate that some of them are not effective. We present here the first real attack by electromagnetic observations against a protected pairing implementation.

Guide of existing countermeasures

W can find in the literature two categories of countermeasures for pairing implementations: external or internal ones.

External countermeasures

The first countermeasure is proposed by the authors of the first attack. Page and Vercauteren [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] suggest to exploit the bilinearity property of the pairings. If a and b are integers coprime to r, then e([a]P, [b]Q) 1/ab = e(P, Q). The countermeasure uses this randomization so that the attacker loses the knowledge of the coordinates of the public point. The calculation of e(P, Q) is replaced by Algorithm 3. We shall name this countermeasure "multiplicative masking". We can omit the exponentiation at the power 1/(ab) if we choose a and b such that ab = 1 mod (r). The second countermeasure of Page and Vercauteren [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] consists in using an additive mask. For example, if Q is the secret, then the point P will be masked as follows: e(P, Q) = e(P + R, Q)e(R, Q) -1 or e(P, Q) = e(P + R, Q)e(-R, Q) for a random point R ∈ G 1 \ {O, -P }. Algorithm 4 describes the principle of this countermeasure by additive masking.

Input : P ∈ G 1 et Q ∈ G 2 .
Output : e(P, Q).

1 a and b are two integers such that ab = 1 mod r ;

2 P ← [a]P ; Q ← [b]Q ; 3 h ← e(P , Q ) ; 4 return h ;
Algorithm 4: Second countermeasure of Page et al. [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF] Input : The secret point Q ∈ G 2 and P ∈ G 1 .

Output: e(P, Q).

1 R ∈ G 1 \ {O} is randomly chosen ; 2 P ← P + R ; 3 h 1 ← e(P , Q) ; 4 h 2 ← e(-R, Q) ; 5 h ← h 1 h 2 ; 6 return h ;

Internal countermeasures

Kim et al. [START_REF] Kim | Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields[END_REF] proposed the use of the third countermeasure of Coron [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. Indeed, the aim is to take advantage of the representation of points in projective coordinates. Let us assume that the Miller algorithm is implemented in projective coordinates. Instruction 2 of Algorithm 1 initializes the point T with the coordinates of P as follows:

X T ← x P ; Y T ← y P and Z T ← 1. ( 9
)
This initialization is replaced by: i. λ is randomly choosen in F p ;

ii. X T ← λx P ; Y T ← λy P and Z T ← λ.

In this cas, the output of the pairing calculation is equal to the output without randomization, because the final exponentiation maps all the elements of F p to 1, which applies to the mask λ. This countermeasure, based on the randomization of the coordinates, is less expensive: it requires only two additional multiplications in F p . The protection method proposed by Scott [START_REF] Scott | Computing the Tate pairing[END_REF] is rather similar because it is based on the idea that it is possible to multiply by an element of F p without adjustment on the input. It suggests masking the sensitive calculations, that is the multiplications between a known and a secret operand, by applying the multiplicative randomization by λ ∈ F p .

This countermeasure is applied to randomize the public point P . This operation of randomization appears during the initialization of the temporary point T with P . A weakness appears at this moment. In Jacobian representation, the coordinates of a given point are not unique, indeed they satisfy the equation

(x, y) = XZ 2 : Y Z 3 : Z , ∀Z = 0. ( 11
)
The principle of the countermeasure is to make the affectation of T with one λ ∈ F p different at each execution. The resulting Miller algorithm with this countermeasure is described by Algorithm 5.

Algorithm 5: Miller algorithm with randomisation of mixed coordinate affine-jacobian (Q is secret)

Input : An elliptic curve E : y 2 = x 3 + ax + b over F p , m = (m n-1 . . . m 0 ) 2 , P ∈ E F p k [m] et Q ∈ E F p k . Output : f m,P (Q) with div(f m,P ) = m(P ) -(mP ) -(m -1)(O). 1 f ← 1 ; 2 λ ∈ F p is randomly chosen ; 3 T = (X T : Y T : Z T ) with X T ← x P λ 2 ; Y T ← y P λ 3 ; Z T ← λ ; 4 for i = n -2 to 0 do 5 H ← 4X T Y 2 T ; I ← 3X 2 T + aZ 4 T ; 6 X T ← -2H + I 2 ; 7 Y T ← -8Y 2 T + I(H -X T ); 8 Z T ← 2Y T Z T ; // Updating T (Doubling) 9 l T ,T (Q) ← 2Y T Z 3 T y Q -2Y 2 T -I(x Q Z 2 T -X T ) ; // Tangent evaluation 10 f ← f 2 l T ,T (Q) ; 11 if m i = 1 then 12 A ← y P Z 3 T -Y T ; B ← x P Z 2 T -X T ; 13 X T ← A 2 -B 2 (X T + x P Z 2 T ) ; 14 Y T ← B 2 (A(X T -X T Z 2 T ) -BY T ) ; 15 Z T ← Z T B ; 16 ; // Updating T (Addition) 17 l T ,P (Q) ← B(Z 3 T y Q -Y T ) -A(Z 2 T x Q -X T ) ; // Line evaluation 18 f ← f l T ,P (Q) ;
19 return f ;

Provided protection with state of art countermeasures

The target of a vertical CPA attack is the modular multiplications between coordinates depending on the secret Q and known integers. In Algorithm 5, the operations which involve x Q and y Q are the following:

-2Y T Z 3 T y Q = h(T ) × y Q , where h depends only on T . -x Q × Z 2 T . -Z 3 T × y Q . -Z 2 T × x Q .
All these multiplications are made between coordinates of Q and for random (unpredictable) integers. Indeed, the coordinates of T are not known and the CPA cannot be applied any more to find the secret Q because the predictions on the intermediate variables are no longer possible. Indeed, λ ∈ F p takes a random value in {1, . . . , p -1} thus λ 2 has p-1 2 possible values, which implies that X T ← x T λ 2 is an unpredictable value among a set of cardinal p-1

2 . The values of X T , Y T and Z T being unpredictable, it is not possible any more to predict the internal states of the algorithm, and thus to achieve the CPA.

Aimed target

In the scenario of the IBE, the decryption of the ciphertext {U, V } by Bob involves the step K = e(U, d B ) where d B is the secret key of Bob. If Bob loses the device where e(U, d B ) is executed, then an attacker can control the input U which is manipulated. The flaw that we present here comes from paper [START_REF] Jauvart | First Practical Side-Channel Attack to Defeat Point Randomization in Secure Implementations of Pairing-Based Cryptography[END_REF] which describes in details the technical aspects.

The calculation K = e(U, d B ) is computed with the Miller algorithm, where the countermeasure using coordinates randomization is used as presented in Algorithm 5.

Let us linger over the randomization operations and the calculation of the tangent in the first iteration. The randomization of the known point P is made in line 3, which involves the operation X T ← x P λ 2 . In the computation of the tangent in the first iteration, the calcu-

lation x Q Z 2
T is performed with Z T = λ. Both executed operations are multiplications between a known coordinate (x P ) with a mask λ = λ 2 , then a secret coordinate (x Q ) with the same mask. In the following the notation λ replaces λ for more readability.

As a consequence, if x P = x Q then the same calculation is executed twice. If the side-channel allows to identify such a situation thanks to a technique of collision detection, the attacker is able to recover the secret x Q . This value is the same as the coordinate x P , which is known.

If the values of x P and x Q are equal (or partially equal) then the measured EM/power traces are similar. The data x P and x Q are multiprecision integers, for example 8 words of 32 bits. Thus it is impossible to test 2 256 values for x P . However, the device computes the modular multiplication by handling the words individually and in a deterministic way. For example, Montgomery's modular multiplication occurs at a precise instant in time, to do the multiplication x 0 λ 0 (here we denote x = x P to ease the reading). Even with this re-mark, the attack would consist in making an exhaustive search on 32 bits. As for the CPA, the attack against 32 bits is made byte by byte. That's why the words x 0 and k 0 are said to be partially equal if they have their least significant bytes identical (k corresponds to the secret coordinate, that is x Q ).

The remaining part of this section is devoted to the detection of similarities between two words x 0 and k 0 during their manipulation in a multiplication with the same unknown integer λ.

Attack schemes against a protected implementation

In order to exploit the above attack, the naive approach for correlation computations can be considered. Let c (i,j) denotes the correlation coefficient between traces C (i,j) x and C (i,j) k , corresponding respectively to the operations x (i) 0 λ (j) 0 and k 0 λ (j) 0 . With this tool, a sketch of the attack is given by Algorithm 6, where N is the number of repetitions which the attacker can make with the same message x (i) 0 . After having kept N measurements, the cross correlation coefficients are calculated, then averaged. Concretely, taking the average of the correlations rather than the traces is useful to give a value of the real similarity between the operations x ;

6 c (i,j) ← ρ C (i,j) x , C (i,j) k ; 7 c(i) ← 1 N j c (i,j) ; 8 k ← arg max |c| ; 9 return k ;
In [START_REF] Jauvart | First Practical Side-Channel Attack to Defeat Point Randomization in Secure Implementations of Pairing-Based Cryptography[END_REF] the authors show that the naive correlation search scheme does not result in a successful attack.

Brief description of vertical detection

In the horizontal approach, traces are compared two by two with a coefficient of similarity before being averaged. The vertical approach consists in comparing the database directly, i.e. without computing the average of the correlation coefficients. For that purpose, a temporal point taken in traces is denoted by

C (i,j) x j
, these data are put in a vector of dimension N . Then, we also indicate a point in traces

C (i,j) k j
, these data are also put in a vector. Finally, the correlation coefficients for these two vectors are calculated. Figure 10 illustrates this principle.

Fig. 10: Illustration of the vertical collision detection

The attacker is then able to create an output correlation for each of the 256 key hypotheses as illustrated by Equation 12:

c i = ρ         C (i,1) x,minterest . . . C (i,N ) x,minterest     ,     C (i,1) k,m . . . C (i,N ) k,m         , ∀m ∈ I, (12)
for i = 0 . . . 255. The attack ends by sending back the key candidate which maximizes the correlations, that is k ← arg max i |c i |.

Attack result against pairings

Figure 11 shows the correlations c i for a vertical correlation collision detection attack by using N = 400 repetitions. The thickest curve corresponds to the correct sub-key hypothesis. We see on Figure 11 that the attack allows to distinguish the good sub-key hypothesis. Indeed, the bold thick curve, corresponding to the good sub-key hypothesis (on 8 bits) has a higher correlation than the other hypotheses.

Because the attack works with N = 400 repetitions (i.e. 400 × 256 = 102400 total number of traces), we modify this parameter in order to see the evolution of the rank for the good sub-key. For N ∈ {100, 110, . . . , 400}, Figure 12a shows this evolution.

From N = 350, the attack allows to distinguish the good sub-key (the least significant byte of k 0 ). When the least significant bits are recovered, the same attack can be applied to the next byte. Collision detection has thus been made easier, Figure 12b shows the evolution of the rank of the good key according to the number N of repetitions. It is enough to take approximately N = 250 to be able to find the 8 targeted bits. We follow the same approach for the successive bytes. This procedure gives even better results for byte #3. More precisely, Figure 13a shows that with N = 200 traces, the attack allows to find the correct key byte 2 . Finally, when the target is the last byte, Figure 13b shows that N = 200 is enough to identify 8 bits of the secret.

In view of the results given in Figures 12 and13, the number of curves needed to find a 32-bit word is: (13) 2 We improve the efficiency of the attack when compared to [START_REF] Jauvart | First Practical Side-Channel Attack to Defeat Point Randomization in Secure Implementations of Pairing-Based Cryptography[END_REF] where 300 curves were necessary to perform the attack Given that there are 7 other 32-bit words to be found, the total number of traces is:

E k0 2 8
E k 8 ×

Some ideas for extra protections

The scheme for this attack does not depend on the configuration for the secret point, whether it is P or Q. The only aspect which comes into play is the choice of the pairing, and more exactly from the choice of the groups G 1 and G 2 .

Order of points P and Q

With a thoughtful choice of the parameters order, the secret integer can be 12 times more difficult to recover. More precisely, a point P in G 1 = E(F p )[r] has three coordinates (in Jacobian representation) which are simply integers on |p| 2 bits, while the point Q, in G 2 ⊂ E F p 12 [r], has three coordinates which are elements of F p 12 (or F p 2 in the case of the use of a twisted curve). Thus, if Q ∈ G 2 is secret, and if we target at first x Q ∈ F p 12 , then it is necessary to perform the attack 12 times in order to find the 12 integers of F p that describe x Q .

Besides, the point Q is made of 12 × |p| 2 bits, while P is contains 2 × |p| 2 bits. As a consequence, there are 6 times more bits to be found if Q is the secret rather than P .

Points representations

So far, we have seen that to choose Q as the secret is better from the defender point of view. Let us now analyze the point representations.

The structure of the Miller algorithm is such that points P and Q have an asymmetric role. Instead of only randomizing the public point, as proposed in the literature for cost reasons, it becomes interesting to study the scenario in which the randomization is used on both points. To counter the effect of the collision attack, both masks have to be different. 1 λ 1 ∈ F p is randomly chosen ;

2 P = (X T : Y T : Z T ) with X P ← x P λ 2 1 ; Y P ← y P λ 3 1 ; Z P ← λ 1 ; 3 λ 2 ∈ F p is randomly chosen ; 4 Q = (X Q : Y Q : Z Q ) with X Q ← x Q λ 2 2 ; Y Q ← y Q λ 3 2 ; Z Q ← λ 2 ; 5 return P and Q ;
Now that both points are randomized (Algorithm 7), the coordinates system is not mixed any more. In this case, the projective representation allows to perform the operations with a minimal cost. When the representation of the points changes, it is necessary to re-compute the cost of mandatory operations (point addition, point doubling, line and tangent evaluation). The various possible combinations are studied and compared in the thesis [START_REF] Jauvart | Sécurisation des algorithmes de couplages contre les attaques physiques[END_REF]. In the Miller algorithm, on one hand we have the tangent line computation and the point doubling, and on the other hand the line evaluation and the addition of two points on the elliptic curve. These pairs of operations are actually very similar and can be computed together to avoid redundant operations.

In this section we are interested in representations that can be randomized, that is, projective and Jacobian for the three points P , T and Q. According to the comparative study in the thesis [START_REF] Jauvart | Sécurisation des algorithmes de couplages contre les attaques physiques[END_REF], the least expensive is the full-projective representation. These operations are detailed in Equations 15 and 16 with denominator elimination.

The doubling point T combined with the tangent evaluation l T,T (Q) becomes:

D = 3X 2 T + aZ 2 T F = Y T Z T G = F Y T X T H = D 2 -8G X [2]T = 2F H Y [2]T = D(4G -H) -8(Y T F ) 2 Z [2]T = 8F 3 l T,T (Q) = 2F (Z T Y Q -Y T Z Q ) -D(X Q Z T -X T Z Q ). ( 15
)
The combined computation of T + P and the line evaluation l T,P (Q) become:

A = Y T Z P -Y P Z T B = X T Z P -X P Z T C = A 2 Z T Z P -B 3 -2B 2 X P Z T X T +P = BC Y T +P = A(B 2 X T Z P -C) -Y T Z P B 3 Z T +P = B 3 Z T Z P l T,P (Q) = B(Z T Y Q -Z Q Y T ) -A(Z T X Q -Z Q X T ). ( 16
)
The threat is now transferred to the randomization operation itself, it must be implemented in a secure way. The distribution of the mask is assumed to be uniform, that is λ ∈ F p is randomly chosen, which spells P (Λ = λ) = 1 p-1 , where Λ denotes the discrete random variable.

We have already seen that x Q λ takes a random (unpredictable) value in a set of p -1 elements. In other words, the secret is not manipulated any more. The only remaining target is actually the randomization step.

Conclusion and perspectives

In this paper, we recall some basic definitions about pairing-based cryptography in order to illustrate the fact that identity-based cryptography can be vulnerable to Side-channel attacks.

We first present pairings and their application to innovative cryptographic protocols, such as Identitybased Encryption. We provide the equations for lines and tangents to efficiently compute pairings by using Jacobian coordinates. The Identity-based Encryption by Boneh-Franklin [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] is our case study to present some side-channel attacks against pairings implementation. Our attacks can be successful for any pairing-based protocol involving a secret as input of the pairing.

Among the state of the art of the side-channel attacks, there are only a small number of practical validations. We describe a classical attack scheme against the pairing and perform the attack on an ARM Cortex-M3. The modular multiplication is the target because it involves an operation between known and unknown integers. Our work shows a slight difference between the attack paths, depending on the fact that the secret is the first or the second operand of the pairing. Besides, we are interested in the optimization of such attack. We show the characterization of the multiplication between two machine words. Some practical results show the efficiency of such an attack path. We also study the feasibility of a more advanced attack than a CPA. We drastically reduce the number of necessary traces and also decrease the memory required for the attack. We perform the first horizontal CPA attack against an Ate pairing. We open the discussion on the consequences of our attack for state of the art secure implementations of PBC. According to [START_REF] Barbulescu | Updating key size estimations for pairings[END_REF], for the 128 bits security level, the KSS16 curves should provide the most efficient pairing implementations. Our horizontal attacks would then require 2 traces with 2 different inputs and the same secret key in order to be successful. We leave as future works the extension of our attacks for dedicated modules in embedded devices designed for higher sizes: 128, 256, 512, 1024 and 2048 bits architectures.

To circumvent classical attacks, the literature has proposed some countermeasures. We show that a practical collision attack defeats the less expensive protections. The practical results of a chosen plaintext collision attack allow us to conclude that the attack of the protected implementations induces a factor 10000 for the number of traces.

Here are some alternative solutions for a secure pairing implementation:

-Arithmetic randomization. For example in Residue Number System (RNS) representation with a new base which is calculated for every execution of the pairing. Of course, this randomization step will involve extra computation, as a future work we will study the risk-benefit ratio of this countermeasure. -The randomization step which we wish to protect is made of three modular multiplications x Q λ, y Q λ and z Q λ. The protection of the modular multiplication was proposed in [START_REF] Bauer | Horizontal and Vertical Side-Channel Attacks against Secure RSA Implementations[END_REF][START_REF] Clavier | ROSETTA for Single Trace Analysis[END_REF][START_REF] Medwed | Randomizing the Montgomery Multiplication to Repel Template Attacks on Multiplicative Masking[END_REF]. These protections can be used in order to secure the three critical multiplications which manipulate the secret coordinates. -Consider slower external countermeasures to pairings such as e(P, Q) = e(aP, bQ) or e(P, Q) = e(P + R, Q)e(-R, Q), as proposed by Page and Vercauteren [START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF].

W × 8 N.Algorithm 2 :

 82 Montgomery Modular Multiplication CIOS [26] Input : The modulus p = (p N -1 . . . p 0 ) W coprime to W, R = W N , p such that RR -1 -pp = 1 and two integers a = (a N -1 . . . a 0 ) W and b = (b N -1 . . . b 0 ) W . Output : The integer c = (c N -1 . . . c 0 ) W such that c = abR -1 mod p.

Fig. 1 :

 1 Fig. 1: Attack scheme on 2z bits

Fig. 2 :

 2 Fig. 2: Characterisation CPA on 32 bits

1 Fig. 4 :

 14 Fig. 4: T-test for both Hamming weight models

Fig. 6 :Fig. 7 :Fig. 8 :

 678 Fig. 6: Correlations for key candidates for the byte 1

Fig. 9 :

 9 Fig. 9: Correlations for key candidates for the byte 4

log 2

 2 (r) ϕ(k) = 256 4 = 64 iterations, where ϕ is the Euler totient function. Doing a CPA with only 64 traces is more difficult.

Algorithm 3 :

 3 First countermeasure of Page et al.[START_REF] Page | Fault and Side-Channel Attacks on Pairing Based Cryptography[END_REF]

Algorithm 6 : 3 for j = 0 to N do 4 C

 634 into account the effect of the mask. Naive attack scheme Input : The plaintexts x (i) 0 , a positive integer N . Output : A key candidate k for the 8 least significant bits of k. 1 c ← M 1,255 (0) ; 2 for i = 0 to 255 do

Fig. 11 :

 11 Fig. 11: Correlations related to a vertical correlation collision detection attack

Fig. 12 :

 12 Fig. 12: Evolution of the rank of the good key for the attack with vertical correlation: byte 1 and 2

4  2 , 7 ×

 427 10 5 .

Fig. 13 :

 13 Fig. 13: Evolution of the rank of the good key for the attack with vertical correlation: byte 3 and 4

  2 8 (400 + 250 + 200 + 200) 2, 2 × 10 6 . (14)

Algorithm 7 :

 7 Randomisation of both point P and Q with two different masks Input : An elliptic curve E : y 2 = x 3 + ax + b over F p , points P ∈ E F p k [r] and Q ∈ E F p k . Output : Randomised Jacobian coordinates of P and Q.

Table 1 :

 1 Origins of the intermediate variables to calculate c 0

			Origins
	Variables	Operations	Intermediate variables Known Unknown

Table 2 :

 2 Attacks comparisons: resources and required traces

		[38]	Our
	Time	2 19	2 16
	Memory	2 19	2 16
	Number of trace 1500	150

For instance if the secret involved in the pairing computation is a session key.