Skip to main content
Erschienen in: Designs, Codes and Cryptography 11/2019

08.04.2019

A probabilistic analysis on a lattice attack against DSA

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

Erschienen in: Designs, Codes and Cryptography | Ausgabe 11/2019

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.
Fußnoten
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.
 
Literatur
1.
Zurück zum Zitat 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). 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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). 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Diem C.: On the discrete logarithm problem in elliptic curves II. Algebra Number Theory 7(6), 1281–1323 (2013).MathSciNetCrossRef Diem C.: On the discrete logarithm problem in elliptic curves II. Algebra Number Theory 7(6), 1281–1323 (2013).MathSciNetCrossRef
7.
Zurück zum Zitat Drmota M., Tichy R.: Sequences, Discrepancies, and Applications. Springer, Berlin (1997).CrossRef Drmota M., Tichy R.: Sequences, Discrepancies, and Applications. Springer, Berlin (1997).CrossRef
8.
Zurück zum Zitat 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). 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat FIPS. Digital Signature Standard (DSS). National Institute of Standards and Technology (NIST) (1994). FIPS. Digital Signature Standard (DSS). National Institute of Standards and Technology (NIST) (1994).
12.
Zurück zum Zitat FIPS. Digital Signature Standard (DSS). pub-NIST, pub-NIST:adr (2013). FIPS. Digital Signature Standard (DSS). pub-NIST, pub-NIST:adr (2013).
13.
Zurück zum Zitat Galbraith S., Gaudry P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016).MathSciNetCrossRef Galbraith S., Gaudry P.: Recent progress on the elliptic curve discrete logarithm problem. Des. Codes Cryptogr. 78(1), 51–72 (2016).MathSciNetCrossRef
14.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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). 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.
Zurück zum Zitat Gómez-Pérez D., Shparlinski I.: Subgroups generated by rational functions in finite fields. Monatsh. Math. 176(2), 241–253 (2014).MathSciNetCrossRef Gómez-Pérez D., Shparlinski I.: Subgroups generated by rational functions in finite fields. Monatsh. Math. 176(2), 241–253 (2014).MathSciNetCrossRef
19.
Zurück zum Zitat Howgrave-Graham N., Smart N.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001).MathSciNetCrossRef Howgrave-Graham N., Smart N.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001).MathSciNetCrossRef
20.
Zurück zum Zitat 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 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
22.
Zurück zum Zitat Koblitz N., Menezes A.: A riddle wrapped in an enigma. IEEE Secur. Priv. 14(6), 34–42 (2016).CrossRef Koblitz N., Menezes A.: A riddle wrapped in an enigma. IEEE Secur. Priv. 14(6), 34–42 (2016).CrossRef
23.
Zurück zum Zitat Lenstra A., Lenstra H., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).MathSciNetCrossRef Lenstra A., Lenstra H., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982).MathSciNetCrossRef
24.
Zurück zum Zitat 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). 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.
Zurück zum Zitat Moreno C., Moreno O.: Exponential sums and Goppa codes. Proc. Am. Math. Soc. 111(2), 523–531 (1991).MathSciNetMATH Moreno C., Moreno O.: Exponential sums and Goppa codes. Proc. Am. Math. Soc. 111(2), 523–531 (1991).MathSciNetMATH
27.
Zurück zum Zitat Nguyen P., Shparlinski I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002).MathSciNetCrossRef Nguyen P., Shparlinski I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002).MathSciNetCrossRef
28.
Zurück zum Zitat 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 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.
Zurück zum Zitat Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1987).MATH Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1987).MATH
31.
Zurück zum Zitat Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1992).CrossRef Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, Philadelphia (1992).CrossRef
32.
Zurück zum Zitat 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). 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.
Zurück zum Zitat Sarkar S., Maitra S.: Further results on implicit factoring in polynomial time. Adv. Math. Commun. 3(2), 205–217 (2009).MathSciNetCrossRef Sarkar S., Maitra S.: Further results on implicit factoring in polynomial time. Adv. Math. Commun. 3(2), 205–217 (2009).MathSciNetCrossRef
34.
Zurück zum Zitat 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). 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.
Zurück zum Zitat Sutherland A.: Structure computation and discrete logarithms in finite abelian p-groups. Math. Comput. 80(273), 477–500 (2011).MathSciNetCrossRef Sutherland A.: Structure computation and discrete logarithms in finite abelian p-groups. Math. Comput. 80(273), 477–500 (2011).MathSciNetCrossRef
36.
Zurück zum Zitat 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). 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.
Zurück zum Zitat Vinogradov I.: Elements of Number Theory (Dover Phoenix Editions). Dover, Dover Publications (2003). Vinogradov I.: Elements of Number Theory (Dover Phoenix Editions). Dover, Dover Publications (2003).
Metadaten
Titel
A probabilistic analysis on a lattice attack against DSA
verfasst von
Ana I. Gomez
Domingo Gomez-Perez
Guénaël Renault
Publikationsdatum
08.04.2019
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 11/2019
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-019-00633-w

Weitere Artikel der Ausgabe 11/2019

Designs, Codes and Cryptography 11/2019 Zur Ausgabe