Abstract
The Elliptic Curves Digital Signature Algorithm (ECDSA) is a standard public key signature protocol. It has become essential to the security of blockchain, digital currency, and many more Internet applications. Currently, it is still one of the most popular algorithms used for digital signing and SSL/TLS transport. Among the possible attacks on ECDSA, side-channel attack poses a serious threat against hardware and software implementations. In particular, Extended Hidden Number Problem can be used when ECDSA leaks side-channel information about the double-and-add chains. The problem is then converted to the shortest vector problem and solved with lattice algorithms. In this paper, we analyze the Extended Hidden Number Problem and present an improved EHNP lattice attack on ECDSA implementations that adopt leaky scalar multiplication. Our attack requires information of double-and-add chains or traces extracted from side-channel results. In addition to methods such as elimination and merging that have been introduced, we make further improvements according to the specific structure of the lattice basis. In fact, the specific property of EHNP allows us to find a sublattice that contains the target vector. We simulate the attack to the secp256k1, and the result shows that three signatures are enough to lead to a success rate greater than 0.8. When 4 or 5 traces are known, the success rate is close to 1. The new algorithm significantly improves the performance of attacks using EHNP methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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
Albrecht, M.R., Göpfert, F., Virdia, F., Wunderer, T.: Revisiting the expected cost of solving uSVP and applications to LWE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 297–322. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_11
Albrecht, M.R., Heninger, N.: On bounded distance decoding with predicate: breaking the “lattice barrier’’ for the hidden number problem. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 528–558. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_19
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 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_11
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, Cham (2019). https://doi.org/10.1007/978-3-030-32101-7_1
Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 329–358. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_12
Dall, F., et al.: Cachequote: efficiently recovering long-term secrets of SGX EPID via cache attacks (2018)
De Micheli, G., Piau, R., Pierrot, C.: A tale of three signatures: practical attack of ECDSA with wNAF. In: Nitaj, A., Youssef, A. (eds.) AFRICACRYPT 2020. LNCS, vol. 12174, pp. 361–381. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51938-4_18
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, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_5
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, pp. 1505–1515 (2016)
Genkin, D., Pachmanov, L., Pipman, I., Tromer, E., Yarom, Y.: ECDSA key extraction from mobile devices via nonintrusive physical side channels. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS 2016, pp. 1626–1638. Association for Computing Machinery, New York (2016). https://doi.org/10.1145/2976749.2978353
Hai, H., Ning, N., Lin, X., Zhiwei, L., Bin, Y., Shilei, Z.: An improved wNAF scalar-multiplication algorithm with low computational complexity by using prime precomputation. IEEE Access 9, 31546–31552 (2021)
Hlaváč, M., Rosa, T.: Extended hidden number problem and its cryptanalytic applications. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 114–133. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74462-7_9
Howgrave-graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Crypt. 23, 283–290 (2001)
Jancar, J., Sedlacek, V., Svenda, P., Sys, M.: Minerva: the curse of ECDSA nonces systematic analysis of lattice attacks on noisy leakage of bit-length of ECDSA nonces. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2020(4), 281–308 (2020). https://doi.org/10.13154/tches.v2020.i4.281-308. https://tches.iacr.org/index.php/TCHES/article/view/8684
Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25
Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-88702-7_5
Micciancio, D., Walter, M.: Practical, predictable lattice basis reduction. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 820–849. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_31
Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Crypt. 30(2), 201–217 (2003)
Nguyen, P.Q., Vallée, B.: The LLL algorithm: survey and applications. Information Security and Cryptography. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02295-1. https://hal.archives-ouvertes.fr/hal-01141414
van de Pol, J., Smart, N.P., Yarom, Y.: Just a little bit more. In: Nyberg, K. (ed.) CT-RSA 2015. LNCS, vol. 9048, pp. 3–21. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16715-2_1
The FPLLL development team: fplll, a lattice reduction library, Version: 5.4.1 (2021). https://github.com/fplll/fplll/
The FPLLL development team: fpylll, a Python wraper for the fplll lattice reduction library, Version: 0.5.6 (2021). https://github.com/fplll/fpylll
The FPLLL development team: The general sieve kernel (g6k) (2021). https://github.com/fplll/fpylll
Yarom, Y., Benger, N.: Recovering openssl ECDSA nonces using the flush+ reload cache side-channel attack. IACR Cryptol. ePrint Arch. 2014, 140 (2014)
Yarom, Y., Falkner, K.: Flush+reload: a high resolution, low noise, L3 cache side-channel attack. In: 23rd USENIX Security Symposium (USENIX Security 2014), pp. 719–732 (2014)
Acknowledgments
This work was supported by the National Natural Science Foundation of China (Nos. 61872449, 62125205).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cao, J., Pan, Y., Cheng, Q., Li, X. (2022). Handle the Traces: Revisiting the Attack on ECDSA with EHNP. In: Nguyen, K., Yang, G., Guo, F., Susilo, W. (eds) Information Security and Privacy. ACISP 2022. Lecture Notes in Computer Science, vol 13494. Springer, Cham. https://doi.org/10.1007/978-3-031-22301-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-22301-3_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22300-6
Online ISBN: 978-3-031-22301-3
eBook Packages: Computer ScienceComputer Science (R0)