Lapin Lubos Gaspar

Gaëtan Leurent
email: gaetan.leurent@inria.fr

François-Xavier Standaert
email: fstandae@uclouvain.be

Hardware Implementation and Side-Channel Analysis of

Keywords: LPN, Ring-LPN, masking, side-channel analysis

Lapin is a new authentication protocol that has been designed for low-cost implementations. In a work from RFIDsec 2012, Berstein and Lange argued that at similar (mathematical) security levels, Lapin's performances are below the ones of block cipher based authentication. In this paper, we suggest that as soon as physical security (e.g. against side-channel attacks) is taken into account, this criticism can be mitigated. For this purpose, we start by investigating masked hardware implementations of Lapin, and discuss the gains obtained over software ones. Next, we observe that the structure of our implementations significantly differs from block cipher ones (for which most results in side-channel analysis apply), hence raising questions regarding how to evaluate physical security in this case. We then provide first results of side-channel analyzes against unprotected and masked Lapin. Despite interesting properties of the masked implementations, our conclusions are still contrasted because of the on-chip randomness requirements of Lapin protocol. These results give strong incentive to design similar but deterministic protocols, e.g. based on the recently introduced Learning With Rounding assumption.

Introduction

In [START_REF] Heyse | Lapin: An Efficient Authentication Protocol Based on Ring-LPN[END_REF], Heyse at al. proposed the Lapin authentication protocol based on the hardness of the Ring-LPN problem. Authors described two different Lapin variants based on a carefully chosen ring R = F 2 [X]/f (X). In the first variant, the ring is constructed with respect to an irreducible polynomial f (X) in F 2 . This way the ring becomes a Galois field. In the second variant the polynomial f (X) is reducible and it factors into distinct irreducible factors over F 2 , leading to improved performances (only this second variant will be considered next).

The claim that such a protocol could provide better performances than standard solutions using block ciphers gave rise to some debate, as witnessed by the work of Bernstein and Lange [START_REF] Daniel | Never Trust a Bunny[END_REF]. In this paper, the authors strongly argued against Lapin, because of its unclear security level, and performances that are anyway below the ones of lightweight ciphers. In this paper, we aim to mitigate these criticisms in light of the interesting properties of Lapin regarding sidechannel resistance. Namely, we would like to argue that 3 as the (physical) security level against side-channel attacks required by some application increases, Lapin gradually becomes an interesting alternative over the AES. The main reason of this interesting feature is the linearity found in its core operations.

For this purpose, we first propose a generic hardware architecture for Lapin, and detail the performance gains that can be obtained from its implementation in an FPGA (compared to previous software implementations of unprotected Lapin and masked AES). Next, we provide a preliminary evaluation of its side-channel properties. Interestingly, the situation of Lapin can be compared to recent investigations of randomness extractors against side-channel attacks [START_REF] Medwed | Extractors against side-channel attacks: weak or strong?[END_REF]. Namely, they can both be masked quite efficiently, while raising questions regarding how to best exploit/evaluate side-channel leakage. As a first step in this direction, we suggest two ways to mount attacks against Lapin: one non-divide-and-conquer DPA-like attack, and one divide-and-conquer collision-like attack, exploiting the correlation between the leakage corresponding to multiple messages.

Overall, these results suggest that Lapin could be a promising candidate for (reasonably) lightweight and physically secure implementations. Yet, and admittedly, a significant drawback remains that it requires the generation of randomness on-chip, which may be an issue both from the performance and the physical security point of view. As the previous work in [START_REF] Heyse | Lapin: An Efficient Authentication Protocol Based on Ring-LPN[END_REF], we ignored this part of the problem so far, leading to two important questions for further research. First, how to generate this noise efficiently and in a leakage-resilient manner. Second, can we build an authentication protocol similar to Lapin, but deterministic, e.g. using the recently introduced Learning With Rounding assumption [START_REF] Alwen | Learning with Rounding, Revisited -New Reduction, Properties and Applications[END_REF][START_REF] Banerjee | Pseudorandom Functions and Lattices[END_REF].

Background

In this section we recall the Lapin authentication protocol and the masking countermeasure.

The Lapin protocol

Lapin is a two-round authentication protocol, illustrated in Figure 1. It is defined over the ring R = F 2 [X]/f (X), where f is a polynomial over F 2 of degree n. The initial public parameters are: λ -security level parameter (in bits); π -mapping {0, 1} λ → R; τ ∈ (0, 1 /2) -Bernoulli distribution parameter; τ ′ ∈ (τ, 1 /2) -reader acceptance threshold. Besides, the secret key of the tag and reader is defined as K = (s, s ′ ), with (s, s ′ ) $ ← R. The protocol is executed as follows.

Public parameters: R, π:{0, 1} λ → R, τ, τ ′ , λ.

Secret key: K = (s, s ′ ) ∈ R 2 .

Tag

Reader

