Cybernetic Entomology: Random Numbers and Response Parsing.

In January of 2015, Random.org stopped serving random numbers over HTTP due to the security risks of an unencrypted protocol. In June of that year, a user of that service named ‘Blockchain.info’, which operated Bitcoin web wallets, noticed that as a result, it had failed.

Many users of Blockchain.info’s service on Android devices all generated the exact same key, the private key corresponding to the public key 1Bn9ReEocMG1WEW1qYjuDrdFzEFFDCq43F. They then secured Bitcoins using that key. And some lucky person among the set who had generated that key, spent them.

How did this Happen?

Up until the failure, Blockchain.info had been using random numbers from Random.org, which was serving them over HTTP, for the purpose of key generation for their clients’ Android systems.

Any keying material read over an unsecured protocol like HTTP should be considered actively harmful because someone will try to use that insecurity to sabotage your application. Especially, and most harmfully, when financially motivated to do so.

HTTP is not private, nor has it any real message integrity. Additionally, Random.org was not a service operated by Blockchain.info, so they didn’t know in the first place whether the numbers were generated by someone who didn’t have an interest in stealing Bitcoins, nor were they likely to be notified when the service was discontinued.

HTTP pages are routinely read and rewritten by middleware in transit, and transit dozens of intermediate hosts before reaching the user’s browser. Further, the wireless networks that Android devices usually connect to are also non-private and also have little message integrity. That makes dozens of places, ranging from routers to telephone switches to ISPs to colocation facilities to Internet cafes with wireless servers, where anybody could be running a program to collect or change those “random” numbers in order to get unsuspecting users to create an easily cracked key. In this case, a malefactor could use such a crack to steal Bitcoins, so there was a big financial motivation to do exactly that.

So, given the utter futility of getting insecure values via HTTP, why was Blockchain.info doing it? It was supposed to be harmless, because the value retrieved via HTTP was to be mixed with bits read from /dev/urandom.

Several weeks prior to the installation of the call to Random.org, blockchain.info had been bitten by a bug in the Random Number Generator used in the Java libraries on Android phones, which made certain sequences of “random” numbers drastically more likely than they ought to have been.  As a result, it had become feasible for attackers to search the more-likely strings and find keys where users of blockstream.info’s wallet had stored bitcoins.  And then, knowing the key, they could spend the coins.  A fair number of coins were stolen due to this Android Java-environment bug, and blockchain.info had rushed out a patch, which added numbers drawn from random.org to the numbers generated by the flawed RNG.  The patch was flawed, as I will discuss below.

About a week later, Google fixed the Android bug – but the call to random.org for “extra randomness” remained in the code, on the erroneous supposition that because it was being added to the numbers from the repaired RNG, it couldn’t hurt.

The engineers at Blockchain.info created a class called LinuxSecureRandom, which was supposed to override the SecureRandom service provided by the Android operating system.

LinuxSecureRandom was initialized using a method called ‘setSeed’ to fill its state with bits read from /dev/urandom, which was fine. This was then mixed with whatever they read from random.org, using a second call to ‘setSeed’, which mixed the new value with its state using XOR. Under normal circumstances, this is useless but not a disaster, because regardless of what you get from random.org, the result of mixing it using XOR with bits read from /dev/urandom will be at least as unpredictable as bits read from /dev/urandom.

On some devices however, their LinuxSecureRandom class didn’t get registered due to an out-of-memory condition. When LinuxSecureRandom didn’t get registered, the call to ‘setSeed’ instead invoked the ‘setSeed’ method of the parent class — SecureRandom.

SecureRandom’s ‘setSeed’ method does not mix the existing generator state with the new sequence of bits. Instead it replaces the existing generator state with the new sequence of bits. This meant that whatever they had previously read from /dev/urandom — which would be millions of times better than anything pulled over an insecure protocol like HTTP in the first place — got removed and replaced by the value from random.org.

On January 4 2015, Random.org migrated their random number server to HTTPS – a protocol which provides some message privacy and integrity, but which can still be easily compromised by any of hundreds of Certificate Authorities.

Thereafter, the HTTP call made by Blockchain.info’s clients resulted in a 301 error – a message that the requested website or service has been permanently moved. The same message. The same sequence of bits. Every time. And the clients were not parsing the response. They were just reading whatever they got and treating it as the result.

The result was that software which Blockchain.info had written and released for Android, looked at the page that Random.org was serving, and every single user of the application on small-memory devices then used the same “random” number to generate keys with. And generated the exact same key.

Android devices have plenty of sensors, input from which is more than adequate to seed a local pseudorandom number generator. /dev/urandom is in the business of using those sensors to generate unpredictable bits, so seeding the operating system’s SecureRandom with bits read from /dev/urandom and stopping right there would have been quite secure once the RNG bug in Android got fixed.

Several things about this episode indicate some absolutely jaw-dropping levels of ignorance about secure applications. But correcting that kind of ignorance is what these articles are about, so without further comment, here are some checklist items:

• Never send keying material over the network.  The call to random.org was stupid no matter how you slice it.  It would have been far better, though still not ideal, to just read (a lot) more of the output of the biased RNG, and then combine it using XOR to smooth out the bias.
• When an entirely adequate service is available don’t override it. The risk that you will make a mistake is far more important than any child class which provides only small advantages.  If an inadequate service that you overrode to overcome a bug gets fixed so it’s no longer inadequate, take the now extraneous code out in order to protect your application from bugs that may be lurking within.
• While a pseudorandom number generator should never be seeded only from a single source, it is best practice for userland software to rely on /dev/urandom as a single source because /dev/urandom is a pseudorandom number generator that’s already in the business of mixing unpredictable bits from many different onboard sources.
• Any security software must be tested to make sure it fails hard on devices with inadequate resources rather than doing anything insecure. If you’re working with a device that can’t do what must be done fast enough or on its limited power budget or within its limited memory space, fail rather than allowing your customers to get their assets stolen.
• Never send sensitive information via unencrypted protocols like HTTP, SMTP, or NNTP, nor trivially-encrypted protocols like wi-fi or cell phone networks, let alone more than one such protocol at the same time.
• Anything your clients use to secure millions of dollars in value is sensitive.
• If you really can’t avoid ever sending anything as sensitive as keying material over the network, HTTPS is not really adequate security unless you can afford to insure your customers against financial losses due to security failures as banks do. There are too many root certs out there and too many of their keys have fallen into the hands of crooks.
• If the security of your users, or your own security, depends on the continued operation of a web service you don’t control, that’s a serious mistake. But if you’ve already made that mistake, you must implement some means of automatically checking that service at intervals much shorter than once in six months to make sure it stays up.
• Everything that uses any networked service needs to be able to parse responses at least closely enough to recognize correct responses as opposed to incorrect responses and error messages. Halting in the event of a network error is far better than sending money to a thief.
• Never allow anyone else to generate random numbers that you use to generate keys (or anything else) which people other than yourself aren’t supposed to know.