Android random number flaw implicated in Bitcoin thefts

Bitcoin is often in the news, not least because it is somewhat controversial.

It’s a digital currency, backed by cryptography, not by any central issuing authority.

Its “coins” are strings of bits, and anyone can generate one, given enough time (and assuming no-one else generates the same coin first).

Greatly simplified, the Bitcoin network is designed so that one transaction gets approved every 10 minutes on average – what you might call a ‘mining event’ – and the person who did the mining receives a bunch of new bitcoins as a reward.

This ‘mining reward’ is specified to halve every four years, so there’s an exponential dropoff in the rate at which new bitcoins appear, with the total supply capped at 21 million bitcoins.

The number remaining will quickly close in on zero, with 1/2 gone in 2012, 3/4 by 2016, 7/8 by 2020, and so on.

By about 2030, we’ll be close to that asmyptotic maximum of 21 million coins, even though the very last fraction of a bitcoin isn’t due until AD 2140.

For what it’s worth, and it is rather a lot, Bitcoin exchanges currently value each Bitcoin (BTC) around US$100.

Now, creating BTCs is one thing, but buying and selling with these digital strings – actually realising that $100/BTC – is quite another matter.

In fact, if you’ve read any BTC-related horror stories, like the time the value on Mt Gox imploded from $15 to 1c in minutes, or the time Bitfloor was floored by cyberintruders who ran off with $250,000, it almost certainly involved to the trading infrastructure surrounding the Bitcoin algorithms, not the Bitcoin system itself.

Well, it’s happened again.

You need somewhere to store your Bitcoins, and a digital wallet that uses public key cryptography is the obvious answer.

Simply put, you can trade in BTCs using an “address”, which is actually a public key that others can use to transact with you.

The private key, as usual, you keep to yourself.

The public key algorithm used in the BTC infrastructure is called ECDSA, short for Elliptic Curve Digital Signature Algorithm.

To cut a long story short, generating a new ECDSA digital signature requires you to use a random number between 1 and 2ks – 1, where ks is the key size.

The mathematical basis of ECDSA means that if you sign two messages with the same private key and exactly the same random number, then you can go backwards from those two signatures and extract the value of the private key.

Of course, that means that each random number you use with your private key has to be unique, but how can you ever be sure?

The answer is that the bare minimum officially sanctioned ECDSA key size is 160 bits, so that, at worst, there are 2160 – 1 random values to choose from.

That’s about 10 million million million million million million million million, so collisions shouldn’t be a problem.

Better yet, Bitcoin signatures use 256-bit keys, giving a choice of a whopping 1077 different possible random numbers; with a truly random choice for each signature, collisions should be as good as impossible.

Unless you use a flawed pseudorandom number generator (PRNG), that is.

A PRNG produces an algorithmic sequence of “random” values, which has to start somewhere; if you start from the same place twice, you get the same sequence.

→ For some applications, where repeatability is needed, reseeding a PRNG from the same point is a feature, not a bug. Generally, however, you try to seed a PRNG using a bit string that is as close to hardware-random as you can get.

Bitcoin wallet software that re-uses random numbers was found last year by a researcher called Nils Schneider, who documented the computational steps that show why this is a bad thing.

Well, it’s happened again.

It looks as though, at least on occasion, the Java-based PRNG on Android will repeat its pseudorandom sequences, thanks to a flaw in Android’s so-called SecureRandom Java class.

The Bitcoin Forum has already reported the theft of close to BTC56 (worth about US$6000) from a number of people.

A list of known-vulnerable Android Bitcoin wallets has been published by the Bitcoin Project, with instructions on what to do when the various wallet apps are fixed to use better-quality random numbers.

The Bitcoin Project doesn’t go as far as suggesting that you stop using Android altogether to manage your BTC savings, but you might want to consider it.

With two bad security holes recently exposed in Android’s digital signature validation for apps, the platform may not yet quite be ready for the financial big time.

What do you think? Are you ready to trust Android and Android apps with your hard-earned funds?

You may remain anonymous in Naked Security comments. Just put “Anonymous” as your name and leave the email address blank.