➀ c c $ ← {0, 1} λ ➁ r $ ← R * ; e $ ← Ber R τ ∈ R ➂ z := r • (s • π(c) ⊕ s ′ ) ⊕ e (r, z) ➃ if r / ∈ R * reject ➄ e ′ := z -r • (s • π(c) ⊕ s ′ ) ➅ if HW (e ′ ) > n • τ ′ reject else accept
Fig. 1. Two-round Lapin authentication protocol.

After the tag is detected in the reader's vicinity, the reader randomly generates a challenge c ∈ {0, 1} λ and sends it to the tag (step ➀ in Fig. 1). The λ parameter determines the security level of the protocol (e.g. λ = 80 bits). In the meantime, the tag generates parameters r and e (step ➁). The parameter r is an uniformly chosen element of the ring R * and e is a low-weight ring element chosen with Bernoulli distribution over F 2 (Ber τ ) with parameter (bias) τ ∈]0, 1 /2[ (i.e., Pr[X = 1] = τ if X ← Ber τ ). After receiving the challenge c, the tag maps the challenge to the ring through π, where

π satisfies π(c) ⊕ π(c ′ ) ∈ R \ R * ⇔ c = c ′ .
We denote R * the set of elements in R that have a multiplicative inverse. Subsequently, the tag responds with (r,

z = r • K(c) ⊕ e) ∈ R × R (step ➂), where K(c) = s • c ⊕ s ′ is
the session key that depends on the shared secret key K = (s, s ′ ) ∈ R 2 and the challenge c. The reader accepts if e ′ = z ⊕ r • K(c) (computed in the step ➄) is a polynomial of low weight (step ➅). More details on the Lapin protocol and all necessary security proofs can be find in [START_REF] Heyse | Lapin: An Efficient Authentication Protocol Based on Ring-LPN[END_REF].

Chinese Reminder Theorem representation (CRT):

In this work, we focus on versions of Lapin over a ring R = F 2 [X]/f (X) where f (X) factors into distinct irreducible factors over F 2 . For an element h in the ring F 2 [X]/f (X), we will denote h its CRT representation with respect to the factors of f (X) (for simplicity f (X) will be further denoted only as f ). In other words, if

f = f 1 • f 2 • • • f m
where all f j are irreducible, then:

h . = (h mod f 1 , . . . , h mod f m ), h i . = h mod f i .
For the protocol to be implemented efficiently, all public and private values must be transformed to the CRT domain. However, in order to obtain the resulting tag response (r, z), it must be reconstructed from the response ( r, z) as follows:

(r, z) =      m i=1 r i • constant f f i • f f i -1 fi , m i=1 z i • constant f f i • f f i -1 fi      . (1)
Although constants in the equation can be precomputed, this transformation still involves m multiplications and additions of size n. Since the transformation from and to the CRT representation only uses public values, the tag response (r, z) can be sent to the reader in its CRT representation ( r, z) without decreasing Lapin's security. This way, the computationally extensive transformation can be performed at the reader side. The challenge mapping π is defined as π(c) = (c, c, c, c, c), i.e. each CRT component is just the challenge padded with zeroes.

The masking countermeasure

Masking is a countermeasure against power analysis attacks based on secret sharing, first proposed by Chari et al. [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF] and Goubin et al. [START_REF] Goubin | DES and Differential Power Analysis (The "Duplication" Method)[END_REF]. Its main objective is to decrease the correlation between the power consumed by a device and the data being processed, by applying one (or several) random mask(s) to intermediate values. More formally, prior to the execution of the algorithm, all sensitive values (i.e. all key-dependent intermediate results used during the cryptographic computations) must be split into shares. Next, the algorithm is implemented in such a way that the processing is only performed on these shares, which are recombined at the end of the computation to produce the correct output result. Given that the shares are refreshed for each new authentication4 , masking provides an increase of the side-channel attacks data complexity that is exponential in their number, under the assumption that the leakage of each share is independent of the others. However, for this exponential security increase to materialize into strong concrete security, it is required that sufficient noise is present in the leakage measurements [START_REF] Standaert | The World Is Not Enough: Another Look on Second-Order DPA[END_REF].

Different types of masking schemes have been proposed in the literature. Boolean masking (where the sharing is performed using a bitwise XOR operation) appears as the most natural candidate in our context, since it can take advantage of the linearity of the computations in Lapin. In this context, the split of a sensitive value h into d shares requires the generation of d -1 random mask values q i , and is defined as follows:

h 1 = q 1 , . . . , h d-1 = q d-1 , h d = h ⊕ d-1 i=1 q i .
Based

z = (π(c) • s ⊕ s ′ ) • r ⊕ e, = [π(c) • (s 1 ⊕ • • • ⊕ s d ) ⊕ (s ′ 1 ⊕ • • • ⊕ s ′ d )] • r ⊕ (e 1 ⊕ • • • ⊕ e d ), = [(π(c) • s 1 ⊕ s ′ 1 ) • r ⊕ e 1 ] ⊕ • • • ⊕ [(π(c) • s d ⊕ s ′ d ) • r ⊕ e d ] , = z 1 ⊕ • • • ⊕ z d , with z i . = (π(c) • s i ⊕ s ′ i ) • r ⊕ e i .
Since Lapin is linear, we can compute the shares z i independently, and there is no need of interaction between them nor refreshing during the computations, as opposed to masking non-linear gates within the AES [START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF], for instance. This leads to very efficient implementations.

