Guillaume Fumaroli and David Vigilant

Axalto

6 rue de la Verrerie, F-92190 Meudon, France.

{gfumaroli,dvigilant}@axalto.com

Abstract. As the core operation of many public key cryptosystems,

group exponentiation is central to cryptography. Attacks on its imple-

mentation in embedded device setting is hence of great concern. Re-

cently, implementations resisting both simple side-channel analysis and

fault attacks were proposed. In this paper, we go further and present an

algorithm that also inherently thwarts di¬erential side-channel attacks

in ¬nite abelian groups with only limited time and storage overhead.

1 Introduction

In traditional cryptanalysis, only inputs and outputs of cryptographic algorithms

are available to the attacker. Unfortunately, this assumption is inaccurate when

the hardware implementation is in the hands of the attacker. A new range of

attacks known as implementation attacks is then applicable. Embedded devices

such as smartcards are especially targeted by these implementation attacks, that

may be either passive or active.

Passive attacks are based on side-channel analysis introduced in [1], whose

principle consists in monitoring the device to ¬nd correlations between some

physical information leakage and the secret key manipulated by the device. While

simple side-channel analysis refers to a correlation involving a single acquisition,

di¬erential side-channel analysis recovers the secret in several attempts by using

the correlation between di¬erent acquisitions and a part of the secret.

Active attacks or fault attacks consist in carefully forcing the cryptographic

device to perform erroneous operations such that the result leaks information

about the secret data involved in the computation.

Group exponentiation is at the basis of many public key cryptosystems such

as RSA, ECC or the Di¬e-Hellman key exchange in some group. Cryptosystems

based on exponentiation are particularly sensitive to implementation attacks

both active [2] and passive [3].

In this paper, we present an exponentiation algorithm that resists all fore-

mentionned implementation attacks in ¬nite abelian groups.

Our countermeasure features a novel base point blinding technique, based

on the so-called Montgomery ladder introduced in [4], that requires fewer group

operations than other techniques achieving the same level of protection.

In any ¬nite abelian group whose order is unknown, our technique becomes

the most e¬cient one requiring no pre-computations. In particular, this is the

case for RSA as the factorization of the modulus and the public exponent are

rarely available to the device. Note that our countermeasure also fully applies to

the ECC setting since the randomization of projective coordinates, introduced

by Coron in [5], was later proven insu¬ciant by Goubin in [6]. As pointed out

recently by Dupuy and Kuntz-Jacques [7], when the attacker can tamper with

the base element, scalar point multiplications also require randomization of the

computation ¬‚ow to provide DPA resistance.

In section 2, the history of exponentiation algorithms targetting constrained

embedded devices is reviewed. Section 3 presents our algorithm and analyses its

security and e¬ciency. Section 4 concludes.

2 A review of previous work

In the sequel, G denotes a multiplicatively-written ¬nite abelian group.

Though more re¬ned algorithms for computing group exponentiations exist

in the litterature, only those based on binary ladders are relevant in constrained

environments such as smartcards.

Square-and-multiply algorithms (Fig. 1) have ¬rst been considered for im-

plementation, but they are easily broken by simple side-channel attacks.

Input: x ∈ G, k = t’1 ki 2i ∈ N

i=0

k∈G

Output: x

R0 ← 1; R1 ← x

for j = t ’ 1 down to 0 do

R0 ← R 0 2

if kj = 1 then R0 ← R0 R1

end for

return R0

Fig. 1. Square-and-multiply

Further, square-and-multiply-always algorithms (Fig. 2) introduced by Coron [5]

were designed to prevent simple side-channel attacks by performing dummy op-

erations. However, such algorithms bring speci¬c weaknesses with respect to

so-called safe-error attacks [8].

Montgomery ladder [4] was initially developped for elliptic curve scalar mul-

tiplication. Later, Joye et al. [8] extended it to exponentiation in any abelian

group and pointed out its intrinsic resistance to simple side-channel attacks and

t’1

safe-error attacks leveraging a slight modi¬cation. Let Lj = i=j ki 2i’j and

Hj = Lj + 1. As pointed out in [8], the principle of Montgomery ladder is based

Input: x ∈ G, k = t’1 ki 2i ∈ N

i=0

Output: xk ∈ G

R0 ← 1; R2 ← x

for j = t ’ 1 down to 0 do

R0 ← R 0 2

Rk j ← R k j R2

¯ ¯

end for

return R0

Fig. 2. Square-and-multiply-always

on the following observation:

±

xLj+1 2 , xLj+1 xHj+1 if kj = 0

(xLj , xHj ) =

xLj+1 xHj+1 , xHj+1 2 if kj = 1 .

This formula leads to Fig. 3 algorithm. The registers R0 and R1 contain the

values of xLj and xHj respectively. (R0 , R1 ) is initialized with (xLt , xHt ) = (1, x).

After t iterations, (R0 , R1 ) contains (xL0 , xH0 ) = (xk , xk+1 ).

Input: x ∈ G, k = t’1 ki 2i ∈ N

i=0

k∈G

Output: x

R0 ← 1; R1 ← x

for j = t ’ 1 down to 0 do

Rk j ← R k j Rk j

¯ ¯

2

Rk j ← R k j

end for

return R0

Fig. 3. Joye et al. Montgomery ladder

However, Montgomery ladder remains sensitive to di¬erential side-channel

analysis. As for group exponentiations, di¬erential side-channel analysis may be

