Andy Russon
email: andy.russon@univ-rennes1.fr

Differential Fault Attack on Montgomery Ladder and in the Presence of Scalar Randomization

Keywords: Differential fault attack, Elliptic curve, Montgomery ladder, Scalar blinding, Scalar splitting

Differential fault attacks are powerful techniques to break a cryptographic primitive, where the adversary disrupts the execution of a calculation to find a secret key. Those attacks have been applied in Elliptic Curve Cryptography under various types of faults, and there exists several protection mechanisms to prevent them.

In this paper, we present a new differential fault attack on the Montgomery ladder algorithm for scalar multiplication. We further present that such attacks can be applied when specific point additions formulas are used and when different scalar blinding techniques to randomize the computation are present.

Introduction

Differential Fault Analysis (DFA) was first introduced on block ciphers [4] and RSA [7]. In these attacks, a fault is induced and modifies the behavior of the execution resulting in an erroneous output. The effects of the fault on the output are compared with the correct one to compromise the full secret key.

The efficiency of Elliptic Curve Cryptography (ECC) makes it popular for embedded devices due mainly to the small parameter size for high-security level, thus it is necessary to protect against physical attacks such as fault attacks. In this paper, we are interested in several unexplored paths for DFA on the scalar multiplication which is the main operation of ECC.

The first main contribution is a new attack on the Montgomery ladder algorithm [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF]. Its most sensitive part as implemented in cryptographic libraries is a conditional swap, and we extend the analysis of DFA when a fault affects this operation. In particular, we look at the use of specific point addition formulas that do not use all point coordinates. Those are specific to the Montgomery ladder algorithm and often used in libraries outside of the classical formulas. Furthermore, we show that point validation or loop invariant verification are not sound measures to protect against our attack.

Our second main contribution is to show that scalar blinding methods do not prevent DFA if the randomizer is too small. Those are the first Coron countermeasure [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] that adds a random multiple of the group order to blind the secret scalar, and the others are methods that separate in several shares the scalar with a multiplicative or Euclidean splitting [START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF][START_REF] Trichina | Implementation of elliptic curve cryptography with builtin counter measures against side channel attacks[END_REF]. We consider the attack in the context of the ECDSA signature scheme, as it is well suited for DFA and can be exploited for key recovery using lattice techniques [START_REF] Nguyen | The insecurity of the elliptic curve digital signature algorithm with partially known nonces[END_REF]. Finally, our attack was experimented on several simulations.

The paper is organized as follows. In Sect. 2 we introduce notations on elliptic curves and ECDSA. Then, Sect. 3 describes our DFA attack on the Montgomery ladder algorithm, followed in Sect. 4 on how the scalar blinding and scalar splitting methods can also be attacked. We give in Sect. 5 a practical evaluation of the implementation of the ladder algorithm in cryptographic libraries, how the attack can be achieved under the skip instruction fault model or with a random fault in a register, and results from several simulations. Finally, we discuss in Sect. 6 past proposed countermeasures to protect against DFA and the limitations of some against our attack, and we conclude in Sect. 7. The construction of the lattices adapted for each case considered in the paper is presented in Appendix A.

Related Works

The first report of DFA with elliptic curves was presented in [START_REF] Biehl | Differential fault attacks on elliptic curve cryptosystems[END_REF]. The target of the fault injection is a point coordinate during a scalar multiplication resulting in a point that does not belong to the original elliptic curve. The algorithm is run backward with the correct and erroneous outputs by making guesses on the bits of the secret scalar processed after the fault was made. The comparison with the correct value is used to check which guess is the correct one. This attack makes the points leave the curve, and a classical countermeasure is to validate them using the curve equation before releasing an output.

Another DFA was proposed in [START_REF] Blömer | Sign change fault attacks on elliptic curve cryptosystems[END_REF], with the advantage that a point validation does not detect the fault. Indeed this sign-change fault attack only modifies the sign of a point, so it still satisfies the curve equation. An example is given to realize such an effect with a fault during the calculation of the NAF representation of the secret scalar, and the paper claims that it could be adapted to the Montgomery ladder algorithm in the case the y-coordinate is used.

In the same line of work, DFA where point validation cannot detect the fault were presented in [START_REF] Schmidt | A fault attack on ECDSA[END_REF] and [START_REF] Schmidt | Fault attacks on the Montgomery powering ladder[END_REF] on the Montgomery ladder algorithm. The faults considered are a skip of one or several operations of the algorithm such that one bit is not processed in the first paper, or with a skip of one multiplication or one squaring when used with RSA in the second paper (but compatible with elliptic curves if one replaces the operations with point doublings and point additions). Then, it is possible to recover the bits of the scalar processed after or before the fault occurred.

Our attack is akin to the previous DFA on the Montgomery ladder algorithm, where the fault does not make the points leave the elliptic curve. But it shares similarities to the sign-change fault attack, as the goal is to change the sign of the implicit loop invariant of the algorithm.

There are other recent fault attacks on ECC, but those are either a DFA against a wNAF algorithm for scalar multiplication [START_REF] Cao | Two latticebased differential fault attacks against ECDSA with wNAF algorithm[END_REF], or target specifically deterministic signature scheme such as the determinist variant of ECDSA or EdDSA [START_REF] Ambrose | Differential attacks on deterministic signatures[END_REF][START_REF] Poddebniak | Attacking deterministic signature schemes using fault attacks[END_REF][START_REF] Romailler | Practical fault attack against the Ed25519 and EdDSA signature schemes[END_REF][START_REF] Samwel | Practical fault injection on deterministic signatures: The case of EdDSA[END_REF] that cover well the subject.

Preliminaries

In this section, we introduce notations of elliptic curves, followed by a description of ECDSA and why it is useful for a DFA attack.

Elliptic Curves over Prime Fields

An elliptic curve E defined over a field F p with p a prime greater than 5 is the set of points (x, y) ∈ (F p ) 2 that satisfy an equation of the form

y 2 = x 3 + Ax + B, A, B ∈ F p , (1)
with ∆ = 4A 3 +27B 2 = 0, and an additional point O, alongside an operation that makes the curve an abelian group. This operation is the point addition, where the identity is O, and the inverse of a point P = (x P , y P ) is -P = (x P , -y P ).

