There has been a bit of drama about the theft of some 55 Bitcoins (worth about $5500 at the current exchange rate), with the common denominator that all of the corresponding private keys were stored in Android wallets. While this is not nearly the first case of Bitcoin theft, it is probably the first one that is a direct result of a crypto bug.

In this case, the problem resulted from the (re)use of the nonce used in the elliptic curve signatures that are used to generate Bitcoin transactions. As everybody familiar with (or even implementing) ECC-based encryption schemes should know well by know, reusing the signature nonce, or using a predictable value even once, results in catastrophic failure: The private key can then be trivially calculated from the signature(s). (If you don't believe me, just ask Sony...) This seems to be the method that was used to steal the Bitcoins in question.

So far, so bad. The obvious question now is: Who was responsible for reusing the nonces in the first place? Since the flaw is not limited to a single wallet implementation, but only occurs on Android (even though some of the Bitcoin libraries are also used on desktop bitcoin clients), people quickly came to the conclusion that there must be a flaw in one of Android's cryptographic libraries.

In an announcement to the Bitcoin dev mailing list, Mike Hearn, the developer of the Java library bitcoinj announced that the offender in question is the class SecureRandom of the Android framework. The various wallets for Android were quickly patched to avoid that class and use /dev/urandom directly, and as far as their developers and users are concerned, the problem is now solved.

However, when there is a bug in a security primitive implemented in a such widely used library, chances are that other users are also affected. So what exactly went wrong, and what are the implications?

Shortly after the announcement of the bug, people were quick to point to a paper discussing several vulnerabilities of the SecureRandom implementations of various Java frameworks, among them Apache Harmony, which is the base for Google's Android framework.

Indeed, Android uses that implementation - but only up to and including version 4.1. Additionally, according to the paper, the flaw limits the entropy of an instance of SecureRandom to 64 bits of entropy. This is not enough for cryptographic applications like key generation or nonces, but also doesn't explain why in many cases, the exact same values were generated. On average, 2^32 transactions would have to be generated to yield a single collision – all of those with the same key, e.g. bitcoin address.

Another problem of the Harmony implementation of SecureRandom is that using setSeed() on an instace replaces the existing entropy in the generator (instead of being mixed securely combined with it). When used wrongly (e.g. by seeding with not-so-random data), this could also lead to predictable values generated by the instance. (This behavior was even used by some applications to use SecureRandom together with a deterministic seed as some kind of key storage facility. Madness, I know...)

With Android 4.2, Google finally switched to a different implementation based on OpenSSL. Since then, calls to the setSeed() method augment the internal entropy, instead of replacing it, as it should be. The new generator is even used when specifically asking for the Harmony-based one; obviously somebody at Google regarded the flaws important enough to allow modifying the behavior of legacy apps. (Of course, this broke all off-label usages of SecureRandom in the process).

So, Android versions from 4.2 should be safe, right? As it turns out, they are not. In some circumstances (I haven't looked at the source yet), the new SecureRandom implementation goes horribly, horribly wrong and returns identical values for successive invocations. This is obviously very bad, not only for Bitcoin wallets, but basically for everybody using the Java cryptographic operations. According to the Android devs, that includes Key generation of symmetric and asymmetric keys (using the KeyGenerator, KeyPairGenerator and KeyAgreement classes).

Ironically, using setSeed() with proper random data with the OpenSSL implementation avoids the bug, which leads to the interesting situation that using setSeed() is discouraged for Android 4.1 and earlier, but is essential for 4.2. (Android 4.3 seems to avoid both bugs, according to the code in the blog post). The Android developers were kind enough to provide a ready-to-use mitigation in the form of a drop-in replacement for SecureRandom that does exactly that. (You should probably still be careful for older Android versions using the Harmony implementation – all the caveats for that mentioned in the paper still apply.)

Every Android developer using one of the affected classes should evaluate their usage, implement the workaround and necessary countermeasures, which could include warning your users to replace any keys generated with the weak random number generator, which is exactly what the developer of Bitcoin Wallet for Android did promptly after learning about the vulnerability (the update generates a new, secure Bitcoin address and immediately transfers all funds to it after the update). If you don't trust any of the Android implementations of SecureRandom anymore, you should take a look at his implementation based directly on /dev/urandom.

As a user, you should check if there is an update available for any of your security-relevant applications, and when in doubt, stop using keys generated on one of the vulnerable Android versions (Android 4.2, and to a lesser degree also everything from before – the 64-bits of entropy again). I plan to evaluate some of the obvious candidates like ConnectBot myself.

This is my preliminary analysis on the situation - if you have anything to share on the matter, or have spotted some wrong conclusions in my argumentation, please leave your comment below or drop me a message!

A side note on the Bitcoin side of the ECC nonce problem: The original Bitcoin implementation elegantly avoids the problem, since it only reveals the public key at the moment of a transaction, and sends the "change" to a newly generated address, to which the ECC key remains unknown until the next transaction. This doesn't apply universally (for example if you receive transactions to an address which you have already used to send coins previously, e.g. well-known donation address; special transactions directly to public keys are also not protected). Since the method is based on a cryptographic hash of the public key, it even provides some protection against quantum-computing based attacks. I wonder what the exact motivation of the creators for using hashes was, but it sure is a nice trick! Unfortunately, bitcoinj currently sends all change to the original address, to which the key has already been revealed, which is why the attack worked in the first place. But there is a good reason to do this: Until we get deterministic address generation, ad-hoc creating addresses to transfer the change to makes wallet backups difficult and is prone to inadverted loss of private keys. But this is probably the topic of another blog post.