Cryptography Reference
In-Depth Information
Algorithm 8.5:
BOS algorithm
Input
:
M
=
0
,
p
,
q
,
d
,
i
q
Output
:
M
d
mod
N
or a random value in
Z
/
N
Z
1
begin
2
Choose two
k
-bit random integers
r
1
and
r
2
;
Store in memory
r
1
,
r
2
,
pr
1
,
qr
2
,
N
,
r
1
r
2
N
,
d
1
,
e
1
,
d
2
,
e
2
;
3
Compute
S
p
=
M
d
1
mod
(
pr
1
)
;
4
S
q
M
d
2
=
mod
(
pr
2
)
;
5
Compute
S
∗
=
CRT
(
S
p
,
S
q
)
mod
(
r
1
r
2
N
)
;
6
S
∗
)
e
1
Compute
c
1
=
(
M
−
(
+
1
)
mod
r
1
;
7
S
∗
)
e
2
c
2
=
(
M
−
(
+
1
)
mod
r
2
;
8
S
∗
)
c
1
c
2
Return
S
=
(
mod
N
9
10
end
=
(
S
∗
c
1
S
)
mod
N
,
S
∗
=
S
∗
=
S
∗
mod
p
. Then the attacker tries to guess the injected
fault on
M
and compute the corresponding value for
S
∗
and
mod
q
but
c
1
until she factorizes
N
by
˜
(
S
e
M
c
1
computing gcd
. Wagner claimed that the success probability
of this attack depends on the byte location of the fault. For a 1,024-bit RSA and
k
−
mod
N
,
N
)
80 bits, the success probability is around 4 %.
Blömer et al. proposed a variant that overcame the weakness by randomizing the
computation of both
c
1
and
c
2
[52].
=
8.4.3 Ciet and Joye's Algorithm and Attack
Another countermeasure based on the infective computation and Shamir's method
was proposed by Ciet and Joye [91].
This method, depicted in Algorithm 8.6, was designed to defeat all previously
published attacks, even Wagner's attack [410]. However, its security has not been
formally proved. The CRT parameters
p
and
i
q
and the values computed
during the first step are assumed to be error-free. This means that these values are
implicitly protected against fault injection. As for Algorithm 8.5, the length of random
values (
l
and
k
) can be tuned according to the application.
Berzati et al. exploited a flaw in the computation of the check values (i.e.,
c
1
or
c
2
)
at FDTC 2008 [38]. Their attack was inspired by Wagner's attack against the BOS
algorithm. They first assumed that an attacker was able to modify transiently one byte
of the result of one of the exponentiations:
,
q
,
d
p
,
d
q
,
S
p
∗
=
stands for a byte
value. They also assumed that no modular reduction occurred in the computation
of the checks. Then
S
p
∗
+
ε
, where
ε
c
1
directly depends on the fault:
˜
c
1
˜
=
1
+
ε
. Because of this
particular form, the value of
will be easily found for 5.4 % of the cases (if the
attacker limits the exhaustive search of
γ
γ
to 40 bits). As a result, the attacker will be
