Abstract
A lattice attack on the Elliptic Curve Digital Signature Algorithm (ECDSA) implementation constructs a lattice related to the secret key by utilizing the information leaked and then recovers the secret key by finding a certain short lattice vector. When the information leaked is discrete bits, Fan et al. (CCS 2016) constructed an efficient lattice by translating the problem of recovering the secret key to the Extended Hidden Number Problem (EHNP). Following their works, we propose two new techniques to construct a more efficient lattice which has a lower dimension and a shorter target vector. Moreover, we further improve the success probability of the secret key recovery by adjusting the lattice. Therefore, it is much easier to recover the secret key. Specifically, injecting our techniques into the existing lattice attacks, we recover the secret key with fewer signatures or a higher success probability.
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
Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: USENIX Security Symposium, pp. 327–343. USENIX Association (2016)
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
Brumley, B.B., Tuveri, N.: Remote timing attacks are still practical. In: Atluri, V., Diaz, C. (eds.) ESORICS 2011. LNCS, vol. 6879, pp. 355–371. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23822-2_20
Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_1
Fan, S., Wang, W., Cheng, Q.: Attacking openssl implementation of ECDSA with a few signatures. In: CCS, pp. 1505–1515. ACM (2016)
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., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001)
Jancar, J., Sedlacek, V., Svenda, P., Sýs, 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)
Johnson, D., Menezes, A., Vanstone, S.A.: The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Sec. 1(1), 36–63 (2001)
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4) (1982)
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
Moghimi, D., Sunar, B., Eisenbarth, T., Heninger, N.: TPM-FAIL: TPM meets timing and lattice attacks. In: USENIX Security Symposium, pp. 2057–2073. USENIX Association (2020)
Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)
Page, D.: Theoretical use of cache memory as a cryptanalytic side-channel. IACR Cryptol. ePrint Arch. 2002, 169 (2002)
Schnorr, C., Euchner, M.: Digital signature standard (dss) FIPS, 186–3 (2013)
Wang, W., Fan, S.: Attacking openssl ECDSA with a small amount of side-channel information. Sci. China Inf. Sci. 61(3), 032105:1–032105:14 (2018)
Weiser, S., Schrammel, D., Bodner, L., Spreitzer, R.: Big numbers - big troubles: systematically analyzing nonce leakage in (EC)DSA implementations. In: USENIX Security Symposium, pp. 1767–1784. USENIX Association (2020)
Acknowledgements
We thank the anonymous reviewers for their helpful comments and suggestions. Xianhui Lu and Shuaigang Li are supported by the National Natural Science Foundation of China (Grant No. 61972391).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, S., Fan, S., Lu, X. (2021). Attacking ECDSA Leaking Discrete Bits with a More Efficient Lattice. In: Yu, Y., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2021. Lecture Notes in Computer Science(), vol 13007. Springer, Cham. https://doi.org/10.1007/978-3-030-88323-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-88323-2_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-88322-5
Online ISBN: 978-3-030-88323-2
eBook Packages: Computer ScienceComputer Science (R0)