Forensic Bitcoin Cracking: As Easy as 1, 3, 7...

Since its release at DEFCON 23, I’ve done quite a bit of work on brainflayer. First, I added support for a few other brainwallet-like schemes and hex-encoded private keys. Then, in October, I integrated some code provided by Dr. Nicolas T. Courtois and Guangyan Song from UCL that sped up brainflayer by about 150%. With a subsequent optimization that yielded a further 65% speedup, it is now over four times faster than the initial release.

In January, I added specialized code for brute force private key search. While trying it out, I found something very interesting.

As brainflayer ran, it found many addresses associated with this transaction. I noticed almost immediately that the private keys increased with each output, but it wasn’t until I displayed them in binary that I saw the actual pattern:

The n^th output is worth n mBTC, and its private key (in binary) is 0s up to the n^th bit from the right, which is a 1, then the remainder is filled with what seem to be random bits. I’m only listing the first 24 here, but it holds at least through the 37^th output.

This appears to be deliberate - perhaps an experiment to see how long it will be before the outputs are taken. I’d love to hear from whoever made it. At the time of writing, of the 256 outputs, only the first 50 have been spent - 1.275 of 32.896 BTC. The first twenty were gone pretty much instantly, all to different addresses. I’m guessing a bot was monitoring the network.

What I find really interesting about this is the timing of when some of the later outputs were taken.

It’s not clear when these attackers noticed this transaction and started cracking, but the times the outputs were spent can be used to estimate lower bounds of their capabilities.

If an attacker stops making guesses on each output once they find the key, on average they’ll make sum(2^x) for x = 0 to n − 2 guesses to crack the first n keys, which is approximately equal to 2^n − 1.

For output 46 (which was spent to the same address as outputs 40 through 45), that’s a search space of about 35 trillion keys in about 1.3 million seconds. That works out to about 27 million guesses per second. With output 50, it’s around 563 trillion keys and 20 million seconds which is just over 28 million guesses per second. For comparison, on my computer, brainflayer can currently do about 1.5 million guesses per second in incremental search mode.

This must have either been done on a bunch of computers, or with a GPU cracker. If I were going to do this, I’d probably hack up vanitygen since it already has GPU support and would do the job with minimal modifications. It wouldn’t be much more complicated to add bloom filter code for searching all addresses.

Fortunately, even at a trillion times those cracking speeds, it’d take longer than the age of the universe to have even a 1% chance of finding a key for any randomly generated address ever used, so there is no cause for concern. Not to be deterred by statistics, some folks on bitcointalk are running a distributed computing project to try anyway.