Abstract
Various attacks are proposed against different ECDSA implementations: the key-related data are acquired through cache side channels, and then processed to recover the private key. For each cache side channel attack, the requirements of the data qualified for sequent processing vary greatly, and the success probability of private key recovery relies on both the acquired data and the parameters of data processing. So it is difficult to tell, for a certain ECDSA implementation, (a) how many signatures does a cache side channel attack need to recover the private key? or which attack performs the best? and (b) what kind of threat level exists due to potential side channel attacks, if the ECDSA implementation runs for a number of signatures on an unprotected system with cache side channels? Currently, there is no quantitative metric to fairly answer the questions. Such a metric to evaluate cache side channel attacks, will provide a reference for the adversaries to choose the suitable attack, and also for the defenders to set up protections for the certain ECDSA implementation (e.g., updating the private key after it has been used for a certain number of signatures). In this paper, we design an evaluation approach to quantitatively compare the cache side channel attacks against ECDSA. The expected minimum number of signatures needed for at least one successful private key recovery, is proposed as the metric, and this metric considers both the data requirements and the success probability. We apply the approach to evaluate various cache side channel attacks against ECDSA. By calculating the metric, we obtain (a) for each attack, the optimal parameters with the minimum number of signatures needed, and (b) for each ECDSA implementation, the minimum number of signatures that will be enough for at least one successful private key recovery of some cache side channel attacks.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In practical implementations, the ephemeral key is added by q or 2q to make sure that k is \(\lfloor \log _{2}{q}\rfloor + 1\) bit long and resist the remote timing side channel attack in [6].
References
Acıiçmez, O., Brumley, B.B., Grabher, P.: New results on instruction cache attacks. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 110–124. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15031-9_8
American National Standards Institute: ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA) (2005)
Barenghi, A., Bertoni, G., Palomba, A., Susella, R.: A novel fault attack against ECDSA. In: Proceedings of the IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 161–166 (2011)
Benger, N., van de Pol, J., Smart, N.P., Yarom, Y.: “Ooh Aah... Just a Little Bit”: a small amount of side channel can go a long way. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 75–92. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_5
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
Cao, W., et al.: Two lattice-based differential fault attacks against ECDSA with wNAF algorithm. In: Kwon, S., Yun, A. (eds.) ICISC 2015. LNCS, vol. 9558, pp. 297–313. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30840-1_19
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48059-5_25
Fan, S., Wang, W., Cheng, Q.: Attacking OpenSSL implementation of ECDSA with a few signatures. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, (CCS), pp. 1505–1515 (2016)
Fouque, P., Lercier, R., Réal, D., Valette, F.: Fault attack on elliptic curve montgomery ladder implementation. In: 5th Workshop on Fault Diagnosis and Tolerance in Cryptography, pp. 92–98 (2008)
Gordon, D.M.: A survey of fast exponentiation methods. J. Algorithms 27(1), 129–146 (1998)
Goubin, L.: A refined power-analysis attack on elliptic curve cryptosystems. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 199–211. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_15
Goudarzi, D., Rivain, M., Vergnaud, D.: Lattice attacks against elliptic-curve signatures with blinded scalar multiplication. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 120–139. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_7
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(3), 283–290 (2001)
Callas, J., Donnerhacke, L., Finney, H., Shaw, D., Thayer, R.: OpenPGP Message Format (RFC 4880) (2007)
Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Secur. 1(1), 36–63 (2001)
Koyama, K., Tsuruoka, Y.: Speeding up elliptic cryptosystems by using a signed binary window method. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 345–357. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_25
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515–534 (1982)
Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36095-4_19
Medwed, M., Oswald, E.: Template attacks on ECDSA. In: Chung, K.-I., Sohn, K., Yung, M. (eds.) WISA 2008. LNCS, vol. 5379, pp. 14–27. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00306-6_2
Miyaji, A., Ono, T., Cohen, H.: Efficient elliptic curve exponentiation. In: Han, Y., Okamoto, T., Qing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 282–290. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0028484
Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008). https://bitcoin.org/bitcoin.pdf
National Institute of Standards and Technology: FIPS PUB 186-4 Digital Signature Standard (DSS), 19 July 2013
Nguyen, P.Q.: The dark side of the hidden number problem: Lattice attacks on DSA. In: Lam, K.Y., Shparlinski, I., Wang, H., Xing, C. (eds.) Cryptography and Computational Number Theory, pp. 321–330. Springer, Basel (2001). https://doi.org/10.1007/978-3-0348-8295-8_23
Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)
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)
Pereida García, C., Brumley, B.B., Yarom, Y.: Make sure DSA signing exponentiations really are constant-time. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, (CCS), pp. 1639–1650 (2016)
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
Schmidt, J., Medwed, M.: A fault attack on ECDSA. In: Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, (FDTC), pp. 93–99 (2009)
Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1–3), 181–199 (1994). https://doi.org/10.1007/BF01581144
Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of the Symposium of Pure Mathematics, vol. 20, pp. 415–440 (1971)
Solinas, J.A.: Efficient arithmetic on koblitz curves. Des. Codes Crypt. 19(2), 195–249 (2000)
Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2 (RFC 5246) (2008)
Wunan, W., Hao, C., Jun, C.: The attack case of ECDSA on blockchain based on improved simple power analysis. In: Sun, X., Pan, Z., Bertino, E. (eds.) ICAIS 2019. LNCS, vol. 11635, pp. 120–132. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24268-8_12
Wang, W., Fan, S.: Attacking OpenSSL ECDSA with a small amount of side-channel information. Sci. China Inf. Sci. 61(3), 032105 (2017). https://doi.org/10.1007/s11432-016-9030-0
Yarom, Y., Benger, N.: Recovering OpenSSL ECDSA nonces using the FLUSH+ RELOAD cache side-channel attack. IACR Cryptology ePrint Archive (2014)
Yarom, Y., Falkner, K.: Flush+Reload: a high resolution, low noise, L3 cache side-channel attack. In: Proceedings of the 23rd USENIX Conference on Security Symposium, pp. 719–732 (2014)
Acknowledgments
This work was supported by the 13th Five-year Informatization Plan of Chinese Academy of Sciences, (Grant No. XXH13507-01) and National Key R&D Program (No. 2017YFB0802100 and No. 2018YFB0804600).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Ma, Z., Cai, Q., Lin, J., Jing, J., Ye, D., Meng, L. (2020). Evaluating the Cache Side Channel Attacks Against ECDSA. In: Liu, Z., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2019. Lecture Notes in Computer Science(), vol 12020. Springer, Cham. https://doi.org/10.1007/978-3-030-42921-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-42921-8_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-42920-1
Online ISBN: 978-3-030-42921-8
eBook Packages: Computer ScienceComputer Science (R0)