Speed Optimizations in Bitcoin Key Recovery Attacks

Courtois, Nicolas; Song, Guangyan; Castellucci, Ryan

doi:10.1515/tmmp-2016-0030

Abstract

In this paper, we study and give the first detailed benchmarks on existing implementations of the secp256k1 elliptic curve used by at least hundreds of thousands of users in Bitcoin and other cryptocurrencies. Our implementation improves the state of the art by a factor of 2.5 with a focus on the cases, where side channel attacks are not a concern and a large quantity of RAM is available. As a result, we are able to scan the Bitcoin blockchain for weak keys faster than any previous implementation. We also give some examples of passwords which we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.

References

[1] BERNSTEIN, D. J.—LANGE, T.: Explicit-formulas database, 2007, https://hyperelliptic.org/EFD/
Search in Google Scholar Back to article
[2] BERNSTEIN, D. J.—LANGE, T.: Faster addition and doubling on elliptic curves, in: Advances in cryptology–ASIACRYPT ’07, Lecture Notes in Comput. Sci., Vol. 4833, Springer-Verlag, Berlin, 2007, pp. 29–50.
Search in Google Scholar Back to article
[3] BRICKELL, E. F.—GORDON, D. M.—MCCURLEY, K. S.—WILSON, D. B.: Fast exponentiation with precomputation, in: Advances in Cryptology-EUROCRYPT ’92, Springer-Verlag, Berlin, 1993, pp. 200–207.10.1007/3-540-47555-9_18
Search in Google Scholar Back to article
[4] BRIER, E.—JOYE, M.: Weierstraß elliptic curves and side-channel attacks, in: International Workshop on Public Key Cryptography—PKC ’02, Springer-Verlag, 2002, pp. 335–345.10.1007/3-540-45664-3_24
Search in Google Scholar Back to article
[5] BROWN, M.—HANKERSON, D.—LÓPEZ, J.—MENEZES, A.: Software implementation of the NIST elliptic curves over prime fields, in: Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer’s Track at RSA, April 08–12, 2001, CT-RSA ’01, London, UK; Lecture Notes in Comput. Sci., Vol. 2020, Springer-Verlag, 2001. pp.250–265.
Search in Google Scholar Back to article
[6] CASTELLUCCI, R.: Cracking cryptocurrency brainwallets, https://www.defcon.org/html/defcon-23/dc-23-index.html
Search in Google Scholar Back to article
[7] CERTICOM RESEARCH: Sec 2: Recommended elliptic curve domain parameters, in: Proceeding of Standards for Efficient Cryptography, Version 1, 2000. www.secg.org/SEC2-Ver-1.0.pdf
Search in Google Scholar Back to article
[8] COHEN, H.—MIYAJI, A.—ONO, T.: Efficient elliptic curve exponentiation using mixed coordinates, in: Advances in Cryptology, ASIACRYPT ’98 (Beijing), Lecture Notes in Comput. Sci., Vol. 1514, Springer-Verlag, Berlin, 1998, pp. 51–65.
Search in Google Scholar Back to article
[9] HANKERSON, D.—MENEZES, A. J.—VANSTONE, S.: Guide to Elliptic Curve Cryptography, Springer Science & Business Media, 2006.
Search in Google Scholar Back to article
[10] KOBLITZ, N.: Elliptic curve cryptosystems, Mathematics of computation, 48 (1987), no.177, 203–209.
Search in Google Scholar Back to article
[11] MILLER, V. S.: Use of elliptic curves in cryptography, in: Proc. Advances in Cryptology–CRYPTO ’85 (Santa Barbara, Calif., 1985), Lecture Notes in Comput. Sci., Vol. 218, Springer-Verlag, Berlin, 1986, 417–426.10.1007/3-540-39799-X_31
Search in Google Scholar Back to article
[12] NAKAMOTO, S.: Bitcoin: A peer-to-peer electronic cash system, https://bitcoin.org/bitcoin.pdf, 2008.
Search in Google Scholar Back to article
[13] RIVEST, R. L.—SHAMIR, A.—ADLEMAN, L.: A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (1978), no. 2, 120–126.10.21236/ADA606588
Search in Google Scholar Back to article
[14] WUILLE, P.: bitcoin secp256k1 library, version 2015/08/11, https://github.com/bitcoin/secp256k1
Search in Google Scholar Back to article
[15] VASEK, M.—BONNEAU, J.—KEITH, C.—CASTELLUCCI, R.—MOORE, T.: The Bitcoin brain drain: A short paper on the use and abuse of Bitcoin brain wallets, Financial Cryptography and Data Security, Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 2016.10.1007/978-3-662-54970-4_36
Search in Google Scholar Back to article

Speed Optimizations in Bitcoin Key Recovery Attacks

Abstract

Paradigm

My account