Tuesday, December 17, 2013

Bitcoin Private Key Necromancy

tl;dr: https://github.com/pierce403/keyhunter

~ The Longer Version ~

A few weeks ago, a friend came to me with a problem.  Way back in 2011, he had the great idea to reinstall Windows.  Without thinking too much about it, he installed the new version of Windows, and used the drive for a while.  It was only later that he realized that the drive actually contained a good quantity if bitcoins.  Luckily, he realized there was a chance that the actual data containing the keys may one day be recoverable, and immediately unplugged it and stored it away for safe keeping.

With the price approaching 1000 USD/BTC, he brought the drive to a local bitcoin meetup and asked around.  One guy ran various profession forensics tools against the drive with no luck, and at the end of the night, the drive ended up in my hands.

Discussions of forensic hygiene out out of scope for this particular blog entry, but needless to say, my first step was using dd to pull the raw data off the drive, giving me a 160 gig file on my local filesystem to work with.

Idea #1 BerkeleyDB recovery
So, of course, the original though was "find and pull out the wallet.dat".  My tool of choice for this sort of thing is magicrescue (http://www.itu.dk/people/jobr/magicrescue/).  Magic rescue is typically used to recover images and documents from large blobs of data, for example, damaged filesystems.  Unfortunately for me, there was no BerkeleyDB "recipe file", which is what magicrescue uses to reconstruct files.  With a bit of poking around, I figured out how to write my own custom recipe files, and I was on my way.  Using a hex editor, I checked out the first 16 bytes or so of a normal wallet.dat, and confirmed that it was the same across multiple wallet.dat files that I had lying around.  I ran the magicrescue scan, and came up with no hits.

I read up some more on the format of BerkeleyDB files, kept tweaking my recipie files to support more and more versions of BerekelyDB, and nothing.

Idea #2 Find *Something*
At this point, I started digging around in the middle of my wallet.day files for anything that might be somewhat unique.  The first few things I tried were coming up negative, and then I noticed the string name"1, which was immediately followed by a bitcoin address in the various wallet.dat files I had.  I built the recipe, ran the scan, and got a single hit.  I looked into the output file, and there it was, a bitcoin address.  I looked the address up in blockexplorer, and there it was.  An address with the exact number of coins my friend had guessed was on the drive, and no transactions since 2011.

!!YAY!!

My next thought was that I needed to carve the wallet.dat file out of this chunk of data I had found.  After a bit of futzing around, I noticed that almost directly above the address was a header for a .NET Assembly.  This meant one thing: fragmentation, which was bad news for me. 

Idea #3 Raw Key Extraction
Okay, it was time to finally figure out how to extract the keys directly.  I found various tools for printing out private keys, but everything was outputting this strange 400 byte format, which didn't seem right.  I read up a bit more about how private keys work in bitcoin, and read a ton of code and specs figuring out how they were supposed to be encoded, and "Wallet Import Format".  That let me to this nifty webapp http://gobittest.appspot.com/PrivateKey.

My big break came last night when I realized I could export one of my own empty private keys, and get the raw 32 byte hex from the website.  Once I knew that, I could dig around in the wallet.dat file.  I noticed that there were some interesting bytes that preceded the private key, and noticed that this preceding magic number was in front of all of the private keys in the wallet.  I quickly whipped up a magicrescue recipe, and before I knew it, I had 400 hits.  I wrote up some code to go through the files, translate the 32 byte data into base58 WIF keys, and threw them into a shellscript that ran "bitcoind importprivkey ...", and imported them into a local wallet that I had.  When that was done, I ran "bitcoind getbalance" and there they were :-D  I quickly moved the coins to a safer place, and let my friend know the good news.

The birth of KeyHunter
I figure not everyone wants to dink around with magicrescue, so I wrote up a tool called keyhunter to automatically rip through a large chunks of data, and spit out the base58 Import Address.  The code is here:

https://github.com/pierce403/keyhunter

If it helps you find any of your lost and forgotten coins, I've set up a donation address here:

1YAyBtCwvZqNF9umZTUmfQ6vvLQRTG9qG

Good luck!