The Carry Leakage on the Randomized Exponent

Carry Leakage

Description

Niveau: Supérieures
The Carry Leakage on the Randomized Exponent Countermeasure Pierre-Alain Fouque 1 , Denis Real 2;3 , Frederi Valette 2 , and Mhamed Drissi 3 1 E ole normale superieure/CNRS/INRIA, 75 Paris, Fran e Pierre-Alain.Fouqueens.fr 2 CELAR, 35 Bruz, Fran e fDenis.Real;Frederi .Valettegdga.defense.gouv.fr 3 INSA-IETR, 20 avenue des oesmes, 35043 Rennes, Fran e fDenis.Real;Mhamed.Drissiginsa-rennes.fr Abstra t. In this paper, we des ribe a new atta k against a lassi al dierential power analysis resistant ountermeasure in publi key implementations. This ountermeasure has been suggested by Coron sin e 1999 and is known as the exponent randomization. Here, we show that even though the binary exponentiation, or the s alar produ t on ellip- ti urves implementation, does not leak information on the se ret key, the omputation of the randomized se ret exponent, or s alar, an leak useful information for an atta ker. Su h part of the algorithm an be not well-prote ted sin e its goal is to avoid atta k during the exponentiation. Consequently, our atta k an be mounted against any kind of exponentiation, even very resistant as soon as the exponent randomization ounter- measure is used.

• prote ted


• bit


• against spa


• has been


• against very


• ted sin


• exponent randomization


• dpa atta

Sujets

• Leakage
• Return
• Fouqué
• Addition
• Has Been

Informations

• Publié par: profil-fouv-2012
• Nombre de lectures: 32
• Langue: English

Extrait

The
Carry
Leak
age
y
er

on
the
the

Randomized
tro
Exp
double-and-add
onen
t
t
m
Coun
er
termeasure
k
Pierre-Alain
and
F

ouque
simple
1
implemen
,
implemen
Denis

R
of

Coron
eal
bit
2
in
;
of
3
v
,
applications
F
of
r
and

a
ed


so
eric
t.
V
use
alette
b
2
h
,
onen
and
ts
Mhamed
of
Drissi
termeasure
3
termeasure,
1


ted.
Ecole
ed
normale
Ho
sup
tire

based
erieure/CNRS/INRIA,
hannel
75
w
P
most
aris,
lev
F
against
rance
o
[e-mail]
the
2
Elliptic
CELAR,
wide
35
to
Bruz,
er
F
a
rance
the
f
op

k
g
is

that
.def
ev
ense.
e
gouv
tial
.fr
[13])
3
and
INSA-IETR,
randomizing
20
scalar
a
order
v
)
en
or
ue
oin
des
e.

prop
esmes,
1999.
35043
onen
Rennes,
same
F
v
rance

f
This
Denis.Real;Mhamed.Drissi
een
g
ouque

Doubling
sa-r
in
ennes
is
.fr
k

or
In
1
this
Side
pap
ks
er,
p
w

e
da
describ
b
e
require
a
of
new


h
k
ks.
against
the
a
algorithms

ultiply
dieren
analog
tial
e,
p
since
o
There
w

