Top

Published in:

2019 | OriginalPaper | Chapter

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

Authors : Joachim Breitner, Nadia Heninger

Published in: Financial Cryptography and Data Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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. If this nonce is not generated uniformly at random, an attacker can potentially exploit this bias 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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

next chapter Snow White: Robustly Reconfigurable Consensus and Applications to Provably Secure Proof of Stake

https://github.com/bitcoin-core/secp256k1/commit/0c6ab2ff.

https://github.com/bitpay/bitcore/pull/409/commits/ac4d318.

https://github.com/bitpay/bitcore/commit/9f9e2f1d.

The code can be found at: https://github.com/nomeata/secp265k1-lookup-table.

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

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

Akavia, A.: Solving hidden number problem with one bit oracle and advice. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 337–354. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_20CrossRef

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, SERIAL 2017, pp. 7:1–7:6. ACM, New York (2017). https://doi.org/10.1145/3152824.3152831. http://doi.acm.org/10.1145/3152824.3152831

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_5CrossRef

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_11CrossRefMATH

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.) FC 2014. LNCS, vol. 8437, pp. 157–175. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_11CrossRef

Brengel, M., Rossow, C.: Identifying key leakage of bitcoin users. In: Bailey, M., Holz, T., Stamatogiannakis, M., Ioannidis, S. (eds.) RAID 2018. LNCS, vol. 11050, pp. 623–643. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00470-5_29CrossRef

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

10.

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

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: 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_1CrossRef

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., et al.: Cachequote: efficiently recovering long-term secrets of SGX EPID via cache attacks. IACR Trans. Cryptogr. Hardware Embed. Syst. 2018(2), 171–191 (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.) CHES 2013. LNCS, vol. 8086, pp. 435–452. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40349-1_25CrossRef

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, October 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, August 2012

19.

Howgrave-Graham, N.A., Smart, N.P.: Lattice attacks on digital signatureschemes. Des. Codes Crypt. 23(3), 283–290 (2001). https://doi.org/10.1023/A:1011214926272CrossRefMATH

20.

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

21.

Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)MathSciNetCrossRef

22.

Michaelis, K., Meyer, C., Schwenk, J.: Randomly failed! The state of randomness in current Java implementations. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 129–144. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36095-4_9CrossRefMATH

23.

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

24.

National Institute of Standards and Technology: FIPS PUB 180-2: Secure Hash Standard, August 2002

25.

National Institute of Standards and Technology: FIPS PUB 186-4: Digital Signature Standard (DSS), July 2013

26.

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). https://doi.org/10.1023/A:1025436905711MathSciNetCrossRefMATH

27.

Nguyen, P.Q., Stehlé, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006). https://doi.org/10.1007/11792086_18CrossRef

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) (2013). https://tools.ietf.org/html/rfc6979

30.

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

31.

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

32.

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

33.

Schwartz, D., Youngs, N., Britto, A.: The Ripple protocol consensus algorithm (2014). https://ripple.com/files/ripple_consensus_whitepaper.pdf. Accessed 08 Aug 2016

34.

Shanks, D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposia in Pure Mathematics, vol. 20, pp. 41–440 (1971)

35.

Blockchain Team: 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)

Title: Biased Nonce Sense: Lattice Attacks Against Weak ECDSA Signatures in Cryptocurrencies
Authors: Joachim Breitner
Nadia Heninger
Publisher: Springer International Publishing
Book: Financial Cryptography and Data Security
Print ISBN: 978-3-030-32100-0

Electronic ISBN: 978-3-030-32101-7

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-32101-7_1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner