Secure programs should rely on /dev/urandom, to the exclusion of other CSPRNGs, and should specifically eschew userland CSPRNG engines even when they're seeded from /dev/urandom.
This Android bug is another in a line of bugs in userland CSPRNGs, the most famous of which was Debian's OpenSSL CSPRNG bug which gave up everyone's SSH key. CSPRNGs have bugs. When you rely on a userland CSPRNG, you're relying on two single points of failure: the userland CSPRNG and the OS's CSPRNG. Failures of either aren't generally survivable.
There are people who are smarter than me (notably 'cperciva) who disagree with me on this, but this is an idea I got from DJB's NACL design paper; it's not my own crazy idea.
I got to eat dinner with Dan Bernstein the other day, by the way, and it turns out NACL is pronounced "lasagna".
Except if /dev/urandom is using a hardware based random number generator, then you have to trust that the hardware hasn't received some NSA alterations at some point during the design.
It would be possible for the NSA to go to Intel and get them to put in something in their random number generator that would let them to basically break the encryption by massively reducing the keyspace if they have the secret key.
I think this is fundamentally wrong, in the way 'secure programs should do their own crypto' is wrong. Secure programs should be able to rely on the platform provider's API to provide a CSPRNG. If the platform doesn't, it's the platform's fault and let's all go yell at them. It seems odd to put this at the doorstep of app developers. Android app developers should reasonably expect that SecureRandom does what it says on the tin as should consumers of similar apis in iOS, .net, OS X, Windows, you name it.
"I'm a Java app, but really, in fact, I happen to know underneath it all it's Linux thus I will read some random file descriptor". It's a Chewbacca defense, it makes no sense!
This comment and the fact that it is so highly rated shows just how easy it is to fall into the trap of "I'll just create my own better crypto!" /dev/urandom is insecure by design. It is a non-blocking version of /dev/random and works by first depleting /dev/random, and then falling back to a very low quality RNG once /dev/random is depleted.
/dev/random is the right way to provide hardware RNG in a UNIX environment. However, programs using it can be blocked for extremely long times if there is no dedicated hardware available for providing RNG. I have regularly seen blocking times in the multiple hour range. This is not practical for most programs.
Even relying on /dev/random isn't necessarily safe. I have seen setups where people connect /dev/random to /dev/urandom in an attempt to eliminate these long block times on /dev/random. A quick google search can bring up multiple examples of how to do this. I'll leave it to you to think about out why this is a bad idea, but the result is that you cannot even trust /dev/random.
Host-based security is a whole dead horse discussion, but I still believe Def-in-Dpht means "use everything you can get your hands on; reveal the least as possible."
Correct me if I'm wrong: which OSes have desirable CSPRNG properties like Fortuna (entropy pools esp.). I've looked at OSX, Win8, Free/Net&Open BSD and still haven't found anything satisfying other than class of algo. (Ignore whether closed/open source and IP issues.) I would like to see all mainstream OSes do these well enough.
The problem is that the PRNG has a weak default entropy source. The same problem existed in the kernel for ages. See http://www.factorable.net
The real advice here ought to be that if you are building an application that generates keys, you should make sure that the system has appropriate entropy before generating the keys. Don't assume the PRNG (whether it's /dev/urandom or OpenSSL) does it for you.
Since this is as good a time as any: I snidely implied that this was likely to have been due to a bug on the part of the Bitcoin community rather than a design error in the Android platform. That seemed like a reasonable guess at the time, but it was wrong, so: sorry, Bitcoin et al devs.
It was not a reasonable guess even at the time because it should have taken you all of 2 minutes to verify it is, in fact, not a reasonable guess. I don't think there is some great tragedy or mistake in being wrong about this but if you're going to gracefully admit wrongness, admit to the right kind.
You were wrong then and you could have easily known you were wrong then. This new disclosure doesn't make you righter or wronger in retrospect.
"Developers who use JCA for key generation, signing or random number generation should update their applications to explicitly initialize the PRNG with entropy from /dev/urandom or /dev/random."
Really? This is what's missing?
They build a whole infrastructure for crypto and forget to do that?
I feel like the author of the post isn't giving this the severity that it deserves. The title makes it sound like a thought experiment, here is an example where the original title is (let's face it) shit and the editorial title here is relevant.
Also, anyone else find it concerning that they advocate presenting /dev/urandom as SHA1-PRNG when it isn't? I don't even see why they did this? They could have wrapped the default SecureRandom and forced it to seed bytes with /dev/urandom.
Let me get this straight. Somebody spent time to hunt down the original issue with the RNG. Followed by the time required to exploit the issue. Then focused on attacking bitcoin environment in some way. Taking a total of 55 bitcoins.
That seem's like a lot of work for $5000.... Some Blackhat burning 0day for giggles?
It's also very impressive that the BT community caught them so quickly.
Part of the philosophical justification for the "full-disclosure movement" is the belief that, much like scientific discoveries, they almost never happen in a vacuum by a lone brilliant researcher.
Which is to say, that it is entirely possible (I'm not going to presuppose how likely) that this has been known about for some time, and used for other nefarious purposes in a manner that wasn't so "easily" detected (the existence of a master record of all Bitcoin transactions makes it much more likely for this to be found than people exploiting it in some random app).
It could be that somewhere right now, in dozens of coffee shops throughout Eastern Europe, South America, and Asia, a group of collective hackers, each unaware of the existence of any others, read this blog post and uttered their linguistic equivalent of "Son of a Bitch".
If I understand correctly, the attacker didn't even need to know which clients were vulnerable or details of why, they simply scanned the Bitcoin blockchain for vulnerable transactions/addresses and stole any Bitcoins they could. Only then did anyone realize which client(s) were vulnerable and the actual bug.
Though they probably could have stolen more money by waiting until they had collected more private keys, there was a risk that someone else would find the same keys and steal it first.
One somewhat fortunate consequence is there will now be lots of people actively scanning the blockchain for these sort of vulnerabilities thus they should be found extremely quickly, which is great for everyone except the unfortunate first victim. Hopefully clients will specifically test for this as well.
Also note that you can avoid this class of vulnerabilities by not reusing Bitcoin addresses.
The first call to ssleay_rand_bytes() (which is what RAND_bytes() calls eventually become with the default RAND_METH) will call RAND_poll(), which on Unix-but-not-OpenBSD-or-VOS will try reading ENTROPY_NEEDED (32) bytes from /dev/urandom, /dev/random, and /dev/srandom (in that order). Then, for grins, it throws getpid(), getuid(), and time() into the pool.
The longer answer is maybe:
• RAND_poll() relies on a #define named DEVRANDOM to figure out where to go looking for random devices. If DEVRANDOM is undefined, e_os.h will define it to "/dev/urandom","/dev/random","/dev/srandom". If DEVRANDOM is defined but empty, then the code in rand_unix.c's RAND_poll() ends up skipping seeding from random devices entirely and only tosses getpid(), getuid(), and time() into the pool.
• If something changes OpenSSL's default RAND_METH so it's not RAND_SSLeay(), all bets are off.
Despite staring at all of the code between Android's SecureRandom.java and their OpenSSL tree's crypto/rand directory for three hours, I can't figure out how they screwed this up.
/dev/urandom is usually pseudo random, so as an initialization for SHA1PRNG random number generator it is not good enough. It seems that the suggested fix is not good enough; you need a real source of entropy - which is /dev/random.
The problem with /dev/random is that sometimes there is not enough system entropy (depending on the available hardware sources), so reading from it can block;
On smartphones they might use the radio signals as a source of entropy, get some data from the radio then MD5 the stuff; couldn't they do just that ?
/dev/urandom and /dev/random follow the same bit generation routine except that /dev/random blocks when the estimated entropy in the input pool falls too low.
The SoCs on phones often have HWRNG support, they just don't always use it, or someone forgets to actually seed their entropy pool with it because they assumed some other bit of code would, which seems to be what happened here.
You mean, take noise that can be readily sampled, by the guys in the black van down the road (or more likely, the guy in the dorm-room next to you) -- and used to reconstruct your random seed?
I'm certainly no radio|crypto expert - but I don't think the "standard" radios on a smart phone are good sources of entropy -- I'm not sure how much raw signal you can actually get out of them (like you can't(?) sample radio noise with your ethernet card, just because it works like a radio).
An AM/FM radio might work (but might still not be a very good idea). There's been some projects using noise from the sound cards in pcs (the idea being sampling electrical noise from the system, not ambient noise, or "actual" sound).
/dev/urandom is usually pseudo random, so as an initialization for SHA1PRNG random number generator it is not good enough.
OpenSSL on most Unix-alike platforms has been seeding its default CSPRNG (which uses SHA-1 internally unless you've built OpenSSL without SHA-1 support) from /dev/urandom for over a decade. I don't understand why has everyone suddenly started framing /dev/urandom as a gigantic crypto bogeyman to be avoided at all costs. It just isn't so.
QC/QA is all about testing for repeatability. Testing for entropy means proving a negative: that the initial parameters will never repeat across all devices that will ever be booted. Entropy gathering is really really difficult to test within a normal engineering process.
[+] [-] tptacek|12 years ago|reply
Secure programs should rely on /dev/urandom, to the exclusion of other CSPRNGs, and should specifically eschew userland CSPRNG engines even when they're seeded from /dev/urandom.
This Android bug is another in a line of bugs in userland CSPRNGs, the most famous of which was Debian's OpenSSL CSPRNG bug which gave up everyone's SSH key. CSPRNGs have bugs. When you rely on a userland CSPRNG, you're relying on two single points of failure: the userland CSPRNG and the OS's CSPRNG. Failures of either aren't generally survivable.
There are people who are smarter than me (notably 'cperciva) who disagree with me on this, but this is an idea I got from DJB's NACL design paper; it's not my own crazy idea.
I got to eat dinner with Dan Bernstein the other day, by the way, and it turns out NACL is pronounced "lasagna".
[+] [-] H3g3m0n|12 years ago|reply
The NSA did design a random number generator that likely had a backdoor in it: https://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy).
Here's Bruce Schneier talking about it: https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_...
Also it's in Windows (although it's not used by default but userspace programs could rely on it). https://www.schneier.com/blog/archives/2007/12/dual_ec_drbg_...
It would be possible for the NSA to go to Intel and get them to put in something in their random number generator that would let them to basically break the encryption by massively reducing the keyspace if they have the secret key.
[+] [-] cperciva|12 years ago|reply
I'm confused, what's the apostrophe eliding? ;-)
[+] [-] glurgh|12 years ago|reply
[+] [-] mh-|12 years ago|reply
edit: for those unaware, the NACL 'tptacek is referring to is [0] - which long predates [1].
[0] http://nacl.cr.yp.to/
[1] https://developers.google.com/native-client/
[+] [-] xxpor|12 years ago|reply
[+] [-] Apes|12 years ago|reply
/dev/random is the right way to provide hardware RNG in a UNIX environment. However, programs using it can be blocked for extremely long times if there is no dedicated hardware available for providing RNG. I have regularly seen blocking times in the multiple hour range. This is not practical for most programs.
Even relying on /dev/random isn't necessarily safe. I have seen setups where people connect /dev/random to /dev/urandom in an attempt to eliminate these long block times on /dev/random. A quick google search can bring up multiple examples of how to do this. I'll leave it to you to think about out why this is a bad idea, but the result is that you cannot even trust /dev/random.
[+] [-] ballard|12 years ago|reply
Correct me if I'm wrong: which OSes have desirable CSPRNG properties like Fortuna (entropy pools esp.). I've looked at OSX, Win8, Free/Net&Open BSD and still haven't found anything satisfying other than class of algo. (Ignore whether closed/open source and IP issues.) I would like to see all mainstream OSes do these well enough.
[+] [-] aliguori|12 years ago|reply
The problem is that the PRNG has a weak default entropy source. The same problem existed in the kernel for ages. See http://www.factorable.net
The real advice here ought to be that if you are building an application that generates keys, you should make sure that the system has appropriate entropy before generating the keys. Don't assume the PRNG (whether it's /dev/urandom or OpenSSL) does it for you.
[+] [-] raverbashing|12 years ago|reply
[+] [-] patio11|12 years ago|reply
[+] [-] glurgh|12 years ago|reply
You were wrong then and you could have easily known you were wrong then. This new disclosure doesn't make you righter or wronger in retrospect.
[+] [-] vbuterin|12 years ago|reply
And I'm saying that as a prominent Bitcoin user and not-so-prominent developer. We undervalue redundancy.
[+] [-] raverbashing|12 years ago|reply
Really? This is what's missing?
They build a whole infrastructure for crypto and forget to do that?
[+] [-] pjmlp|12 years ago|reply
Just Dalvik does not.
[+] [-] rsynnott|12 years ago|reply
[+] [-] dekz|12 years ago|reply
I feel like the author of the post isn't giving this the severity that it deserves. The title makes it sound like a thought experiment, here is an example where the original title is (let's face it) shit and the editorial title here is relevant.
[+] [-] healsjnr1|12 years ago|reply
Also, anyone else find it concerning that they advocate presenting /dev/urandom as SHA1-PRNG when it isn't? I don't even see why they did this? They could have wrapped the default SecureRandom and forced it to seed bytes with /dev/urandom.
Also, why are they writing to /dev/urandom??
[+] [-] conformal|12 years ago|reply
just another secure mobile OS. nothing to see here, move along.
did i mention that you should never store anything of actual import on a phone?
[+] [-] cbhl|12 years ago|reply
[+] [-] metafunctor|12 years ago|reply
[+] [-] ParadisoShlee|12 years ago|reply
That seem's like a lot of work for $5000.... Some Blackhat burning 0day for giggles?
It's also very impressive that the BT community caught them so quickly.
[+] [-] m0nastic|12 years ago|reply
Which is to say, that it is entirely possible (I'm not going to presuppose how likely) that this has been known about for some time, and used for other nefarious purposes in a manner that wasn't so "easily" detected (the existence of a master record of all Bitcoin transactions makes it much more likely for this to be found than people exploiting it in some random app).
It could be that somewhere right now, in dozens of coffee shops throughout Eastern Europe, South America, and Asia, a group of collective hackers, each unaware of the existence of any others, read this blog post and uttered their linguistic equivalent of "Son of a Bitch".
[+] [-] tlrobinson|12 years ago|reply
Though they probably could have stolen more money by waiting until they had collected more private keys, there was a risk that someone else would find the same keys and steal it first.
One somewhat fortunate consequence is there will now be lots of people actively scanning the blockchain for these sort of vulnerabilities thus they should be found extremely quickly, which is great for everyone except the unfortunate first victim. Hopefully clients will specifically test for this as well.
Also note that you can avoid this class of vulnerabilities by not reusing Bitcoin addresses.
[+] [-] marshray|12 years ago|reply
I thought OpenSSL's default code already pulled from /dev/[u]random at initialization?
[+] [-] rwg|12 years ago|reply
The first call to ssleay_rand_bytes() (which is what RAND_bytes() calls eventually become with the default RAND_METH) will call RAND_poll(), which on Unix-but-not-OpenBSD-or-VOS will try reading ENTROPY_NEEDED (32) bytes from /dev/urandom, /dev/random, and /dev/srandom (in that order). Then, for grins, it throws getpid(), getuid(), and time() into the pool.
The longer answer is maybe:
• RAND_poll() relies on a #define named DEVRANDOM to figure out where to go looking for random devices. If DEVRANDOM is undefined, e_os.h will define it to "/dev/urandom","/dev/random","/dev/srandom". If DEVRANDOM is defined but empty, then the code in rand_unix.c's RAND_poll() ends up skipping seeding from random devices entirely and only tosses getpid(), getuid(), and time() into the pool.
• If something changes OpenSSL's default RAND_METH so it's not RAND_SSLeay(), all bets are off.
Despite staring at all of the code between Android's SecureRandom.java and their OpenSSL tree's crypto/rand directory for three hours, I can't figure out how they screwed this up.
[+] [-] Maxious|12 years ago|reply
[+] [-] MichaelMoser123|12 years ago|reply
The problem with /dev/random is that sometimes there is not enough system entropy (depending on the available hardware sources), so reading from it can block;
On smartphones they might use the radio signals as a source of entropy, get some data from the radio then MD5 the stuff; couldn't they do just that ?
[+] [-] __alexs|12 years ago|reply
The SoCs on phones often have HWRNG support, they just don't always use it, or someone forgets to actually seed their entropy pool with it because they assumed some other bit of code would, which seems to be what happened here.
[+] [-] e12e|12 years ago|reply
I'm certainly no radio|crypto expert - but I don't think the "standard" radios on a smart phone are good sources of entropy -- I'm not sure how much raw signal you can actually get out of them (like you can't(?) sample radio noise with your ethernet card, just because it works like a radio).
An AM/FM radio might work (but might still not be a very good idea). There's been some projects using noise from the sound cards in pcs (the idea being sampling electrical noise from the system, not ambient noise, or "actual" sound).
[+] [-] rwg|12 years ago|reply
OpenSSL on most Unix-alike platforms has been seeding its default CSPRNG (which uses SHA-1 internally unless you've built OpenSSL without SHA-1 support) from /dev/urandom for over a decade. I don't understand why has everyone suddenly started framing /dev/urandom as a gigantic crypto bogeyman to be avoided at all costs. It just isn't so.
[+] [-] general_failure|12 years ago|reply
[+] [-] marshray|12 years ago|reply
[+] [-] oggy|12 years ago|reply
[+] [-] syjer|12 years ago|reply
The first is only applied to jelly bean. The prng one is for all the versions.