On the independent leakage assumption: In addition, the linearity of Lapin also allows to compute the shares sequentially. This time separation typically reduces the risk of glitches and other hardware effects that are well known to contradict the independence assumption [START_REF] Mangard | Side-Channel Leakage of Masked CMOS Gates[END_REF]. This is especially interesting in the context of hardware implementations as considered in the next section; this is the typical context in which glitches can appear [START_REF] Mangard | Successfully Attacking Masked AES Hardware Implementations[END_REF].

Hardware implementation

In this section we discuss our design choices for (unprotected and masked) Lapin. We present several implementations of a Lapin co-processor and report their area and timing performance. A hardware implementation takes advantage of parallel computing in order to generate sufficient algorithmic noise, which allows significant security gains in practice (and improved performances).

Generic architecture

In order to implement the Lapin protocol, we use the same parameter values as defined in Heyse at al. [START_REF] Heyse | Lapin: An Efficient Authentication Protocol Based on Ring-LPN[END_REF]. The degree of the polynomial f is chosen as n = 621, the security level parameter λ = 80 bits, Bernoulli distribution bias parameters τ = 1 /6, τ ′ = 0.29 and the number of factors of f as m = 5. The five f j polynomials are defined as follows:

f1(X) = X 127 ⊕ X 8 ⊕ X 7 ⊕ X 3 ⊕ 1, f2(X) = X 126 ⊕ X 9 ⊕ X 6 ⊕ X 5 ⊕ 1, f3(X) = X 125 ⊕ X 9 ⊕ X 7 ⊕ X 4 ⊕ 1, f4(X) = X 122 ⊕ X 7 ⊕ X 4 ⊕ X 3 ⊕ 1, f5(X) = X 121 ⊕ X 8 ⊕ X 5 ⊕ X ⊕ 1.
Assuming that the Lapin protocol is performed on d shares (each of them computed for all m CRT parts), we will denote the i-th share of the j -th CRT part for a sensitive variable h as h i,j . Next, we propose a flexible architecture that allows splitting the sensitive variables into arbitrary number of shares. Taking advantage of generic VHDL coding enables the generation of such implementations by re-synthetizing the same code with different parameters. For this purpose, we present the masked Lapin algorithm, the combined polynomial multiplicationreduction algorithm, and the hardware implementation of the complete Lapin core.

Masked Lapin: The generic masked Lapin algorithm is illustrated in Algorithm 1. First, a padded public challenge π(c) is multiplied by a secret key s divided into shares s i,j for 1

≤ i ≤ d, 1 ≤ j ≤ m.
Following, the result is added to the secret key s ′ divided into shares s ′ i,j . The sum is then multiplied by a public random tag response r j . Subsequently, the product is added to a low-weight element e i,j . The last step is to sum all resulting shares to form an unmasked tag response z j . Finally, r j and z j are sent back to the reader to finish the authentication process. Note that all computations are performed on all m CRT parts. for i from 1 to d do 8:

Algorithm 1 Masked Lapin algorithm

ti,j ← (π(c) • si,j ⊕ s ′ i,j ) • rj ⊕ ei,j 9: end for 10:

for i from 1 to d do 11: zj ← zj ⊕ ti,j 12:

end for 13: end for 14: Return z Reduction of a low-weight error element e: Unlike the other parameters in Lapin, the low-weight error element e cannot be generated or pre-stored in CRT representation directly: its m CRT parts must be calculated prior to other computations. The reduction of such a large element is not straightforward and requires additional hardware resources. In order to simplify this problem, we first write each share of e (a polynomial of degree 621) in Horner form using five polynomials [e (4) , e (3) , e (2) , e (1) , e (0) ] of degree 127 (except for e (4) of degree 109):

e i,j = e (4) i •X 128 ⊕e (3) i •X 128 ⊕e (2) i •X 128 ⊕e (1) i •X 128 ⊕e (0) i mod f j . (2)
Next, the polynomial X 128 can be reduced by each characteristic polynomial f j resulting in constant polynomials g j of degree less than deg(f j ). After substitution Equation 2becomes:

e i,j = e (4) i g j mod f j ⊕ e (3) i • g j mod f j ⊕ e (2) i • g j mod f j ⊕ e (1) i •g j mod f j ⊕e (0) i . (3)
This way, only four multiplications, four reductions and four additions have to be computed to obtain each e i,j . Moreover, the same hardware as used for performing the computations in Algorithm 1 can be re-used to calculate the e i,j 's. Note that since e (3) , e (2) , e (1) and e (0) are of degree 127, some extra hardware is still necessary for their reduction.

Polynomial multiplication and reduction:

