<<

. 2
( 2 .)



exploited by the attacker.
Only those acquisitions for which r is a weak mask may be relevant to an at-
tacker. In this case, the intermediate variables are unmasked after some steps of
our algorithm. Clearly, the expected number of acquisitions to mount a di¬eren-
tial side-channel attack against our algorithm grows inversely proportional with
the probability that r be a weak mask. Since the probability of picking a weak
mask is negligible, di¬erential side-channel attacks are infeasible in practice.

Fault attacks The resistance of our algorithm against fault attacks is based
on the relationship R2 (R0 , R1 ) = (xκ , xκ+1 ) for some κ ∈ N. If an error occurs
on a temporary result or during one of the group operations at any time during
the computation, the mutual coherence of R0 , R1 , and R2 is de¬nitively lost.
As a consequence, the result of the last multiplication R2 R0 is just some perfect
random number to an attacker that cannot be exploited as such, at least if we
assume the input was not blinded with a weak mask. Again, as weak masks are
extremely unlikely in practice, any such error will be caught by our countermea-
sure.
However, as in [11], Fig. 4 algorithm fails to thwart exponent or loop counter
disturbance as it does preserve the former relationship. Such faults hence have
to be handled by other techniques. As pointed out in [12], avoiding conditional
branching is safer since modifying the result of a comparison or the value of a
loop counter by tampering with the associated register is easy. On the contrary,
in order to by-pass an instruction, the attacker would have to increment the
program counter. Such a precise modi¬cation is hardly feasible in practice. For
that reason, we propose combining the on-the-¬‚y checksum computation of [11]
with the infective computation technique of [12] (Fig. 5). Let γ = CKS • CKSref
be the di¬erence between the re-computed checksum CKS and the reference
checksum value CKSref . The most signi¬cant bits of R2 are xored with γ before
the last multiplication. Hence, the ¬nal result will be spoiled whenever γ = 0
i.e. whenever the exponent or the loop counter has been tampered with.


3.2 E¬ciency Analysis

Time Montgomery ladder (Fig. 3) requires t multiplications and t squarings.
Our algorithm (Fig. 4) requires t more squarings for computing the compen-
sative factor. The inversion and the two multiplications involved in the masking
and unmasking process can be neglected with respect to the cost of the overall
computation. Let M denote the cost of a multiplication. The cost of a squaring
can be approximated to 0.8M . Each step of our algorithm costs 2.6M compared
to 1.8M for Montgomery ladder, that is a 44.44% time complexity increase.


Storage Compared to Montgomery ladder, our algorithm requires one more
register R2 for the compensative factor, that is a 50% storage increase.
Note however that many cryptographic co-processors cannot store the result
of some operations “ as the modular multiplication or squaring “ at the address
of the operands. With such architectures, three registers for the standard Mont-
gomery ladder and four registers for our algorithm are needed, corresponding to
a 33% storage increase.


4 Conclusion

This paper presents an algorithm for computing exponentiations in ¬nite abelian
groups, especially relevant in the RSA and ECC setting, that is intrinsically
resistant to all known simple and di¬erential side-channel analysis and fault
attacks, while requiring roughly at most 50% more time and storage compared
to traditional balanced implementations.
Our countermeasure is especially suited when only the parameters needed
for the computation itself are known, which is extremely valuable as additional
parameters are rarely available to the cryptographic device. In particular, neither
the group order nor the public exponent are required.


Acknowledgment

The authors would like to thank Jean Creignou for many helpful remarks on the
preliminary version of this paper.


A Proof of Theorem 1

Lemma 1 (Cauchy™s Lemma). Any ¬nite group whose order is divisible by a
prime number p contains an element of order p.
De¬nition 2. Let G be a ¬nite abelian group and p be a prime number. Let
Gp denote the subgroup of all elements of G whose order is a power of p. Any
element x ∈ Gp is called a p-torsion element of G.
Lemma 2. Let G be a ¬nite abelian group. We have

G∼ Gp .
=
p | |G|

n
Proof. Let |G| = i=1 pβi where pi,i∈{1,...,n} are prime numbers.
i
Let us show that the homomorphism ψ de¬ned as
n
ψ
Gpi ’’ G
i=1
n
(x1 , . . . , xn ) ’’ xi
i=1

is an isomorphism. First, we show that ψ is a monomorphism.
Let x and y be in the abelian group G. Let | x | = a be the order of x and
| y | = b the order of y in G. First, observe that if a and b are coprime, then
xy = 1 ’ x = y = 1. This is a consequence of B´zout™s identity. Since a and b
e
are coprime, there exists integers u and v such that au + bv = 1. We have

xy = 1 ’ (xy)au = 1 (1)

and as xa = 1, we have (xy)au = xau y au = y au . Then, since y b = 1, we get

(xy)au = y au = y au y bv = y au+bv = y . (2)

From (1) and (2), we have y = 1. In the same way, we show xy = 1 ’ x = 1.
n
Now let us suppose that ψ(x1 , . . . , xn ) = i=1 xi = 1. Clearly the order of x1
n n
and the order of i=2 xi are coprime, and as we have shown above, x1 — i=2 xi =
1 ’ x1 = 1 and n xi = 1. In particular x1 = 1. Then, by induction on the
i=2
n
relation i=2 xi = 1, we get the expected result
n
ψ(x1 , . . . , xn ) = xi = 1 ’ x1 = . . . = xn = 1 .
i=1

Now let us show that ψ is an epimorphism.
n
For all y ∈ G, | y | divides |G|. Hence, | y | = i=1 pγi where γi ¤ βi for
i
γ
all i ∈ {1, . . . , n}. Let ui = j=i pj j for i ∈ {1, . . . , n}. Then, y ui ∈ Gpi since
| y ui | = pγi . Moreover, the ui,i∈{1,...,n} are coprime as there exists no integer
i
dividing all ui . According to B´zout™s identity, there exists a1 , . . . , an such that
e
n n ui ai
i=1 ai ui = 1. Hence, for all y ∈ G, y = i=1 xi with xi = y ∈ Gpi .
n
pβi where pi,i=1...n are prime
Lemma 3. Let G be a group with |G| = i
i=1
numbers. Then, |Gpi | = pβi .
i
Proof. Necessarily, |Gpi | is a power of pi , say pγi . Indeed, from Cauchy™s Lemma,
i
if |Gpi | were divisible by some prime number p = pi , it would contain an element
of order p, which is contradictory with the de¬nition of Gpi . Then, since G ∼ =
βi γi
p | |G| Gp , we have i pi = i pi , so γi = βi for all i.

We have WG = G2 and, from lemma 3, |G2 | = 2β . Finally,
|WG | 1
Pr {r ∈ WG } = =.
|G| ±
r←G



References
1. Kocher, P.C.: Timing Attacks on Implementations of Di¬e-Hellman, RSA, DSS,
and Other Systems. In: CRYPTO. Volume 1109 of Lecture Notes in Computer
Science. (1996) 104“113
2. Boneh, D., DeMillo, R.A., Lipton, R.J.: On the Importance of Checking Cryp-
tographic Protocols for Faults. Lecture Notes in Computer Science 1233 (1997)
37“51
3. Kocher, P., Ja¬e, J., Jun, B.: Di¬erential Power Analysis. Lecture Notes in Com-
puter Science 1666 (1999) 388“397
4. Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization.
Mathematics of Computation 48(177) (January 1987) 243264
5. Coron, J.S.: Resistance Against Di¬erential Power Analysis for Elliptic Curve
Cryptosystems. In C.K. Ko¸, Paar, C., eds.: Cryptographic Hardware and Embed-
¸ c
ded Systems ” CHES 2002. Volume 1717 of Lecture Notes in Computer Science.
(1999) 292“302
6. Goubin, L.: A re¬ned power analysis attack on elliptic curve cryptosystems. In
Springer-Verlag, ed.: Public Key Cryptography PKC 2003. Volume 2567 of Lecture
Notes in Computer Science. (2003) 199211
7. Dupuy, W., Kunz-Jacques, S.: Resistance of Randomized Projective Coordinates
Against Power Analysis. In B.S. Kaliski Jr., c.K., Paar, C., eds.: Cryptographic
Hardware and Embedded Systems ” CHES 2005. Volume 3659 of Lecture Notes
in Computer Science. (2005) 1“12
8. Joye, M., Yen, S.M.: The Montgomery Powering Ladder. In B.S. Kaliski Jr., c.K.,
Paar, C., eds.: Cryptographic Hardware and Embedded Systems ” CHES 2002.
Volume 2523 of Lecture Notes in Computer Science. (2002) 291“302
9. Trichina, E., Bellezza, A.: Implementation of elliptic curve cryptography with
built-in counter measures against side channel attacks. In B.S. Kaliski Jr., c.K.,
Paar, C., eds.: Cryptographic Hardware and Embedded Systems ” CHES 2002.
Volume 2523 of Lecture Notes in Computer Science. (2002) 98“113
10. Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms
over GF(p) and its cryptographic signi¬cance. IEEE Transactions on Information
Theory 24 (1978) 106“110
11. Giraud, C.: Fault Resistant RSA Implementation. In Breveglieri, L., Koren, I.,
eds.: 2nd Workshop on Fault Diagnosis and Tolerance in Cryptography ” FDTC
2005. (2005) 142“151
12. Ciet, M., Joye, M.: Practical Fault Countermeasures for Chinese Remaindering
Based RSA. In Breveglieri, L., Koren, I., eds.: 2nd Workshop on Fault Diagnosis
and Tolerance in Cryptography ” FDTC 2005. (2005) 124“131

<<

. 2
( 2 .)