For an integer k, the operation called scalar multiplication is the repeated addition of a point P that appears k times and is noted [k]P . For all points P , there exists a smallest positive integer k such that [k]P = O and is called the order of the point.

Given Q a point in the subgroup of prime order q generated by P , then there exists an integer k such that Q = [k]P and is called the discrete logarithm of Q in base P . The security of ECC is based upon the hardness of finding the discrete logarithm, and the best algorithms are Baby Step-Giant Steps (BSGS) [START_REF] Shanks | Class number, a theory of factorization, and genera[END_REF] and Pollard's rho algorithms with complexity O( √ q). In the case k is known to lie in a relatively small interval [a, b], then it can be found in complexity O( √ b -a) with BSGS or Pollard's kangaroo algorithm [START_REF] Pollard | Monte Carlo methods for index computation (mod p)[END_REF].

ECDSA

This is an elliptic curve-based signature scheme [24]. Its domain parameters are an elliptic curve E and a base point P of prime order q that belongs to the curve.

Given a private key α in [1, q -1] and a hashing function H, signing a message M is done according to Algorithm 1, and the pair (r, s) forms the signature.

The verification process consists of computing the point

Q = [H(M )s -1 ]P + [rs -1 ]P pub (2)
where P pub = [α]P is the public key of the signer, and the signature is valid if r is equal to the x-coordinate of Q (lifted as an integer, then reduced modulo q).

Algorithm 1 ECDSA signature generation.

Require: message M , private key α, point P of order q on an elliptic curve Ensure: signature (r, s) of the message M under the private key α

1: repeat 2: k ← random integer in [1, q -1] 3: Q ← [k]P 4: r ← xQ mod q 5:
s ← k -1 (H(M ) + αr) mod q 6: until r = 0 and s = 0 7: return (r, s) Faulty Signature. The differential fault attack of this paper results in the production of a faulty signature. If a fault is made during the scalar multiplication such that the output is Q , then the resulting signature (r , s ) is

r = x Q mod q s = k -1 (H(M ) + αr ) mod q.
It is not possible to recover the full signature (r, s) from the faulty signature, but the point Q from which r is derived can be reconstructed using the public point of the signer from the relation that is used for signature verification:

[H(M )s -1 ]P + [r s -1 ]P pub = [k]P = Q.
The point Q can also be obtained by lifting the integer r as a point on the elliptic curve. However, the value x Q has been reduced modulo the prime q. It has been shown that outside of Q there are only a few possible points [START_REF] Barenghi | A fault-based secret key retrieval method for ECDSA: analysis and countermeasure[END_REF]. Since the prime q is generally the curve cardinality and is very close to the field order, there are likely only two possible points, Q and -Q .

Therefore, an attacker can obtain both Q and Q , which is a major part of a DFA attack.

Hidden Number Problem

The attack presented in this paper allows an attacker to retrieve partial knowledge of the nonce in an ECDSA signature. This can be turned into an instance of the Hidden Number Problem, and solve it using lattices to recover the private key [8,[START_REF] Nguyen | The insecurity of the elliptic curve digital signature algorithm with partially known nonces[END_REF].

By injecting the partial information of nonces in the linear equations of n signatures, it can be rewritten as a linear system of n equations and (n + 1) variables:

u i X + v i ≡ Y i , (mod q), 1 ≤ i ≤ n. (3)
The unknowns are X (the private key α) and Y 1 , . . . , Y n (the unknown parts of the nonces). The Hidden Number Problem is finding X when the variables Y i are known to belong in a relatively small interval.

The simplest case is when the most significant bits (respectively least) of the nonces are known, thus the variables Y i consist of their least significant bits (respectively most). The number of signatures to collect depends on the leak obtained on each nonce. We can get a rough idea with a rule of thumb: with a t-bit curve and bits leaked per nonce, we can expect around t/ signatures for the lattice attack to succeed. For instance, with 5 least significant bits leaked on a 256-bit curve, an average of 54 signatures are generally sufficient. Therefore, this step in the attack has a negligible cost from a few milliseconds up to a few seconds.

Explanation and construction of lattices for each situation are detailed in Appendix A.

DFA on Montgomery Ladder

In this section, we present the Montgomery ladder algorithm, then we describe our attack.

The Montgomery Ladder Algorithm

One advantage of the Montgomery ladder algorithm for computing Q = [k]P is that the same elliptic curve operations are executed for each bit processed: the algorithm has a regular behavior. This is done by using two variable points R 0 and R 1 that satisfy the invariant R 1 -R 0 = P in each loop. Let k = (k n-1 , . . . , k 0 ) 2 the binary representation of the scalar k, and suppose the leading bits k down to k j are already processed, meaning that R 0 = [ k]P and R 1 = [ k +1]P . The state of the Montgomery ladder algorithm is updated depending on the current bit k j-1 as follows:

(R 0 , R 1 ) = ([2]R 0 , R 0 + R 1 ) if k j-1 = 0, (R 0 + R 1 , [2]R 1 ) if k j-1 = 1. ( 4
)
As a consequence, at the end of the step, we have R 0 = [2 k + k j-1 ]P , and the relation R 1 -R 0 = P still holds. The process goes on until the last bit, and the final state gives R 0 = [k]P .

To avoid branch conditions, a conditional swap with bitwise masking techniques is commonly used in implementations so the point doubling is executed with the correct value, and a second time after the operations to restore R 0 and R 1 (see Algorithm 2).

Remark 1. There is also a padding method to avoid a leak of the bit length of its input given in [START_REF] Brumley | Remote timing attacks are still practical[END_REF], using the group order q of bit length t: the scalar k is replaced with k +εq with ε ∈ {1, 2} that makes the new scalar exactly a (t+1)-bit integer. Since q is the order of the base point, the final result of the scalar multiplication is unchanged. We suppose in the following that this countermeasure is implicitly used.

Algorithm 2 Montgomery ladder

Require: k = (kn-1, . . . , k0)2, P , kn-1 = 1 Ensure:

Q = [k]P 1: R0 ← P 2: R1 ← [2]P 3: for i = n -2 down to 0 do 4: conditional swap(ki, R0, R1) 5: R1 ← R0 + R1 6: R0 ← [2]R0 7:
conditional swap(ki, R0, R1) 8: return R0

New Attack: Invariant Sign-Change Fault

We consider a fault that inverts the state of the ladder algorithm after the processing of the bit k j (see Sect. [START_REF] Blömer | Singular curve point decompression attack[END_REF] for examples of how it can be achieved):

R 0 = [ k]P R 1 = [ k + 1]P ----------→ fault R 0 = [ k + 1]P R 1 = [ k]P (5)
The value R 0 for processing the next bit is R = [ k + 1]P and the invariant for the remainder of the algorithm is the point I = -P . Thus, the resulting point of the scalar multiplication is

Q = [2 j ]R + [k]I = [( k + 1)2 j -k]P, (6)
where k = (k j-1 , . . . , k 0 ) 2 are the least significant bits following the bit processed when the fault was made. Then, the following difference is a point that depends only on the j least significant bits of k:

Q -Q = [2k -2 j ]P. ( 7
)
Those j bits can be found with an exhaustive search. An alternative is to calculate the sum

Q + Q = [ k2 j+1 + 2 j ]P, (8)
that depends only on the most significant bits of k. While this type of fault is undetectable with a point validation, a check of the invariant reveals that a wrong calculation occurred. This is true for classical formulas such as affine point addition or their projective equivalent (including the complete formulas of [START_REF] Renes | Complete addition formulas for prime order elliptic curves[END_REF]). However, there are specific formulas that do not use all point coordinates which has an impact on the previous description and makes the fault undetectable by a check of the invariant, and it is covered below. Remark 2. In the particular case of k = 2 j-1 the points Q and Q are equal, so it is impossible to distinguish with the cases where the fault has no impact on the swap operation.

x-only Formulas. The particularity of those formulas is that the y-coordinates of the points are not used to compute either a point doubling or a point addition [START_REF] Brier | Weierstraß elliptic curves and side-channel attacks[END_REF][START_REF] Izu | A fast parallel elliptic curve multiplication resistant against side channel attacks[END_REF]. Let P 1 = (x 1 , y 1 ) and P 2 = (x 2 , y 2 ). Given x 1 and x 2 , and the auxiliary value x P the x-coordinate of P 1 -P 2 , then those formulas compute the x-coordinate of P 1 + P 2 . No auxiliary data is needed for the point doubling (outside of the elliptic curve parameters). Those formulas are well adapted for the Montgomery ladder algorithm since the point addition occurs between two points whose difference is invariant and equal to the input of the scalar multiplication.

The invariant is replaced by -P in our attack. Its x-coordinate is the same as P , so the point additions in the following steps are correctly calculated, and the differential analysis can be done.

The interesting side-effect happens for the reconstruction of the missing coordinate y of the resulting faulty point, since it uses formulas involving the two coordinates of the invariant (see Appendix B for the formula). In this case, the invariant has changed from (x P , y P ) to (x P , -y P ), and the code might use the original invariant directly, stored in registers and not modified by the execution. The sign difference only impacts the y-coordinate of the output Q which is the same as in Eq. ( 6) with a sign change (so it passes a point validation test). However, the attack on ECDSA needs to construct candidates for Q which also includes -Q so it makes no difference in the analysis.

Furthermore, a check of the invariant would not detect the fault. Indeed, the points R 0 and R 1 will be reconstructed as R 0 = -R 0 and R 1 = -R 1 as explained above, so the difference

R 1 -R 0 = -(R 1 -R 0 ) = P
would yield the invariant P as if no fault occurred.

Co-Z Formulas. We look now at the co-Z formulas based on Jacobian projective representation of the points: a point (x, y) is represented by (X : Y : Z) with x = X/Z 2 and y = Y /Z 3 . The particularity of those formulas is the requirement that the two points share the third projective coordinate Z. We consider the variant that does not use this coordinate in the formulas [START_REF] Goundar | Scalar multiplication on Weierstraß elliptic curves from co-Z arithmetic[END_REF].

Instead of a regular point doubling and point addition in a ladder step, it is composed of two additions, XYcoZ-ADDC and XYcoZ-ADD, such that the two inputs share the same Z-coordinate, and give two outputs with the same property: XYcoZ-ADDC : (P 1 , P 2 ) → (P 1 + P 2 , P 1 -P 2 ) XYcoZ-ADD : (P 1 , P 2 ) → (P 1 + P 2 , P 1 ).

A formula for the recovery of the missing coordinate Z is necessary at the end of the scalar multiplication during the processing of the last bit to get the affine form.

The formulas are correct as long as the points share the Z-coordinate, and this property is not impacted by the attack. What remains to observe is the effect on the Z-coordinate recovery. The original invariant (x P , y P ) might be used instead of the new one (x P , -y P ) following the fault for the same reason as with the x-only formulas, and the consequence is the appearance of a factor -1 in the reconstructed coordinate Z of the points R 0 and R 1 (see Appendix B for details). But it only changes the sign of the affine coordinate y due to the Jacobian coordinates. So the erroneous output Q is a valid point of the elliptic curve.

Finally, as with the x-only formulas, a check of the invariant would not detect the fault. Indeed, we have R 1 -R 0 = -P after the fault, and the points are reconstructed as R 0 = -R 0 and R 1 = -R 1 so the difference R 1 -R 0 would yield the correct invariant. Remark 3. An alternative view for the x-only and co-Z formulas is that the invariant of the algorithm is not the full point P anymore, but only its x-coordinate which stays intact during the attack.

Unknown

Step. The differential points in Eq. ( 7) and ( 8) do not depend only on the least or most significant bits of the secret scalar, but also on the step where the fault was made. This could result in several candidates if several steps j are considered during the analysis.

Conservative choices can be made to lift this indeterminacy, at the cost of losing a few bits of the scalar. Suppose we retrieved the discrete logarithm d = 2k -2 j of the differential point of Eq. ( 7), but the step j is unknown. We can compute d/2 mod 2 i for an integer i that we expect to be smaller than j (say 5 for i against 10 for j), then the i least significant bits are retrieved.

The loss of precision is not impactful as the lattice attack on ECDSA can still be successful from a few bits per nonce.

DFA with Scalar Randomization

In this section, we present how differential fault attacks might still be applicable when the scalar is randomized with scalar blinding methods in the context of ECDSA.

Scalar Blinding with Group Order

This is the most classical measure proposed in [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]. The secret scalar k is replaced with

k = k + mq,
where m is a random integer of λ bits. Since q is the order of the base point P , then we have

Q = [k ]P = [k]P + [mq]P = [k]P.
Write k = k 2 j +k where k are the j least significant bits, and k the most significant bits. Suppose that a DFA reveals k (as in our attack on Montgomery ladder), then the unknown part satisfies the inequality

q -k 2 j ≤ k < q + 2 λ q -k 2 j , (9)
which is an interval of width q/2 j-λ . Then, it is necessary to have j > λ for the unknown to be in an interval of width less than q, a necessity for exploitation in a lattice attack on ECDSA as described in Appendix A.

Cost. Suppose that we get a point whose discrete logarithm depends on the j = λ + ε least significant bits of the blinded scalar for a nonnegative ε. An exhaustive search on those bits is expensive in this case, so a discrete logarithm algorithm such as BSGS and Pollard's kangaroo might be used to find the bits more efficiently in complexity O(2 (λ+ε)/2 ). For example, if λ is 20 (as was originally suggested in [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF]), then a fault on the step j = 24 would make the discrete logarithm easy to find, and a small ε is sufficient to attack ECDSA as can be attested in our simulation tools. Therefore, the cost depends essentially on λ which has to be chosen quite large to prevent the attack or to make it impractical.

Euclidean Splitting

This method was proposed in [START_REF] Ciet | Virtually) free randomization techniques for elliptic curve cryptography[END_REF] to protect against side-channel attacks as an alternative for scalar blinding. The secret scalar k is rewritten as We show here how to recover the random divisor (or one of its factors) and the remainder of the Euclidean division of a secret scalar k from a single fault. This can be used in ECDSA for a lattice attack, and on a fixed scalar with the Chinese Remainder Theorem.

