Count Upon Security

The blockchain is the underlying technology that enables the bitcoin cryptocurrency to exist. A foundational component of this technology is its complex cryptosystem. The blockchain cryptosystem relies on public key algorithms based on Elliptic Curve and message digest functions like SHA-256 and RIPEMD-160. When you create a bitcoin wallet, under the hood you are creating an Elliptic Curve key pair based on Secp256k1 curves. The key pair has a private key and a public key. The private key is the one you keep secret and allows you to sign transactions. For example, when you send bitcoins to someone, you are signing this transaction with your private key and then you announce it to the network. The miners will pick up your transaction and verify that the transaction signature is valid and broadcast to the network until enough miners have validated the transaction and thus achieving consensus. The checks and balances of the Blockchain ledger are updated and when consensus is achieved, your transaction is written in “digital stone”.

On the other hand, the public key is the one used to create your bitcoin wallet address. The public key allows you to receive bitcoins. However, your bitcoin wallet address is not your raw Elliptic Curve public key There are additional steps performed in order to create an address. First, a digital representation of your public key is computed using SHA-256 followed by RIPEMD-160. Second, a byte with network id is prepended to this string. Third, a checksum of this string is computed by performing SHA-256 twice. From these results the first 4 bytes are appended to the string produced in second step. This string is encoded in Base58 and this is your bitcoin wallet address. The picture below illustrates this steps in a non-automated way.

There are many forms to store your bitcoins as well as to create wallets. One of the early methods to create bitcoin wallets was known as brain wallets. Unfortunately, this user-friendly method allowed you to enter a password or passphrase which was then hashed using an algorithm such as SHA-256 and used as seed to generate your private key. Due to its popularity and easy usage, many Brain wallets were used in the last few years with weak passwords or passphrases, transforming the Blockchain wallet address hashes in password or passphrases representation of your private key. This weak way of generating your private key allowed attackers to steal your bitcoins just by doing password cracking against the hashes stored in the Blockchain.

Although, this attack has been known for years,  it only got widely known recently due to the work made by Ryan Castellucci. Ryan’s released on 7th August 2015 at DEFCON 23 the results of his work cracking brain wallets in conjunction with a tool called BrainFlayer : A proof-of-concept cracker for cryptocurrency brain wallets and other low entropy key algorithms. You can view Ryan’s talk here.  Two months after Ryans’ initial release of BrainFlayer, he released a faster version. This was the result of the work done by Nicolas Courtois, Guangyang Song from
International Association for Cryptologic Research (IACR), University College London, and Ryan’s to optimize the speed of computing secp256k1 bitcoin elliptic curve. This has been detailed in the paper Speed Optimizations in Bitcoin Key Recovery Attacks.  Furthermore, this year at the Financial Cryptography and Data Security conference, Marie Vasek presented another article The Bitcoin Brain Dain: A Short Paper on the Use and Abuse of Bitcoin Brain Wallets. This paper published the results of evaluating 300 billion passwords against Blockchain hashes and their findings about 884 brain wallets that had funds at a given time, suggesting they might have been drained by active attackers.

So, how do you perform such attack?

The attempt to recover a password just by knowing its encrypted representation can be made mainly using three techniques. Dictionary attacks, which is the fastest method and consists of comparing the dictionary word with the password hash. Another method is the brute force attack, which is the most powerful one but the time it takes to recover the password might render the attack unfeasible. This is of course dependable on the complexity of the password and the chosen algorithm. Finally, there is the hybrid technique which consists of combining words in a dictionary with word mangling rules.

With that being said let’s go over the steps needed to perform this attack against the Blockchain hash160 hashes using a dictionary. This is done in 6 steps:

• Bootstrap the Blockchain.
• Parse the Blockchain by running Blockparser and get allBalances.
• Extract hash160 strings.
• Create a Bloomfilter.
• Run BrainFlayer with your favorite dictionary.
• Use Addressgen to generate key pair.

