[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-Based Attacks

  • Conference paper
  • First Online:
Advances in Cryptology – ASIACRYPT 2024 (ASIACRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15491))

  • 293 Accesses

Abstract

The Hidden Number Problem (HNP) has found extensive applications in side-channel attacks against cryptographic schemes, such as ECDSA and Diffie-Hellman. There are two primary algorithmic approaches to solving the HNP: lattice-based attacks and Fourier analysis-based attacks. Lattice-based attacks exhibit better efficiency and require fewer samples when sufficiently long substrings of the nonces are known. However, they face significant challenges when only a small fraction of the nonce is leaked, such as 1-bit leakage, and their performance degrades in the presence of errors.

In this paper, we address an open question by introducing an algorithmic tradeoff that significantly bridges the gap between these two approaches. By introducing a parameter x to modify Albrecht and Heninger’s lattice, the lattice dimension is reduced by approximately \((\log _2{x})/ l\), where l represents the number of leaked bits. We present a series of new methods, including the interval reduction algorithm, several predicates, and the pre-screening technique. Furthermore, we extend our algorithms to solve the HNP with erroneous input. Our attack outperforms existing state-of-the-art lattice-based attacks against ECDSA. We obtain several records including 1-bit and less than 1-bit leakage on a 160-bit curve, while the best previous lattice-based attack for 1-bit leakage was conducted only on a 112-bit curve.

Yiming Gao and Jinghui Wang are the co-first authors of this work.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 49.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 64.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    https://github.com/JinghuiWW/ecdsa-leakage-attack.

  2. 2.

    In fact, the samples used in the lattice construction, the linear predicate, the interval reduction algorithm, and the prescreening technique are all distinct from each other.

