Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 11/2019

08-04-2019

A probabilistic analysis on a lattice attack against DSA

Authors: Ana I. Gomez, Domingo Gomez-Perez, Guénaël Renault

Published in: Designs, Codes and Cryptography | Issue 11/2019

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Analyzing the security of cryptosystems under attacks based on the malicious modification of memory registers is a research topic of high importance. This type of attack may affect the randomness of the secret parameters by forcing a limited number of bits to a certain value which can be unknown to the attacker. In this context, we revisit the attack on DSA presented by Faugère, Goyet and Renault during the conference SAC 2012: we modify their method and provide a probabilistic approach in opposition to the heuristic proposed therein to measure the limits of the attack. More precisely, the main problem is formulated as a closest vector problem in a lattice, then we study the distribution of vectors with bounded norm in the lattices involved and apply the result to predict the attack behavior. The benefits of this approach are several: The probability of success of this attack can be lower bounded under some conjecture, which is validated by computational experiments. Also, it finds applications to the FLUSH+RELOAD side-channel attack, studied by van de Pol et al. At the end of the article, there is a summary of findings.
previous article Partitioned difference families versus zero-difference balanced functions
next article A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths
Footnotes
1
Notice that \(\beta _i\) are elements of the set \(\overline{\varGamma }\) plus \(s_1^{-1}m_1\) and then reduced modulo q. But this does not change the discrepancy value.
 
