TY - JOUR

T1 - The insecurity of the digital signature algorithm with partially known nonces

AU - Nguyen, Phong Q.

AU - Shparlinski, Igor E.

PY - 2003/6

Y1 - 2003/6

N2 - We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log1/2 q, but can be decreased to log log q with a running time g0(1/log log q) subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie-Hellman key exchange. The HNP consists, given a prime number q, of recovering a number α ε Fq such that for many known random t ε Fq a certain approximation of tα is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.

AB - We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant or least significant bits, the number of required bits is about log1/2 q, but can be decreased to log log q with a running time g0(1/log log q) subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie-Hellman key exchange. The HNP consists, given a prime number q, of recovering a number α ε Fq such that for many known random t ε Fq a certain approximation of tα is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one should be very cautious with the pseudo-random generation of the nonce within DSA.

UR - http://www.scopus.com/inward/record.url?scp=33746391879&partnerID=8YFLogxK

U2 - 10.1007/s00145-002-0021-3

DO - 10.1007/s00145-002-0021-3

M3 - Article

AN - SCOPUS:33746391879

VL - 15

SP - 151

EP - 176

JO - Journal of Cryptology

JF - Journal of Cryptology

SN - 0933-2790

IS - 3

ER -