Hacking Dormant Bitcoin Wallets in C

3 months ago 2

LeetArxiv is Leetcode for implementing Arxiv and other research papers.

This is Chapter 2 in our upcoming book: A Programmer’s Guide to Hacking Satoshi’s Billion Dollar Wallet.

Available Chapters

Chapter 1 : A Friendly Introduction to Elliptic Curves.
Chapter 2 (we are here) : Hacking Dormant Bitcoin Wallets in C and Elliptic Curves.
Chapter 3 : Can we Find the Edwards Form of the Bitcoin Curve.
Chapter 4 : What Every Programmer Needs To Know About Conic Sections (To Attack Bitcoin)
Chapter 5 : The Discrete Logarithm Problem and the Index Calculus Solution
Chapter 6 : Finding the Montgomery Form of the Bitcoin Curve.
Chapter 7 : The US Government Hid a Mathematical Backdoor in another Elliptic Curve

This chapter demonstrates how to gain access to a bitcoin wallet.

Here are the chapter’s main takeaways:

Not Your Keys Not Your Wallet:
- Knowing a private key lets you takeover a bitcoin wallet.
Private keys are used to generate bitcoin addresses:
- One can test knowledge of a private key by generating a wallet address.
- A private key generates a public key. The public key is hashed by SHA256 + RIPEMD. These are the summarized steps:
  - Private key →Public Key → SHA-256 → RIPEMD-160 → Base58Check = Bitcoin Address
Official Bitcoin libraries are written in C.
- This is a C programming guide since the official bitcoin libraries are written in the C language.

This section is a step-by-step guide to coding a wallet breaker. It is split into these parts:

Setting up a C coding environment on Linux.
Writing the logic for a wallet breaker.
The underlying elliptic curve theory needed to generate a public key from a private key.

If you’re in a hurry then grab a copy of this section’s code here.

This is a C coding tutorial for Linux users. This section demonstrates how to install the official Secp256k1 library and where to get public keys and addresses.

We use the secp256k1 library written by the official bitcoin-core team.

Step 1: Clone the library from GitHub:
git clone https://github.com/bitcoin-core/secp256k1.git
Step 2: Open the directory:
cd secp256k1
Step 3: Use Autotools to build the library:
./autogen.sh # Generate a ./configure script ./configure # Generate a build system make # Run the actual build process make check # Run the test suite sudo make install # Install the library into the system (optional)
Step 4: Do NOT close your terminal window. You need to add the library path to your bashrc. First export the path:
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
Step 5: Then add the path permanently. Close all terminal windows after this step.
echo 'export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH' >> ~/.bashrc source ~/.bashrc

We need OpenSSL for SHA256 and RIPEMD. This library tends to come preinstalled on Linux. Here’s the GitHub repo with installation instructions.

Our primary testing data source is the Bitcoin puzzles. This is a set of private keys we are encouraged to bruteforce, or rather, “a crude measuring instrument of the cracking strength of the community.” (Saatoshi_Rising, 2017)

A list of known private keys and wallet addresses is available on BitcoinTalk

Create a folder called MiningPOC and a file named PrivateKey.c.

Add this code to your file:

#include <stdio.h> #include <stdint.h> #include <string.h> #include <assert.h> #include <secp256k1.h> #include <openssl/sha.h> #include <openssl/ripemd.h> //Run: clear && gcc PrivateKey.c -lsecp256k1 -lcrypto -o m.o && ./m.o int main() { char *walletAddress = "1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH"; printf("%s\n", walletAddress); }

Compile the code using this command:

clear && gcc PrivateKey.c -lsecp256k1 -lcrypto -o m.o && ./m.o

Your terminal window should output the annotated string:

This section demonstrates a bruteforce attack on the Bitcoin Puzzle wallets. We illustrate how to convert a private key into a bitcoin wallet address in C.

Owning a bitcoin is equivalent to knowing a wallet’s private key.

Here’s a summary of the logic needed to convert a private key into a bitcoin wallet address:

The Bitcoin Puzzles demand one find a private key that generates a known bitcoin address.

The challenge is structured such that we know where to look for the keys. The upper bound is the maximum possible value of a puzzle solution.

Each private key in the bitcoin puzzle is a 32 bit integer ranging between 0 and the upper bound inclusive. Thus, most of the private keys in the challenge tend to start with lots of zeros.

We shall work with Puzzle #3 for the remainder of this section:

We need to initialize the secp library, set our variables and destroy the secp context. At this point, your main function should resemble this:

