LINEBURG

Generation Algorithm

Christophe Clavier and Jean-SĀ“bastien Coron

e

1

Gemalto, Security Labs,

La Vigie, Avenue du Jujubier, ZI AthĀ“lia IV,

e

F-13705 La Ciotat Cedex, France

christophe.clavier@gemalto.com

2

University of Luxembourg,

Faculty of Sciences, Technology and Communication,

6, rue Richard Coudenhove-Kalergi,

L-1359 Luxembourg

jean-sebastien.coron@uni.lu

Abstract. A side-channel analysis of a cryptographic algorithm gener-

ally concentrates on the encryption or decryption phases, rarely on the

key generation phase. In this paper, we show that, when not properly

implemented, the fast prime generation algorithm proposed by Joye and

Paillier at CHES 2006 is susceptible to side-channel analysis; its main

application is the generation of RSA key-pairs for embedded platforms

like smart-cards. Our attack assumes that some parity bit can be recov-

ered through SPA when it appears in a branch condition. Our attack can

be combined with Coppersmithā™s theorem to improve its eļ¬ciency; we

show that for 1024-bit RSA moduli, one can recover the factorization of

roughly 1/1000 of the RSA moduli.

Key-words : Simple Power Analysis, Prime generation algorithm, Copper-

smithā™s theorem.

1 Introduction

Side-channel analysis, such as Simple Power Analysis (SPA) and Diļ¬erential

Power Analysis (DPA) [7], generally concentrates on the encryption or decryp-

tion phases, rarely on the key generation phase. Namely encryption or decryption

oļ¬er more ļ¬‚exibility to the attacker who can provide various messages as input

and each time record a side channel leakage. In contrast, a key generation al-

gorithm doesnā™t take any input (beyond a security parameter) and in general

it doesnā™t help to execute it multiple times since a diļ¬erent key is obtained for

each new execution.

In this paper, we show that, when not properly implemented, one of the fast

prime generation algorithms proposed by Joye and Paillier at CHES 2006 [6] is

susceptible to side-channel analysis. The main application of the Joye-Paillier

algorithm is to generate RSA keys on embedded platforms like smart-cards,

where eļ¬ciency is of crucial importance. Prime generation usually works by

applying a primality test on randomly generated integers, until a prime is found.

The technique described in [6] consists in generating random integers that are not

divisible by the ļ¬rst primes pi ; then a prime appears with higher probability, and

on average fewer primality tests have to be applied, which improves eļ¬ciency.

A faster variant is described in [6] where a sequence of candidates is generated

from a random seed and the parity of each candidate is tested before applying

a primality test, until a prime is found. In this paper, we concentrate on an

implementation of this faster variant; we show that if n primality tests have been

applied and if the parity bits can be obtained through SPA, then we can recover

the n ā’ 1 least signiļ¬cant bits of the output prime. Coppersmithā™s theorem

[1] shows that an RSA modulus N = pq can be factored in polynomial time

given half of the least signiļ¬cant (or most signiļ¬cant) bits of p. Therefore, if the

number n of primality tests for p or q is more than half the bit-size of p, one can

recover the factorization of N eļ¬ciently. We provide an analysis which shows

that for certain parameters (bmin = bmax = 0) and for 1024-bit RSA moduli,

this happens for 10ā’3 of the generated RSA moduli.

2 The Joye-Paillier Prime Generation Algorithm

The Joye-Paillier algorithm [6] consists in generating a sequence of candidates

q that are co-prime with the ļ¬rst small primes pi ; a primality test T (q) is then

applied on each candidate until a prime is found. Here we concentrate on the

faster variant (from Fig. 3 in [6]). One deļ¬nes Ī as the product of the r ļ¬rst

primes, excluding p1 = 2, so that Ī is odd :

r

Ī = pi

i=2

Let [qmin , qmax ] be the interval in which the prime integers must be generated.

One deļ¬nes integers bmin , bmax and v such that :

qmin ā¤ (v + bmin )Ī , and (v + bmax + 1)Ī < qmax

The prime integers will actually be generated in the sub-interval :

[(v + bmin )Ī , (v + bmax + 1)Ī ]

See [6] for more details on the selection of parameters bmin , bmax and v. We

denote by T (q) a primality test (for example, Miller-Rabin [8]).