First step is to bootstrap the blockchain. To perform this, we need to download, install and run the bitcoin software on a system connected to the Internet. The system then becomes a node and part of the peer-to-peer blockchain network. The first task performed by the node is to download the entire database of records i.e., the public transaction ledger and verify it using the transaction engine. In other words, the node downloads the entire blockchain and verifies the validity of all blocks by performing a series of checks   This needs a lot of bandwidth and computing power. As I write this the Blockchain size is 90.633 Gb and contains 438556 blocks. The data contains every transaction that has been made in the blockchain since the genesis block was created on the 3rd of January 2009 at 18:15:05 GMT. To download the entire Blockchain, took me more than 72 hours . The image below illustrates the steps needed to perform the download, installation and running the bitcoin software.

Then, the picture below illustrates the steps needed to perform the configuration and running the bitcoin software. You can view the progress by executing the getblockchaininfo command and check the number of blocks that have been already downloaded.

After downloading the entire Blockchain we move into the second step. Parse the Blockchain.  The tool to perform this heavy lifting exercise is called Blockparser and is a powerful utility, open source, written in C++ that was created by Znort987. The tool doesn’t seem to be maintained anymore but is still able to perform its work. When blockparser performs the parsing, it creates and keeps the index in RAM which means with the current size of the blockchain you need enough RAM to be able to parse it in reasonable amount of time. The tool can perform various task but for this exercise we are interested in the allBalances command. To perform the parsing, I used a system with 64 GB ram and the process was smooth. I tried it on a system with 32Gb and stopped it due to the heavy swapping that was happening. The allBalances produced a 30Gb text file. The image below exemplifies these steps.

Third step is to extract the hash160 addresses from the allBalances. We are interested in the hash160 because this field contains the representation of the Bitcoin public key. Below you can see the output of allBalances.

Forth step, we create a bloom filter with the tool hex2blf which is part of the brainflayer toolkit. We also need to create a binary file containing all the hashes sorted in order to be used with the bloom filter. This will reduce the false positives.

Fifth step, we launch brainflayer using our favorite dictionary against the bloom filter file we generated in the previous step. If there is a match you will see the password or passphrase and the corresponding hash. In the output of cracked password you could see C or U in the second column. This is to indicate if the key is Compressed or Uncompressed. In the below image you can see these steps.

Sixth step and last step is to create the Elyptic Curve key pair using the known password or passphrase. This can be done using the tool Addressgen created by sarchar. Addressgen is a utility written in Python 3 to generate private keys and their corresponding addresses using secp256k1. This utility will allow you to generate the ECDSA key pair which can be used to take over the wallet.

Financial gain is a significant incentive to have people performing all kinds of activities in order to attempt to steal your coins. If you are interested in attacks against the Blockchain I would suggest looking at the different papers created by the professor Dr. Nicolas Courtois and available on his website. On a different note, there are other researchers that are brute forcing the entire bitcoin private key keyspace in order to find private keys for addresses that have funds. There is one project that has the code name Large Bitcoin Collider which is a distributed effort with a pool where people can contribute computing power. The thread on Bitcointalk forum is quite interesting and the author has the following aim for this project: “allow the Bitcoin community to actually have a better shot at risk assessment of this threat vector. Right now, the math says the danger is negligible. Should there at some point be evidence or indication of the contrary, then it’s still better to have a project like this for analysis/experimentation of this concrete attack vector”. The author also writes that the project is a derivative of brainflayer and supervanitygen. Moreover, brainflayer can also perform brute force attack, sequentially against the entire private key space. This would be unfeasible to perform in a reasonable time frame but better to view the talk “Stealoing Bitcoin with Math – HOPE XI” given by Fillippo Valsorda and Ryan’s where among other things they show how quick brain wallets get drained, attacks against newer Brainwallet implementations and other attacks against Eliptic Curve Digital Signature Algorithm (ECDSA).

References:
Mastering Bitcoin – Unlocking Digital Cryptocurrencies by Andreas M. Antonopoulos