Bitcoin Basics: How to Hack a Bitcoin Address

bitsanity (25)in #bitcoin • 6 years ago (edited)

Dear hackers, the Bitcoin blockchain is not entirely secure. This article will reveal a simple method to take control of any Bitcoin address so you can take the coins.

Being greedy, let us select a very wealthy target for our efforts. Here is one address currently holding over 66,000 bitcoin:

1EBHA1ckUWzNKN7BMfDwGTx6GKEbADUozX

Each bitcoin is worth roughly $7000 USD at time of writing. That address therefore controls over $460 million. That would make a very nice paycheck.

Finding and exploiting some as-yet-unknown weakness in cryptography might be too difficult. Our method is a brute-force approach. We will try to guess the private key that corresponds to our target's address. Modern computers with gigahertz CPUs and fast memory can make many guesses per second, so we just have to let the attack run for some time.

Once we find the private key we could then sign a transaction with it and transfer the bitcoin to our own account.

Private Keys

We first need to understand what a private key is in computer terms. A bitcoin private key is a series of 256 bits. Here's an example of one private key that I generated and formatted for readability:

10110011 10001100 10111011 11011000 00011011 00101000 11011101 11011110 
11000101 01100001 01100001 00110000 00010111 10000011 10011010 11101110 
10100010 01110101 01101110 01011010 00001001 11000010 11100101 11110000 
10000010 10000101 00010000 00011011 01000001 01000000 10101000 01010010

That is 256 ones and zeroes. There are 8 bits in a byte, therefore a private key is 32 bytes. Random means random in the mathematical sense. If we collected a large number of keys and summed up the number of '1' and '0' bits, the counts would be fairly close to equal.

How many different private keys could exist? We have 256 bits with 2 possible values for each bit ('1' or '0'). The number of unique possibilities is then 2 raised to the power of 256, or 2^256.

Bitcoin Addresses

A Bitcoin Address is derived from a private key using a well-known sequence of operations[1] that a computer can do easily and quickly. For the curious, here is a basic description of the steps:

Take the private key and multiply it by a known constant some people call 'G'. The rules of multiplication are a little different here, as G is really a point (x,y) on an elliptic curve. The result of this multiplication is another point, represented in 65 bytes including a sign byte, 32 bytes for x and 32 bytes for the y. This result of step (1) is a public key. It is easy for the computer to transform a private key to public key, but impossible to go the other way. So one can safely reveal a public key without fear of any other being able to figure out the private key. Public and private keys work together to perform cryptography (encryption and decryption) and digital signing.
Scramble the result of (1) and take the last 32 bytes (256 bits) of the result. The scrambling process is called Secure Hashing Algorithm (SHA). We call it SHA-256 because the output is 256 bits. Scrambling (or "hashing") is similar to the public key transformation in the sense that one can go forward but not backward, can scramble but not unscramble.
Scramble the result of (2) again. Why? Because if a little scrambling is good then more scrambling must be better, right? This step uses a different scrambling algorithm, called RIPEMD-160, because using more algorithms must be better too. The name ends in "160" and the result is 160 bits (20 bytes).
Add a "version" byte to the front of (3) for a total length of 21 bytes. The bits in this byte are 00000000 to indicate this address is for the main/production bitcoin network.
Digital communications often include some extra bits whenever information is stored or transmitted in order to detect errors. Calculate a checksum by scrambling (4) and then scrambling the result again, both times using SHA-256.
Add the first four bytes of the checksum calculated in step (5) to the end of our address from step (4). Now we have 25 bytes.
Take the result of (6) and convert from binary representation to another scheme known as Base58 that uses alphanumerics instead of '1's and '0's.

Designing the Attack

We know that our victim's address is 1EBHA1ckUWzNKN7BMfDwGTx6GKEbADUozX and now we know how it was created. Yet we do not know, nor can we find the private key that created it.

Here is the pseudo-code:

WHILE not done DO
  generate a new, random private key
  convert the private key to bitcoin address

  IF the bitcoin address matches our target's address THEN
    print out the private key
    EXIT - we're rich!
  ENDIF
ENDWHILE

Implementing the Attack

Here is some simple Java code, minus a few lines to measure guesses/second:

import java.security.SecureRandom;
import tbox.*; // see https://github.com/bitsanity/cryptils

public class Guesser
{
  public static final String TARGETADDR = "1EBHA1ckUWzNKN7BMfDwGTx6GKEbADUozX";

  public static void main( String[] args ) throws Exception
  {
    byte[] privateKey = new byte[32];
    BitcoinAddress addr = null;

    while (true)
    {
      new SecureRandom().nextBytes( privateKey ); // overwrites prev value
      addr = new BitcoinAddress( privateKey );

      if (addr.equals(TARGETADDR))
      {
        System.out.println( "FOUND KEY: " + HexString.encode(privateKey) );
        break;
      }
    }
  }
}

Estimating Run-time

It would be good to get an idea of how long this attack is going to take.

I did a test run of my guesser on my recent-ish desktop PC for some minutes and counted the number of guesses my computer generated in that time. My experiment indicates the computer could make 329,287,013,709 guesses (almost 330 billion guesses) in a year.

I expect I will have to make 2^256 / 2, or 2^255 guesses. If I divide the number of guesses to make by the number of guesses I can make in a year, I can determine how many years it will take.

Dusting off the few remaining brain cells that did math once upon a time, I calculate I could find the target's private key in roughly 1.73 x 10^65 years.

It turns out that 2^255 is a really big number. Someone said it is roughly the same as the number of atoms in the Milky Way galaxy. Imagine the task of searching every atom in our galaxy, one at a time.

Quantum computers are on the way and some are saying it could accelerate computing by a factor of 10^6. My quantum computer might then complete the hack in roughly 10^59 years. Maybe I could adjust my code and use many quantum computers at once. Even with a billion quantum computers it would still take 10^50 years to guess the key.

Let us hope the address-holder never moves those coins before the program completes!

The guessing attack may be simple, basic math and some code, but the attack using this approach is certainly not easy. I'm not going to pursue this attack now, but if you do then good luck and happy hacking!