Examining the previous algorithms reveals that 6 × d × m polynomial multiplications, reductions and polynomial additions have to be performed to generate a response z. Among those, the most time-consuming operations are the polynomial multiplications and subsequent reductions of the products. Although the performances of the "schoolbook" multiplication algorithm is theoretically lower (O(2 n )) than the Karatsuba algorithm (O(n log23 )), it has a very simple structure, and so the resulting implementation is area-efficient and can operate at high clock frequencies. Moreover, polynomial reduction and multiplication operations can be executed simultaneously in this case, so that no computational time is lost for the reduction step. For this reason, we have implemented a combined polynomial multiplicationreduction based on the schoolbook multiplication, as explained in Algorithm 2. Two input polynomials a i,j and b i,j of degree at most n j -1 (represented with bit arrays A[n j -1 : 0] and B[n j -1 : 0]) are multiplied together while partial products are reduced by the characteristic polynomial f j of degree n j (represented with the bit array F [n j : 0]) simultaneously. A closer examination of the algorithm shows that B is multiplied by one bit of A at a time. Therefore, if A contains a secret value, Lapin will be vulnerable to a Simple Power Analysis (SPA) attack, where each partial multiplication leaks one bit of a key. For this reason, A must contain only public data. On the contrary, B is processed in larger blocks (according to the datapath size), so we used it to manipulate sensitive data (that will additionally be protected against DPA thanks to masking).

Lapin architecture: We implemented Lapin as a hardware co-processor core, synthesized using Xilinx ISE 12.4 for Xilinx Virtex-5 XC5VLX50T FPGAs. Our implementation is illustrated in Figure 2. All variables are stored in the data register that is implemented in a dual-port embedded RAM. Random ring elements r and low-weight error elements e have to be generated by a TRNG. Three Output: c(X) = ai,j. bi,j mod fj) 4: C ← 0 5: for i from 1 to nj do 6:

if A[nj -i] = 1 then 7: C ← C ⊕ B 8: end if 9: if C[nj -1] = 1 then 10: C ← (C ≪ 1) ⊕ Fj[nj -1 : 0] 11: else 12: C ← (C ≪ 1) 13:
end if 14: end for 15: Return C[nj -1 : 0] distinctive parts can be identified in the datapath of this Lapin core: the polynomial multiplication logic (shown in blue in Figure 2), the reduction logic (in red) and the addition logic (in green). During multiplication, a public parameter is stored in the shift register (implemented in logic). By shifting this register, one bit is selected at a time and multiplied with the secret parameter. The resulting partial product is stored in the accumulator (also implemented in a dual-port RAM). Subsequently, this partial product is shifted and added to the next partial product. Whenever the size of this sum exceeds n j bits (n j = deg(f j )), reduction circuitry is activated in the next clock cycle to reduce the exceeding bit. Once the multiplication is finished, the result can be summed with a next secret parameter stored in the data register. Prior to this addition, all exceeding bits of this parameter are reduced by an auxiliary reduction circuitry. As can be observed from the figure, multiplication involves shifting of partial products stored in the accumulator. However, if a partial product of size n j is shifted in more than one clock cycle (which is the case when k < 128), the most significant bit of each shifted word must be stored in a carry bit register Cr. This way a stored carry bit becomes a least significant bit of the next word in the next clock cycle.

Performance evaluation

Implementation results: In order to investigate the performance trends resulting from different datapath sizes, we implemented our design for different values of the k parameter in Figure 2, namely we considered k =8-, 16-, 32-, 64-or 128-bit wide architectures, as summarized in Table 1. These results correspond to an unprotected implementation (i.e. d = 1) -but thanks to the linear structure of Lapin, the masked versions have essentially the same cost: only the memory requirements will increase proportionally to the number of shares, in order to store intermediate results. We observe that if the datapath size is decreased by half, the number of allocated fine-grained FPGA resources does not always decrease accordingly. This can be explained by the fact that narrower datapaths usually require more multiplexers and more complex control logic. Moreover, this extra logic increases the overall datapath delays, resulting in lower maximal clock frequency (see the fifth column in Table 1). Comparison: The timing comparison of software AES [START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF], software Lapin [START_REF] Heyse | Lapin: An Efficient Authentication Protocol Based on Ring-LPN[END_REF] and our hardware Lapin are given in Figure 3. In the case of software Lapin, the cycle counts for the masked versions are extrapolated from the unprotected implementation. These results lead to two main observations. First, we see that masked Lapin implementations indeed become interesting alternatives over AES ones, as the number of shares increases. This is caused by the fact the the implementation cost of non-linear operations (which become dominant in masked AES implementations) increases quadratically with d, while this increase is only linear in the case of Lapin. Interestingly, the number of shares for which this gain concretely appears is reasonably small, hence close to practical interest. The software figures we have for protected implementations of AES and Lapin on ATMega suggest that Lapin could become more efficient than AES even with d = 2, but the crossing point can move significantly depending on the masking scheme used, and the optimization level of the implementation.

Second, we see that (as usual) specialized hardware implementations allow a significant optimization of the performances of Lapin. Gains already appear in the comparison of 8-bit architectures: computing a tag response in software requires 112,500 clock cycles (that can be decreased to 30,000 clock cycles if precomputation is allowed); our 1-share 8-bit hardware implementation requires only 20,977 clock cycles in this case (without precomputations). These advantages naturally amplify as we consider larger datapath sizes.

