. 1
( 2 .)



>>

Blinded Fault Resistant Exponentiation

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

. 1
( 2 .)



>>