k = am + b,
We start by giving the general principle. Let R = [a]P the scalar multiplication with the quotient, so the output is given by The first list depends only on the base point, so it can be computed once and stored for reuse. Since both m and b are less than 2 λ , both the time and space complexities of the algorithm are O(2 λ ).

Q = [m]R + [b]P.
The proposed target is the scalar multiplication [m]R with the random divisor. We suppose a fault has been made such that the effective calculation is [m ]R where the difference δ = m -m belongs to a set of size T . Then the result of the whole scalar multiplication

Q = [m]R + [b]P is altered in a point Q = [m ]R + [b]P ,
and their difference is

Q -Q = [δ]R.
A candidate for R is constructed from each candidate δ for δ:

R = [1/ δ](Q -Q ).
The BSGS strategy is applied to get candidates ( m, b) that satisfy the equality

Q -[ m] R = [ b]P.
Cost. There are T possible values for δ and the BSGS algorithm runs in O(2 λ ) steps, so the overall cost is O(2 λ T ). So it is practical only for a small parameter λ (the only library implementing this technique that we found uses a parameter λ of 32 bits so the time and memory constraints are low enough). In particular, the memory constraints of BSGS should make the attack infeasible for λ = 64.

from which we derive the relation

a ≡ δ( b -b)(m δ -mδ) -1 (mod q). (11)
The quotient a is recovered, so the scalar k can be fully reconstructed and verified with the relation Q = [k]P . This case seems unlikely to happen.

In the case the candidates are ( m1 , b), . . . , ( mN , b), then we can pose d = gcd( m1 , . . . , mN ), and we get the relation k ≡ b (mod d).

Example with the Invariant Sign-Change Fault. We apply the attack of Sect. 3.2 when no specific formulas are used. After a fault on the scalar multiplication

[m]R, then the result is [m ]R with m = ( m + 1)2 j -m. The difference with the correct output Q is Q -Q = [2m -2 j ]R,
and the value δ = 2m -2 j depends only on the least significant bits of m. Therefore, the BSGS part of the attack only needs to run an exhaustive search on the most significant bits of m. If the baby steps are precomputed, then the complexity is O(2 λ ).

Multiplicative Splitting

This technique was proposed in [START_REF] Trichina | Implementation of elliptic curve cryptography with builtin counter measures against side channel attacks[END_REF]. A random value m of λ bits is randomly generated, and γ is defined such that we have the relation

k ≡ mγ (mod q).
The scalar multiplication Q = [k]P is computed in two successive scalar multiplications as R = [m]P and Q = [γ]R.

The differential fault attack can be applied with a fault in the second scalar multiplication. We suppose a fault has been made such that the effective calculation is [γ ]R where the difference δ = γ -γ belongs to a set of size T . Then the result of the whole scalar multiplication Q = [γm]P is altered in a point Q = [γ m]P , and their difference is

Q -Q = [δm]P.
The value δm can be found by running through all possible values for δ, and then computing the discrete logarithm of the point [m]P in base P with BSGS or Pollard's kangaroo algorithms.

Cost. Since m is a positive integer less than 2 λ the overall cost is O(2 λ/2 T ). The cost is similar to the attack on the blinding with the group order, so it is tractable for small λ (such as 20 or 32).

Example with the Invariant Sign-Change Fault. In certain cases, a single discrete logarithm is sufficient when δ represents a small value. For example, if we consider the fault of Sect. 3.2 during the processing of the bit γ j , then the difference with the result of the whole scalar multiplication is

Q -Q = [(2γ -2 j )m]P.
We obtain a point whose discrete logarithm in base P is less than 2 λ+j (in absolute value), so the complexity to find it is O(2 (λ+j)/2 ). Again, this is practical when λ is relatively small (as was suggested in the paper that proposed this method), then the discrete logarithm can be found in a matter of seconds or minutes.

