12 ms·
Google confirms Java and OpenSSL crypto PRNG on Android are broken
- tptacek 13y agoHere again I will posit: 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".
- mh- 13y agoI'd be curious to know how he pronounces Google's NaCl. ;) edit: for those unaware, the NACL 'tptacek is referring to is [0] - which long predates [1]. [0] http://nacl.cr.yp.to/ http://nacl.cr.yp.to/ [1] https://developers.google.com/native-client/ https://developers.google.com/native-client/
- cbhl 13y agoI always thought it was weird hearing Google devs pronounce it like "na-cull" (like na in "na na na na na na" and "cull" as in killing something) instead of "salt".
- xxpor 13y agoWhat's the CS part of CSPRNG?
- tptacek 13y agoCryptographically secure.
- xxpor 13y agoThanks
- mh- 13y agocryptographically secure. http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo...
- deleted 13y ago[deleted]
- xxpor 13y agoThink about the man-hours of productivity saved by having the explanation right there ;)
- deleted 13y ago[deleted]
- cperciva 13y ago(notably 'cperciva) I'm confused, what's the apostrophe eliding? ;-)
- tptacek 13y agoI quote HN usernames. It's a weird me thing that I've done ever since I saw a user named "the". If I did @cperciva that would make intuitive sense to everyone, but then it wouldn't work for people not on Twitter.
- cperciva 13y agoHuh, I never noticed that before. It's a useful notation which I might well adopt. Thanks!
- e12e 13y agoI'm assuming Bobby Tables can't get a nick on HN, then? (That is, nicks like 'nick, and "' or '1'='1' -- '" aren't allowed?).
- Florin_Andrei 13y ago> but then it wouldn't work for people not on Twitter. I think the @user idiom is by now understood by anyone not relying exclusively on pigeons to send their missives.
- tptacek 13y agoIn places outside Twitter, the @foo idiom addresses a comment to that user, but that's not always what I intend when I reference a user. I'm simply trying to prevent evaluation of a token as English text.
- anyfoo 13y agoI understand where you are coming from, but I think that at this point the interpretation of @foo as an idiom for not addressing but merely mentioning a user has permeated most online cultures. Those who really do not know (yet) will quickly understand from context. All in all, I think @foo is less confusing than 'foo, and will spare you questions like in this thread.
- H3g3m0n 13y agoExcept 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. The NSA did design a random number generator that likely had a backdoor in it: https://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy 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_ad.html 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_ad.html 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.
- gizmo686 13y agoNo you don't. The only time you need to worry about the NSA having a back door into your random number generator is if you are worried either about the NSA attacking you (in which case you probably don't have a chance anyway), or are worried that some learned of the NSA's back door and is exploiting that.
- derefr 13y agoThat reminds me of a question I've been pondering on-and-off for a while: is it possible even in theory to use Sufficiently Advanced Mathematics (e.g. homomorphic encryption) to build a trusted computation environment on top of an untrustworthy foundation? For example, I want to run a VM on EC2, knowing the NSA's after something I have. Is there some way I could, even theoretically, build my VM, that would protect it from the NSA compelling Amazon's cooperation in ripping the data right from my VM's memory at the hypervisor level?
- tptacek 13y agoPossibly. For instance, look up some papers on White Box Cryptography; these are implementations of things like AES designed to run AES computations on untrusted platforms without revealing their key (the key gets "baked in" to the code that runs the algorithm in such a way that it's theorized to be cryptographically hard to extract the key from the algorithm). You are getting into the flip side of the DRM coin here; put differently: if there's a way to do what you want, there's also a way for the MPAA to do what it wants on PCs. Personally, I think there is, at least in the dollar-cost model of security.
- ballard 13y agoHost-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.
- tptacek 13y agoOS X does. The kernel CSPRNG in Linux is comparatively primitive.
- glurgh 13y agoI 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!
- tptacek 13y agoWould that every platform had done what Golang did and simply wrap /dev/random. In the meantime, you have to make a choice: do you trust your language designer's CSPRNG AND the OS CSPRNG on which it (and the rest of the system) doubtless depends, or instead trust only the OS CSPRNG?
- doe88 13y agoI think iOS does just that see the function SecRandomCopyBytes in http://opensource.apple.com/source/Security/Security-55179.11/sec/Security/SecFramework.c http://opensource.apple.com/source/Security/Security-55179.1... it just wraps /dev/random
- glurgh 13y agoSure but down that path lies 'did Intel and the NSA backdoor my CPU' tinfoilhattery. If you're an app developer, rather than implementor of original crypto from dry sticks and a bit of flint, you have to trust something and the platform API is a sane place to start. Google, who have specialists on staff, seems to have got this wrong at least twice. It seems unreasonable to expect a person who's simply looking for a nonce to do better or to keep careful track of how to do better because the APIs at hand just don't do what they claim they do.
- tptacek 13y ago
- raverbashing 13y agoAnd why /dev/urandom instead of /dev/random?
- ikawe 13y agoThe entropy needed to generate random numbers is a finite resource. If you don't have enough entropy stored up, /dev/random may block until such a time as it has sufficient entropy. /dev/urandom reuses existing entropy to produce more pseudo-random numbers. It may be less "random", but will never block. more at http://en.wikipedia.org/wiki//dev/random http://en.wikipedia.org/wiki//dev/random
- raverbashing 13y agoAnd that should be a very good reason for using random instead of urandom I don't want less entropy thank you. If I don't have enough then let's wait until some more become available I would use urandom if I need random but I don't care about their quality (even though urandom is good most of the time)
- aliguori 13y agoI don't think you understand the problem. 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 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.
- tptacek 13y agoThe problem with this comment is that /dev/random wasn't broken, and the OpenSSL CSPRNG used by Android Java was. Further, it is harder to imagine a circumstance in which /dev/random could be broken and an app-layer CSPRNG like OpenSSL's could not be broken. It's a little fuzzy in this case because part of the patch feeds entropy back to /dev/random, but observe (a) that the bulletin doesn't tell developers to re-key if they were depending on /dev/random (as some apps do), despite naming 5 other interfaces that do demand rekeying, and (b) that this particular patch would be an inadequate fix for a broken /dev/random anyways. It's true that you care about entropy at cold start either way. But your choice of CSPRNGs doesn't resolve that problem for you, except that the OS needs to have secure random regardless and so you're boned whether or not you rely on /dev/random, and hence are better off just relying on /dev/random.
- taway2012 13y agoDo you mean /dev/random or /dev/urandom? They are different, AFAIK.
- tptacek 13y agoRandom and urandom are interfaces to the same kernel CSPRNG. The difference is that reads from random block until an internal counter that estimates the entropy in the CSPRNG crosses a threshold, and reads from urandom don't do that. In practice, this is a distinction without a meaningful difference. In more modern implementations (like OS X) the CSPRNG works the same way with both interfaces. You should generally prefer urandom. There is a wellspring of urban legands about the security difference between these two interfaces because the Linux man page is misleading.
- Apes 13y agoThis 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.
- tptacek 13y agoYour comment more or less expands on an urban legend. The legend started because of the way the Linux man page for random(4) was written. Thankfully, Thomas Pornin wrote a definitive debunking of the urban legend here: http://security.stackexchange.com/questions/3936/is-a-rand-from-dev-urandom-secure-for-a-login-key http://security.stackexchange.com/questions/3936/is-a-rand-f... In short: that's not how urandom works. It's not a "fallback to a crappy RNG". Random and urandom are two different interfaces to the same CSPRNG engine. One of them happens to block based on entropy estimates, but that's a design weakness of the Linux CSPRNG, not a great feature of a CSPRNG in general. While considering how highly rated my comment was, and weighing your own expertise on cryptographic randomness, you might also consider reading the NaCL design paper (Bernstein, Lange, Schwabe) for more details on why you want to use the OS CSPRNG instead of your own. Or, for that matter, consult the NaCL source code to see which they use. Finally, to your main point: the reason you should use the OS CSPRNG (typically: urandom) is precisely so that you don't end up using some random bit of aspirational app crypto. The OS has to get its CSPRNG right no matter what, so just let it do the work for you.
- marshray 13y ago(cross post from other article) I thought OpenSSL's default code already pulled from /dev/[u]random at initialization?
- Maxious 13y agoThe developers that used this flawed API thought so too. Mea culpa.
- rwg 13y agoThe short answer is yes: 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.
- marshray 13y agoComplexity kills. Thank you for staring at the code for three hours BTW. :-)
- rwg 13y agoAfter staring at convoluted Java code and OpenSSL's code for three hours, I need a stiff drink...
- rwg 13y agoAs an added fun bonus, it looks like the NativeCrypto Java wrapper around OpenSSL wrongly assumes that RAND_bytes() returns 0 on failure and not-zero on success. In reality, it returns 1 on success, 0 on failure, and -1 on super ultra mega failure.
- raverbashing 13y ago"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?
- dekz 13y ago> Some SecureRandom Thoughts 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 13y agoAgreed. The whole thing is a bit blase. 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??
- tptacek 13y agoPresumably because some Android devices don't boot cold with a lot of entropy, so there's a virtue in helping kickstart it.
- taspeotis 13y agoI'm a layperson when it comes to cryptography. Can you clarify how much entropy a device would need to become cryptographically secure, and the profile of an Android device that couldn't collect enough entropy quickly? E.g. most devices could collect battery %, 3G radio noise levels, wifi noise, readings from the capacitive touch sensors, accelerometer, microphone etc., yes?
- ParadisoShlee 13y agoLet 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.
- m0nastic 13y agoPart 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".
- e12e 13y agoYou forgot the coffee shops in Langley, VA.
- tlrobinson 13y agoIf 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.
- conformal 13y agoneedless to say, android passed its fips certification with flying colors. 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 13y agoAt what point do you differentiate between a phone and a computer?
- throwawaykf02 13y agoIn this context: At the point where one begins to be much, much more likely to be misplaced than the other.
- metafunctor 13y agoFIPS is about compliance, not about security.
- 4ad 13y agoOf course, but OP's point was that compliance is meaningless...
- general_failure 13y agoI don't understand. Isn't seeding very fundamental? How could they forget this?
- marshray 13y agoQC/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.
- patio11 13y agoSince 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.
- vbuterin 13y agoI would still say it's a bug from the Bitcoin community to rely on one generator rather than XORing a few just in case. And I'm saying that as a prominent Bitcoin user and not-so-prominent developer. We undervalue redundancy.
- x1024 13y agoXORing random streams doesn't have as much value as you think.
- deleted 13y ago[deleted]
- patio11 13y agoThat would be a very, very bad decision. As one possible implementation flaw, consider what happens where Generator A is /dev/urandom and Generator B is SecureRandom whose platform implementor has decided to implement their own pseudorandom number generation algorithm in cases where they're sure they have enough entropy but, if they aren't, they fallback to /dev/urandom. That will pass all tests and work fine for all purposes right until hilarity ensues in whatever real world circumstances deplete the entropy pool. Note that after attackers realize that depleting the entropy pool is a victory condition, they can actively work to cause that.
- marshray 13y agoGenerator A returns 32 bytes from /dev/urandom. Generator B returns 32 bytes from /dev/urandom. The application XORs them. What's the problem?
- MichaelMoser123 13y ago/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 ?
- e12e 13y agoYou 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).
- __alexs 13y ago/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.
- rwg 13y ago/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.
- oggy 13y agoAm I reading the patch correctly in that Android versions below 4.1 are not affected?
- syjer 13y agothere are two fix: applyOpenSSLFix and installLinuxPRNGSecureRandom . The first is only applied to jelly bean. The prng one is for all the versions.