▲ 232 points
back
171 comments
Could someone explain DJB's point to me:
Cryptographers are certainly not responsible for this superstitious nonsense.
Think about this for a moment: whoever wrote the /dev/random manual page seems to
simultaneously believe that
(1) we can't figure out how to deterministically expand one 256-bit /dev/random
output into an endless stream of unpredictable keys (this is what we need from
urandom), but
(2) we _can_ figure out how to use a single key to safely encrypt many messages
(this is what we need from SSL, PGP, etc.).
For a cryptographer this doesn't even pass the laugh test.
The same types of cryptographic algorithms used in SSL, PGP, etc. are also used to securely expand a small bit of entropy into an endless stream of good randomness. It's intellectually inconsistent to not trust these algorithms when used in an RNG, but to trust them when used in SSL, PGP, etc. See the contradiction with stressing the importance of using random, not urandom, when generating SSL/PGP keys?
I don't understand your theory, sorry. I can't tell if you are right. So, I'll just put my understanding here.
There are people that assume that both: 1 - 256 bits aren't enough entropy to create a long chain of random numbers in a CSPRNG; 2 - 256 bits (after adjusting for known attacks) are enough entropy to encrypt a long chain of data in a symmetric cryptography algorithm.
Since encryption and creating random numbers are normally the same operation, 256 can't be both enough and not enough.
I don't know if SSL even supports symmetric encryption with more than 256 bits of entropy. I've certainly never seen it.
Well close, though you use the word random or randomness where he uses unpredictable.
His basic point is that we can use the 256-bit random output as the key for a stream cipher, and voilà you have yourself an endless stream of unpredictable keys. And if you don't believe that, then in what sense do you trust the stream cipher?
It's an informal way to put it, but yes, it boils down to that. It's almost the definition of a block cipher.
These aren't myths, they're platform guarantees. It just so happens that a few of the most common unixes (Linux, BSD) implement a very good /dev/urandom and the author is suggesting that we write non-portable software that depends on implementation details of these platforms.
There can be benefits from depending on non-portable implementation details but also significant drawbacks.
There's no standard for this - Linux folks came up & implemented it first and other platforms have taken that as compatibility target. So "non-portable implementation details" is all there is, and it works fine for CSPRNG.
No. Applications on Linux should use urandom to the exclusion of any other CSPRNG.
In which way are those platform guarantees? Honest question, I don't understand where you're getting at.
> Both /dev/urandom and /dev/random are using the exact same CSPRNG
The author keeps coming back to this fact, but I don't understand how it negates any of the arguments in favour of using /dev/random. What does it matter if the numbers are ultimately coming out of the same PRNG? I don't see how this negates the "self-healing" property of /dev/random or any of the other advantages. It seems like the author is really just saying, "/dev/urandom is probably good enough".
This is basically a response to the widespread conception that /dev/random has some mechanism whereby it generates "true" random numbers, while /dev/urandom only uses some lowly PRNG.
The idea that a lot of people get from that is that urandom is not much better than Mersenne twister, while /dev/random is the real thing.
And yes, you're right, the argument is precisely "computational security is good enough".
By the way, /dev/urandom is also self-healing.
Which other advantages of /dev/random might be there, apart from the cold boot case?
Another misconception. Talking about urandom is a little like playing whack-a-mole. Both random and urandom "self-heal"; they both continually rekey based on new entropy events. But there is no meaningful security benefit to giving your application control over that rekeying, which is effectively what /dev/random does by having your application sleep until some arbitrary counter elapses.
I think he's saying something along the lines: It's better to use /dev/urandom than /dev/random when you're in need of a high throughput of randomness. He even said people use /dev/random and do weird shit, which,makes their system less secure, when their app runs slow to make up for it.
In the end, it boils down to: Why not use /dev/urandom and get good enough security, instead of insecurity.
The same "self-healing" property also applies to /dev/urandom. Author tries to show that only way in which is urandom better than random is that it blocks when there is not enought entropy by some pretty arbitrary estimate, and that this behavior is almost never what you require.
I could be mistaken, but weren't there a security issue a while back with keys generated at boot time by using /dev/urandom? Since there weren't enough entropy, using urandom created an silent failure in the security design.
I think this is a key point that the article is missing. Silent security failures are very, very bad. Blocking will at least provide assertion that either things are as expected, or the issue will be detected early.
It's not missing:
Linux's /dev/urandom happily gives you not-so-random numbers before the kernel even had the chance to gather entropy. When is that? At system start, booting the computer.
I invite you to read the article, because there's more.
The parent is likely referring to Nadia Heninger et al's Mining Your Ps and Qs (https://factorable.net/weakkeys12.extended.pdf).
Another good source explanation of the difference between urand and rand is the Linux source code, which is well commented:
https://github.com/torvalds/linux/blob/master/drivers/char/r...
The operation is explained starting on line 52. The 2 paragraphs starting on line 78 explain the relationship behind the entropy estimator and the CSPRNG (It relies on SHA-1).
> As more and more random bytes are requested [from /dev/urandom] without giving time for the entropy pool to recharge, this will result in random numbers that are merely cryptographically strong
Thank you! That was actually much clearer. Line 307 is also relevant - it seems that the urandom pool is reseeded at most every 60 seconds?
https://github.com/torvalds/linux/blob/master/drivers/char/r...
I'm not a crypto expert but I find the arguments of this article (and tptacek et al) convincing.
The one thing I still don't like about /dev/urandom is this: urandom's proponents say that it only fails on first boot, because modern linux distros capture entropy to seed urandom on following boots.
This means that in order for /dev/urandom to be ok, I have to depend on specific functionality of both the kernel and the linux distribution. In contrast, /dev/random is (arguably) harder for the distro to mess up, as it's primarily a function of the kernel.
Given the number of times distros have screwed up crypto, what are the odds that this will someday matter in the real world?
> Virtual machines are the other problem. Because people like to clone them, or rewind them to a previously saved check point, this seed file doesn't help you.
There is work on fixing this problem (or, at least, improving the situation) on Ubuntu: http://blog.dustinkirkland.com/2014/02/random-seeds-in-ubunt...
Cloning: okay. Regenerate the seed, and also regenerate your sshd's private key.
But rewinding and restoring to a previous save point? What's the harm in keeping the seed?
Why not make /dev/urandom block, but only at boot time until sufficient entropy has been achieved? Then you could "trust" it, even in boot conditions and in normal operations it would still never block…
Or if the change in semantics is too onerous, a new /dev/drandom (delayed-random) could do this.
This article's premise seems to come down to the key argument under the section "What's wrong with blocking?", which seems to summarize as "security should not get in the way of the developer: if it does, they will turn off the security". This frankly just seems silly: if the developer cannot be trusted to not do something insane (seriously? "patching out the call to random()"?!), then they should not be developing :/.
This is like saying that using consistent databases for things that require consistency is also "wrong", because the developer is going to add some ludicrous poorly-implemented caching layer in front on production as the performance dips, leading you to have a poorly-controlled inconsistent system anyway. It's an argument I appreciate, but one that indicates a deeper problem of developers thinking they can fix things they can't.
...and that's the only argument in the entire document for why /dev/random is bad: everything else is a justification for why /dev/urandom should be considered a reasonable alternative to /dev/random, most of which is difficult to confirm or deny unless you are a cryptographer. I mean, from a naive standpoint, it would sound like "putting all your eggs in one basket" could lead you to a problem, but how would I know, right?
Helpfully, the article claims to quote cryptographers on the matter. However, and this pretty much damns this article for me: he takes these quotes out of context. If you read the original sources, Daniel Bernstein makes it clear that /dev/urandom is broken on Linux (more on this later), and Thomas Pornin was responding to a user that was simply trying to get unique random values (where /dev/urandom is obvious).
As for Thomas Ptacek's emphatic "use /dev/urandom" repetition, his article was about people attempting to use user-land replacements for the kernel implementations, not people who were using /dev/random. In essence, he's trying to make the argument that people shouldn't be so afraid of /dev/urandom so as to use something clearly worse. He does state that /dev/random is overrated, but correctly points out its flaws.
Back to this article: after a ton of argumentation that the people suggesting that there is a key difference between /dev/random and /dev/urandom are inherently being misleading, the author gets around to quoting a section of the man page that sounds perfectly reasonable, and even is willing to cede that there is no issue using /dev/random for those use cases. I think the author is just mad because some service is slow. :/
Now, here's what I'll leave you with: an argument why this author's article is not just wrong but promoting beliefs that are actively harmful, an argument that can I hope can be believed even if you aren't a cryptographer and does not rely on me being a cryptographer: its an argument based on practical concerns only, with a demonstration of the problem not just in theory, but that happened to real people/developers.
[edit: Apparently, I misremembered this Android issue, so when I pulled sources for it I ended up with something that is not actually an issue with /dev/urandom. I have added details on a different situation where /dev/urandom actually was the culprit, but the argument isn't quite as strong. I was hoping for an argument that anyone would believe without invoking even a single hypothetical, but sadly I screwed up: I'm sorry for the confusion :/. I think the new example still makes a strong, though not impervious, point.]
So, if the author got his way, then all source code everywhere would be referencing /dev/urandom instead of /dev/random for all use cases (including "long-lived keys"). However, the author also admits that /dev/urandom "isn't perfect", and that on Linux it never blocks, even when it really should. It is then claimed that the correct solution to this problem is that you should seed virtual machines with entropy before using them.
Look: that just isn't always possible. I say this not from theory, but from the trenches of information security. On Android, some poor developer made java.security.SecureRandom use /dev/urandom. This meant that all Java libraries that rely on random numbers were getting ones from urandom, even when they claimed that they wanted "cryptographically strong" ones. Put short: the author's dream come true, codified into the library.
Sadly, users expect to be able to use Android devices soon after they boot, the user is not in control of the entropy sources, and the people who build the kernel drivers for these devices often didn't include enough entropy sources to fill the pool faster. This meant that all of this code was now broken: instead of blocking until "seriously-random numbers" could be generated, it would get "reasonably random-looking ones".
This is not a theoretical issue: people built bitcoin wallet applications sitting on top of these APIs, and some of the people using those wallets ended up with bitcoin addresses secured by keys that were painfully predictable across usages on different devices (the specific concern people bring up using /dev/urandom!). This was looked into, traced back to this design flaw, and Google even commented on the situation.
[edit: For clarity, this is the part that is wrong; as pointed out in the author's rebuttle to my comment, SecureRandom was actually doing something ludicrous here--the kind of thing that Thomas Ptacek was angry about ;P--and thereby Google's own article, which I had pulled up as a source for something I had apparently misremembered, claims that developers could consider using /dev/random or /dev/urandom to replace it.]
http://android-developers.blogspot.com/2013/08/some-securera...
[edit: Thankfully, there is another situation I can cite: the attack on routers from a year or two ago that involved low-entropy keys that were generated at boot. It is the same issue, but what makes this a weaker argument is that the user is now the developer, and the developer is actually in control of the device and could have fixed the entropy pool as stated by both this author and by Daniel Berstein's full comment.]
[edit:]
So, in this new example, the key issue is that a bunch of embedded systems--routers and firewalls from companies such as Cisco--were generating keys to secure their configuration portals and administrator consoles using /dev/urandom. This was done, on first boot (when there would be no entropy available), and the result was that many RSA keys were generating the exact same input prime numbers. If you are trying to factor a large semi-prime, and you have another large semi-prime that shares a factor, you can break it apart very easily with simple math.
Some researchers went through to determine why this happened, and their conclusion was that reliance by library developers on /dev/urandom, being used on devices and at moments where /dev/urandom didn't end up working very well, was the "root cause" of the issue, and made a recommendation to library developers that usage of less secure mechanisms should be a non-default option and that any tradeoffs in its selection should be clearly documented, lest security be contingent on factors that do not immediately seem related to security.
https://factorable.net/weakkeys12.extended.pdf
> In the final component of our study, we experimentally explore the root causes of these vulnerabilities by investigating several of the most common open-source software components from the population of vulnerable devices (Section 5). Based on the devices we identified, it is clear that no one implementation is solely responsible, but we are able to reproduce the vulnerabilities in plausible software configurations. Every software package we examined relies on /dev/urandom to generate cryptographic keys; however, we find that Linux’s random number generator (RNG) can exhibit a boot-time entropy hole that causes urandom to produce deterministic output under conditions likely to occur in headless and embedded devices. In experiments with OpenSSL and Dropbear SSH, we show how repeated output from the system RNG can lead not only to repeated long-term keys but also to factorable RSA keys and repeated DSA ephemeral keys due to the behavior of application-specific entropy pools.
> When we disabled entropy sources that might be unavailable on a headless or embedded device, the Linux RNG produced the same predictable stream on every boot. The only variation we observed over 1,000 boots was the position in the stream where sshd read from urandom.
> On stock Ubuntu systems, these risks are somewhat mitigated: TLS keys must be generated manually, and OpenSSH host keys are generated during package installation, which is likely to be late in the install process, giving the system time to collect sufficient entropy. However, on the Fedora, Red Hat Enterprise Linux (RHEL), and CentOS Linux distributions, OpenSSH is installed by default, and host keys are generated on first boot. We experimented further with RHEL 5 and 6 to determine whether host keys on these systems might be compromised, and observed that sufficient entropy had been collected at the time of key generation (due to greater disk activity than with Ubuntu Server) by a slim margin. We believe that most server systems running these distributions are safe, particularly since they likely have multiple cores and gather additional entropy from physical concurrency. However, it is possible that other distributions and customized installations do not collect sufficient entropy on startup and generate weak keys on first boot.
> For library developers: Default to the most secure configuration. Both OpenSSL and Dropbear default to using /dev/urandom instead of /dev/random, and Dropbear defaults to using a less secure DSA signature randomness technique even though a more secure technique is available as an option. In general, cryptographic libraries should default to using the most secure mechanisms available. If the library provides fallback options, the documentation should make the trade-offs clear.
[/edit]
Of course, this is covered by the idea that these devices were not properly configured; but that's kind of the point, right? What everyone is saying about /dev/urandom is that it isn't guaranteed to produce anything "seriously" random; it happens to, most of the time, on most operating systems, produce something incredibly random, but some times, on some operating systems, it might produce something that is barely random at all.
This means that if everyone switches to using /dev/urandom in their code, a ton of libraries are going to work on some systems, and not on others; they might work on a properly configured server, but not on an Android device, or might work on one cloud provider, but not another... this is insane... if I download "secure off-the-record messaging implementation library for Linux", am I going to expect it to fail like this?
Certainly, the developers this article seems to believe are both common and acting reasonably enough to be worked around by people writing code--the ones who are supposedly going around patching random() out their libraries ;P--are not going to realize their code isn't secure, or that they they need to configure their kernel or operating system distribution to make it secure; but this is even going to burn the people reasonable enough to download code and not try to hack it :/.
[edit: And, to close the earlier edit: clearly the people who were building these embedded routers didn't realize these tradeoffs. The author of this article is thereby asking developers to be cognizant of how these different pseudo-random number generators operate and design their entire systems in ways that will make specific sub-components, components they probably don't understand well and "just want to be secure", continue to work correctly under potentially-modified assumptions. While they technically can do this--unlike the sadly-flawed Android argument I wanted to make, where users and developers had no control--this seems like a much higher bar than keeping people from taking random() and patching it out entirely due to a performance benefit, and comes down to a simple heuristic.]
Thanks for laying out your thoughts, but obviously I disagree.
Let me rebut two points that kind of irk me:
You claim that the Android problem that bit several Bitcoin wallets was due to java.security.SecureRandom using /dev/urandom.
That is mistaken, as the blog posting you gave clearly shows:
"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."
So, in their opinion, /dev/urandom is fine.
Furthermore you claim that I've taken quotes out of context.
I was aware that there is the danger of misunderstanding these people's point of view, so I emailed all three of them, right when I put this web page up some days ago, specifically asking them if they felt that I might be misrepresenting them or if they are otherwise unhappy about me using their names.
Of those three two replied (both very quickly).
Daniel Bernstein replied very shortly with "Seems reasonable.", but noted that he disagrees with the "more entropy cannot hurt" point. That's why I added the little sidebar with a link to his blog posting.
Thomas Pornin seems to have taken the time to really read the article, he wrote "That's a fine page. I like it.", noted a mistake in the boot scripts section (that I have fixed) and suggested some additional points to discuss (which I did not put on the page).
Off-topic remark: All in all I was really fascinated how easy it is to get in touch with those highly-respected people, and how respectful they treat "us normals". :-)
The correct solution to the Linux urandom problem is to seed it explicitly at boot (or at your app startup), usually from /dev/random, and then never use /dev/random again.
Once urandom is seeded, there is absolutely no security benefit to using /dev/random, for any cryptographic application, anywhere. urandom is a stream cipher engine generating a keystream whose keys are entropy events. Keystreams don't (in practical terms) "run out of key", and urandom outputs don't "run out of entropy".
"What's wrong with blocking?", which seems to summarize as "security should not get in the way of the developer: if it does, they will turn off the security". This frankly just seems silly
Time and time again, ignorant and lazy human beings are the enablers of security breaches. You can blame humans all you want, but if systems aren't designed with such human factors in mind, they simply won't work in the real world.
Look: that just isn't always possible. I say this not from theory, but from the trenches of information security.
I'd have to say that you're confusing "not possible" with "hasn't been done yet." Manufacturers have been flashing unique identifiers and even completely individually customized firmware as part of the assembly line process for decades now. (I know of one Fortune 500 manufacturer that can automatically customize virtually every engine controller's firmware.) Considering how foundational good CSPRNG are to cryptosystems and how cheap such resources are now, I'd say that this is one situation where there should be government regulations. How about a regulation mandating generous initial entropy pools in all computing devices that will be encrypting end user data? That doesn't cover all situations where insufficient entropy can cause harm, and such regulations would ultimately be much more complicated than my 3 paragraph comment might seem to suggest, but it would be a good start. (Yes, embedded devices are going to complicate this a lot, I know.)
The security field needs to start using some of the same pragmatic strategies the NTSB uses to prevent plane crashes. We can't just stand around wishing programmers know more about crypto and security. We need to put measures in place that actually work.
>"security should not get in the way of the developer: if it does, they will turn off the security"
You wrote a very long text, but I wasn't able to understand where you think it has sense to block?
There were problems with routers with too little entropy, but unless you are the person implementing the code which initializes the router's keys after the first boot, you still should not use blocking.
I guess the simplest rule is: 1) If you are programming something which is to be used as a normal program, on the normal computer, use /dev/urandom. 2) If you are responsible for developing the device or virtual device which doesn't have valid entropy sources after the first boot, do consult somebody in the know how you can provide the needed initial entropy. After it's there, use /dev/urandom.
In short, I really don't know where using /dev/random regularly is a good practice.
What if certificates and SSL weren't guaranteed to work properly "on cold boot" and the industry expected OS implementers to know this and take appropriate steps to "do it right?" This wouldn't make any sense at all. Yet CSPRNG are pretty foundational to cryptographic tools across the board, and the programming field seems to have this kind of hair-shirted attitude about it.
We as a technical community and we as a society need to start using the same stances and strategies that governments and agencies like the NTSB use to prevent accidents. When planes crashed in the wooly pioneering days of aviation, people probably stood around sadly tsk-tsking someone's failure to recognize a stall. Today, the NTSB conducts root cause analyses and the industry takes concrete steps to prevent future mishaps. (Like equipment that detects stall and warns the pilot.)
In this case, why don't we simply have classes of devices that are expected to implement crypto for end-users, and require them to be built with generous entropy pools? (To head-off the expected smart-asses: Each one gets their own unique one, of course.)
(EDIT: An analogy: What if you knew that pilots all had conflicting opinions on how to fly and maintain a plane, with constant acrimonious debates, and where some large swathe of all pilots simply were operating on misinformation? Would you fly? Would you expect lots more crashes? Now ask yourself what the situation is like with computer security, where knowledgeable people expect security to always be broken.)
> In this case, why don't we simply have classes of devices that are expected to implement crypto for end-users, and require them to be built with generous entropy pools?
Intel added a generous entropy source to their processors. The result is that nobody trusts it as a single entropy source, and /dev/random blocks anyway. Also, we are learning that using it only as an added source may also be harmful, and maybe we should ignore it completely.
I don't think this'll have any simple solution, although the idea of a CSPRNG that may block only at boot is interesting.
The author seems to be assuming that all operating systems use the same implementation or have the same man page even for these random number generator devices -- they do not.
For example, on Solaris from random(7D):
The /dev/random and /dev/urandom files are suitable
for applications requiring high quality random numbers
for cryptographic purposes.
...
While bytes produced by the /dev/urandom interface are
of lower quality than bytes produced by /dev/random, they
are nonetheless suitable for less demanding and shorter
term cryptographic uses such as short term session keys,
paddings, and challenge strings.
How much do you want to bet that that man page isn't grossly misleading, just like the linux one?
No, I wrote specifically in the beginning that I'm talking about Linux.
> Imagine an attacker knows everything about your random number generator's internal state ... But over time, with more and more fresh entropy being mixed into it, the internal state gets more and more random again.
Of course that probably only only counts if an external or local unprivileged entity manages to become informed of the random source's internal state. If the attacker has direct access to the kernel's state then they probably have access to influence (or at least monitor) the incoming entropy such that they can stay informed of the full internal state.
There is a point in some attacks beyond which your only half way guaranteed solution is the metaphorical orbital nuke platform.
If you always use the same seed, and the attackers knows the PRNG implementation details, then he can devise the seed, and after that he can predict the next value. So, reseeding makes sure this doesn't happen. I think. I'm not a cryptography expert, more of an aspiring noob. :D
You don't need access to the machine.
The only sensible long-term solution for Linux seems to be to adopt FreeBSD's way of /dev/random operation - block once until enough entropy is gathered and then never block.
This would make sure that distro vendors don't even get a chance to mess initial seeding at boot time. It will also force vendors of embedded or "cloud" distributions (eg. Ubuntu's AWS images) to find a way to pre-seed the images to reduce the initial boot times.
Unfortunately there is such a huge amount of software that depends on this particular difference between /dev/random and /dev/urandom that I don't see the change happening soon.
Always good to see people trying to fight superstition. :) Just one tiny nitpick if you don't mind: it seems to me it's somewhat unclear what does FreeBSD actually do. In FreeBSD there is in fact no /dev/urandom, it's just a symlink to /dev/random. If one already doesn't know this, relevant parts of the last section can be a bit confusing, IMO, so maybe you should point out that they are the same device (or that urandom doesn't really exist, or something like that).
Thanks!
I found this article very confusing, second paragraph:
/dev/urandom is a pseudo random number generator, a PRNG,
while /dev/random is a “true” random number generator.
Fact: Both /dev/urandom and /dev/random are using the exact same CSPRNG (a cryptographically secure pseudorandom number generator). They only differ in very few ways that have nothing to do with “true” randomness.
He's saying:
This a commonly believed myth
Fact: This is the real factI'm not sure I understood you, but the statements in bold are the widely-held myths.
most libraries use some form of specialized crypto random number generator (openssl uses the ssleay random number generator, JDK has the same schema for java.security.SecureRandom): /dev/rand is used to seed it with some random numbers, each iteration computes the SHA1 checksum of the previous state, the algorithm returns part of the state as random number output.
The assumption here is that the initial state can't be guessed, i guess you would rather use /dev/random for that, even if it blocks. Now be careful with the initialization step of your favorite crypto library, most inconsistencies /fishy tricks do happen right here !
Also another issue is that that such a random number generator introduces locks; I have a small program that encrypts everything with RSA, and uses multiprocessing to speed up the process; RSA encryption is supposed to use padding schema that needs to generate random numbers, so it locks, however you don't have this problem with decryption - that's where it counts because RSA decryption is much slower than encryption.
here is my project: http://mosermichael.github.io/cstuff/all/projects/2014/02/24...
As people have pointed out in this thread and other articles, clearly there can be issues with using /dev/urandom on boot where there is a lack of entropy. What I would love to know more than anything on this topic though, is whether it might ever make sense to use /dev/random after boot--after the CSPRNG has been properly seeded with good entropy. Specifically, I would love to hear of any real attacks. Anyone?
What is the point behind an 18-point font? Even if you Ctrl-minus to reduce the font you get this tiny squeezed column of text and still have to scroll forever. My scrolling finger and eyes are exhausted.
For the vast majority of cases, urandom is fine. I am glad random exists though.
Nice try, NSA!
tldr..
haveged, /dev/random