This discrete logarithm is useful for lattice attacks on ECDSA. Indeed, we have the relation

k -mγ m2 j ≡ γ (mod q), ( 12
)
where γ is a relatively small integer compared to the order q (at least j bits less). When it is possible to distinguish m from 2γ -2 j in the discrete logarithm (if m is prime for instance), then a lattice attack can be applied.

Practical Evaluation

In this section, we consider the practicality of the attack and present evidence on how it can be achieved on several cryptographic libraries, with simulated experiments to validate our claims that are publicly available. 1

Montgomery Ladder in Libraries

In most cryptographic libraries, the second swap in the loop is merged with the first swap of the next step to avoid an unnecessary swap: the swap is effective only if the scalar bit differs from the previous one. This variant is presented in Algorithm 3. We list in Table 1 the variant used for several libraries that implement the Montgomery ladder algorithm for the elliptic curve scalar multiplication. Elliptic curves in Montgomery form such as Curve25519 are also present in the table, though those are not used for ECDSA, the attack might still be applicable in situations where the attacker can obtain the correct and erroneous outputs.

It shall be noted that in some cases side-channel attacks could be sufficient, but those are inherent to how the actual swap is implemented. There is the binary masking technique, where the swap is made using a mask with its bits 1 https://github.com/orangecertcc/dfa-ladder.

all set to 0 or 1, and a template attack was applied where the leak comes from the AND binary operator [START_REF] Nascimento | Attacking embedded ECC implementations through cmov side channels[END_REF]. In the case of Mbed TLS, the multiplication by 0 or 1 is used to swap the values, and is also vulnerable to a template attack [START_REF] Loiseau | Template attacks against ECC: practical implementation against Curve25519[END_REF]. In both cases, a single trace could reveal the whole scalar.

Assuming that an implementation is protected against these attacks, then a fault attack becomes relevant. In the following we present a strategy to perform our attack with the variant of Algorithm 3.

Realization of the Fault Attack

Physical access to the device is necessary, and the attacker must be able to disturb the calculation at a specific point in time and location.

Skip Instruction. The first model considered is the skip instruction that was applied successfully in practice on RSA exponentiation with a spike injection on a microcontroller to skip a squaring [START_REF] Schmidt | A practical fault attack on square and multiply[END_REF]. It was also recently applied in the elliptic curve point decompression algorithm to make a point lie on weak curve [START_REF] Blömer | Singular curve point decompression attack[END_REF][START_REF] Takahashi | Degenerate fault attacks on elliptic curve parameters in OpenSSL[END_REF].

The effects described in Sect. 3.2 can be achieved if line 1 of Algorithm 3 is omitted during one iteration of the algorithm. Indeed, the variable pbit at the beginning of the loop refers to the previous scalar bit, and keeps track of the current state of the couple (R 0 , R 1 ) such that the loop invariant is

R 1-pbit -R pbit = P.
So, if the line "pbit ← pbit ⊕ k i " is not executed and the bit k i is 1, then the variable pbit is not updated:

-If pbit was 0, then we have R 1 -R 0 = P , the points are not switched, so we still have R 1 -R 0 = P ; -If pbit was 1, then we have R 0 -R 1 = P , the points are switched, so we have now R 1 -R 0 = P .

In both cases, the variable pbit gets the value 1 at the end of the loop, so starting from the next iteration we have

R 1-pbit -R pbit = R 0 -R 1 = -P,
and the sign of the loop invariant has changed for the remainder of the algorithm. One alternative is to target the line "pbit ← k i ". If this line is skipped and the bit k i differs from the value in the variable pbit, then it will not be consistent with the current state or (R 0 , R 1 ), but starting from the processing of the next loop iteration.

Remark 4. Of course, in half of the cases, skipping one of these instructions will not have an effect and result in a correct output (and it is discarded in our attack).

Algorithm 4 Constant-time conditional swap of two values with binary operators (comments: alternative version)

Require: (w0, w1), bit b Ensure:

(w b , w 1-b ) mask ← (b, . . . , b)2 tmp ← mask ∧ (w0 ⊕ w1) tmp ← w0 w0 ← w0 ⊕ tmp w0 ← (w0 ∧ ¬mask) ∨ (w1 ∧ mask) w1 ← w1 ⊕ tmp w1 ← (w1 ∧ ¬mask) ∨ (tmp ∧ mask) return (w0, w1)
Fault in a Register. A common method for the conditional swap is to use binary masks as presented in Algorithm 4. The interesting part is the construction of the binary mask. It is generally done using the binary representation of -1 in a machine-word with all bits set to 1. So the value -b gives a null mask if b is 0, and a binary mask with all bits set to 1 if b is 1.

However, there are other ways to construct such masks, where any nonzero b ends up with a binary mask with bits set to 1. Let N the bit length of machinewords, then the two equivalent following formulas give an example of such construction (the first one is present in Mbed TLS and the second in OpenSSL) where ">>" is the bitwise shift right operator:

-(b ∨ (-b)) >> (N -1) or (¬b ∧ (b -1)) >> (N -1) -1.
A fault that randomly modifies the register that contains the bit b will have the desired effect and swaps the points if the original value of b is 0. This can be achieved with a random fault on a register.

Simulations

Simulations were used to put in practice our attack and evaluate the other different cases of the paper. The first one uses the GNU Debugger GDB to simulate faults according to the fault models presented above in the OpenSSL implementation of the Montgomery ladder algorithm. The second is based on the Unicorn engine2 to test the effect of faults wrongly injected with the skip instruction fault model. Finally, other cases with the randomization methods were also simulated in Python and the lattice attack used the fpylll library [START_REF]The FPLLL development team: fpylll, a Python wraper for the fplll lattice reduction library[END_REF].

GDB Simulation. We give in Listing 1.1 part of the assembly code related to the loop of the Montgomery ladder algorithm in OpenSSL version 1.1.1k (compiled on a Raspberry Pi device model 4B).

The instruction on address 0xdd208 corresponds to the line "pbit ← pbit ⊕ k i " that needs to be ignored in the skip instruction fault model. The second fault model can be achieved with a modification of register r6 after this same instruction. Indeed, this variable is only used thereafter for the conditional swap on each point coordinates.

