A critical security vulnerability has been found in Android which renders bitcoins stored in Android Bitcoin wallets vulnerable to theft, and the exploit is currently being used in the wild to steal people’s bitcoins. Several people have reported that their Android wallets were cleared out and the funds sent to 1HKywxiL4JziqXrzLKhmB6a74ma6kxbSDj, an address which currently contains 55.8 BTC. Because the bug is a flaw in Android itself, all Android Bitcoin wallets are vulnerable; Bitcoin Wallet for Android, Bitcoin Spinner, the mobile version of blockchain.info and Mycelium Wallet are all on the list. Users are encouraged to send all of their funds to a desktop or online wallet and wait until their favorite mobile wallet comes out with an upgrade to fix the problem. Bitcoin Wallet for Android already did; Bitcoin Wallet for Android users need only download the latest version from the play store and the wallet will move insecure funds to a new secure address automatically.
The source of the bug is the java.security.SecureRandom method in Android, which, as developer Andreas Schildbach describes it “has multiple severe bugs that render it useless for cryptographic purposes.” The problem is this: the elliptic curve digital signature algorithm, which Bitcoin transactions rely on for security, has three inputs: the transaction, the signer’s private key and a random number. The algorithm then outputs two values, denoted r and s, where s is calculated with the formula k-1(z+rd), z being the hash of the message, k the random number and d the private key. r is dependent only on k. Thus, if the owner of an address signs two transactions with the same random number (and of course the same private key, as every address is linked to one private key), one can extract two s values from the two signatures, subtract them to make the rd terms cancel out, and extracting the private key from there becomes a simple division problem (a more detailed writeup can be found here). Normally, this is not a problem; given a true random number generator, the first “collision” should take place roughly at the same time as the heat death of the universe. As it turned out, however, java.security.SecureRandom proved to be not so random, generating the same “random” number twice on many occasions.
It is because of the possibility of clever attacks like this that Bitcoin developers recommend a simple strategy: never re-using the same address twice. Whenever money is sent from a Bitcoin address, the wallet should empty out the entire contents of that address, send as much as needed to the intended recipient, and send the rest of the funds to other, previously unused addresses, controlled by the wallet. Not doing this does not mean that your funds are insecure; the exploit here relies on the weakness of Java’s random number generator, and given a proper random number generator (eg. os.urandom) elliptic curve DSA remains as strong as ever. However, if the implementation turns out to be somewhat flawed it does leave you vulnerable, and even in normal cases address re-use weakens Bitcoin’s privacy. If some mad scientist in an underground cave suddenly appears with a fully-functional quantum computer, only addresses that have never been spent from will be safe. The reason is that if you have bitcoins in an address that you never sent any transactions from, there is very little information that attackers have to figure out your private key; in fact, the 34-character string is all an attacker has to go on. And even that doesn’t help much; the hash algorithms used to derive the address are extremely secure, and will hold their own even against a quantum computer.
This event should also be a wake-up call to Bitcoin users to look at other potential flaws in their wallet security. There have been many instances of Bitcoin users having their wallets hacked through little fault of their own, with attackers grabbing their passwords through Android root privileges, Java keyloggers and worse; if you are holding a large number of bitcoins, you would do well to store them in a wallet that you use as little as possible. Keeping a separate spending and savings wallet should be the norm; ideally, you should use some kind of mixer to send money between the two to preserve privacy. Today, the problem is insecure random number generators. Tomorrow, it might be a breakthrough in repurposing Bitcoin mining ASICs to cracking brainwallets. Or another integer overflow. Or a multi-confirmation double-spend attack made possible by hacking into some Electrum servers or forging blockchain.info’s SSL certificate. The lesson here is this: there is still a long way to go before we iron out all of the security flaws that Bitcoin implementations might have. The traditional financial system has had forty years, and even they aren’t done.
