Cryptography Reference
In-Depth Information
in high dimension, such exponential factors may not be enough for cryptanalytic
purposes, depending on the application. If better approximation factors are required,
one should perform experiments to see if existing algorithms are sufficient. If the
lattice and the input basis are not exceptional, there is no reason to believe that exact
SVP can be solved in very high dimension (say
400), although one can always give
it a try. Furthermore, if the target vector is not unusually close to the lattice, there
is also no reason to believe that exact CVP could be solved in very high dimension
(say
≥
≥
400).
12.3 Fault Attacks on DSA Signatures
At PKC 2005, Naccache et al. [300] presented a fault attack against smart card
implementations of the DSA signature standard. The attack combines a glitch attack
on signature generation that produces DSA signatures where a few bits of the nonce
are known, and a previously introduced lattice-based technique [304] that will recover
the DSA secret key from sufficiently many such signatures with partially known
nonces.
In practice, for DSA signatures using a 160-bit subgroup, it was found that 27
faulty signatures with one zeroed byte were sufficient to recover the secret key.
Moreover, the technique generalized to other El Gamal-type signature schemes, such
as ECDSA [305] and Schnorr signatures.
The attack is based on the well-known fact that the security of DSA signatures
crucially relies on the nonce used in signature generation being chosen uniformly at
random. Statistical biases can often be exploited for key recovery. This fact has been
illustrated by many attacks, the latest example being Sony's PlayStation 3 gaming
console: hackers have apparently been able to retrieve ECDSA secret keys [134]
because some nonces have allegedly been reused.
12.3.1 The DSA Signature Scheme
DSA is an El Gamal-like signature algorithm specified by NIST in their Digital
Signature Standard [141]. It can be described as follows.
Parameters and Keys
,
The system parameters are three integers
p
q
, and
g
where
p
and
q
are prime,
q
∈ Z
p
has order
q
, as well as a cryptographic hash function
H
of output length equal to the byte size of
q
. The private key is an element
divides
p
−
1, and
g
α
∈ Z
q
,
g
α
(
and the public key is
β
=
mod
p
)
.
