All Bitcoin Wallets On Android Vulnerable To Theft

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"

Comments

How can an OS have such a fundamental problem?

[Karganeth]

It's ridiculous in this day and age that an OS can fail to make random numbers properly. That's one of the most basic operations. How lazy/incompetent are the Google programmers?

Re:How can an OS have such a fundamental problem?

[gweihir]

It is both a solved problem and an ignored problem. I find that I have to explain the risks of not using proper random numbers for anything cryptographic time and again even to customers with experience in using cryptography. I blame the CS and programmer education, which is still badly broken when it comes to security.

Re:How can an OS have such a fundamental problem?

[MickLinux]

Question: would it be correct or incorrect to...

suppose you take your best pseudo-random generated number, and xoror seed it with a word made by stringer together the second-lowest bit each from the temperature gauge, the gps-x the gps-y ,the compass, the ping time, and so on?

Would that #increase# or #decrease# the entropy on the random number generator?

Re:How can an OS have such a fundamental problem?

[bondsbw]

This doesn't mean you throw in the towel. 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. Then throw the seed into a good PRNG and it becomes practically impossible to decode the seed values and, thus, produce any mechanism for finding patterns in the seed data.

Re:How can an OS have such a fundamental problem?

[Saint Gerbil]

Number confirmed to be random as certified by a dice roll.

Re:How can an OS have such a fundamental problem?

[Anonymous Coward]

Question: would it be correct or incorrect to...

suppose you take your best pseudo-random generated number, and xoror seed it with a word made by stringer together the second-lowest bit each from the temperature gauge, the gps-x the gps-y ,the compass, the ping time, and so on?

Would that #increase# or #decrease# the entropy on the random number generator?

It would increase it only if you aren't showing a temp of 32F and a GPS of 00N/00W heading of 0, and a ping of 0 and so on. Seeding from things that arent *surely* good and random is not a smart idea. Why didn't you mention the accelerometers? A program with a little sense to turn on the accels, ask you to shake the phone up a bit, and validate that the results aren't all the same should yield enough to do a good unpredictable RNG seed.

Re:How can an OS have such a fundamental problem?

[Joce640k]

The problem isn't doing it, the problem is in getting the "random needs effort" message though thick developer's skulls.

(Same as most other cryptographic problems, eg. correctly implementing AES isn't what makes your code secure, it's only the very first step...)

Re:How can an OS have such a fundamental problem?

[TheCarp]

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:How can an OS have such a fundamental problem?

[radiumsoup]

There are workarounds to this already in use. Bitinstant is one that promises trusted "instant" transactions for bitcoin with specific vendors, although they're reworking their website right now. Others will follow. It'll be a matter of dealing with trusted big-name transaction clearinghouses that settle bitcoin transactions in real-time between their own customers while also transmitting to the network for inclusion in the chain later.

Re:How can an OS have such a fundamental problem?

[bill_mcgonigle]

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 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:How can an OS have such a fundamental problem?

[xaxa]

I'm not a cryptographer, but....

If your random seed really is random, then it's better. But your random source might not be able to provide enough numbers (how often is it sampling the environment?), and according to http://en.wikipedia.org/wiki/Hardware_random_number_generator it's best to constantly check if the numbers are still random.

"collisions" isn't the problem, it's repeating the sequence. (Ask people to draw random dots on paper and they'll often draw quite an even distribution. That's not random!)

There are also uses of random numbers outside cryptography.I came across this: http://en.wikipedia.org/wiki/Mersenne_twister which is good for some uses, but bad for cryptography.

Re:How can an OS have such a fundamental problem?

[kasperd]

It is build on top of Linux, which has /dev/urandom. I'd like to know if this is a generic kernel bug, or if Android doesn't use /dev/urandom.

You could work around such issues in user code. You could for example have your own 20 byte random seed which you concatenate with 21 bytes from the system random number generator and 14 bytes from other sources (the later don't need to be high entropy, every extra bit helps). Now send the entire 55 bytes through SHA1 and store the output as seed for the next iteration.

Re:How can an OS have such a fundamental problem?

[slew]

There are also uses of random numbers outside cryptography.I came across this: http://en.wikipedia.org/wiki/Mersenne_twister [wikipedia.org] which is good for some uses, but bad for cryptography.

Pet peeve of mine, but people often casually use MT as an example of a "golden" PRNG when it is really the first (1997) "popular example" for generating extremely long period uniform distributions using a generalized LFSR-like technique. Unfortunatly with simplicity come certain flaws. The biggest flaw is that it takes many iterations for a seeded initial state to get to a state that is really random. For user that aren't simulating huge universe-sized things (or need an extremely large non repeating, but uniform distribution PRNG), this isn't really the best tradeoff. If you have to throw away the first million numbers to sample a few thousand, that isn't the best efficiency ratio.

Fortunatly, most things get improved over time. For example, the "WELL" PRNG (2004) claims to have a faster state randomization time and is probably suited more to the needs of people wanting a default off-the-shelf PRNG for medium sized simulation purposes (e.g, the average scientist that doesn't spend time researching the properties of PRNGs for their simulations). Sadly, WELL isn't more popular since it is a better default PRNG for nearly all uses.

If your needs are more cryptographic based, DRBGs (deterministic random bit generators) are designed to resist identification of the current state (I've heard that it only takes observing 624 iterations to identify MT19937's state vector) and to reasonably stretch any existing true-random sources. NIST has some reasonably good standardized examples of these EXCEPT for Dual_EC_DRBG which paranoid folks should probably avoid...

Re:How can an OS have such a fundamental problem?

[gweihir]

Indeed. You need to know that your entropy sources provide _more_ entropy than needed in the worst case.

But the problem in this case seems to be that Java SecureRandom is broken, while the Linux kernel /dev/random is perfectly fine, yet unused. There seem to be BitCoin apps for Android that are not vulnerable, because the y use /dev/random. This basically means that the designers of Java SecureRandom on Android messed up badly. Which is a disgrace, as it means Google had nobody with actual security skills on that team. Pathetic.

Re:How can an OS have such a fundamental problem?

[kasperd]

/dev/urandom is not a cryptographically secure source of random numbers.

Maybe you should actually have taken a look at the source before trying to educate somebody who has. It is clearly stated in the source, that /dev/urandom produces cryptographically strong random numbers.

/dev/random is (when correctly implemented). In fact, it's supposed to be better than the frivolous combining-bits-and-hashing scheme you propose.

LOL. You probably don't even know the difference between what I proposed and what /dev/random does. They are more similar than you imagine.

Re:How can an OS have such a fundamental problem?

[kasperd]

And since SHA1 has a fixed length, the 20 bytes with zero entropy you fed into it forced out some of whatever entropy the other 35 bytes contained. Luckily, in this case you only force out some of SHA1's chunk padding

Nothing is forced out. 55 bytes plus padding fits within a single block of SHA1 compression.

but you still aren't accomplishing anything useful by adding compile-time constants either.

I didn't propose usage of any constants.

Cryptography is something that really, really, really should be left for the experts rather than just hacked together on gut feeling.

I don't hack things together on gut feeling. I wouldn't have proposed an exact algorithm if there was a risk it could make security worse. Since the hash input has 21 bytes from the system random number generator, and the hash output is only 20 bytes, that output is going to have at least as much entropy per bit as the system random number generator produced in the first place (unless you find a vulnerability in SHA1). The remaining 34 bytes are only there to strengthen the random numbers in case the system random number generator, you would have used otherwise, does not provide sufficient entropy.

The bigger issue...

[supersat]

... 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 seems to suggest it's a vulnerability in the SecureRandom class, but no actual details.

Random numbers on a mobile device

[Kinthelt]

Shouldn't the RNG tap into the device's accelerometer? That should provide random data if the user gives it a few successive shakes.

Re:Random numbers on a mobile device

[gweihir]

The problem is not doing it right once you understand the issue. The problem is understanding the issue.

Re:Random numbers on a mobile device

[c]

Shouldn't the RNG tap into the device's accelerometer?

The Linux kernel has has the ability to push device input into the random number entropy pool for a long time (/dev/random and /dev/urandom). If the device drivers aren't pumping accelerometer events into the pool, someone really missed an opportunity.

In this case, it sounds like something went wrong with the Java/Dalvik random number generator. It's not clear to me from glancing at the various write-ups whether it's a failure to RTFM on the part of the Bitcoin wallet writers (or maybe whoever wrote a common Bitcoin reference implementation) or if there's something broken in the Android implementation of the RNG class.

Re:Software generated random numbers are never ran

[Sockatume]

"Arbitrary number generator" might be a more useful name, where the numbers generated follow a given distribution and their selection is arbitrary. Calling them pseudo-random invites mistaken conclusions.

Re:Number re-use?

[Sockatume]

Right. If Bitcoin mistakenly assumed that the RNG "shuffled" numbers and they would not be reused, I don't think that's an Android bug. However given that Bitcoin clients work fine on every other platform I assume that's not the problem and there genuinely is something up with the RNG.

Re:I'll just leave this here.

[Sockatume]

If this random number is ever used twice with the same private key it can be recovered. This transaction was generated by a hardware bitcoin wallet using a pseudo-random number generator that was returning the same “random” number every time.

If this is true there's a vanishingly small but nonzero chance of recovering any private key, depending on how large the random number is; poorly-written RNGs simply increase that chance spectacularly.

Some details

[grimJester]

Here

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). 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:Some details

[supersat]

This is exactly how the PS3 got thoroughly 0wned. I'm curious what the problem with SecureRandom is.

Re:Some details

[Wookie Monster]

The problem really is the implementation on Android, from a old buggy open source library. http://armoredbarista.blogspot.com/2013/03/randomly-failed-weaknesses-in-java.html

Re:If Android's RNG is kaput... so is Linux's

[ameen.ross]

There's an interesting article over at LWN about /dev/random and /dev/urandom

http://lwn.net/Articles/489734/

Re:Proper implemenation

[Agent ME]

The correct and highest voted answer on that page says to avoid seeding SecureRandom yourself. It's designed to be the most secure with its default constructor. The issue is that Android's implementation of SecureRandom is bad even when you use it correctly.

Re:If Android's RNG is kaput... so is Linux's

[Agent ME]

The issue is with Android's SecureRandom class. SecureRandom does not rely on /dev/urandom or /dev/random.

Re:Number re-use?

[Agent ME]

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:Description of vulnerability

[Agent ME]

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.

Why did they even consider using the OS's routine?

[jc42]

The most cursory search will turn up similar complaints for every OS's library random-number routine, over the history of computing. It's quite common for a random-number routine that has been good for years to suddenly become non-random in a new release. Basic advice has always been that, if it's important to have truly "random" numbers with any specific property, you should simply ignore any routines that came from vendors. You should look in "the literature" for routines with the properties you need, and have a good programmer (i.e., one who can handle basic arithmetic ;-) to code it up in whatever language you're using.

And part of your testing suite is a test of your random-number routines(s), to verify that they are still generating numbers with the appropriate level of randomness. It's funny what things like "improved" optimizations in the compiler can do to the correctness of such code.

If the bitcoin software managers are using any OS's random-number generators, well, they're just incompetent. Their job should be handed to someone with minimal understanding of the math that they're using. Someone who will ensure that other managers don't force their programmers to do it wrong.

(Yes, I have been ordered by several managers to implement incorrect arithmetic. I've generally responded by writing and distributing a proof of the incorrectness of my orders, and updated my resume. Sometimes they've responded by putting me in charge of the math routines in question. But far more often, I've found a new job. ;-)

(But this wasn't quite as funny as the case where a manager gave us written orders that clearly required that we implement messages that went faster than light. We quickly learned that his superiors supported him, so the entire team had new jobs a week later. We eventually learned that the product was finally abandoned. ;-)