Myths about /dev/urandom (2014)(2uo.de) |
Myths about /dev/urandom (2014)(2uo.de) |
* https://news.ycombinator.com/item?id=7359992
Also:
2020: https://news.ycombinator.com/item?id=22683627
2018: https://news.ycombinator.com/item?id=17779657
Having a good entropy source makes mathematical sense, and you want something a bit more "random" than a dice roll, but I wonder at which point it becomes security theatre.
Of all the possible avenues for exploiting a modern OS might have, I figure kernel PRNG prediction to be very, very far down the list of things to try.
That being said, [1] from 2012. The challenge with security is that structural weaknesses can take a long time to be discovered but once they are it’s catastrophic. Modern Linux finally switched to CSPRNG and proper construction and relies less on the numerology of entropy estimation it had been using (ie real security instead of theater). RDRAND has also been there for a long time on the x86 side which is useful because even if it’s insecure it gets mixed with other entropy sources like instruction execution time and scheduling jitter to protect standalone servers and iot devices.
Of course you hit the nail on the head in terms of the challenge of distinguishing security theater because you won’t know if the hardening is useful until there’s a problem, but there’s enough knowledgeable people on it that it’s less security theater than it might seem if you know what’s going on.
[1] https://www.usenix.org/system/files/conference/usenixsecurit...
the greatest danger is right after boot where it's possible the kernel didn't have enough randomness to mix in yet. not as much of an issue on modern systems.
cloning/snapshotting VMs might have entropy problems, but a proper VM manager will also inject entropy into the VM on boot
I also believe there were some android ASLR issues based on the same weakness (i.e., low early boot-time entropy).
But this is all quite old, and there've been massive improvements. Basically, "don't use a very old linux kernel" is your mitigation for these issues.
If you have bad PRNG, you should be able to quantify it in terms of bits. The Debian bug resulted in 15 bits of randomness, since all inputs to the PRNG were erased except for the pid, which was 15 bits at the time.
Another real-world example, albeit not Linux. I once worked on a program that had the option of encrypting save files. The encryption was custom (not done by me!) and had a bit of an issue. The encryption itself was not bad, but the save file's master encryption key was generated from the current time. This reduced the number of bits of randomness to well within brute-force range, especially if you could guess at roughly when the key was created. This was convenient for users who had lost their passwords, but somewhat less convenient for users who wanted to actually protect their data.
An attacker isn't going to spontaneously try breaking your PRNG, but if you do have an issue, it's a real concern. It'll be far down the list of things to try just because any modern system will hopefully have very good randomness.
They are actually pretty poor random number generators. For starters, dice are chaotic, not random, the outcome is based entirely on initial conditions. For humans rolling dice, the space of initial conditions can become surprisingly constrained, especially if the human wants to achieve specific outcomes.
Oh, people hate it… and even someone I definitely look up to.
You‘re absolutely right, though, I don‘t remember it being that bad, and probably I just read over it when resurrecting the article, because I‘m so familiar with every word.
I‘ll slap some <hr> tags on it when I‘m back home from my holiday.
Definitely a lot more readable! Something must have changed in the meantime.
It looks like some links have gone too, like the one in the sentence "how does /dev/random know how much entropy there is available to give out?"
This'll all wait for later, hope you're enjoying a nice mai tai on your holiday.
Oh wow.
I want to know as much as you're willing to write about how Deadpool is hard to follow. (A shot-for-shot commentary track would be ideal.)
A CSPRNG is just an algorithm that uses some entropy as a key and feeds back on itself to generate a stream of random bytes. It is a way of expanding a small bit of entropy into a much larger sequence of random values.
From that you can derive the underlying objection here: estimating entropy, blocking /dev/random, and all the other noise is equivalent to saying "cryptography doesn't work". It is both wrong and pointless.
The only place it matters is at boot when there is no hardware source of randomness _which excludes pretty much all PCs which have hardware generators_. You need a true random key to start the CSPRNG but that's it. If you don't have a hardware unit you use time of arrival of the next network packet. Or the frequency of keystrokes on the keyboard.
Now you might ask: why bother seeing the entropy pool at all? The answer is Perfect Forward Secrecy. By mixing in new randomness you are effectively slowly swapping out the key used for the encrypted stream. Thus even if someone is able to compromise something based on guessing the random number sequence your CSPRNG generated their guesses will get more and more wrong as new entropy enters the pool eventually becoming useless. This is a defense-in-depth policy though, not a practical attack mechanism.
On linux it is unfortunate that /dev/urandom has the property of silently vending non-random bytes on hardware without an RNG just after boot and that /dev/random was designed to block when the magical fairies say so but of the two failure modes /dev/urandom is the least bad because practically most hardware (even embedded hardware these days) simply can't encounter its failure mode.
You say yourself that there is a distinction. CSPRNGs can generate unpredictable ("random") bytes, given entropy. They cannot, however, produce entropy. They are entirely deterministic.
Entropy gas to be gathered. It cannot be generated. Therefore, there is a meaningful distinction between the input entropy and output random bits.
I do agree that once the PRNG is sufficiently initialized, it does not make sense to say that “entropy ran out”, however. Given a 256 bit key, modern PRNGs can generate unpredictable bit streams of sizes that will practically never be exhausted.
I couldn’t find any good way to debug it and a friend suggested GDB. I had never thought of using such a low level debugger on a scripting language, but what choice did I have? Fired it up, found a blocked process and sure enough it was blocked on reads to /dev/random.
I leaned two things that day: the decision to make and keep /dev/random blocking was dumb and GDB (or lldb, or valgrind, etc.) is useful for debugging just about anything.
The author is on holiday (and enjoying their birthday!) and will get to it when they're back home.
[1] https://web.archive.org/web/20140309183752/http://www.2uo.de...
Were the man page musings written in response to the (alleged, but... uh... NSA) kleptographic backdoor in Dual_EC_DRBG? It requires multiple successive outputs to compromise and derive internal PRNG state, if memory serves.
In that one construction, /dev/random blocking on seeding would have a mild state-hiding advantage over /dev/urandom, I imagine... but, sheesh. Nobody use that generator.
Edit: can't count.
Of course, when searching for man urandom you still found the old versions at the top of the search results for years and years afterwards. And the German Wikipedia page will probably never change.
> Note from 2024: This article was published on March 16th, 2014. It is still correct in its discussion of entropy and randomness, but the Linux kernel random number generator has been reworked several times since then and does not look like this anymore. Good news: the separation between /dev/urandom and /dev/random is practically gone.
My understanding is that on modern Linux system:
At early boot phases, /dev/random can still block, because not enough entropy has been seeded yet. /dev/urandom will not block, but the random data might be of poor quality and not suitable for crypto purposes. This happens very early in the boot, so probably it's not even possible to run user stuff at this time. At least on my laptop, the message "random: crng init done" gets logged almost instantly after boot and long before even initrd starts. Might be different for exotic platforms, I guess.
Once there was enough entropy seeded, both /dev/random and /dev/urandom works identically, they don't block and they return high quality random data. So for most userspace purposes, these files can be used interchangeably, one is not better than another.
I hate it when updates, migrations or cosmic radiation break fidelity.
Unless you're doing something at the quantum level (maybe) this is true of every random number generator.
Myth: the moon is made of green cheese.
Fact: the moon is made of yellow and green cheese.OpenBSD didn't exist yet when /dev/random and /dev/urandom were created for Linux.
OpenBSD was using an insecure PRNG before 2014 when they upgraded to ChaCha20 to replace RC4. Yarrow came about in 1999 with Fortuna following in 2003 as a more secure version. Apple switched to Fortuna in 2020 while Linux switched to ChaCha20 in 2016.
Windows is possibly in the strongest position using SHA-1 prior to Vista but the specific details are largely unknown. There were known weaknesses found in Windows 2000 which used RC4 (the same thing OpenBSD was using until 2014). They migrated to AES-CTR-DRBG at least from 2019.
So 30 years ago, that's 1996 and everyone was basically some form of insecure. 20 years ago, we're in the early 2000s and probably FreeBSD was the first to start trying to secure but their implementation was quite weak (Yarrow was a good step but it was weak). It took up until about the mid 2010s for everyone to migrate and Linux was not the first nor the last.
The strongest I'll say is that Theodore Ts'o's objections to Yarrow have not stood the test of time (Yarrow itself was weak, but the argument against CSPRNG in favor of entropy numerology was incorrect). Linux similarly has made some troubling statements when it comes to security / cryptography. I think those cultural things are the things that give a certain impression even though technically Linux does seem to have ultimately navigated to a decent position overall.
Short-lived isolated VMs (like might be used for CI) are one place where entropy can be a problem. The relevant definition of “platform” here is less about the CPU architecture and more about the environment.
Just yesterday I encountered people complaining about a VM not connecting to a cloud service when they neglected to put their DNS server’s address in the config for the DHCP server used by that particular host. And a dysfunctional RNG is much more difficult to detect.