It is easy to instrument these faults with GDB, and has been automatized with two scripts. In both cases the analysis on the signatures followed by the lattice attack resulted in a successful private key recovery.

Unicorn Simulation. Unicorn is CPU framework emulator and we used it through the Rainbow tool3 that makes it easy to trace the execution of all instructions of a binary. It can be stopped at any moment and the next instruction can be read. Then the skip instruction fault model can be instrumented as follows: we read the next instruction, and it is skipped by resuming the execution at the following instruction using the size of the skipped instruction.

The constant-time big integer modular arithmetic of the secp256r1 curve written in assembly was chosen (taken from the OpenSSL project). It has no external dependency which makes it easier to work with the emulator. Two binaries were created to implement the Montgomery ladder variant of Algorithm 3: the first with Jacobian projective coordinates, and the second with co-Z formulas.

The instructions related to the lines "pbit ← pbit ⊕ k i " and "pbit ← k i " are present in the assembly code of both binaries. When one of those is skipped during an iteration of the main loop, then the analysis of Sect. 3.2 is successful and the least significant bits of the scalar are recovered.

A. Russon

However, we found a false positive situation with both binaries when the fault skips one instruction in the function that extracts one bit of the scalar. What happens is that the extracted bit is incorrect: the bit k j is replaced with 1 -k j , but the remaining of the scalar multiplication is done correctly. This is equivalent to a bitflip of the scalar, and as a consequence we have

Q -Q = [-2 j ]P if k j = 0, [2 j ]P if k j = 1.
If we look at Eq. ( 7), this might wrongly reveal that the least significant bits of the scalar are only composed of zero bits. Therefore, to avoid a wrong signature in the lattice attack against ECDSA, it might be better to discard this case (say j is 16, then there would be one out 65536 scalars on average where the 16 least significant bit are indeed set to 0 so discarding a correct result would be rare). Another false positive was observed with the Jacobian projective formulas: after a specific instruction skip in the point addition function, one of the points is not loaded correctly and the addition happens with the same point: the doubling function is called instead, and the analysis catches a wrong value.

For the co-Z binary, we included the invariant check at the end of the scalar multiplication as a countermeasure [START_REF] Vasyltsov | Fault detection and a differential fault analysis countermeasure for the Montgomery power ladder in elliptic curve cryptography[END_REF]. We adapted the XYcoZ-ADD function such that it computes the difference of the inputs (the invariant) instead. Once the missing Z-coordinate is recovered and the points are converted to their affine representation, the calculated invariant I is XORed with P , the correct invariant, and the output Q:

Q ⊕ I ⊕ P.

If the calculated invariant is correct, it should be canceled by P . As was expected from Sect. 3.2, I is indeed correctly calculated as P . The output is a valid point and it does not prevent our attack.

Countermeasures

As with other works where the fault does not make the elliptic curve point leave the curve, a point validation cannot detect the fault, even in the case of x-only or co-Z formulas (for the former it was suggested in [START_REF] Ebeid | Securing the elliptic curve Montgomery ladder against fault attacks[END_REF] to recover the missing coordinate and perform the verification, but in the context of the attack of [START_REF] Fouque | Fault attack on elliptic curve Montgomery ladder implementation[END_REF], and would not be able to prevent our attack). Verification of the Montgomery ladder invariant was proposed in [START_REF] Dominguez-Oviedo | Algorithm-level error detection for Montgomery ladder-based ECSM[END_REF][START_REF] Vasyltsov | Fault detection and a differential fault analysis countermeasure for the Montgomery power ladder in elliptic curve cryptography[END_REF] against fault attacks. As we have seen in Sect. 3.2, it should work in general because the invariant is changed, except in the cases of the x-only and co-Z formulas (the reconstructed invariant would be the correct one) as was experimented in Sect. 5.3.

There is another idea from [START_REF] Dominguez-Oviedo | Algorithm-level error detection for Montgomery ladder-based ECSM[END_REF] to prevent our attack with the x-only and co-Z formulas. It is a variant of the point blinding countermeasure from [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] adapted to Montgomery ladder: the algorithm is initialized as R 0 = P + R and R 1 = [2]P + R for a random point R, and the invariant R 1 -R 0 is still the input P . At the end of the scalar multiplication we have R 0 = [k]P + [2 n-1 ]R, so a subtraction by S = [2 n-1 ]P is needed to get the correct output. In our attack, the points R 0 and R 1 are inverted and the invariant becomes -P :

R 0 = [k ]P + [2 n-1 ]R R 1 = R 0 -P.
We have seen that it changes the sign of the reconstructed point after the recovery of the missing coordinate. Therefore, subtracting the blinded point to get the output would give

Q = -R 0 -[2 n-1 ]R = -[k ]P -[2 n ]R,
and without the knowledge of the point R, the output is useless for an attacker. However, this is true as long as R is randomly selected at each new execution, and it was originally proposed to update R by replacing it with the point [(-1 β )2]R with β ∈ {0, 1} chosen randomly. With faults successfully injected in consecutive runs, it might be possible to deduce the point R, and then the differential analysis could be done.

Classic countermeasures such as repeating the operations twice and check consistency can be applied against our attack. To reduce the cost, it was proposed in [START_REF] Blömer | Sign change fault attacks on elliptic curve cryptosystems[END_REF] to make the second computation on an elliptic curve E p over a smaller prime field F p , and the first on an elliptic curve E pp over the integer ring Z/pp Z. On one hand, the reduction modulo p of the result gives the expected calculation, and on the other hand, the reduction modulo p is checked with the calculation on E p .

A variant of the previous method was proposed in [START_REF] Joye | A method for preventing "skipping" attacks[END_REF][START_REF] Schmidt | A fault attack on ECDSA[END_REF] where the second computation is done on an auxiliary group glued together with the elliptic curve operation. For instance, it can be done by adding an integer to point coordinates which keeps track of the current discrete logarithm of the points using the following rules:

(P 1 , 1 ) + (P 2 , 2 ) = (P 1 + P 2 , 1 + 2 ), [2](P, ) = ([2]P, 2 ).
If no fault occurred the resulting point should be ([k]P, k) with k the secret scalar. This method should detect the fault in our attack since the auxiliary value is consistent with the point, so a change in the point affects the value too.

Finally, in the case of an attack on ECDSA, it is always possible to verify the signature at the end of the calculation.

Conclusion

In this paper, we presented a new differential fault attack on Elliptic Curve Cryptography with the Montgomery ladder algorithm. We showed that an attacker can switch two points with either a skip instruction or a random fault in a register. With this modification in the program flow, the least (or most) significant bits of the secret scalar can be determined from the difference between the correct and erroneous outputs.

Furthermore, this attack bypasses some of past countermeasures against fault attacks on ECC. A consequence is that particular care is necessary to choose the right measures to protect an implementation when protection against fault attacks is part of the threat model.

Finally, we presented evidence that scalar randomization with common methods is not enough to thwart differential fault attacks. It requires that the randomizer is small enough for the attack to be practical. However, it is generally suggested in the papers that proposed such methods to choose them small to reduce the extra cost.

Future work could explore further ways to achieve the effects of our attack using other fault models or targeting other instructions, or investigate other randomization methods.

A Lattice Attack

In this appendix, we present the lattice construction to solve the Hidden Number Problem, then we give the values for the particular cases met in the paper.

A.1 Lattice Construction

First we introduce the notation | • | q defined as |z| q = min y∈Z |z -yq|, for any real z, which is a reduction modulo q in the range [-q/2, q/2] followed by an absolute value.

Let uX + v ≡ Y mod q a linear equation in the variables X and Y , where an approximation viewed as an integer of Y is known:

B 1 ≤ Y < B 2 ,
where B 1 and B 2 are two integers with (B 2 -B 1 ) < q/L for a positive integer L. The width of the interval can be reduced by centering around 0. Let C = (B 1 + B 2 )/2 be the center of the interval, and we get the bound

|Y -C| < q/(2L). Therefore, noting v = C -v, we have |uX -v | q = |Y -C| q = |Y -C|, since we know that (Y -C) is in [-q/2, q/2].
Then, using the bound on it, we obtain the inequality |uX -v | q < q/(2L),

whose meaning is that when seen modulo q, the value v is close to a multiple of the hidden number X.

Given n inequalities of the form |u i X -v i | q < q/(2L i ) derived from equations where X is a common variable, we construct the lattice generated by this integer matrix:

         2L 1 q 2L 2 q . . . 2L n q 2L 1 u 1 2L 2 u 2 • • • 2L n u n 1 0 2L 1 v 1 2L 2 v 2 • • • 2L n v n 0 q          .
Denoting m i the i-th line of the matrix, and u = (2L 1 u 1 , . . . , 2L n u n , 1, 0) v = (2L 1 v 1 , . . . , 2L n v n , 0, q), the vectors from the last two lines of the matrix, there exists integers λ i such that the vector Xu -v + n i=1 λ i m i is a short vector of the lattice according to the inequalities, since each coordinate is bounded by q.

Applying a lattice basis reduction algorithm such as LLL [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] or BKZ [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF], there is a possibility that one of the vectors of the reduced basis is the one we are looking for. By construction, this short vector has the hidden number X as its penultimate coordinate. In the different settings, it corresponds with a private key and can be easily checked with the public key.

A.2 Application to ECDSA

First, we recall that a signature (r, s) can be rewritten: k ≡ αr/s + H(M )/s (mod q). The hidden number X is the private key α, while the unknown variable Y corresponds partially to the ephemeral value k in various ways depending on each of the following cases. With the padding method applied on k beforehand, we have 2 t ≤ k < 2 t + q so the unknown a is bounded by

2 t -b m ≤ a < 2 t + q -b m ,
of width q/m. When the blinding method of Sect. 4.1 is used instead of a padding, we have the inequality in Eq. ( 9) when the least significant bits are known.

Algorithm 5 Recovery of the missing coordinate with co-Z formulas in the last step of the Montgomery ladder algorithm.

1: R 1-k 0 , R k 0 ← XYcoZ-ADDC(R k 0 , R 1-k 0 ) 2: Z ← (X(R1) -X(R0))xP Y (R k 0 )/yP X(R k 0 ) 3: R k 0 , R 1-k 0 ← XYcoZ-ADD(R 1-k 0 , R k 0 ) 4: Q = (X(R0)/Z 2 , Y (R0)/Z 3 )

If the invariant sign-change fault attack of Sect. 3.2 is successful, then we have R 1 -R 0 = -P = (x P , -y P ). A correct reconstruction of R 0 should use -y P instead of y P in Eq. ( 14). On the contrary, it will introduce a factor -1 in the computation of y 0 , so the reconstructed point will be R 0 = -R 0 . A similar formula can be derived for R 1 and the reconstruction would give R 1 = -R 1 . So the difference R 1 -R 0 would still be equal to the original invariant.

B.2 Co-Z Formulas

Those formulas are based on the Jacobian projective coordinates: a point (x, y) is represented by (X : Y : Z) with x = X/Z 2 and y = Y /Z 3 . The variant considered does not use the third coordinate Z in calculation.

The missing coordinate is mandatory to get the affine representation. Let P = (X : Y : Z) with the coordinate Z unknown, and (x, y) its known affine representation, then we have

Z = x • Y y • X . (15)
On the last step of the Montgomery ladder algorithm, the XYcoZ-ADDC operation computes the difference of the points R 0 and R 1 , so the invariant P appears in Jacobian projective form. The above formula allows the reconstruction of its missing Z-coordinate which is common to R 0 and R 1 . This is given in Algorithm 5 (another factor is present in line 2 to take into account the final XYcoZ-ADD operation).

If the invariant sign-change fault attack of Sect. 3.2 is successful, then the invariant becomes -P which introduces a factor -1 in Eq. ( 15) since the affine coordinates of P will be used. As a consequence, the missing coordinate reconstructed in line 2 of Algorithm 5 will be -Z. Let R 0 = (X 0 : Y 0 : Z) and R 1 = (X 1 : Y 1 : Z) the two points at the end of the Montgomery ladder algorithm. Then using -Z instead of Z to get the affine form will result in

