One of the biggest fears of Bitcoin users is that one day they will wake up and find their virtual currency wallet emptied, signaling that someone, somehow, has managed to uncover the user’s private key. A Bitcoin private key is a secret number that acts as a kind of identifying “ticket,” allowing coins from the corresponding wallet to be spent.
Since 2010, an estimated $500 million worth of Bitcoin has reportedly been stolen with approximately 6.6% percent of all Bitcoin in circulation being in the possession of someone who stole it. With statistics like this, it is natural for Bitcoin users to be concerned about the safety of their private key.
In a talk at HITB 2014 in Malaysia, security researcher and cryptographer, Filippo Valsdora explores how weak signatures lacking randomness values, if found in the Bitcoin blockchain, can be used to uncover the private keys of unsuspecting Bitcoin users. The talk highlighted not only how the glitch in signatures can and has been exploited, but also ways Bitcoin wallet providers can design their services to prevent ECDSA failures in the Bitcoin blockchain, reducing the chances of private key leaks. He also offered a list of Bitcoin wallets which have proven to be the safest, based on their use of safer deterministic ECDSA operations.
How Bitcoin Works: A Primer
To understand how a user’s private key can be uncovered, you must first understand how Bitcoin works and the ways in which the virtual currency is traded amongst users.
To put it as simply as possible, Bitcoin, although used as a virtual payment system, is in reality a kind of secure messaging system. With Bitcoin, the “messages” being sent are actually monetary transactions. The only way a user can send a message or spend the money from a given Bitcoin wallet is to have the private key to the wallet. The private key provides a unique signature that verifies the sender actually owns the account from which the Bitcoin is transferring. These signatures are generated using what is called an elliptical curve based signature scheme known as ECDSA.
So how is a private key created? Pretty simply, actually. It’s just a random number. You can choose any number at all. Once your number is chosen, you are now ready to create a public key. The public key is basically the address you give people in order to send or receive Bitcoin. This is generated by multiplying the user’s private key by a generator point on an elliptical curve. In the case of Bitcoin, the elliptical curve used is known as Secp256k1.
Once you have a private key and public key pair, you now officially have a Bitcoin wallet set up. The public key is used to give to others for sending and receiving money. For anyone who has used PayPal before, distributing a public key to others its similar to giving someone your PayPal address to make a payment.
But how can the person on the other end of the transaction know you are the owner of the Bitcoin wallet? This is where the private key comes in. To make a transaction, first the “message” or transaction to be sent has to be “hashed.” Hashing basically turns the message into a number – kind of like the number on a check you might write. Next, another random number is chosen – known as k – and this is multiplied by that same generator point we used earlier to create the public key. A few more mathematical steps are completed which incorporate the use of your private key (equations found below) and a unique signature for a transaction is created – one that would be impossible to create, without the private key.
When Random Number Generation Ceases To Be Random
This system is brilliantly complex, making Bitcoin a secure. However, if and when a break down occurs in random number generation. If somehow the random number K was used more than once, a duplicate signature would be produced for more than one transaction. Once this happens, anyone with the time and proper tools could scan the Bitcoin blockchain – the public ledger of all bitcoin transactions ever executed -- and find duplicate signatures, leading to the decoding of a user’s private key.
This kind of attack was used in August 2013 by a hacker dubbed as “Gomez” who succeeded in stealing approximately 59 Bitcoin from users who were the victims of a random signature generation fail. Failing to generate a random signature has lead to significant security breaches, not only of Bitcoin wallets but across other platforms as well. For example, in December 2010, a group calling fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random k for each signature. Gaining access to Sony’s private key, the hacking group was able to break the encryption of Sony PS3 and jailbreak the device.
So how does this glitch in random number generation even happen and what can be done to prevent it? According to Valsorda the glitch can happen when using a random number generator. If you are using a good random number generator in a good environment the likelihood that it will produce a repeated number is almost nil, but in the case that you are using a badly programmed random number generator or using it within an environment without enough entropy, then the risk of generating a duplicate signature increases.
As a solution, Valsorda calls for Bitcoin wallet providers then to make a change from random number generation to generation of the K value deterministically. In reality, all K needs to be is secret and unique each time. Therefore, Valsorda advocates using the specifications outlined in RFC 6979, which calls for the deterministic generation of K values.
For Valsorda the switch to deterministically generated K values is critical, as he’s dubbed it “good cryptography for the real world”. In the closing of his HITB talk, Valsorda issued this call to action for developers of all kinds.
“Programmers will screw up, users will screw up, environments will be terrible,” said Valsorda. “You will find your code running in some environment you didn’t expect. But, if you can make design decisions that make using your software safer … why not do it? Protect the next programmer, protect the next user. If you can make cryptography that’s safer, that won’t blow up in your face as soon as you touch it, do it … there is no reason not to do it … let’s reduce the attack surface, let’s make safer cryptography.”
What Is The Best Bitcoin Wallet?
For those interested in knowing which Bitcoin wallets are currently using the safer deterministic model of signature generation, Valsorda has cited these providers:
Electrun
MultiBit/BitcoinJ
Bitrated/BitcoinJS-Lib
Meanwhile, Bitcoin wallet providers such as Bitcoin Core, Blockchain.info and Armory were cited less safe choices. Though the probability that a user’s Bitcoin wallet will be compromised due to duplicate signature generation is incredibly small – less than 1% probability – still, developers of these systems should seek to protect even that .001% of users that may be victimized in this way.
To see the slides from Filippo Valsorda’s presentation, visit HITBSecConf2014.
