Cryptography Reference
In-Depth Information
Provided that we have that many faulty signatures, if we can find the closest vector
to
v
in the lattice
L
, it is heuristically likely to be the hidden vector
c
, which makes
it possible to recover the private key
α
.
For
N
=
160 and
=
8 (one byte zeroed out), we get
d
23. Practical experi-
ments in [300] indicate that, in this setting,
α
is retrieved with probability about 10 %
for
d
27. In all those cases, the lattice
dimension is small enough that solving the closest vector problem is easy in practice.
The above estimate is heuristic, but it is possible to give parameters for which
attacks of this kind can be proved rigorously [304]. Such attacks apply to DSA but
also to any El Gamal-type signature scheme (see, for instance, [305] for the case of
ECDSA).
=
23, 63 % for
d
=
25 and 100 % for
d
=
12.3.4 Proposed Countermeasures
Contrary to what happens in many other fault attacks, these faulty DSA signatures
are actually valid signatures. In particular, checking their validity after signature
generation will not help thwart the attack.
Several countermeasures are proposed in [300] to prevent the attacker from suc-
cessfully generating signatures with partially zeroed nonces, including execution
randomization (e.g. randomize the order in which the buffer containing the nonce is
filled, using a linear congruential generator) and repeated refreshment (e.g. generate
several random numbers with random delay in between, and use the XOR of these
values as the nonce).
12.4 Fault Attacks on Randomized RSA Signatures
One of the best-known examples of a fault attack is the so-called Bellcore attack [56,
199] on RSA-CRT signatures. Let us first recall it succinctly.
To sign a message
m
with RSA, a signer computes
d
σ
=
μ(
m
)
mod
N
, where
N
is the public modulus,
d
is the private exponent and
is a certain encoding function.
Since this computation is time-consuming, it is very common to use the Chinese
Remainder Theorem (CRT) to obtain a four fold speedup by first evaluating
μ
d
mod
p
−
1
d
mod
q
−
1
σ
p
=
μ(
m
)
(
mod
p
)
and
σ
q
=
μ(
m
)
(
mod
q
)
σ
q
with the CRT.
This method is vulnerable to fault attacks: if an attacker can inject a fault during
the computation of
σ
σ
p
and
and then deducing
from
σ
σ
q
, the whole computation will produce a faulty signature
satisfying
σ
≡
μ(
d
σ
≡
μ(
d
m
)
(
mod
p
)
and
m
)
(
mod
q
),