Side-channel analysis of Lapin

The previous section suggests that Lapin is an interesting candidate for masking. First, its linearity allows increasing the number of shares for only a linear implementation cost penalty. Second, it also allows manipulating the shares independently, which implies a better chance to fulfill the independent leakage requirements that is crucial for masking to provide its expected security improvements. Third, it is efficiently implemented in hardware with large datapaths, providing algorithmic noise that is needed for the exponential data complexity increase of masking to materialize into strong security levels. On the other hand, a limitation of this analysis remains that it "only" considers the security orders of the masking schemes (i.e. the minimum number of shares of which the leakage must be exploited to recover key-dependent information). While this is a traditional approach in side-channel analysis, it remains to understand how these security orders translate into actual attack complexities. In particular, since Lapin has a significantly different structure than block ciphers (to which most published higher-order side-channel attacks apply), it is interesting to study attacks that exploit the design of its multiplier. In this section, we consequently suggest several scenarios to analyze/evaluate a Lapin implementation using side-channel information, and we study the efficiency of those attacks depending on the masking order of this implementation. As will be seen, these attacks differ from classical DPA in some interesting respects.

We first point out that we can attack the CRT components independently: each component is computed separately, and we can test a key candidate s i from the an authentication transcript without knowing the other CRT components. In the following we describe attacks on a single CRT component.

As a starting point, we consider a non-protected implementation of Lapin, and we study how to apply a standard DPA attack. In order to evaluate power analysis on our implementation of Lapin, we first have to study what parts of the computations are key-dependent, and how it might affect the power consumption. In our analysis we target the first multiplication s • π(c) in the Lapin protocol, where s is a secret value, and c is a challenge that can be set by the attacker. Our architecture for Lapin includes a large accumulator that is updated at each clock cycle, as shown in Figure 2, and we assume that this accumulator will induce a significant leakage dependent on its value a. In order to simplify our analysis, we use a Hamming weight model, i.e. we assume that the power consumption is correlated with HW(a), and we run simulations where the samples are computed as HW(a) + N , with N a Gaussian-distributed random noise. Our attacks will typically exploit the fact that, when computing a • c, the multiplication algorithm updates the accumulator a as (we consider the optimized multiplication with an 80-bit c):

a 0 = 0 a i+1 ← 2 • a i ⊕ s if c[80 -i] = 1 2 • a i otherwise.
Hence, the value of the a after a few cycles of computation is a small multiple of the secret:

a 80 = s • c a i = s • i j=1 c[80 -j]X i-j .
Cautionary note: Assuming Hamming weight leakages is admittedly a simplification of the real measurements used in side-channel attacks. However, it is a reasonable abstraction for preliminary analyses, that has been used in numerous contexts [START_REF] Mangard | Power analysis attacksrevealing the secrets of smart cards[END_REF]. While the actual complexities provided by these simulated attacks are only meaningful up to the extent that true leakages behave similarly, they are usually informative to confirm whether some attack techniques can be successful. This is typically what the following results aim to exhibit, i.e. how side-channel attacks against Lapin differ from standard DPA against block ciphers.

4.1 A first DPA-like attack against unprotected Lapin.

In an unprotected design, the leakage reveals the Hamming weight of multiples of the secret, with a chosen multiplier m i (c) = i j=1 c[80 -j]X i-j , depending on the challenge c and the cycle i we target. If we exploit several different cycles in a given trace, we can get information about HW(a i ) = HW(s • m i (c)) for the same c and different values of i. However, the same information can also be obtained by targeting a fixed cycle ι of the computation if we capture several traces and send the appropriate challenges c j so that m ι (c j ) = m j (c).

In a DPA attack, we guess a small part of the key, then predict the value of the leakage for a key guess according to a model, and compare the prediction to the actual measurements in order to rank the key candidates. For a block cipher, the key is usually divided according to the structure of the cipher; for instance, an attack on the AES will target the key bytes independently because each SBox in the first round depends on a single key byte. In the case of Lapin there is no such natural division of the key, but we can study the key bits required to compute some bits of the accumulator.

Recovering a few key bits. For a given t, if m i (c) is of degree at most t (e.g. if i ≤ t), we can compute the p least significant bits of s • m i (c) from the p least significant and the t -1 most significant bits of s. This allows to build a simple DPA attack: after guessing the key bits, we compute the least significant bits of a i and we consider the remaining bits as algorithmic noise. We can then compute the correlation between the leaked weight of a and the weight of the predicted bits, and use it to rank the key candidates.

Note that if there is no measurement noise, we can only use 2 t different measures in this attack, because there are only 2 t different polynomials of degree t or lower. Extra measures are only useful to reduce the measurement noise.

We implemented this attack using Pearson's correlation coefficient as a comparison tool [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF], and we show an example of results in Figure 8 in Appendix A.

We can see from this example that the information from the measures is not sufficient to recover exactly the secret key bits; there is a cluster of key candidates with the same correlation coefficient. This is due to the algebraic structure of the multiplier; for instance, if we consider two key candidate s and s ′ = s • X, our prediction for the least significant bit of the accumulator using the key s will match the second-least significant bit of the accumulator for candidate s ′ . Therefore, both candidates will be in the same cluster.

