Paper 2016/103

Speed Optimizations in Bitcoin Key Recovery Attacks

Nicolas Courtois, Guangyan Song, and Ryan Castellucci

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 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 have we have cracked, showing that brain wallets are not secure in practice even for quite complex passwords.

Note: updated related work including more recent work in this area. Added a list of students name who helped finding new password in appendix.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
BitcoinElliptic Curve CryptosystemCryptocurrencyBrain wallet
Contact author(s)
g song @ cs ucl ac uk
History
2016-05-07: revised
2016-02-08: received
See all versions
Short URL
https://ia.cr/2016/103
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/103,
      author = {Nicolas Courtois and Guangyan Song and Ryan Castellucci},
      title = {Speed Optimizations in Bitcoin Key Recovery Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2016/103},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/103}},
      url = {https://eprint.iacr.org/2016/103}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.