Fast Prime Generation Algorithm [6] :

Parameters : Ī odd, bmin , bmax , v

Output : a random prime q ā [qmin , qmax ]

1. Compute ā vĪ

2. Randomly choose k ā (Z/Ī Z)ā—

2

3. Randomly choose b ā {bmin , . . . , bmax } and set t ā bĪ

4. Set q ā k + t +

5. If (q even) then q ā Ī ā’ k + t +

6. If T (q) = false then

(a) Set k ā 2k mod Ī

(b) Go to step 4.

7. Output q

It is easy to see that the candidate q at step 6 is odd and co-prime with all

primes in Ī . Namely, we have that q = Ā±k mod Ī and k remains always in

(Z/Ī Z)ā— , because 2 ā (Z/Ī Z)ā— . This implies that q is co-prime with all primes

in Ī . Moreover, if q = k+t+ is even at step 4, then q = Ī ā’k+t+ = Ī ā’2k+q

must be odd since Ī is odd, and therefore q is odd at step 6. Since we ensure

that each candidate q is not divisible by the ļ¬rst small primes, each candidate

is prime with higher probability, so one gets a faster prime generation algorithm

(see [6] for a complete analysis).

3 Our Side-Channel Attack

Our attack is based on the assumption we can recover the parity of k at step

4 thanks to the parity test performed on q at step 5. Namely, on a practical

implementation, a branch condition usually produces a diļ¬erent physical leakage

depending on the result of the test. Indeed by measuring power consumption,

the attacker may be able to determine if the operation q ā Ī ā’k +t+ has been

performed or not, which gives him the parity bit of q. Our attack is therefore a

Simple Power Attack (SPA) on the parity bit of q. In practice, this assumption

may be realistic or not, depending on the micro-processor used, the presence of

hardware countermeasures, and the way the test is implemented. We note that

SPA attacks based on analogous assumptions have been described in [3, 4].

Here we show that this sequence of parity bits enables us to recover the least

signiļ¬cant bits of the prime q returned as output. Our attack is based on the

following simple lemma :

Lemma 1. Let Ī be an odd integer and let k0 ā Z Ī . Deļ¬ne Bi = 2i k0 /Ī

Z

i

and the sequence ki = 2 k0 mod Ī . Then, for i ā„ 1, Bi = j=1 (kj mod 2)2iā’j .

i

Proof. By deļ¬nition, we have 2iā’1 k0 = Biā’1 Ī + kiā’1 . Hence, we have 2i k0 =

2Biā’1 Ī + 2kiā’1 = (2Biā’1 + 2kiā’1 /Ī )Ī + ki , which gives Bi = 2Biā’1 +

i

2kiā’1 /Ī . It follows that Bi = j=1 2kjā’1 /Ī 2iā’j (note that B0 = 0).

Moreover, we have 2kjā’1 = 2kjā’1 /Ī Ī + kj . Taking the relation modulo

2, we get 2kjā’1 /Ī ā” kj (mod 2) as Ī is odd, and since 2kjā’1 < 2Ī , we have

2kjā’1 /Ī = kj mod 2. This concludes the proof.

Proposition 1. With the previous notation and letting bj = kj mod 2, we have

i

ki ā” ā’( j=1 bj 2iā’j ) Ī (mod 2i ).

3

Proof. This follows immediately from the previous lemma by observing that

Bi Ī = 2 i k0 ā’ k i .

We assume that the parameters Ī , bmin , bmax and v are public and known

to the attacker. Let ki = k0 Ā· 2i mod Ī for i ā„ 0 denote the sequence of integers

k which appear at step 4, where k0 is the integer initially generated at step 2.

Let qi = ki + t + denote the corresponding integer computed at step 4. From

the parity of qi tested at step 5, one can therefore obtain the parity of ki ; this

is done by making an assumption on the parity of t + , which is constant after

step 4. Then using the previous lemma, after n + 1 primality tests the value of

kn mod 2n is obtained 3 . Then we can write :

kn = 2 n Ā· x + x0

where 0 ā¤ x0 < 2n is known and x is unknown. Therefore the prime generated

q = kn + t + or q = Ī ā’ kn + t + can be written :

q = 2 n Ā· x + x0 + b Ā· Ī +

where x and b ā [bmin , bmax ] are integers unknown to the attacker, and the