int main() { //Initialize secpContext secp256k1_context *secpContext = secp256k1_context_create(SECP256K1_CONTEXT_SIGN); //Set upper bound and target wallet address uint32_t upperBound = 7; char *walletAddress = "19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA"; printf("%s\n", walletAddress); //Destroy secpContext secp256k1_context_destroy(secpContext); }

This is a coding section. Feel free to compare your code with mine here.

First, we write a function to print strings in hexadecimal:

void PrintHexadecimalString(size_t stringLength, uint8_t *string) { for(size_t i = 0; i < stringLength; i++) { printf("%02X", string[i]); } printf("\n"); }

Next, we write a for loop to generate private keys between 0 and our upper bound.

We also use secp256k1_ec_seckey_verify function to validate our private (secret) key. It returns 0 if the private key is invalid:

*0 is an invalid key

//Test different private keys for(uint8_t privateKey = 1; privateKey <= upperBound; privateKey++) { uint8_t privateKeyString[32] = {0}; privateKeyString[31] = privateKey; assert(secp256k1_ec_seckey_verify(secpContext, privateKeyString) != 0); PrintHexadecimalString(32, privateKeyString); }

Your main function and terminal output should resemble this:

This section splits the inner workings of a private key to wallet address function into:

Generating a public key from a private key.
- We use the secp256k1_ec_pubkey_create to generate a public key.
  - It returns 0 upon failure.
- We use the secp256k1_ec_pubkey_serialize to compress a public key into a 33-byte string.
- Your for loop should resemble this:
  //Test different private keys for(uint8_t privateKey = 1; privateKey <= upperBound; privateKey++) { uint8_t privateKeyString[32] = {0}; privateKeyString[31] = privateKey; assert(secp256k1_ec_seckey_verify(secpContext, privateKeyString) != 0); printf("\nPrivate Key:\n");PrintHexadecimalString(32, privateKeyString); //Generate public key secp256k1_pubkey publicKey; size_t publicKeyLength = 33; uint8_t publicKeyString[33]; assert(secp256k1_ec_pubkey_create(secpContext, &publicKey, privateKeyString) != 0); secp256k1_ec_pubkey_serialize(secpContext, publicKeyString, &publicKeyLength, &publicKey, SECP256K1_EC_COMPRESSED); printf("Public Key:\n");PrintHexadecimalString(33, publicKeyString); }
- This is the expected output:
  Private key and corresponding public keys
Writing a wrapper function to convert a public key into a wallet address.
- We write a function called PublicKeyToBitcoinWalletAddress. It takes as input a compressed public key: publicKeyString and a string to hold the generated bitcoin address: generatedAddress.
- We assume publicKeyString is 33 bytes and generatedAddress is 64 bytes:
  //Assumes publicKeyString is 33 bytes //Assumes generatedAddress is 64 bytes void PublicKeyToBitcoinWalletAddress(uint8_t *publicKeyString, char *generatedAddress) { }
- The function is called inside the main for loop:
  //Generate wallet address char generatedAddress[64]; PublicKeyToBitcoinWalletAddress(publicKeyString, generatedAddress);
Finding the SHA256 hash of the public key.
- We use OpenSSL’s SHA256:
  uint8_t sha256Hash[32]; SHA256(publicKeyString, 33, sha256Hash);
Finding the RipeMD160 hash of the SHA256 hash.
- We use OpenSSL’s RIPEMD160:
  uint8_t ripemd160Hash[20]; RIPEMD160(sha256Hash, 32, ripemd160Hash);
Setting the version payload.
- This is the mainnet’s version byte and it is 21 bytes:
  uint8_t versionedPayload[21]; versionedPayload[0] = 0x00; // version byte for mainnet memcpy(versionedPayload + 1, ripemd160Hash, 20);
Finding a SHA256 checksum of the payload.
- We double SHA256 hash the payload:
  uint8_t checksumInput[25]; memcpy(checksumInput, versionedPayload, 21); uint8_t hash1[32], hash2[32]; SHA256(checksumInput, 21, hash1); SHA256(hash1, 32, hash2); memcpy(checksumInput + 21, hash2, 4);
Encode all the hashes in Base58.
- We call the function like this:
  EncodeInBase58(25, checksumInput, 64, generatedAddress);
- Then we write it:
const char *BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"; void EncodeInBase58(size_t inputLength, uint8_t *input, size_t outputLength, char *output) { uint8_t temp[32] = {0};memcpy(temp, input, inputLength); uint8_t result[64] = {0};int resultLength = 0; for(size_t i = 0; i < inputLength; i++) { int carry = temp[i]; for(int j = 0; j < resultLength || carry; j++) { if(j == resultLength) resultLength++; carry += 256 * result[j]; result[j] = carry % 58; carry /= 58; } } int leading_zeros = 0; for(size_t i = 0; i < inputLength && input[i] == 0; i++) {output[leading_zeros++] = '1';} for(int i = resultLength - 1; i >= 0; i--) {output[leading_zeros++] = BASE58_ALPHABET[result[i]];} output[leading_zeros] = '\0'; }
Your final PublicKeyToBitcoinWalletAddress function should resemble this:
Complete PublicKeyToBitcoinWalletAddress function
We add a comparison function at the bottom of our for loop:
//Generate wallet address char generatedAddress[64]; PublicKeyToBitcoinWalletAddress(publicKeyString, generatedAddress); printf("Generated Address:%s\n",generatedAddress); if(strcmp(generatedAddress, walletAddress) == 0) { printf("**MATCH FOUND: Private Key = %u\n", privateKey); break; }