R i = X i (-Z) 2 , Y i (-Z) 3 = (x i , -y i ) = -R i , i ∈ {0, 1}.
So the difference R 1 -R 0 would still be equal to the original invariant.

  where m is a random integer of λ bits with a = k/m and b = k mod m. Then, the scalar multiplication Q = [k]P can be computed as Q = [m]([a]P ) + [b]P using three individual scalar multiplications and a point addition.

  If the point R is known, then the BSGS algorithm can be applied to find m and b. It consists of computing a first list of possible values for [b]P (the baby steps), then a second list of possible points for Q -[m]R (the giant steps) until a collision with the first list occurs, revealing the values m and b.

  Several Candidates. Eventually, several candidates for (m, b) can be found, but we can still salvage valuable information on the scalar k. Let ( m, b) a candidate alongside the corresponding value δ. The correct values (m, b) and δ are also amongst the candidates. We start with the case b = b. Since ( m, b) is a candidate, we have [ m] R + [ b]P = [m]R + [b]P,

Case 1 .

 1 Let k = am + b the Euclidean division of k by an integer m. This case concerns the attack on the Euclidean splitting in Sect. 4.2, but also cases when the least significant bits are known by setting m = 2 . If m and b are known, then we have      Y = a, u = r/(sm) mod q, v = H(M )/(sm) -b/m mod q.

Table 1 .

 1 Overview of Montgomery ladder in several cryptographic libraries.

	Library	Init.	Swap variant Formulas Remarks
	Weierstrass curves
	OpenSSL 1.1.1k	(P, 2P ) Algorithm 3* x-only
	LibreSSL 3.2.4	(P, 2P ) Algorithm 3* Jacobian
	CoreCrypto (Apple) (P, 2P ) Algorithm 3 Co-Z	Point valid., Eucl. split
	Montgomery curves
	SymCrypt	(O, P ) Algorithm 3 x-only
	Mbed TLS	(O, P ) Algorithm 2 x-only
	libsodium †	(O, P ) Algorithm 3 x-only
	*The source code is slightly different but the compiled code corresponds to
	Algorithm 3.
	†ref10 implementation of Curve25519 present in other libraries.

Algorithm 3 Processing of the bit k i in the Montgomery ladder variants with merged swaps.

1: pbit ← pbit ⊕ ki 2: conditional swap(pbit, R0, R1) 3: R1 ← R0 + R1 4: R0 ← [2]R0 5: pbit ← ki

  Listing 1.1. Excerpt of assembly code of the function ec scalar mul ladder in OpenSSL 1.1.1k.

	dd1e8 : mov	r1 , r8
	dd1ec : ldr	r0 , [ sp , #8]
	dd1f0 : bl	8 b440 < BN_is_bit_set >	; r0 <-current bit k_i
	dd1f4 : ldr	r6 , [ sp , #12]	; r6 <-pbit
	dd1f8 : mov	r3 , r9
	dd1fc : ldr	r2 , [ fp , #8]
	dd200 : ldr	r1 , [ r7 , #8]
	dd204 : sub	r8 , r8 , #1
	dd208 : eor	r6 , r6 , r0	; r6 <-pbit XOR k_i
	dd20c : mov	sl , r0
	dd210 : mov	r0 , r6
	dd214 : bl	8 b554 < BN_consttime_swap > ; swap X if r0 = 1
	dd218 : mov	r0 , r6
	dd21c : mov	r3 , r9
	dd220 : ldr	r2 , [ fp , #12]
	dd224 : ldr	r1 , [ r7 , #12]
	dd228 : str	sl , [ sp , #12]	; pbit <-k_i
	dd22c : bl	8 b554 < BN_consttime_swap > ; swap Y if r0 = 1
	dd230 : mov	r0 , r6
	dd234 : mov	r3 , r9
	dd238 : ldr	r2 , [ fp , #16]
	dd23c : ldr	r1 , [ r7 , #16]
	dd240 : bl	8 b554 < BN_consttime_swap > ; swap Z if r0 = 1

https://www.unicorn-engine.org/.

https://github.com/Ledger-Donjon/rainbow.

A. Russon

Case 2. Instead, if a and m are known in the Euclidean division of k by m, then we have

The unknown b is a non-negative integer less than m. This case corresponds to the most significant bits of k known. Suppose that we know the ( + 1) most significant bits (including one from the padding), then m = 2 t-(which can be approximated to q/2 when q is very close to 2 t for some standardized elliptic curves).

Case 3. This is the situation of Sect. 4. [START_REF] Biehl | Differential fault attacks on elliptic curve cryptosystems[END_REF] where k is randomized by an integer m of at most λ bits, and is rewritten as k ≡ mγ mod q. If m and the least significant bits γ of γ are known, we can write

where the unknown is γ (the most significant bits of γ). We have

If no padding was applied on the scalar multiplication with γ, then the unknown is bounded by 0 ≤ γ < q/2 , and if a padding is applied then the bound on the unknown is

both of them of width q/2 .

B Coordinates Recovery

In this appendix, we give more details on the recovery of the missing coordinates for the x-only and co-Z formulas.

B.1 x-only Formulas

Those are based on the homogeneous projective coordinates: a point (x, y) is represented as [X : Z] where x = X/Z for a nonzero Z.

The missing coordinate can be recovered in the case of the Montgomery ladder algorithm. Let [X 0 : Z 0 ] and [X 1 : Z 1 ] the representations of two points R 0 and R 1 , and P = (x P , y P ) the point such that R 1 -R 0 = P . The formula to recover the affine y-coordinate of R 0 is y 0 = 2BZ 2 0 Z 1 + Z 1 (AZ 0 + x P X 0 )(x P Z 0 + X 0 ) -X 1 (x P Z 0 -X 0 ) 2 2y P Z 2 0 Z 1 [START_REF] Dominguez-Oviedo | Algorithm-level error detection for Montgomery ladder-based ECSM[END_REF]