Cryptography Reference
In-Depth Information
Algorithm 8.4:
Basic concept of infective computation
Input
:
M
=
0
,
d
,
N
Output
:
M
d
mod
N
or a random value in
Z
/
N
Z
1
begin
2
Choose a (small) random integer
r
;
Compute
S
∗
=
M
d
M
d
mod
rN
and
Z
=
mod
r
;
3
Choose a random integer
ρ>
r
;
4
S
∗
−
Compute
c
=[
ρ(
Z
)
+
1
]
mod
r
;
5
S
∗
)
c
Return
S
=
(
mod
N
6
7
end
al. noted that error detection based on decisional tests should be avoided. From the
viewpoint of low-level implementation of this decision procedure, it often totally
relies on the status of the zero flag of a processor. The zero flag is a bit of the
status register in a processor. So, if an attack can induce a random fault into the
status register, a conditional jump instruction may perform incorrectly. As shown in
Algorithm 8.4, the conditional check can be replaced with infective computation.
Unfortunately, the first two protocols using infective computation [429] were
rapidly broken by Yen and Kim [428]. In spite of this, the concept of infective
computation was later used in other protocols such as [53, 91].
8.4.2 BOS Algorithm and Attack
Blömer, Otto and Seifert suggested a countermeasure based on Shamir's method and
infective computation [53]. The principle of the algorithm is recalled in Algorithm
8.5. At the beginning of the algorithm, two
k
-bit random integers,
r
1
and
r
2
,have
to be carefully chosen. From this the algorithm precomputes and stores in memory
random public/private exponents:
d
1
−
1
d
1
=
d
mod
ϕ(
pr
1
),
e
1
=
mod
ϕ(
pr
1
),
d
2
−
1
and
d
2
=
d
mod
ϕ(
pr
2
),
e
2
=
mod
ϕ(
pr
2
).
S
∗
mod
N
. The length
of the random value
k
is a trade-off between security and device capabilities.
However, this algorithm has two main drawbacks. First the knowledge of the
private exponent
d
is required to compute
d
1
and
d
2
, which is not a CRT secret key.
The second one deals with the efficiency, because two modular inverses need to be
performed in the precomputation phase (i.e., computation of
e
1
and
e
2
).
Wagner found a way to exploit a vulnerability in Algorithm 8.5 [410]. The attack
consists in injecting a random transient byte fault in
M
, just before computing
S
p
,in
a way that subsequent accesses to
M
will be error-free. The returned signature will
be faulty, since
In the case of a correct execution,
c
1
=
c
2
=
1, and so
S
=
