Cryptography Reference
In-Depth Information
⎛
⎛
⎞
2
b
⎞
t
−
1
n
−
1
m
2
j
d
j
i
m
2
j
d
j
i
S
i
⎝
⎝
⎠
±
⎠
·
=
(7.2)
j
=
0
j
=
t
n
−
1
m
2
j
d
j
i
2
b
=
S
i
±
·
mod
N
(7.3)
j
=
t
m
d
[
t
]
i
=
S
i
±
2
b
or
S
i
·
mod
N
(7.4)
with
d
[
t
]
=
n
−
1
2
j
d
j
. If we use the signature's verification operations, the previous
j
=
t
equation becomes
m
d
[
t
]
i
=
(
S
i
±
2
b
e
mod
N
.
)
.
m
i
(7.5)
One can notice that this equation is interesting because it only depends on the mes-
sage
m
i
and the corresponding faulty signature
S
i
(i.e. the knowledge of the correct
signature is no longer required). Moreover, the fault injection has isolated a part
d
]
of the private exponent
d
. This is precisely this part of the exponent the attacker has
to determine with a guess and determine approach.
The whole exponent is gradually recovered, from the most to the least significant
bits, by repeating the previous analysis on different faulty signatures. In each analysis,
w
[
t
bits of exponent are retrieved. In more detail, for each analysis, the attacker has
to simultaneously guess the values of the part of the exponent isolated
d
and the
[
t
]
2
b
such that (
7.5
) is satisfied. According to [56], the whole private
exponent
d
can be determined in this way, with probability greater than
fault induced
±
1
2
,from
(
n
/w)
log
(
2
n
)
message-signature pairs. In this case, the attack complexity is about
2
w
n
3
log
2
3
exponentiations. We can additionally remark that this fault
attack was later generalized to “left-to-right"-based exponentiations by Blömer and
Otto [315].
O
((
(
n
))/w
)
7.3.1.2 Faults on the Private Exponent
This attack was published by Bao et al. in [20] and then Bar et al. in [21]. The
principle is to induce a transient error during the decryption that produces the same
effect as a bit modification of the private exponent. In practice, such an effect can
be obtained by flipping a bit of the private exponent, or by corrupting the evaluation
made just before the conditional branch in the classical implementations of modular
exponentiation (see Sect.
7.2.2
). The following paragraph only describes the attack
for a bit error on the exponent
d
.
General Methodology
Let
m
be a plaintext and
C
be the corresponding ciphertext obtained from an RSA
encryption (see Sect.
7.2
). In the case of a faulty computation, the deciphered text
ˆ
m
is