prevented by randomizing either the group, the exponent or the base element.

Randomization of the group structure was not explored in this paper. Known

techniques targetting the exponent and the base element are presented in more

details in [5, 9]. Blinding the exponent is not well suited for exponentiations in

¬nite abelian groups. Indeed, the group order is generally unknown and its com-

putation may be di¬cult. So blinding the base seems to be the most appropriate

countermeasure. Usually, blinding the base element consists in multiplying the

input x ∈ G with a random element r picked at random from G; the value

of xd ∈ G is then obtained as (xr)d — (r’1 )d . This countermeasure introduced

in [5] requires two balanced group exponentiations, or a subtle but unpractical

pre-computation trick that may be di¬cult to handle by the personalization

process.

3 Our algorithm

t’1

As in the previous section, Lj = i=j ki 2i’j and Hj = Lj + 1. Let us consider

Fig. 3 algorithm and suppose (R0 , R1 ) contains ρ(xLj+1 , xHj+1 ) at the beginning

of some iteration for some ρ ∈ G. Then, (R0 , R1 ) will contain ρ2 (xLj , xHj ) at

the beginning of the next iteration. This remark leads to Fig. 4 algorithm.

Input: x ∈ G, k = t’1 ki 2i ∈ N

i=0

Output: xk ∈ G

Pick a random r ∈ G

R0 ← r; R1 ← rx; R2 ← r ’1

for j = t ’ 1 down to 0 do

Rk j ← R k j Rk j

¯ ¯

2

Rk j ← R k j

2

R2 ← R 2

end for

return R2 R0

Fig. 4. Side-channel analysis resistant Montgomery ladder

As will be shown in the sequel, the more re¬ned Fig. 5 algorithm will have

to be considered as Fig. 4 algorithm fails to detect some fault attacks.

At initialization, the couple of registers (R0 , R1 ) is multiplicatively blinded by

a secret random element r ∈ G. Throughout the computation, (R0 , R1 ) is then

t’j

instrinsically multiplicatively masked by the element r2 ∈ G. The register R2

t’j

is initialized with r ∈ G and holds the compensative factor r’2

’1

∈ G such

Lj Hj 2

that R2 (R0 , R1 ) equals (x , x ) ∈ G . At the end of the computation, the

actual multiplication R2 R0 hence evaluates to xk ∈ G.

3.1 Security Analysis

j

Some masking elements r ∈ G exhibit the undesirable property that r2 = 1

for some j ∈ N. For such elements, (R0 , R1 ) is permanently unmasked after j

iterations.

Input: x ∈ G, k = t’1 ki 2i ∈ N,

i=0

CKSref the checksum of k.

Output: xk ∈ G

Pick a random r ∈ G

R0 ← r; R1 ← rx; R2 ← r ’1

init(CKS)

for j = t ’ 1 down to 0 do

Rk j ← R k j Rk j

¯ ¯

2

Rk j ← R k j

2

R2 ← R 2

update(CKS, kj )

end for

R2 ← R2 • CKS • CKSref

return R2 R0

Fig. 5. Side-channel analysis and fault attacks resistant Montgomery ladder

i

x ∈ G x2 = 1 . Any element

De¬nition 1 (Weak mask). Let WG = i∈N

x ∈ WG is called a weak mask.

Theorem 1 (Weak mask probability in ¬nite abelian groups). Let G

be a ¬nite abelian group with |G| = ±2β for some odd ±. Let Prr←G {r ∈ WG }

denote the probability that r be a weak mask when r is picked randomly uniformly

from G. We have

1

Pr {r ∈ WG } = .

±

r←G

Proof. See Appendix A.

In our context, the fraction 1/± where ± denotes the greatest odd factor of

|G| is necessarily negligible. Otherwise, |G| would be smooth and the discrete

logarithm in G would be e¬ciently solved by the Pohlig“Hellman algorithm [10].

Suppose β = 100 and |G| 21024 . Then, the probability of picking a weak

mask is about 1/2924 < 10’278 . This shows that weak masks never happen in

practice.

Simple side-channel analysis and safe-error attacks The square-and-

multiply algorithm (Fig. 1) is sensitive to simple side-channel analysis. Indeed,

it contains a conditional branching on the multiplication that directly depends

on the secret exponent. Then, since the physical leakage of a square can be dis-

tinguished from that of a multiplication, the secret data can be easily retrieved

from just one acquisition.

The square-and-multiply-always algorithm (Fig. 2) perfectly balances the

former conditional branching by adding dummy multiplications. However, it in-

troduces a speci¬c weakness toward safe-error attacks that consist in carefully

injecting a fault during the execution and checking whether it impacts on the

result. In particular, the so-called M-safe-error attack consist in disturbing the

multiplication. The value of the secret exponent can then be retrieved by dis-

tinguishing between required and dummy multiplications, corresponding to an

exponent bit equal to 1 and 0, respectively.

Because of its high regularity, the Montgomery ladder algorithm (Fig. 3) is

intrinsically resistant to simple side-channel attacks. It is also insensitive to safe-

error attacks [8]. If a fault is injected at any time during the computation, the

result is necessarily faulty. As it keeps the same structure, our algorithm (Fig. 4)

clearly remains equivalent to Montgomery ladder in terms of simple side-channel

analysis and fault attack resistance.

Di¬erential side-channel analysis The intermediate variables are masked by

i

r2 at each step i of the computation, and are hence statistically independant

from the input and the output throughout the computation, so they cannot be