Cryptography Reference
In-Depth Information
where
B
and
C
are public constants (in the ISO/IEC 9797-2 case, suitable powers
of 2),
A
is a number representing the known part of the encoding, and
x
0
and
y
0
are the unknown parts (equal to
r
and
H
(
m
)
respectively). The signature is then
d
computed as
σ
=
μ(
m
)
mod
N
as usual, using the CRT.
12.4.2 Attack Model
A fault is injected into the exponentiation modulo
q
part of the RSA-CRT signature
generation, resulting in a faulty signature
σ
satisfying
e
e
σ
≡
A
+
B
·
x
0
+
C
·
y
0
(
mod
p
)
and
σ
≡
A
+
B
·
x
0
+
C
·
y
0
(
mod
q
).
Dividing by
B
and subtracting the left-hand side, the faulty signature yields a relation
of the form
+
x
0
+
·
y
0
≡
(
)
+
x
0
+
·
y
0
≡
(
)
a
c
0
mod
p
and
a
c
0
mod
q
B
−
1
e
B
−
1
where
a
=
(
A
−
σ
)
mod
N
is a value known to the attacker, and
c
=
·
C
mod
N
is a public constant.
In other words, the fault attack provides the attacker with an integer
a
such that
for a certain unknown pair
(
x
0
,
y
0
)
of bounded size, the following holds:
a
+
x
0
+
c
·
y
0
≡
0
(
mod
p
)
and
a
+
x
0
+
c
·
y
0
≡
0
(
mod
q
).
N
γ
N
δ
. The total
We will write the bounds on
x
0
and
y
0
as 0
≤
x
0
<
and 0
≤
y
0
<
fraction of unknown bits in the encoded message is thus
.
Intuitively, in both of the attacks described below, the attacker takes advantage
of the affine relation in
x
0
and
y
0
mod
p
to recover the unknown part with lattice
techniques, and use it to factor
N
.
In practice, the fault can be injected using, for example, voltage spikes during the
computation modulo
q
(see [104, Sect. 4]).
The resulting value modulo
q
(of the faulty signature, or equivalently of
a
γ
+
δ
+
x
+
cy
)
is usually modeled as a random element in
Z
q
; this is the random fault model.
12.4.3 Single-Fault Attack
(
,
)
=
After a single fault, the attacker obtains a bivariate linear polynomial
f
x
y
a
+
x
+
c
·
y
such that
f
(
x
0
,
y
0
)
≡
0
(
mod
p
)
and
f
(
x
0
,
y
0
)
≡
0
(
mod
q
)
for some
unknown pair
satisfying known bounds. They can then apply the following
Coppersmith-like result by Herrmann and May.
(
x
0
,
y
0
)
