Note: You are viewing this blog post without the intended style information, which may result in formatting issues.

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:

0000...........................00001
0000..........................000011
0000.........................0000111
0000........................00001000
0000.......................000010101
0000......................0000110001
0000.....................00001001100
0000....................000011100000
0000...................0000111010011
0000..................00001000000010
0000.................000010010000011
0000................0000101001111011
0000...............00001010001100000
0000..............000010100100110000
0000.............0000110100011110011
0000............00001100100100110110
0000...........000010111011001001111
0000..........0000110000100000001101
0000.........00001010111010010011111
0000........000011010010110001010101
0000.......0000110111010010100110100
0000......00001011011110010000001111
0000.....000010101010110111001010010
0000....0000110111000010101000000100

The nth output is worth n mBTC, and its private key (in binary) is 0s up to the nth 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 37th 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.

Output(s) Time of Spend
001-020 2015-01-15 18:07:14
021,023 2015-01-15 18:54:21
022,024-028 2015-01-15 22:00:37
029 2015-01-16 02:38:53
030 2015-01-16 12:55:06
031 2015-01-16 07:53:02
032 2015-01-16 04:54:21
033 2015-01-16 16:20:40
034 2015-01-17 00:12:12
035 2015-01-17 07:19:05
036 2015-01-17 16:50:00
037 2015-01-18 23:27:23
038 2015-01-19 10:25:58
039 2015-01-21 06:20:01
040-045 2015-01-30 18:21:52
046 2015-01-30 20:28:57
047-050 2015-09-01 20:20:24

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(2xfor x = 0 to n − 2 guesses to crack the first n keys, which is approximately equal to 2n − 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.