er
v
analysis
o
resistan
(SP
t
that

p
termeasure
ultiply
in
op
public
all
k
of
ey
are
implemen
dep
tations.

This
ery


termeasure
implemen
has
Ho
b

een

suggested
k
b
using
y
o
Coron
(DP
since
hniques
1999
in
and
p
is

kno

wn
or
as
y
the
of
exp
the
onent
(
r
the
andomization
mo
.
the
Here,
base
w
in
e
Elliptic
sho
h
w
b
that
b
ev
℄
en
this
though

the
will
binary
e
exp
DP
onen
that
tiation,
the
or
y
the
e
scalar
W
pro
ell-kno

has
on

ellip-
y

V

using
es
ttac
implemen
ev
tation,
h
do
adv
es
en
not

leak
ey
information
RSA
on
ECC
the


In
k

ey

,

the
are

ery
of
o
the
erful
randomized
ks

to
exp
y
onen
em
t,
edded
or
that
scalar,
high

el
leak

useful
use
information
termeasures
for

an
kind


k
Tw
er.
of

most
h
studied
part
are
of
square-and-m
the
algorithm
algorithm
its

on
b
Curv
e
the
not
algorithm,
w
its
ell-protected
usage.
since
exists
its

goal
termeasure
is
a
to
oid
a
p
v
w
oid
analysis

A)
k
k,
during
alw
the
ys
exp
erforms
onen
m
tiation.
or
Consequen
add
tly
eration
,
that
our
the

erations
k
the

tation
b
not
e
ey
moun
enden
ted
This
against
termeasure
an
v
y

kind
in
of
so
exp
most
onen
tations
tiation,
it.
ev
w
en
er,
v
h
ery
tations
resistan
b
t

as
ed
so
y
on
dieren
as
p
the
w
exp
analysis
onen
A
t

randomization


as
ter-
[14]
measure
a
is
opular
used.
termeasure
W
in
e
the
target
exp
an
t
`

-bit
b
adder
a
whic
ultiple
h
the
adds
of
`
elemen
-bit
'
w
N
ords
in
of

the
RSA

dulus
exp
of
onen
order
t
the
and
p
of
t
a
the
random
of
v
Curv
alue.

W

e
has
sho
een
w
osed
that
y
if
in
the
since

With
leaks

during
the
the
exp
addition,
t
then
nev
w
b
e
the

and
almost
A
learn
ks
the

high
er
order

bits
b
of
bit

b
h
moun
w
Related
ord
ork.
of
w
the
wn

termeasure
exp
b
onen
rst
t.
k
Finally
b
,
F

and
h
alette
information
[11]

the
b
A
e
k.
then
w
used
er,
to



v
the
er
ersary
the
assumedto
b
e
side
and
a
able
other
to
v
send
for
man
of
y
for
times
w
the
)
same
base
message
k
and
the
that
er
no
of
randomization
to
of
ot
the
k
message

is
x
p
with
erformed
v
b
not
efore
en
the
tiation
exp

onen
Then
tiation.
step
Here,

our
onen

the
k
is
a
in
v
missing
oids
t
these
whole
t
of
w
d
o
and
dra
the
wbac
eration
ks
random
since
[17]
the
part

in
k

do
w
es
uses
not

need
the
the
w
kno
e
wledge
the
of
k
the
that
message.
other
In
eys
[10],
alue
F
are
ouque
et
et
Ho
al.
ust
sho
since
w
birthda
that
requiremen
if
ot
Coron's
um

In
termeasure
that
is

used

with

some
no
windo
is
wing
itself
exp

onen
an
tiation
onen
algorithms
d
and
random
a
one,
small
of
public
um
k
the
ey
P
e
al.
,

then
on
a

simple
since
SP
and
A
Finally
follo

w
ery
ed
exp
b
t
y
age
a
from
v
sho
ery
t,

in
er


h
k
the

-bit

go
v
er
er
the
the
is

y
k
b
ey
required
d

and
k
'
ering
(
the
N
the
)
addition
in
y
the
in
same
mo
time.
ev
In
bits
[10],
b
the
n
implemen
metho
tation
on
is
parado
not
and
protected
are
against
square
SP
fourth
A
the

er
ks
Our
since
pap
the
sho

exp
SP

A
e

v
k
and
do
k
es
e
not
The
w
elt
ork

on
target
the
the
windo
j
wing

algorithms.
(
In

this
mo
w
the
ork,
x
the
j
authors
.
ha
of
v
alue
e
and
to
targeted
solv
the
e

a
random
problem
er,
similar
ultiple
of
of
that
oin
whic
Seifert
h
Brier
w
℄
e
also
try
on
to
the
solv
public
e
Here,
here,
is
namely
asiv
,
e

hange
v
e
ering

the
this

v
d
since
in
against
RSA,
or
kno
v
wing
tiation
some
exp

since
onse
hannel

from
bits
and
of
exp
d
W
.
that
Indeed,
exp
side
scalar,

are
hannel
`

then
hnique
the
allo
and
ws

F
to
ouque
order
et
h
al.
ord
to
with
learn
d
some

k
whole
ey
,
bits
um