References

  1. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: 33rd ACM STOC. pp. 601–610. (2001). https://doi.org/10.1145/380752.380857

  2. Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 717-746. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_25

  3. Albrecht, M.R., Heninger, N.: On bounded distance decoding with predicate: Breaking the “lattice barrier” for the hidden number problem. In: Canteaut, A., Standaert, FX. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 528-558. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_19

  4. Albrecht, M.R., Heninger, N.: Bounded distance decoding with predicate sourcecode (2020). https://github.com/malb/bdd-predicate

  5. Aranha, D.F., Fouque, PA., Gérard, B., Kammerer, JG., Tibouchi, M., Zapalowicz, JC.: GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 262-281. Springer, Berlin, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45611-8_14

  6. Aranha, D.F., Novaes, F.R., Takahashi, A., Tibouchi, M., Yarom, Y.: LadderLeak: Breaking ECDSA with less than one bit of nonce leakage. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, pp. 225-242. ACM Press (2020). https://doi.org/10.1145/3372297.3417268

  7. Babai, L.: On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6, 1-13 (1986). https://doi.org/10.1007/BF02579403

  8. Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10-24. ACM-SIAM (2016).https://doi.org/10.1137/1.9781611974331.ch2

  9. Becker, A., Gama, N., Joux, A.: Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. Cryptology ePrint Archive, Report 2015/522 (2015). http://eprint.iacr.org/2015/522

  10. Bleichenbacher, D.: On the generation of one-time keys in DL signature schemes. Presentation at IEEE P1363 Working Group Meeting (2000)

    Google Scholar 

  11. Bleichenbacher, D.: Experiments with DSA. Rump session at CRYPTO (2005). https://www.iacr.org/conferences/crypto2005/r/3.pdf

  12. Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO 96. LNCS, vol. 1109, pp. 129-142. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_11

  13. Breitner, J., Heninger, N.: Biased nonce sense: Lattice attacks against weak ECDSA signatures in cryptocurrencies. In: Goldberg, I., Moore, T. (eds.) FC 2019. LNCS, vol. 11598, pp. 3-20. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-32101-7_1

  14. De Mulder, E., Hutter, M., Marson, M.E., Pearson, P.: Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA. In: Bertoni, G., Coron, J.S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 435-452. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40349-1_25

  15. Ducas, L.: Shortest vector from lattice sieving: A few dimensions for free. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 125-145. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-78381-9_5

  16. Ducas, L., Stevens, M., van Woerden, W.: Advanced lattice sieving on GPUs, with tensor cores. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 249-279. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_9

  17. Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Mathematics of Computation 44(170), 463-471 (1985)

    Google Scholar 

  18. Fitzpatrick, R., Bischof, C., Buchmann, J., Dagdelen, Ö., Göpfert, F., Mariano, A., Yang, B.-Y.: Tuning GaussSieve for speed. In: LATINCRYPT 2014. LCNS, vol. 8895, pp. 288-305. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-16295-9_16

  19. Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257-278. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_13

  20. Heninger, N.: Using Lattices for Cryptanalysis. (2020). https://simons.berkeley.edu/-talks/using-lattices-cryptanalysis

  21. Herold, G., Kirshanova, E., Laarhoven, T. : Speed-ups and time-memory trade-offs for tuple lattice sieving. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol 10769, pp.407-436. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_14

  22. Jancar, J., Sedlacek, V., Svenda, P., Sys, M.: Minerva: The curse of ECDSA nonces. IACR TCHES 2020(4), 281-308 (2020). https://doi.org/10.13154/tches.v2020.i4.281-308

  23. Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415-440 (1987). https://doi.org/10.1287/moor.12.3.415

  24. Laarhoven, T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 3-22. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_1

  25. Laarhoven, T., Mariano, A.: Progressive lattice sieving. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 292-311. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-79063-3_14

  26. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 366-389 (1982). https://infoscience.epfl.ch/record/164484/files/nscan4.PDF

  27. Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Charika, M. (ed.) 21st SODA. pp. 1468-1480. ACM-SIAM (2010). https://doi.org/10.1137/1.9781611973075.119

  28. Moghimi, D., Sunar, B., Eisenbarth, T., Heninger, N.: TPM-FAIL: TPM meets timing and lattice attacks. In: Capkun, S., Roesner, F. (eds.): USENIX Security 2020. pp. 2057-2073. (2020). https://www.usenix.org/system/files/sec20-moghimi-tpm.pdf

  29. Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. Journal of Cryptology 15(3), 151-176 (2002). https://doi.org/10.1007/s00145-002-0021-3

  30. Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. of Mathematical Cryptology 2(2), 181-207 (2008). https://doi.org/10.1515/JMC.2008.009

  31. Ryan, K.: Return of the hidden number problem. IACR TCHES 2019(1), 146-168 (2018). https://tches.iacr.org/index.php/TCHES/article/view/7337

  32. Schnorr, C.P. : Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145-156. Springer, Berlin, Heidelberg (2003). https://doi.org/10.1007/3-540-36494-3_14

  33. Schnorr, C., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program. 66, 181-199 (1994). https://doi.org/10.1007/BF01581144

  34. Sun, C., Espitau, T., Tibouchi, M., Abe, M.: Guessing bits: Improved lattice attacks on (EC)DSA with nonce leakage. IACR TCHES 2022(1), 391-413 (2022). https://tches.iacr.org/index.php/TCHES/article/view/9302

  35. Takahashi, A., Tibouchi, M., Abe, M.: New Bleichenbacher records: Fault attacks on qDSA signatures. IACR TCHES 2018(3), 331-371 (2018). https://tches.iacr.org/index.php/TCHES/article/view/7278

  36. The G6K development team: G6K (2020). https://github.com/fplll/g6k

  37. The G6k-GPU-Tensor development team: G6k-GPU-Tensor (2021). https://github.com/WvanWoerden/G6K-GPU-Tensor

  38. Xu, L., Dai, Z., Wu, B., Lin, D.: Improved attacks on (EC)DSA with nonce leakage by lattice sieving with predicate. IACR TCHES 2023(2), 568-586 (2023). https://doi.org/10.46586/tches.v2023.i2.568-586

Download references

Acknowledgements

We would like to thank the anonymous reviewers of ASIACRYPT 2024, EUROCRYPT 2024 and CRYPTO 2024 for their insightful suggestions. We also thank Fan Huang, Xiaolin Duan, Yaqi Wang, and Changhong Xu for their valuable support to this work. This work was supported by National Natural Science Foundation of China (Grant No. 62472397) and Innovation Program for Quantum Science and Technology (Grant No. 2021ZD0302902).

Author information

Authors and Affiliations

  1. School of Cyber Science and Technology, University of Science and Technology of China, Hefei, 230027, China

    Yiming Gao, Jinghui Wang, Honggang Hu & Binang He

  2. Hefei National Laboratory, Hefei, 230088, China

    Honggang Hu

Authors
  1. Yiming Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinghui Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Honggang Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Binang He
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Honggang Hu .

Editor information

Editors and Affiliations

  1. Academia Sinica, Taipei, Taiwan

    Kai-Min Chung

  2. NTT Social Informatics Laboratories, Tokyo, Japan

    Yu Sasaki

Rights and permissions

Reprints and permissions

Copyright information

© 2025 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Gao, Y., Wang, J., Hu, H., He, B. (2025). Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-Based Attacks. In: Chung, KM., Sasaki, Y. (eds) Advances in Cryptology – ASIACRYPT 2024. ASIACRYPT 2024. Lecture Notes in Computer Science, vol 15491. Springer, Singapore. https://doi.org/10.1007/978-981-96-0944-4_1

Download citation

  • DOI: https://doi.org/10.1007/978-981-96-0944-4_1

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-96-0943-7

  • Online ISBN: 978-981-96-0944-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics