I could be wrong, but this is what I think happened.
My basic understanding is that, in typical BSD/Linux fashion, it comes down to a philosophical question.
“Is there ever a case where a user would use a worse source because it is faster?”
The Linux view is of course “Maybe, so we should support it”, and so the /dev/urandom (short of unlimited random) source is provided. It doesn’t block, makes a best-effort at randomness, and is useful for things like shredding disks in a timely fashion. However, they still have the /dev/random source, which can block for quite some time, that is guaranteed to make artisinal organic free-trade entropy in bespoke batches for whomsoever asks.
The BSD (at least OpenBSD, maybe FreeBSD as well but am unsure) view is:
There should be one (1) place to get randomness.
If it’s too slow for normal use we’ll find a way to make it fast to use everywhere.
Giving users more than one option for this is going to lead to subtle fuckups.
So far, it appears that the OpenBSD folks are correct.
Making /dev/random just work would not break any existing applications. It’s not possible to depend on /dev/random blocking because it’s not possible to determine when or if it will do so.
That’s the narrative I’m used to, and I guess it’s probably more or less correct. I looked at the history a bit, and Linux is definitely the first UNIX to have both /dev/random and /dev/urandom, implemented by Ted Ts'o (which I think I knew but forgot). It seems that ever operating system that adopted it basically threw out the distinction between /dev/random and /dev/urandom and symlinked the latter to the former, and then added the “block until entropy estimate hits a certain threshold and then never block again” behavior. So, they did it right, essentially.
This is pretty interesting, and I’ll probably be reading it start to finish. If I find a clear statement of the motivation, I’ll post back here.
What’s clear is that Ted Ts'o seems to think it’s a good idea to use /dev/random for generation of “long-lived” keys, but I can’t figure why he thinks that. If he thinks that some flaw in the CSPRNG algorithm might be discovered (which is my best guess), then I don’t understand how he thinks /dev/random will solve the issue: either the PRNG is “CS” or it’s not, no?
I think the attack Linux’s /dev/random is intended to prevent is keeping the kernel PRNG from reseeding and then pulling out enough random numbers to predict the result of future calls. (In principle this is always possible, because a PRNG by definition produces only a finite number of different output streams; read enough output to know which stream you’re looking at and you can predict every additional number that comes out of it. In practice, of course, the PRNG must be broken six ways from Sunday for this to be feasible.) /dev/random prevents this by disallowing stringing out the PRNG without reseeding.
Attacks like this have been carried out (attacks on weak RNG on online poker sites, for instance), though AFAIK entirely against non-CS PRNGs. The blocking /dev/random approach has the interesting property of preventing prediction attacks even if the PRNG is broken, but this is not a high-impact property.
Okay, so that’s cute, but it also strikes me as totally bizarre. Two things strike me as the bizarre-est:
Let’s say the PRNG is broken, and we’re reading from /dev/random when it lets us. So instead of relying on the output of the PRNG to be unpredictable — which, to my understanding, is a well-studied issue — we’re relying on the entropy estimation to be meaningful. Is the latter well-studied? What kind of trust should we place in that? And, following Ts'o’s advice, having generated our long-lived key with a known-broken RNG, what does having read form /dev/random buy us, exactly?
You mention this:
keeping the kernel PRNG from reseeding and then pulling out enough random numbers to predict the result of future calls
This doesn’t seem to match (to my untrained brain) the assertion that if the PRNG has been seeded with enough entropy (say, 256 bytes as the posted article suggests) that the output is as random as needed for any cryptographic purpose. Do you mean the above in the case where the PRNG is broken? Is it just that the amount of random numbers you’d have to pull from a “good” PRNG is so large as to be computationally infeasible, whereas for a totally borked PRNG it just might be feasible?
So instead of relying on the output of the PRNG to be unpredictable — which, to my understanding, is a well-studied issue — we’re relying on the entropy estimation to be meaningful.
Essentially, yes.
Is the latter well-studied?
It’s not unstudied. I don’t know enough information theory to say for sure. Estimating entropy is a Hard Problem, and I’m almost sure I can remember effective /dev/random-poisoning attacks from controlling something the kernel uses as an entropy source—network interface packet timing, for instance.
Estimating the predictability of a PRNG is essentially the same problem, but you get to do it offline at your leisure before implementing the thing, rather than on the fly in realtime.
what does having read form /dev/random buy us, exactly?
Confidence that we weren’t victims of an RNG prediction attack, and possibly a long wait.
I should maybe note that I’m not trying to defend these design decisions—just explain what are, to the best of my knowledge, the justifications for them. I don’t think attacks on a CSPRNG are anywhere near enough of a credible concern for all this rigamarole.
Is it just that the amount of random numbers you’d have to pull from a “good” PRNG is so large as to be computationally infeasible, whereas for a totally borked PRNG it just might be feasible?
Exactly this. A simple linear congruential PRNG (N_x = (a N_(x-1) + b) % m) can be broken (have its internal state N_x, a, b, m recovered) from just a handful of sequential outputs; good CSPRNGs have the same attack resistance properties as good key-based ciphers, that is, mathematically speaking they can be reversed, but practically speaking, it would require more energy than exists in the universe.
Proof that any PRNG can, in principle, be broken like this is actually very straightforward by the pigeonhole principle. By definition, a PRNG has a finite amount of internal state from which it generates its pseudorandom numbers (otherwise it would be an actual random number generator). Thus, it can produce at most as many different sequences as it has states (in actuality, it will produce many fewer; ideally, it will produce only one, with each internal state corresponding to a different point along that sequence, but proving that this happens for a CSPRNG is, for all intents and purposes impossible). Since there are only finitely many possible output sequences, we can, given enough sequential outputs from the PRNG, know which one we’re looking at.
It’s not clear to me whether it’s true, and I strongly suspect that it isn’t, but I believe there was at one time an idea that /dev/random produced “true” entropy as opposed to pseudorandomness. Additionally, there appears to be a notion that mixing the two kinds produces something of intermediate utility.
I note that the first is an easily answered implementation question, and the second is a number theory question. It’s possible the latter has been studied in relation to key stretching algorithms, and it’s probably worth reading about those if somebody cares, but I haven’t seen anybody actually claiming there is a theoretical basis for the claim, so…
So, here’s a question for y'all:
Does anyone know the history of how Linux ended up both
/dev/randomand/dev/urandom?If I recall correctly, no other Unix as this, so I’m pretty curious about this.
I could be wrong, but this is what I think happened.
My basic understanding is that, in typical BSD/Linux fashion, it comes down to a philosophical question.
“Is there ever a case where a user would use a worse source because it is faster?”
The Linux view is of course “Maybe, so we should support it”, and so the
/dev/urandom(short of unlimited random) source is provided. It doesn’t block, makes a best-effort at randomness, and is useful for things like shredding disks in a timely fashion. However, they still have the/dev/randomsource, which can block for quite some time, that is guaranteed to make artisinal organic free-trade entropy in bespoke batches for whomsoever asks.The BSD (at least OpenBSD, maybe FreeBSD as well but am unsure) view is:
So far, it appears that the OpenBSD folks are correct.
The more choices the user makes, the more freedom they have!
What’s more incredible is how damn resistant the Linux maintainers have been to change in the face of reality.
At this point removing one of them would amount to terribly backwards-incompatible API change.
Edit: Off-topic downvotes? I might be incorrect, but I thought this was on point of the discussion…
Making /dev/random just work would not break any existing applications. It’s not possible to depend on /dev/random blocking because it’s not possible to determine when or if it will do so.
Right, of course. I don’t know why I couldn’t came up with making both of them work the same way.
That’s the narrative I’m used to, and I guess it’s probably more or less correct. I looked at the history a bit, and Linux is definitely the first UNIX to have both
/dev/randomand/dev/urandom, implemented by Ted Ts'o (which I think I knew but forgot). It seems that ever operating system that adopted it basically threw out the distinction between/dev/randomand/dev/urandomand symlinked the latter to the former, and then added the “block until entropy estimate hits a certain threshold and then never block again” behavior. So, they did it right, essentially.This is pretty interesting, and I’ll probably be reading it start to finish. If I find a clear statement of the motivation, I’ll post back here.
What’s clear is that Ted Ts'o seems to think it’s a good idea to use
/dev/randomfor generation of “long-lived” keys, but I can’t figure why he thinks that. If he thinks that some flaw in the CSPRNG algorithm might be discovered (which is my best guess), then I don’t understand how he thinks/dev/randomwill solve the issue: either the PRNG is “CS” or it’s not, no?I think the attack Linux’s
/dev/randomis intended to prevent is keeping the kernel PRNG from reseeding and then pulling out enough random numbers to predict the result of future calls. (In principle this is always possible, because a PRNG by definition produces only a finite number of different output streams; read enough output to know which stream you’re looking at and you can predict every additional number that comes out of it. In practice, of course, the PRNG must be broken six ways from Sunday for this to be feasible.)/dev/randomprevents this by disallowing stringing out the PRNG without reseeding.Attacks like this have been carried out (attacks on weak RNG on online poker sites, for instance), though AFAIK entirely against non-CS PRNGs. The blocking
/dev/randomapproach has the interesting property of preventing prediction attacks even if the PRNG is broken, but this is not a high-impact property.Okay, so that’s cute, but it also strikes me as totally bizarre. Two things strike me as the bizarre-est:
Let’s say the PRNG is broken, and we’re reading from
/dev/randomwhen it lets us. So instead of relying on the output of the PRNG to be unpredictable — which, to my understanding, is a well-studied issue — we’re relying on the entropy estimation to be meaningful. Is the latter well-studied? What kind of trust should we place in that? And, following Ts'o’s advice, having generated our long-lived key with a known-broken RNG, what does having read form/dev/randombuy us, exactly?You mention this:
This doesn’t seem to match (to my untrained brain) the assertion that if the PRNG has been seeded with enough entropy (say, 256 bytes as the posted article suggests) that the output is as random as needed for any cryptographic purpose. Do you mean the above in the case where the PRNG is broken? Is it just that the amount of random numbers you’d have to pull from a “good” PRNG is so large as to be computationally infeasible, whereas for a totally borked PRNG it just might be feasible?
Essentially, yes.
It’s not unstudied. I don’t know enough information theory to say for sure. Estimating entropy is a Hard Problem, and I’m almost sure I can remember effective
/dev/random-poisoning attacks from controlling something the kernel uses as an entropy source—network interface packet timing, for instance.Estimating the predictability of a PRNG is essentially the same problem, but you get to do it offline at your leisure before implementing the thing, rather than on the fly in realtime.
Confidence that we weren’t victims of an RNG prediction attack, and possibly a long wait.
I should maybe note that I’m not trying to defend these design decisions—just explain what are, to the best of my knowledge, the justifications for them. I don’t think attacks on a CSPRNG are anywhere near enough of a credible concern for all this rigamarole.
Exactly this. A simple linear congruential PRNG (
N_x = (a N_(x-1) + b) % m) can be broken (have its internal stateN_x,a,b,mrecovered) from just a handful of sequential outputs; good CSPRNGs have the same attack resistance properties as good key-based ciphers, that is, mathematically speaking they can be reversed, but practically speaking, it would require more energy than exists in the universe.Proof that any PRNG can, in principle, be broken like this is actually very straightforward by the pigeonhole principle. By definition, a PRNG has a finite amount of internal state from which it generates its pseudorandom numbers (otherwise it would be an actual random number generator). Thus, it can produce at most as many different sequences as it has states (in actuality, it will produce many fewer; ideally, it will produce only one, with each internal state corresponding to a different point along that sequence, but proving that this happens for a CSPRNG is, for all intents and purposes impossible). Since there are only finitely many possible output sequences, we can, given enough sequential outputs from the PRNG, know which one we’re looking at.
It’s not clear to me whether it’s true, and I strongly suspect that it isn’t, but I believe there was at one time an idea that /dev/random produced “true” entropy as opposed to pseudorandomness. Additionally, there appears to be a notion that mixing the two kinds produces something of intermediate utility.
I note that the first is an easily answered implementation question, and the second is a number theory question. It’s possible the latter has been studied in relation to key stretching algorithms, and it’s probably worth reading about those if somebody cares, but I haven’t seen anybody actually claiming there is a theoretical basis for the claim, so…
The solution to fuckups is education, not paternalism.
We are all adults here.
Offering two okay solutions instead of one good solutions is not fighting paternalism….it is showing poor judgement.
All evidence to the contrary… :(