Recovering the full key. As opposed to a typical side channel attack on a block cipher, we don't have independent parts of the key affecting different parts of the computation. Therefore, we don't attack key parts independently using a divide-and-conquer approach, but we recover key information gradually: if we have a good candidate for n bits of the key, we generate key candidates for n + 1 bits by considering both values for the next key bit. This defines a tree of key candidates, and we explore the tree following the best candidates.

More precisely, we compute a score for the candidates as the ratio of Pearson's correlation coefficient over the expected correlation coefficient for the right key (the square root of the number of predicted bits divided by the total number of bits on the bus, over which the Hamming weight is computed). This allows to compare the quality of key guesses of different lengths: if more key bits are guessed, we can predict more bits, and we expect a better correlation coefficient. The score of a node is computed when its parent is explored, and we select the node with the higher score among all nodes whose score has been computed. In practice, we use a priority queue to store the nodes and to extract the best one efficiently.

If we have 2 t traces, we begin by guessing the t -1 most significant bits, and one least significant bit of the key; this allows to predict one bit of the accumulator a t after t cycles. Next, we guess the second-least significant bit of the key, so that we can predict two bits of a t .

Figure 5 in Appendix A shows the success rate of this DPA-like attack, with various parameters. The attack becomes less efficient with a large datapath, because the Hamming weight over a larger bus size introduces more algorithmic noise to the predicted value.

Those experiments clearly show the effect of the algorithmic noise from the unknown bits in the Hamming weight (with variance k/4 for a k-bit datapath), and of the physical noise (with variance σ 2 ). When the physical noise is dominant, i.e. σ 2 > k/4, we see the data complexity increasing linearly with the variance of the noise, as expected [START_REF] Mangard | Hardware Countermeasures against DPA ? A Statistical Analysis of Their Effectiveness[END_REF]. For instance, our experiment show a data complexity of about 2 7 .σ 2 to reach a high success rate with k = 8. When k increases, this increases the algorithmic noise, and we have a similar increase of the data complexity if the algorithmic noise is dominant, i.e. when σ 2 < k/4. We note that this increase is somewhat faster than k/4 because there are more nodes to explore to locate the correct key when k is larger, but we stop after a fixed number of nodes are explored.

Collision-like attack.

We now describe an attack based on the structure of the operations in Lapin. The main advantage of this attack is that we can eliminate the algorithmic noise due to the Hamming weight with a large datapath by comparing the leakage with two different inputs. This is similar to side-channel collision attacks [START_REF] Schramm | A Collision-Attack on AES: Combining Side Channel-and Differential-Attack[END_REF] where two traces are compared to detect specific events.

More precisely, we use the fact that the operation α → α•X has a predictable effect on the Hamming weight of α. We have:

α • X mod f = (α ≪ 1) if MSB(α) = 0 (α ≪ 1) ⊕ f if MSB(α) = 1,
where ≪ to denotes a left shift. Alternatively, we can write it using a rotation ≪ over deg(f ) bits:

α • X mod f = (α ≪ 1) if MSB(α) = 0 (α ≪ 1) ⊕ f if MSB(α) = 1,
where f = f ⊕ X deg(f ) ⊕ 1 is f without the highest and lowest coefficients. Since the polynomials f used in Lapin are pentanomials, we have HW( f ) = 3, and we can relate the Hamming weight of α and the Hamming weight of α • X mod f :

HW(α • X mod f ) =                HW(α) if MSB(α) = 0 HW(α) + 3 if MSB(α) = 1 and HW(α ≪ 1 ∧ f ) = 0 HW(α) + 1 if MSB(α) = 1 and HW(α ≪ 1 ∧ f ) = 1 HW(α) -1 if MSB(α) = 1 and HW(α ≪ 1 ∧ f ) = 2 HW(α) -3 if MSB(α) = 1 and HW(α ≪ 1 ∧ f ) = 3.
Therefore, the distribution of HW(α•X)-HW(α) for a random α is the following:

if MSB(α) = 0: HW(α • X) -HW(α) = 0, if MSB(α) = 1: HW(α • X) -HW(α) =         
+3 with probability 1/8 +1 with probability 3/8 -1 with probability 3/8 -3 with probability 1/8.

To exploit this property, we will use two measures such that m i (c) = m and m i ′ (c ′ ) = m•X. Then, we can recover the value MSB(m•s) (i.e. a linear equation in s) by comparing HW(m • s) and HW(m • X • s) (we use the analysis above with α = m • s). If there is no noise, we will recover a key bit with only two measures, with probability one.

As opposed to the attack of Section 4.1, this analysis uses the full state of the multiplier, and avoids algorithmic noise due to the Hamming weight. This makes the attack quite efficient. However, there is also an important limitation: because the challenge used in Lapin is only 80-bit long, the multiplication m • c only takes 80 cycles, and we can only recover 80 bits from each CRT component of the key with this technique.

