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!

17 comments:

  1. Had luck with this before.. Maybe there are some nuggets of wisdom in it:

    #!/usr/bin/perl
    $_ = `cat CORRUPT_wallet.dat`;
    while (/keyA(.{65})/sg) { $k{$1}++ }
    for my $k (keys(%k)) {
    while (/(\xfd.{216}\Q$k\E)/sg) {
    print("PUBKEYHEX=", unpack("H*", $k), "\n");
    print("KEYPAIRHEX=", unpack("H*", $1), "\n\n");
    }
    }

    ReplyDelete
  2. Would this work for a namecoin wallet?

    ReplyDelete
  3. What then was your total treasure recovery?

    ReplyDelete
  4. Hi ! I had some success using photorec: http://blog.cyplo.net/2012/04/01/bitcoin-wallet-recovery-photorec/ However, as pointed out in the comments there might a problem of sifting through false positives if the drive is large. Will try your tool and recommend for my commenters to try it out also definitely !

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. I made an image using dd for windows (http://aeroquartet.com/movierepair/dd%20for%20windows). Scanned the resulting image file using keyhunter.py and found nothing. Atleast I got no message returned and the scan of the 147gig file was fairly fast. I know there's atleast one wallet.dat file on the drive. I was trying to find an older wallet file that might have had coins in it. Anyways, I got no results. Not sure if its a windows related issue or if I am doing something wrong. Any tips?

    ReplyDelete
    Replies
    1. Hey Raja, did you ever figure this out? Was this a regular bitcoin-qt wallet? Do you have any idea what version of the client made the wallet? Do you know if it was encrypted? I don't think my tool will find encrypted wallets at the moment.

      Delete
    2. My wallet was made from a client earlier than 0.3.2 I think and was unencrypted. I installed in the really early days and still don't understand how the wallet file got overwritten/lost. Anyways, keyhunter didn't work on windows at all. I switched to Linux and got keyhunter to work but didn't find any lost keys. :(

      Delete
  7. Will this work with Android based wallets?

    ReplyDelete
  8. Over the past few months I have watched stores that accept Bitcoin value rise exponentially. I had no idea what where to spend bitcoin was and never even heard of crypto currency a few months ago

    ReplyDelete
  9. What ever the interests, end up being these people Bitcoin inexperienced or perhaps investment possibilities, locate facts in addition to media concerning current business styles when they relate with Trade bitcoin online

    ReplyDelete
  10. This is very unique services that exkash is offering in the world ever. I am sure that you will enjoy about to hair that. Now suppose that you have money into your wallet and you want to change into real cash.
    Bitcoin to Bank, Bitcoin, Bitcoin to Bank wire

    ReplyDelete
  11. hi buddy. i keep getting no permition when i try your code on c:/ any ideas? thanks alot

    ReplyDelete
  12. Hi buddy could you help this newbie out ? i am trying to recover my PrivateKeys. i have downloaded keyhunter but i dont know what to do next. PLEASE HELP ME OUT. SOME HELP WOULD ME REALLY APPRECIATED BOSS.

    ReplyDelete
  13. if anyone needs help with their lost keys and wallets. send me a note. In most cases I can extract your keys. I charge 20% of value for service.

    ReplyDelete
  14. Wow, this article is really very good, so that I can't say how happy feeling. The article make every detail of the story depicts streaming with the best, and every movement of the characters all write so lifelike, let me see the waves excited. bitcoin hosting

    ReplyDelete