Wednesday, January 16, 2019

Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies

Cryptology ePrint Archive: Report 2019/023

Date: 2019-01-08

Author(s): Joachim Breitner, Nadia Heninger

Link to Paper

​

Abstract

In this paper, we compute hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS private keys by carrying out cryptanalytic attacks against digital signatures contained in public blockchains and Internet-wide scans. The ECDSA signature algorithm requires the generation of a per-message secret nonce. This nonce must be generated perfectly uniformly, or else an attacker can exploit the nonce biases to compute the long-term signing key. We use a lattice-based algorithm for solving the hidden number problem to efficiently compute private ECDSA keys that were used with biased signature nonces due to multiple apparent implementation vulnerabilities.

​

References

  1. The most repeated r value on the blockchain. https://bitcointalk.org/index.php?topic=1118704.0 (2015)

  2. Bitcoin wiki: Address reuse. https://en.bitcoin.it/wiki/Address reuse (2018)

  3. Akavia, A.: Solving hidden number problem with one bit oracle and advice. In: Halevi, S. (ed.) Advances in Cryptology - CRYPTO 2009. pp. 337–354. Springer Berlin Heidelberg, Berlin, Heidelberg (2009)

  4. Bartoletti, M., Lande, S., Pompianu, L., Bracciali, A.: A general framework for blockchain analytics. In: Proceedings of the 1st Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers. pp. 7:1–7:6. SERIAL ’17, ACM, New York, NY, USA (2017). https://doi.org/10.1145/3152824.3152831, http://doi.acm.org/10.1145/3152824.3152831

  5. 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.) Cryptographic Hardware and Embedded Systems – CHES 2014. pp. 75–92. Springer Berlin Heidelberg, Berlin, Heidelberg (2014)

  6. Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in diffie-hellman and related schemes. In: Koblitz, N. (ed.) Advances in Cryptology — CRYPTO ’96. pp. 129–142. Springer Berlin Heidelberg, Berlin, Heidelberg (1996)

  7. Bos, J.W., Halderman, J.A., Heninger, N., Moore, J., Naehrig, M., Wustrow, E.: Elliptic curve cryptography in practice. In: Christin, N., Safavi-Naini, R. (eds.) Financial Cryptography and Data Security. pp. 157–175. Springer Berlin Heidelberg, Berlin, Heidelberg (2014)

  8. Brengel, M., Rossow, C.: Identifying key leakage of bitcoin users. In: Bailey, M., Holz, T., Stamatogiannakis, M., Ioannidis, S. (eds.) Research in Attacks, Intrusions, and Defenses. pp. 623–643. Springer International Publishing, Cham (2018)

  9. Brown, D.R.L.: SEC 2: Recommended elliptic curve domain parameters. http://www.secg.org/sec2-v2.pdf (2010)

  10. Buterin, V.: Ethereum: A next-generation smart contract and decentralized application platform. https://github.com/ethereum/wiki/wiki/White-Paper (2013)

  11. Castellucci, R., Valsorda, F.: Stealing bitcoin with math (2016), https://news.webamooz.com/wp-content/uploads/bot/offsecmag/151.pdf

  12. Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: ASIACRYPT. Lecture Notes in Computer Science, vol. 7073, pp. 1–20. Springer (2011)

  13. Courtois, N.T., Emirdag, P., Valsorda, F.: Private key recovery combination attacks: On extreme fragility of popular bitcoin key management, wallet and cold storage solutions in presence of poor rng events. Cryptology ePrint Archive, Report 2014/848 (2014), https://eprint.iacr.org/2014/848

  14. Dall, F., De Micheli, G., Eisenbarth, T., Genkin, D., Heninger, N., Moghimi, A., Yarom, Y.: Cachequote: Efficiently recovering long-term secrets of SGX EPID via cache attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems 2018(2), 171–191 (May 2018). https://doi.org/10.13154/tches.v2018.i2.171-191, https://tches.iacr.org/index.php/TCHES/article/view/879

  15. 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.) Cryptographic Hardware and Embedded Systems - CHES 2013. pp. 435–452. Springer Berlin Heidelberg, Berlin, Heidelberg (2013) Biased Nonce Sense 17

  16. Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) protocol. IETF RFC RFC5246 (2008)

  17. Durumeric, Z., Adrian, D., Mirian, A., Bailey, M., Halderman, J.A.: A search engine backed by Internet-wide scanning. In: 22nd ACM Conference on Computer and Communications Security (Oct 2015)

  18. Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: Detection of widespread weak keys in network devices. In: Proceedings of the 21st USENIX Security Symposium (Aug 2012)

  19. Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signature schemes. Designs, Codes and Cryptography 23(3), 283–290 (Aug 2001). https://doi.org/10.1023/A:1011214926272, https://doi.org/10.1023/A:1011214926272

  20. Klyubin, A.: Some SecureRandom thoughts. https://android-developers.googleblog.com/2013/08/some-securerandom-thoughts.html (August 2013)

  21. Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. MATH. ANN 261, 515–534 (1982)

  22. Michaelis, K., Meyer, C., Schwenk, J.: Randomly Failed! The State of Randomness in Current Java Implementations. In: CT-RSA. vol. 7779, pp. 129–144. Springer (2013)

  23. Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system. http://bitcoin.org/bitcoin.pdf (2009)

  24. National Institute of Standards and Technology: FIPS PUB 180-2: Secure Hash Standard (Aug 2002)

  25. National Institute of Standards and Technology: FIPS PUB 186-4: Digital Signature Standard (DSS) (Jul 2013)

  26. Nguyen, P.Q., Shparlinski, I.E.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Designs, Codes and Cryptography 30(2), 201–217 (Sep 2003). https://doi.org/10.1023/A:1025436905711, https://doi.org/10.1023/A:1025436905711

  27. Nguyen, P.Q., Stehl´e, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) Algorithmic Number Theory. pp. 238–256. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)

  28. Pollard, J.M.: Monte Carlo methods for index computation (mod p). In: Mathematics of Computation. vol. 32 (1978)

  29. Pornin, T.: Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA). https://tools.ietf.org/html/rfc6979 (2013)

  30. rico666: Large bitcoin collider. https://lbc.cryptoguru.org/

  31. Schnorr, C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53(2-3), 201–224 (Aug 1987). https://doi.org/10.1016/0304-3975(87)90064-890064-8), http://dx.doi.org/10.1016/0304-3975(87)90064-890064-8)

  32. Schnorr, C.P., Euchner, M.: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program. 66(2), 181–199 (Sep 1994). https://doi.org/10.1007/BF01581144, http://dx.doi.org/10.1007/BF01581144

  33. Schwartz, D., Youngs, N., Britto, A.: The Ripple protocol consensus algorithm. https://ripple.com/files/ripple consensus whitepaper.pdf (2014), https://ripple.com/files/ripple consensus whitepaper.pdf, accessed: 2016-08-08

  34. Shanks, D.: Class number, a theory of factorization, and genera. In: Proc. of Symp. Math. Soc., 1971. vol. 20, pp. 41–440 (1971)

  35. Team, B.: Android wallet security update. https://blog.blockchain.com/2015/05/28/android-wallet-security-update/

  36. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 8.1) (2017), http://www.sagemath.org

  37. Valsorda, F.: Exploiting ECDSA failures in the bitcoin blockchain. Hack In The Box (HITB) (2014)

  38. Ylonen, T., Lonvick, C.: The Secure Shell (SSH) transport layer protocol. IETF RFC 4253 (2006)


Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)