If there is some measurement noise, we can remove it either by repeating the measures of HW(m • s) and HW(m • X • s) and averaging them, or by using all the measures in a template attack [START_REF] Chari | Template Attacks[END_REF]. We performed simulations with various levels of noise using a template attack, and the rank estimation code from [START_REF] Veyrat-Charvillon | Security Evaluations beyond Computing Power[END_REF] to compute the rank of the full key from the estimated key bits probability. We report our results in Appendix A, Figure 6. Those experiments show that with a 128-bit datapath we can recover 80 key bits with very few candidates using only 2 6 traces with a noise variance of 1. Again, the data complexity grows linearly with the noise variance σ 2 , and we need about 2 6 • σ 2 traces to reduce the key space to a few candidates.

If the datawidth k is smaller than 128, we have to combine 128/k measures to build the full Hamming weight HW(a) in order to perform the attack. If the noise variance is σ 2 this becomes equivalent to a noise variance of 128/k • σ 2 for an attack with a 128-bit datapath, and the number of traces required is about 2 6 • σ 2 • 128/k. As expected, this behavior is opposite to what happens in the attack of Section 4.1 where a larger datapath implies a higher attack complexity because of the extra algorithmic noise.

For the acquisition of the data, one can either extract the two leakages from a single trace at two different points of interest, or use two traces with chosen challenges and extract the leakage from each trace at the same point in time. In order to minimize the number of traces required for the attack, we use all the clock cycles of the multiplier. More precisely, we send the challenge c = 2 79 , so that m

i (c) = X i-1 and m i+1 (c) = X i = m i (c) • X.
Order of the attack. This attack exploits information from two different measures, and combines them using the difference operation. Since we use a single pair of challenges for each key bit, we can average the measures and the information can be extracted from the average leakage values by testing whether it is zero or in {-3, -1, +1, +3}. Therefore, this attack can be seen as a first-order bivariate attack.

Attack on masked Lapin

We now study how this attack can be applied against a masked implementation of Lapin such as the implementation described in Algorithm 1. In a masked implementation the multiplication π(c) • s is split in d computations π(c) • s j , with s = d j=1 s j . Therefore we have to combine leakages from each of the d computations to recover information about the secret s.

