#! /usr/bin/perl

# findkeys.pl Copyright (C) 2011 John Tobey, <John.Tobey@gmail.com>

#   THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY
# APPLICABLE LAW.  EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT
# HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY
# OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
# PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM
# IS WITH YOU.  SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF
# ALL NECESSARY SERVICING, REPAIR OR CORRECTION.

#   IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
# WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MODIFIES AND/OR CONVEYS
# THE PROGRAM, BE LIABLE TO YOU FOR DAMAGES, INCLUDING ANY
# GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
# USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF
# DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD
# PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),
# EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGES.

# This script searches for Bitcoin private keys in a disk partition
# containing a deleted wallet file.  You would do this after failing
# to recover the bitcoins from backups, filesystem recovery tools, and
# Berkeley DB recovery tools, if applicable.

# This program is not easy to use.  I don't personally need it, I
# wrote it as an experiment for someone who lost their wallet.

# These instructions assume you are running Linux and know the partition you
# want to search (example: /dev/sda2).  If you want to search a file instead
# of a partition, replace "sudo dd if=/dev/sda2" with "cat FILENAME" below.

# This script reads a file named pubkeys.dat containing possible public keys.
# To create pubkeys.dat prior to running this script, use a command like the
# following, with the partition name in place of "/dev/sda2":

# sudo dd if=/dev/sda2 |perl -e '$| = 1; $bufsize=4096; while(read(STDIN,$_,$bufsize,70)) { print $1 while /\03keyA(.{65})/sg; $_=substr($_,$bufsize); }' > pubkeys.dat

# Searching for many possible keys takes a long time.  findkeys.pl
# allows searching for only a range of the possible keys in
# pubkeys.dat.  Experiment to find the right number to search in one
# run.  You can interrupt a run (hit Ctrl-C) and restart it with
# different arguments if it is too slow.

# The script puts the most "interesting" possible keys first in the
# sequence.

# Run findkeys.pl with no arguments to show the number of keys in pubkeys.dat.
# To search partition /dev/sda2 for the first 10 keys:
# sudo dd if=/dev/sda2 | ./findkeys.pl 10 >> keys.txt
# To search for the next 20 keys:
# sudo dd if=/dev/sda2 | ./findkeys.pl 20 10 >> keys.txt

# If the output file (keys.txt) is not empty, it may contain private keys in
# hexadecimal format.

use strict;
use warnings;
$| = 1;

my $count = shift;
my $start = shift || 0;
my $pubkeys_file = "pubkeys.dat";
my (%seen, @interesting, @boring, @pubkeys);
my $bufsize_MB = 10;

open(PKD, "<", $pubkeys_file) || die("$pubkeys_file: $!");
while (read(PKD, my $pubkey, 65)) {
    next if $seen{$pubkey}++;
    if ($pubkey =~ /\A\x04/) {  # Bitcoin pubkeys tend to start with hex 04.
        push(@interesting, $pubkey);
    }
    else {
        push(@boring, $pubkey);
    }
}
@pubkeys = (@interesting, @boring);

if (!defined($count)) {
    if (scalar(@pubkeys) == 0) {
        print STDERR "No keys found in $pubkeys_file, sorry.\n";
        exit 1;
    }
    print STDERR "Keys to search for: " . scalar(@pubkeys) . "\n";
    print STDERR "Interesting keys: " . scalar(@interesting) . "\n";
    print STDERR "Run $0 COUNT to look for COUNT keys.\n";
    print STDERR "Run $0 COUNT START to skip the first START keys.\n";
    exit;
}

my @patterns;
for my $pubkey (@pubkeys[$start .. ($start + $count - 1)]) {
    push(@patterns, quotemeta($pubkey));
}
my $searcher = eval("sub { /(.{217}(" . join("|", @patterns) . "))/sg }");
my $bufsize = $bufsize_MB * 1024 * 1024;
my $MB_read = 0;
while(read(STDIN, $_, $bufsize, 288)) {
    for my $found (&$searcher()) {
        my $output = unpack("H*", $found);
        print "$output\n";
        if ($output =~ /^fd/ && $output !~ /036b657941/) {
            print STDERR "\rProbable key: $output\n";
        }
    }
    last if length($_) <= $bufsize;
    $_ = substr($_, $bufsize);
    $MB_read += $bufsize_MB;
    print STDERR "\r$MB_read MB scanned. ";
}