integers n, k0 , Ī and are known.

We make the following assumption : we assume that bmin = bmax = 0, so

that b = 0. We note that taking bmin = bmax = 0 is a valid parameter choice in

the Joye-Paillier algorithm. In this case, the integer q can be written :

q = 2n Ā· x + C

where C is a known constant and x is an unknown integer.

Theorem 1 (Coppersmith [1]). Given N = pq and the high-order or low-

order 1/4 log2 N bits of p, one can recover the factorization of N in time poly-

nomial in log N .

Using Coppersmithā™s theorem, one can therefore recover the factorization of

N in polynomial-time if the number n of primality tests is at least half the

bit-size of p. Let Ī± denote the probability that a random n0 -bit odd integer

q co-prime with Ī is prime. We make the heuristic approximation that the

candidates qi behave as if they were uniformly and independently distributed.

From the analysis of [5], we obtain that a candidate qi is prime with probability :

1 Ī

Ī±= Ā·

n0 Ā· ln 2 Ļ(Ī )

where Ī = 2Ī and Ļ is Eulerā™s function. Therefore, letting X be the random

variable that gives the number of primality tests, we have :

Pr[X = i] = (1 ā’ Ī±)iā’1 Ā· Ī±

3

We need n + 1 parity bits because we donā™t use the ļ¬rst one.

4

which gives E[X] = 1/Ī± and :

Pr[X ā„ i] = (1 ā’ Ī±)iā’1

To summarize, if the attack is applied for both p and q, the factorization of a

2n0 -bit RSA modulus can be recovered in polynomial-time for a fraction :

n0 /2ā’1

1 Ī

Ī“ 2Ā· 1ā’ Ā·

n0 Ā· ln 2 Ļ(Ī )

of the generated moduli. We provide in Table 1 the corresponding fraction for

various moduli size. For a prime size of n0 bits, we take the largest r such that :

r

pi < 2n0 ā’1

Ī =

i=2

Then we take v = 2n0 /Ī and qmin = v Ā· Ī and qmax = (v + 1) Ā· Ī , with

bmin = bmax = 0; this is a valid parameter choice for the Joye-Paillier algorithm.

Table 1 shows that for a 1024-bit RSA modulus, our side channel attack enables

8.4 Ā· 10ā’4 of the RSA moduli. If the algorithm is run

to factor a fraction Ī“

only once inside a smart-card, this means that in practice a fraction 8.4 Ā· 10ā’4

of the smart-cards could be broken.

RSA n0 r E[X] Ī“

512 bits 256 43 18.7 1.8 Ā· 10ā’3

768 bits 384 60 26.1 1.1 Ā· 10ā’3

1024 bits 512 75 33.3 8.4 Ā· 10ā’4

2048 bits 1024 131 60.0 3.7 Ā· 10ā’4

Table 1. RSA modulus bit-size, bit-size n0 of primes p and q, number r of primes pi

in Ī , average number E[X] of primality tests, and fraction Ī“ of weak RSA moduli.

We note that the assumption bmin = bmax = 0 could be relaxed to small

(known) values for bmin and bmax ; in this case the value b ā [bmin , bmax ] would

be exhaustively searched 4 .

4 Countermeasures

In this section we discuss three possible countermeasures. Our ļ¬rst countermea-

sure is to periodically re-generate a fresh seed k so that the attacker doesnā™t

4

Alternatively, one could try to derive a variant of Coppersmithā™s theorem for primes

of the form q = 2n Ā· x + b Ā· Ī + C, with unknown x and b, and known constants Ī

and C.

5

obtain enough information about the prime q. Let s > 0 be the maximum num-

ber of primality tests performed for a given seed k. The integer s should be small

enough to prevent the previous attack, but not too small to keep the same level

of eļ¬ciency; we propose to take s = n0 /4 where n0 is the prime bit-size. One

gets the modiļ¬ed algorithm :

Modiļ¬ed Prime Generation Algorithm :

Parameters : s, Ī odd, bmin , bmax , v

Output : a random prime q ā [qmin , qmax ]

1. Compute ā vĪ

2. Let i ā 0.

ā—

3. Randomly choose k ā (Z/Ī Z)

4. Randomly choose b ā {bmin , . . . , bmax } and set t ā bĪ

5. Set q ā k + t +

6. If (q even) then q ā Ī ā’ k + t +

7. If T (q) = false then

(a) Set k ā 2k mod Ī

(b) Let i ā i + 1

(c) If i < s then go to step 5, otherwise go to step 2.

8. Output q

Our second countermeasure consists in replacing the instruction k ā 2 Ā· k

mod Ī by k ā 2t Ā· k mod Ī where t is a small random integer. If k ā 2t Ā· k

mod Ī is implemented in constant time, then the attacker doesnā™t know for

which integers ki = 2i Ā· a mod Ī he gets the parity bits, which prevents the

previous attack. This second countermeasure is eļ¬cient because the additional

running time is probably negligible compared to the primality test running time.

Our third countermeasure is to implement the test so that it doesnā™t leak.

The standard way is to compute both sides of the branch and select the correct

result. This countermeasure is analogous to the square & multiply always and

double & add always countermeasures in RSA exponentiation and ECC scalar

multiplication (see [2]). The instruction :

6. If (q even) then q ā Ī ā’ k + t +

is then replaced by :

6. (a) Let u ā q mod 2

(b) Set A[0] ā Ī ā’ k + t +

(c) Set A[1] ā q

(d) Let q ā A[u]

In this case the computation of Ī ā’ k + t + is always performed so it is likely

more diļ¬cult for the attacker to recover the parity of q.

6

5 Conclusion and Open Problem

We have demonstrated that an improper implementation of the Joye-Paillier

prime generation algorithm may succumb to side-channel analysis. Our attack is

based on the assumption that a Simple Power Analysis can give us the parity bits

which appear in a branch condition. We have shown that for certain parameters

(bmin = bmax = 0) and for 1024-bit RSA moduli, a fraction 10ā’3 of those moduli

can be factored eļ¬ciently. However in practice, some of the parity bits obtained

through SPA may be erroneous. Therefore an interesting open problem is to ļ¬nd

an attack that works with errors; formally :

Open Problem: let Ī² > 0, let Ī be an odd integer and let k0 ā Z Ī . Deļ¬ne

Z

i

the sequence ki = 2 k0 mod Ī and bi = ki mod 2 for i ā„ 1. Let bi = bi with

probability 1 ā’ Ī² and bi = 1 ā’ bi otherwise, independently for each i ā„ 1. Given

the sequence bi for i ā„ 1, ļ¬nd k0 in time polynomial in log Ī .

Acknowledgments : we wish to thank Marc Joye and the anonymous reviewers

for their valuable comments.

References

1. D. Coppersmith, Small solutions to polynomial equations, and low exponent vul-

nerabilities. J. of Cryptology, 10(4)233-260, 1997. Revised version of two articles

of Eurocrypt ā™96.

2. J.S. Coron, Resistance against Diļ¬erential Power Analysis for Elliptic Curve Cryp-

tosystems. Proceedings of CHES ā™99. LNCS, Springer-Verlag.

3. W. Dupuy and S. Kunz-Jacques, Resistance of Randomized Projective Coordinates

Against Power Analysis, Proceedings of CHES 2005, LNCS.

4. P.A. Fouque, S. Kunz-Jacques, G. Martinet, F. Muller, and F. Valette. Power At-

tack on Small RSA Public Exponent. Proceedings of the 8th International Work-

shop on Cryptographic Hardware and Embedded Systems (CHES ā™06), LNCS 4249,

Springer-Verlag, 2006.

5. M. Joye, P. Paillier and S. Vaudenay, Eļ¬cient Generation of Prime Numbers.

Proceedings of CHESā™00, Lecture Notes in Computer Science, Springer-Verlag No

1965, pp. 340-354.

6. M. Joye and P. Paillier, Fast Generation of Prime Numbers of Portable Devices:

An Update. Proceedings of CHES 2006, LNCS 4249, pp. 160-173, 2006.

7. P. Kocher, J. Jaļ¬e, and B. Jun, Diļ¬erential power analysis, Advances in Cryptol-

ogy - CRYPTO ā™99, Lecture Notes in Computer Science, vol. 1666, pp. 388ā“397,

Springer-Verlag, 1999.

8. G. Miller, Riemannā™s Hypothesis and Tests for Primality. J. Comp. Syst. Sci. 13,

300-317, 1976.

7

Copyright © Design by: Sunlight webdesign