First, we can see that if there is no noise, it is still easy to recover the key using the attack of Section 4.2. If we send the challenge c = 2 79 , we have HW(X i • s j ), we can recover MSB(X i-1 • s j ), and we can rebuild a bit of s using MSB(

m i (c) = X i-1 and m i+1 (c) = X i = m i (c) • X. By comparing HW(X i-1 • s j
X i-1 • s) = j MSB(X i-1 • s j ).
More generally, we study the 2d-dimensional distribution of:

HW(α j ), HW(α j • X) d j=1 , with α = d j=1 α j .
Following the analysis of Section 4.2, we combine the measures using a difference operation, and reduce them to d dimensions:

HW(α j • X) -HW(α j ) d j=1 , with α = d j=1 α j .
We will later use this analysis with α = m • s and α j = m • s j . We now study the case d = 2 in more details. Following the analysis of Section 4.2, we expect different distributions depending on the most significant bit of α. MSB(α) = 1: If MSB(α) = 1, then we have either MSB(α 1 ) = 0 and MSB(α 2 ) = 1, or MSB(α 1 ) = 1 and MSB(α 2 ) = 0. This results in the distribution of Figure 4.1: either HW(α 1 • X) -HW(α 1 ) = 0 and HW(α 2 • X) -HW(α 2 ) ∈ {-3, -1, +1, +3}, or HW(α 1 • X) -HW(α 1 ) ∈ {-3, -1, +1, +3} and HW(α 2 • X) -HW(α 2 ) = 0. MSB(α) = 0: If MSB(α) = 0, then we have either MSB(α 1 ) = 0 and MSB(α 2 ) = 0, or MSB(α 1 ) = 1 and MSB(α 2 ) = 1. The first case gives HW(α 1 • X) -HW(α 1 ) = 0 and HW(α 2 • X) -HW(α 2 ) = 0. In the second case, we have HW(α 1 • X) -HW(α 1 ) ∈ {-3, -1, +1, +3} and HW(α 2 • X) -HW(α 2 ) ∈ {-3, -1, +1, +3}, but we need to look at HW(α ≪ 1 ∧ f ) in order to predict all the possibilities. The results are shown in Figure 4.

We can use those distributions to mount a template attack against a masked implementation of Lapin. We use c = 2 79 , in order to collect traces with HW(X i-1 • s j ) and HW(X i • s j ), and we recover MSB(X i-1 • s) by distinguishing the distributions (i.e. we have α = X i-1 • s). We report our simulations results in Figure 7 in Appendix A. We can see that the data complexity increases roughly like the squared variance σ 4 , which is typical of a second-order attack [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. In our simulations, the rank of the correct key becomes smaller than 2 10 when the data complexity is about 2 10 • σ 4 .

Order of the attack. This attack exploits information from four different measures, and combines pairs of measures using the difference operation. Then we have to distinguish the distributions of Figure 4, which can be done by computing the covariance and testing whether it is zero or in {-6, -2.25, 2.25, 6}. Therefore, this attack can be seen as a second-order 4-variate attack.

Conclusion

The previous results suggest that Lapin has interesting properties for secure and efficient masking, because it can be implemented by manipulating shares independently. They also exhibit that the exploitation of its leakage does not directly derive from standard DPA such as applied in the context of block ciphers. Yet, it is possible to mount attacks against both unprotected and masked Lapin, with similar intuition regarding the security order as for block ciphers. Admittedly, our side-channel experiments are only a first step, and several problems remain open. Technically, it would certainly be worth investigating other leakage models (e.g. distance-based) and actual measurements. Besides, it could be interesting to further study the possible presence of more data-dependent algorithmic noise in an implementation (i.e. capturing more than the main register activity), and how to get rid of it taking advantage of multiple plaintexts in a collision-like attack. Eventually, and as pointed out in introduction, the problem of on-chip randomness generation remains an important drawback of Lapin. Analyzing its leakage, or designing deterministic protocols based on the Learning With Rounding assumption are interesting scopes for further research. Fig. 6. Security graphs for the collision-like attack, with k = 128. We assume that all the clock cycles are used for each trace. Alternatively, the attack can be mounted targeting a single point of interest if the data complexity is multiplied by 80.

B Additionnal implementation results

Input: 1 :

 1 Padded public challenge π(c) 2: Public random element r 3: Secret keys s and s ′ divided to shares s and s ′ respectively 4: Secret low-weigh error element e divided into shares e Output: Response ( z, r) 5: for j from 1 to m do 6: zj ← 0 7:

Algorithm 2

 2 Combined polynomial multiplication-reductionInput:1: polynomial ai,j, deg ( ai,j) ≤ nj -1 represented as bit array A[nj -1 : 0] 2: polynomial bi,j, deg bi,j ≤ nj -1 represented as bit array B[nj -1 : 0] 3: characteristic polynomial fj(X) of degree nj represented as bit array Fj[nj : 0]

Fig. 2 .

 2 Fig.2. Datapath with multiplication (blue), reduction (red) and addition (green) circuitry.

Fig. 4 .

 4 Fig. 4. Possible distributions for HW(α1 • X) -HW(α1), HW(α2 • X) -HW(α2) . The probabilities are represented as: : 1/16, : 2/16, : 3/16, : 8/16

Fig. 7 .

 7 Fig. 7. Security graphs for the collision-like attack on a masked Lapin, with k = 128.

Fig. 8 .

 8 Fig. 8. Correlation coefficient for the key candidates, depending on the number of traces. We use t = 7 and p = 3, and don't add any noise to the Hamming weights.

  on this sharing, a masked version of Lapin becomes straightforward to implement. The secret keys s, s ′ and low-weight element e are first divided to shares s 1 , s 2 , . . . , s d ; s ′ 1 , s ′ 2 , . . . , s ′ d and e 1 , e 2 , . . . , e d , respectively. The final result z is then obtained by recombining shares z 1 , z 2 , . . . , z d that are computed as follows:

Table 1 .

 1 Implementation results: resource usage and timing information. The detailed timing characteristics of our implementations are given in Table2(see Appendix B), in which each line corresponds to the number of clock cycles required for the computations in one characteristic polynomial domain (f j ), and the last line represents the total number of clock cycles for the full Lapin execution, i.e. one tag response for one authentication request.The left part of the table shows results if no masking is used (secret variables are not divided into shares, i.e. d = 1); its right part summarizes results for three-share computations (i.e. d = 3). For completeness, timing characteristics are again provided for all the aforementioned datapath sizes. The datapath and the control logic were designed in order to eliminate cycles with no activity (i.e. pipeline bubbles). As a result, decreasing the datapath size by half results in doubling the number of clock cycles in most cases. The only exception is the 128-bit datapath where some extra dummy cycles were necessary to avoid RAM read/write collisions.

	Datapath Slices	BRAM	fmax	Clock cycles
	(k)		18kb 36kb (MHz) d = 1	d = 2	d = 3
	8	213	2	0	125.3 20,977 41,969 62,961
	16	232	2	0	127.5 10,489 20,985 31,481
	32	311	1	1	127.2	5,245 10,493 15,741
	64	330	0	3	130.2	2,623	5,247	7,871
	128	451	0	6	140.3	1,332	2,664	3,996
	Timing results:

Table 2 .

 2 Number of clock cycles required for Lapin calculation.

	One share (d = 1)	Three shares (d = 3)
	8-bit 16-bit 32-bit 64-bit 128-bit 8-bit 16-bit 32-bit 64-bit 128-bit

This implies storing all the shares of the secret key, for which the initial split is assumed to be performed once without leakage (otherwise this initialization can always be the target of simple attacks).

This work has been funded in part by the ERC project 280141 (acronym CRASH), by the European Commissions 7th framework program's project TAMPRES, and by the Belgian Cybercrime Center of Excellence for Training Research and Education (B-CCENTRE). F.-X. Standaert is an associate researcher of the Belgiam Fund for Scientific Research (FNRS-F.R.S).

A Simulation results of the side-channel attacks