Literature
1.
Adleman L., DeMarrais J.: A subexponential algorithm for discrete logarithms over all finite fields. In: Advances in Cryptology—CRYPTO ’93, 13th Annual International Cryptology Conference, Lecture Notes in Comput. Sci., pp. 147–158. Springer, Berlin (1993).
2.
Barbulescu R., Gaudry P., Joux A., Thomé E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Advances in Cryptology—EUROCRYPT 2014, 33rd Annual International Conference, Lecture Notes in Comput. Sci., pp. 1–16. Springer, Berlin (2014).MATH
3.
Cohen H., Frey G., Avanzi R., Doche C., Lange T., Nguyen K., Vercauteren F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2005).CrossRef
4.
De Mulder E., Hutter M., Marson M., Pearson P.: Using Bleichenbacher’s solution to the Hidden Number Problem to attack nonce leaks in 384-bit ECDSA. In: Cryptographic Hardware and Embedded Systems-CHES 2013, Lecture Notes in Comput. Sci., pp. 435–452. Springer, Berlin (2013).
5.
De Mulder E., Hutter M., Marson M., Pearson P.: Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version. J. Cryptogr. Eng. 4(1), 33–45 (2014).CrossRef
6.
7.
Drmota M., Tichy R.: Sequences, Discrepancies, and Applications. Springer, Berlin (1997).CrossRef
8.
Fan S., Wang W., Cheng Q.: Attacking OpenSSL implementation of ECDSA with a few signatures. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security—CCS’16, pp. 1505–1515. ACM, New York (2016).
9.
Faugère J., Marinier R., Renault G.: Implicit factoring with shared most significant and middle bits. In: Public Key Cryptography, Lecture Notes in Comput. Sci., pp. 70–87. Springer, Berlin (2010).CrossRef
10.
Faugère J., Goyet C., Renault G.: Attacking (EC)DSA given only an implicit hint. In: Selected Areas in Cryptography, 19th International Conference, SAC 2012, Lecture Notes in Comput. Sci., pp. 252–274. Springer, Berlin (2012).CrossRef
11.
FIPS. Digital Signature Standard (DSS). National Institute of Standards and Technology (NIST) (1994).
12.
FIPS. Digital Signature Standard (DSS). pub-NIST, pub-NIST:adr (2013).
13.
Galbraith S., Gaudry P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016).MathSciNetCrossRef
14.
Garaev M.: Sums and products of sets and estimates of rational trigonometric sums in fields of prime order. Russ. Math. Surv. 65(4), 599 (2010).MathSciNetCrossRef
15.
Genkin D., Shamir A., Tromer E.: RSA key extraction via low-bandwidth acoustic cryptanalysis. In: Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Lecture Notes in Comput. Sci., pp. 444–461. Springer, Berlin (2014).CrossRef
16.
Göloglu F., Granger R., McGuire G., Zumbrägel J.: On the function field sieve and the impact of higher splitting probabilities. In: Advances in Cryptology—CRYPTO 2013—33rd Annual Cryptology Conference, Lecture Notes in Comput. Sci., pp. 109–128. Springer, Berlin (2013).CrossRef
17.
Göloglu F., Granger R., McGuire G., Zumbrägel J.: Solving a 6120 -bit DLP on a desktop computer. In: Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Lecture Notes in Comput. Sci., pp. 136–152. Springer, Berlin (2013).
18.
Gómez-Pérez D., Shparlinski I.: Subgroups generated by rational functions in finite fields. Monatsh. Math. 176(2), 241–253 (2014).MathSciNetCrossRef
19.
Howgrave-Graham N., Smart N.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001).MathSciNetCrossRef
20.
Joux A.: Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields. In: Advances in Cryptology—EUROCRYPT 2013, 32nd Annual International Conference, Lecture Notes in Comput. Sci., pp. 177–193. Springer, Berlin (2013).CrossRef
21.
22.
Koblitz N., Menezes A.: A riddle wrapped in an enigma. IEEE Secur. Priv. 14(6), 34–42 (2016).CrossRef
23.
Lenstra A., Lenstra H., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).MathSciNetCrossRef
24.
May A., Ritzenhofen R.: Implicit factoring: on polynomial time factoring given only an implicit hint. In: Public Key Cryptography, Lecture Notes in Comput. Sci., pp. 1–14. Springer, Berlin (2009).
25.
Moreno C., Moreno O.: Exponential sums and Goppa codes. Proc. Am. Math. Soc. 111(2), 523–531 (1991).MathSciNetMATH
26.
27.
Nguyen P., Shparlinski I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002).MathSciNetCrossRef
28.
Nguyen P., Shparlinski I.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30(2), 201–217 (2003).MathSciNetCrossRef
29.
30.
Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1987).MATH
31.
Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1992).CrossRef
32.
Rivest R., Shamir A.: Efficient factoring based on partial information. In: Advances in Cryptology—CRYPTO ’85, 5th Annual International Cryptology Conference, Lecture Notes in Comput. Sci., pp. 31–34. Springer, New York (1986).
33.
Sarkar S., Maitra S.: Further results on implicit factoring in polynomial time. Adv. Math. Commun. 3(2), 205–217 (2009).MathSciNetCrossRef
34.
Schnorr C.: Efficient identification and signatures for smart cards. In: Advances in Cryptology—CRYPTO ’89, 9th Annual International Cryptology Conference, Lecture Notes in Comput. Sci., pp. 239–252. Springer, New York (1990).
35.
Sutherland A.: Structure computation and discrete logarithms in finite abelian p-groups. Math. Comput. 80(273), 477–500 (2011).MathSciNetCrossRef
36.
van de Pol J., Smart N., Yarom Y.: Just a little bit more. In: Cryptographer’s Track at RSA Conference, Lecture Notes in Comput. Sci., pp. 3–21. Springer, Berlin (2015).
37.
Vinogradov I.: Elements of Number Theory (Dover Phoenix Editions). Dover, Dover Publications (2003).
Metadata
Title
A probabilistic analysis on a lattice attack against DSA
Authors
Ana I. Gomez
Domingo Gomez-Perez
Guénaël Renault
Publication date
08-04-2019
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 11/2019
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-019-00633-w

Other articles of this Issue 11/2019

Designs, Codes and Cryptography 11/2019 Go to the issue

OriginalPaper

Partial geometric designs from group actions

OriginalPaper

Linear complexity of generalized cyclotomic sequences of period

OriginalPaper

A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram–Schmidt lengths

OriginalPaper

Partitioned difference families versus zero-difference balanced functions

OriginalPaper

Functional repair codes: a view from projective geometry

OriginalPaper

Matrix theory for minimal trellises

Premium Partner

    Image Credits