Sophos Cloud Optix
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.
A few corrections:
"the value on Mt Gox imploded from $15 to 1c in minutes"
This is grossly misleading. As you pointed out in the original article, this was due solely due to Mt. Gox (one Bitcoin exchange of many) being hacked; no trades were actually settled at a price of 1 cent, and the price on all other Bitcoin exchanges was completely unaffected. A later, unrelated incident (caused by a bug rather than a hack) caused the price on Mt Gox to briefly rise to $1 billion; again, no trades took place at this price, and neither case represents an actual rise or fall in the market value.
"if you want to sell a Bitcoin sum, you can trade the private key for real money."
While technically possible, this would be incredibly insane, as there's nothing stopping you from keeping a copy of the private key after you sell it. Transferring bitcoins from one person to another is actually accomplished by broadcasting a message containing the new owner's public key, which is signed with the original owner's private key, forming a digital "chain of title", as illustrated in the helpful diagram you included but never actually referred to.
The explanation of the flaw itself is totally wrong. It has nothing to do with the generation of keypairs (although the keys themselves are almost certainly weakened as a result of this flaw, that is not what led to the private keys being compromised in this case), instead it involves the generation of digital signatures. An ECDSA signature requires a random number, which is published as part of the signature. This random number is not secret (indeed, it CANNOT be kept secret, as it is necessary to verify the signature), but it must be unique: if two different signatures from the same private key both use the same random number, it is possible to calculate the private key. This is how the private keys were compromised and the bitcoins stolen.
Also, Bitcoin uses 256-bit ECDSA keys, not 160-bit keys, not that it makes any difference as far as this particular problem is concerned.
I think with your help I have sorted out the errors around keypairs versus sigs. Please take a look and let me know if there is still anything incorrect or confusing.
I also added in that Bitcoin's keys exceed the 160-bit FIPS minimum, just for clarity.
Thanks for taking the trouble to send in your comment to the level of detail you did – it's much appreciated.
(But I am not changing the word "imploded" to describe the Mt Gox price-plunge, and I am not accepting that choice of word is misleading, let alone grossly so. So we shall have to disagree on that 🙂
“The mathematical basis of ECDSA means that if two messages have signatures that were created with the same random number, the private key used in signing one message can be recovered if you know the private key from the other message.”
No […shortened…], if two messages have signatures that were created with the same random number, AND the same private key, said private key can be calculated from just the signatures themselves. (Note that private key reuse is not the problem […] and is perfectly safe as long as a new random number is used each time.)
I think I got there in the end 🙂 Explained as you put it makes the article more concise, too: a second bonus along with correctness. Have another look…thanks for your effort so far!
"Are you ready to trust Android and Android apps with your hard-earned funds?"
No.
It sounds like Google need a slap for not sorting out SecureRandom.
Back in the late 90’s, I was doing low level embeded programming in Java, and everyone knew that Sun’s reference implementaion of java.security.SecureRandom was rubish. It burned a huge number of CPU cycles for each random byte returned, while still returning fairly poor quality entropy, especialy on realtime embeded systems where you could not rely on user processes to perterb timings. The only good thing about it was that it was portable because it did not make any OS dependent system calls.
Most people who where serous about java just replaced the internals with one that read from /dev/random (or the OS specific equvalent), for better entropy and low CPU load.
Considering that all this was well know over 10 years ago, and how Google are supposedly hot on security it supprises me that they did not sort this out before Andoid was relseasd to the public.