All Bitcoin Wallets On Android Vulnerable To Theft 137
judgecorp writes "Bitcoin users have been warned that storing them in a wallet app on Android is insecure, A weakness in Android's random number generator means its random numbers may not be so random, giving attackers a chance of breaking into the wallet. those with Bitcoins have been advised to put them elsewhere, by bitcoin.org"
The bigger issue... (Score:5, Informative)
... is that supposedly Android's "secure" random number generation... isn't. This could potentially affect much more than Bitcoin wallets.
Does anyone know what the issue is? This article [thegenesisblock.com] seems to suggest it's a vulnerability in the SecureRandom class, but no actual details.
Some details (Score:5, Informative)
The problem is this: the elliptic curve digital signature algorithm, which Bitcoin transactions rely on for security, has three inputs: the transaction, the signerâ(TM)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 [nilsschneider.net]). Normally, this is not a problem; given a true random number generator, the first âoecollisionâ 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 âoerandomâ number twice on many occasions.
I just noticed the "found here" link goes to an article from January. That makes me both unsure they've got the right bug and annoyed it hasn't been fixed already.
Re:How can an OS have such a fundamental problem? (Score:5, Informative)
Depends pm what you mean. Any time there are less than, I believe the number is 5400 blocks in two weeks, that the hardness adjusts to attempt to maintain, or about one block every 10 minutes. Technically, if someone can present a valid transaction, you could accept it instantly and say bitcoin has no delay.
Technically the transaction isn't official till its in a block, but once its transmitted out to the network valid, its almost guaranteed to be in one within 10 minutes or so, and each block that buries it, solidifies it further.
What is accepted? Last I looked, the default client didn't consider a transaction accepted until several blocks AFTER it was accepted, so we are talking 20-30 minutes or so.
But.... you could accept bitcoins "instantly" (pretty quick anyway) if you have the most recent block chain, and are sure the transaction has been transmitted out to the public network. There are some small risks in terms of the possibility of accepting a transaction while the block chain is split and a competing transaction being inserted into the other chain, which then wins.... but.... if anyone really does make exploiting such a situation practical and profitable, countermeasures could be achieved pretty easily, it wouldn't be hard to use multiple nodes to watch for block chain splits and monitor what transactions are going out.
Have a few nodes that are not peers of eachother, one transmits the transaction, all the rest watch for it, and watch for splits/competing transactions, etc. I am sure somebody can come up with a pretty safe way to fast accept bitcoins if they haven't already.
Re:Some details (Score:5, Informative)
Re:Number re-use? (Score:5, Informative)
The chance of getting the same number twice should be equal to the chance of an attacker brute-forcing it. Judging by the fact some keys were brute-forced in well under a billion years, I'm going to assume it's much more likely that Android's RNG is broken.
Re:How can an OS have such a fundamental problem? (Score:5, Informative)
There are bad PRNG algorithms and better PRNG algorithms, and it's worth using better ones. Plus, these devices have so many sensors that finding a fairly complex and truly random seed isn't all that difficult.
Great insight. I don't understand why linux still uses a known-weak /dev/[u]random when BSD and OSX have used a Yarrow-based PRNG for a decade, and there was even a patch for a Fortuna-based [wikipedia.org] device in the -mm tree at one point.
One of the issues is people say, "just use EGD", but most people don't know about it, don't have it running, and software often uses egd only when /dev/random doesn't exist, if it can use it at all. Having two interfaces isn't the right approach. I can see an argument for leaving something like accelerometer-based entropy gathering in userspace, but as far as I know, there's not a socket setup in place where egd can feed data to /dev/random's pool.
Perhaps we need somebody to grab hold of this issue and drive it forward. Strong crypto is becoming more and more important by the week.
Re:Description of vulnerability (Score:5, Informative)
By "implement" you mean "use"?
From looking at the Android Bitcoin client's code, it appears it already used SecureRandom correctly (default empty constructor). The Android implementation of SecureRandom itself is broken.
Re:Some details (Score:4, Informative)