Insecurities in the Linux /dev/random

https://www.schneier.com/blog/archives/2013/10/insecurities_in.html

by e1ven • 13 years ago

123 74 13 years ago

buo11• 13 years ago

From the abstract: "A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform."

I think this is incorrect, since it would imply that a program that produces the sequence 1,2,1,2,1,2,1.... is a PRNG.

gvb2• 13 years ago

Not all deterministic algorithms with uniform distributions are PRNGs.

buo11• 13 years ago

I know that, but that is what the first sentence in the paper's abstract is claiming. As I said, I think it's wrong.

syzo2• 13 years ago

you can also check that (1,1), (1,2), (2,1), and (2,2) all happen with expected frequencies (i.e. roughly 25%), where the two numbers in the pair are just two numbers in a row in the sequence. You would have gotten 100% (1,2) and 0% for the rest, so that's suspicious.

same for 3-tuples, 4-tuples, ..., and n-tuples.

There's probably other, more sophisticated tests as well, but I'm not an expert.

buo11• 13 years ago

I think you missed my point, which is this: the first sentence in the paper's abstract is wrong.

phaemon2• 13 years ago

Nope, because you don't have the same number of 9s and 8s as 1s and 2s, so it's not uniform.

buo11• 13 years ago

I don't think you're correct. A discrete distribution can be defined for any number of values. Linux, which is the subject of the paper, uses a discrete distribution too.

mcherm2• 13 years ago

No, your sequence IS distinguishable from a uniform sequence. At least it is if I understand what you mean by "...".

If you mean that it generates 1,2,1,2,1,2,1 and then after that generates a mix of different values that include all possible values in approximately equal frequency, then you may have a fairly good PRNG. If you mean that it produces 1,2,1,2,1,2,1 and then after that it continues to alternate between 2 and 1, then this is easily distinguished from uniform.

buo11• 13 years ago

But I never said it was indistinguishable. What I'm saying is that the definition in the first sentence of the paper is wrong or, at least, incomplete.

pmelendez5• 13 years ago

"No, your sequence IS distinguishable from a uniform sequence." No, it is not distinguishable. The definition according to wikipedia: The discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n.

So the distribution is indeed uniform but it fails in being random.

andrewcooke3• 13 years ago

you're quoting the first sentence from the abstract in isolation; there's a lot more detail in the paper. in particular the define the notion of epsilon-closeness (section 2) for any distinguisher (which could include one that detects repeated patterns).

buo11• 13 years ago

My intention is not to criticize the paper, which I don't even claim to understand. I just thought the authors definition of a PNRG is wrong (or at least incomplete) and that caught my attention. If I'm wrong, I hope somebody will set me right.

manulp• 13 years ago

This sequence is trivially distinguishable from something uniform.

deutronium• 13 years ago

Using ent, and 0's and 1's (instead of 1's and 2's).

(By this I mean a pattern of 0,1,0,1 bits etc. - 4248759 bytes worth in this case)

Below is the output from ent:

----------------------------

Entropy = 0.000000 bits per byte.

Optimum compression would reduce the size of this 4248759 byte file by 100 percent.

Chi square distribution for 4248759 samples is 1083433545.00, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 170.0000 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is undefined (all values equal!).

bmm6o3• 13 years ago

I don't think people understand what your point is. What do you think is missing from the sentence? An explicit mention of independence? Why do you think 1,2,1,2,1,2,... is indistinguishable from uniform? In another response you said

But I never said it was indistinguishable

which is confusing in context. What properties do yo claim your sequence has?

buo11• 13 years ago

I'm sorry for being unclear.

The authors define a a PRNG as a sequence such that, if you find its distribution (histogram), it resembles the uniform distribution (all values appear the same number of times).

In 1,2,1,2,1,2,..., all values appear the same number of times and its histogram is uniform. However, it is not random. It is clearly not random -- so it is distinguishable from a uniform "true random" sequence, which was my point.

However, as was explained to me by another commenter, what I missed is that you may group a number of consecutive numbers together and find the histogram of that, and, in that case, my sequence fails to have a uniform histogram.

So, at this point I'm willing to accept that the author's definition is correct and I just had a hole in my understanding.

mistercow• 13 years ago

I am not terribly good with statistical terminology, but I don't think that the definition you're assuming for "uniform distribution" is the one in general use. Once you know a[n], a[n+1] will follow a delta distribution, not a uniform distribution.

akjj• 13 years ago

Clearly, a PRNG is a subtle concept and it's common for abstracts to not be completely precise. In context, it's clear to me that by "uniform" they mean "a random process which generates numbers independently from a uniform distribution." Your process is generating numbers uniformly, but successive outputs are definitely not independent.

One reason why I feel your interpretation is strained is that the phrasing makes "uniform" sound like a single process. You seem to be reading it as "numbers which are distributed uniformly," but the word indistinguishable really suggests that it's more than just the distribution that matters.

betterunix3• 13 years ago

The sequence 1,2,1,2,1,2,1... is not indistinguishable from a uniform sequence, at least in the context of cryptography. With high probability, an algorithm that checks if all the even indexed inputs are 1 and all the odd indexed inputs are 2 will distinguish that sequence from a uniform random sequence (this is easy to see, as the probability of a sequence of that form being generated by repeatedly tossing a fair coin is very small).

tiagobraw• 13 years ago

why not 4, 4, 4, 4, 4,... ;)

obligatory: http://xkcd.com/221/

poizan42• 13 years ago

Or: http://dilbert.com/strips/comic/2001-10-25/

tptacek6• 13 years ago

This is an interesting paper that was discussed widely on Twitter a few months back. It includes a very useful breakdown of the Linux kernel CSPRNG starting on page 17. The attacks the paper describes start on page 22. The front part of the paper is dominated by a discussion of the theoretical modeling of CSPRNGs, in part because the theoretical foundations for CSPRNGs and their interactions with applications are not well documented.

The most important bit of information you probably want to know about this paper is that it is modeling the security of a CSPRNG when its entropy inputs are entirely controlled by attackers. For instance, one of the attacks involves tricking the entropy estimator into believing it's seeding itself with high-quality random data when that data in fact has no entropy.

This is not a realistic attack scenario for the vast majority (maybe all) of applications.

Having said that, the Linux kernel CSPRNG doesn't (as far as I know) have a particularly well formalized design. There are good CSPRNG designs out there; for instance, the BSDs use Yarrow, and Ferguson followed that design up with Fortuna, which dispenses with the need for entropy estimators altogether.

XorNot• 13 years ago

Wouldn't this in fact be completely unrealistic? If attackers have full control of entropy inputs, they can just hook up a very high quality randomness source, but record every single bit before it gets to /dev/random.

Of course, why bother with that if you have that kind of access?

plantsbeans• 13 years ago

Using a "false entropy" model feels partially like a response to criticism of things like RdRand, for example.

tytso4• 13 years ago

So I'm the maintainer for Linux's /dev/random driver. I've only had a chance to look at the paper very quickly, and I will at it more closely when I have more time, but what the authors of this paper seem to be worried about is not even close to the top of my list in terms of things I'm worried about.

First of all, the paper is incorrect in some minor details; the most significant error is its (untrue) claim that we stop gathering entropy when the entropy estimate for a given entropy pool is "full". Before July 2012, we went into a trickle mode where we only took in 1 in 096 values. Since then, the main way that we gather entropy, which is via add_interrupt_randomness(), has no such limit. This means that we will continue to collect entropy even if the input pool is apparently "full".

This is critical, because secondly their hypothetical attacks presume certain input distributions which have an incorrect entropy estimate --- that is, either zero actual entropy but a high entropy estimate, or a high entropy, but a low entropy estimate. There has been no attempt by the paper's authors to determine whether the entropy gathered by Linux meets either of their hypothetical models, and in fact in the "Linux Pseudorandom Number Generator Revisited"[1], the analysis showed that our entropy estimator was actually pretty good, given the real-life inputs that we are able to obtain from an actual running Linux system.

[1] http://eprint.iacr.org/2012/251.pdf

The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don't want to block, that they end up with keys that aren't very random. We had some really serious problems with this, which was written up in the "Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices"[2] paper, and the changes made in July 2012 were specifically designed to address these worries.

[2] https://www.factorable.net/paper.html

However, it may be that on certain systems, in particular ARM and MIPS based systems, where a long-term public key is generated very shortly after the first power-on, that there's enough randomness that the techniques used in [2] would not find any problems, but that might be not enough randomness to prevent our friends in Fort Meade from being able to brute force guess the possible public-private key pairs.

Speaking more generally, I'm a bit dubious about academic analysis which are primarily worried about recovering from the exposure of the state of the random pool. In practice, if the bad guy can grab the state of random pool, they probably have enough privileged access that they can do much more entertaining things, such as grabbing the user's passphrase or just grabbing their long-term private key. Trying to preserve the amount of entropy in the pool, and making sure that we can extract as much uncertainty from the system as possible, are much higher priority things to worry about.

That's not to say that I might not make changes to /dev/random in reaction to academic analysis; I've made changes in reaction to [2], and I have changes queued for the next major kernel release up to make some changes to address concerns raised in [1]. However, protection against artificially constructed attacks is not the only thing which I am worried about. Things like making sure we have adequate entropy collection on all platforms, especially embedded ones, and adding some conservatism just in case SHA isn't a perfect random function are some of the other things which I am trying to balance as we make changes to /dev/random.

tptacek6• 13 years ago

Nit: the cold start entropy problem (specifically in the Linux kernel CSPRNG) was published way before Heninger; Zvi Gutterman presented it at Black Hat in 2006. "P's and Q's" got a lot of publicity, but could some of that exposure have been mitigated had earlier reports been acted on? (I seriously have no idea and am just asking).

The term for the "academic analysis" of "recovering from exposure of state" is "forward secrecy", and from what I can tell the whole of the crypto literature that discusses CSPRNGs in any depth seems to be unified on the opinion that forward secrecy is an important property for a CSPRNG to have.

(But that's a reaction to your comment, not your opinion of the paper, because I agree that the attacks here don't seem very practical.)

What do you think of Ferguson's belief that entropy estimators are a flawed design approach for CSPRNGs? FreeBSD uses Yarrow for this, which has two benefits --- first, it loses the silly notion of a "urandom" that is somehow marginally less secure than "random" but is in practice not actually less secure, and second, it comes from a design that has a formal research track record, that people can analyze from the paper and not solely by reversing code.

(I sound snippy but am in fact thrilled that you took the time to comment, and thank you).

tytso4• 13 years ago

Yes, I'm aware of the concept of forward secrecy, and the formalism around it. Without intending to sound snippy myself, I think there is a tendency for academicians (whose promotion/tenure prospects are directly related being able to generate papers that get published in high impact journals) to be biased in favor of those things for which formal models can be created. We saw that for example in the academic focus on formal proof of correctness of programs, which at this point is recognized as a blind alley, as opposed to a more engineering approach of using tools like valgrind and lint and static program analysis. So I am a bit unpersuaded regarding the academic focus on forward secrecy. It's something that if we can add to a design, I'll certainly do it --- and indeed there is a Yarrow-style "catastrophic reseeding" in the /dev/random design.

We have been moving away from using entropy estimators in /dev/random, actually. We still use it for certain entropy sources, most notably for the keyboard and mouse inputs, where it is useful for filtering out event timings caused by the user leaning on the key and triggering autorepeat. But these days we have a "fast mix pool" (which is per-CPU) where we sample on every single interrupt, and then down-mix from there to much larger entropy pool, and the bulk of the entropy, especially on servers, comes from the fast mix pool.

I tend to focus much more on engineering/social aspects; for example, the fundamental cause of the failure found by the Mining Your P's and Q's paper (as opposed to the hypothetical failures of things like the forward secrecy papers), was people disabling the entropy collection in many/most device drivers because they thought it was too slow for high speed devices, in particular network devices. They made arguments that it was because an adversary could monitor the packet arrival times on the Ethernet (which is not true in a switched fabric anyway, and if the attacker is sitting at Fort Meade, or even at AT&T's data center, they won't know about your local area network), but that was just an excuse; the main reason was engineers who were worried about performance.

So using a fancy "approved by academics" design which uses crypto hashing to mix entropy into the mixing pools may be pointless, if downstream kernel hackers disable the entropy collection "because it's too slow". We now have something hard-wired into the main interrupt code path (it's now no longer optional, so it can't be configured on or off on an individual device driver basis), and I've gone through a lot of work to make it be extremely fast, including using per-CPU pools, worrying about cache effects, etc. These are concerns that I'm sure would never help a professor achieve tenure, but as a practicing engineer, I've been painfully aware about how important these sorts of concerns really are.

Don't get me wrong; I do read the papers from those academics who try to analyze /dev/random, and I appreciate their attention. But I do come from a someone different perspective than they do, and over the years I've learned that it's not wise to blindly take the advice of every single bug report that you get (and I consider papers to be simply formal bug reports :-) since sometimes you can't satisfy every single user and every single bug report.

nullc2• 13 years ago

Their "solution" is also pretty blunt. Basically replacing the whole thing with a construct that looks a lot like AES-GCM (basically using a field multiply to mix in new random state)... which they show is strong for their particular complaint, but would abandon all the existing reasons to have any confidence in the current approach. (and also appears(?) to substantial shrink the random pool size)

ape4• 13 years ago

Its academic papers and discussion from the maintainer like this that makes open source so great.

Tomte• 13 years ago

Actually my impression is that many many user space programs use /dev/random, even for short term keys and nonces and stuff, just because they have learned by "more experienced Linux users" that /dev/urandom is not secure.

Just look at all those "OpenSSL hangs on my server" bug reports and forum posts.

And the man pages are better today than they used to be, but they still don't forcefully dispel that myth.

I really would love to see FreeBSDs /dev/urandom behavior on Linux, i.e. "block once at system start". Yes, you need some kind of entropy estimator for that.

rwmj• 13 years ago

Tips: If you're cloning or creating Linux virtual machines, run virt-sysprep[1] on them. It will insert a new random seed into the cloned VM, ensuring it boots with different entropy from the clone source or other clones from the same source. Secondly, run your VMs with the new virtio-rng driver[2].

[1] http://libguestfs.org/virt-sysprep.1.html

[2] https://fedoraproject.org/wiki/Features/Virtio_RNG

dspillett• 13 years ago

So I'm the maintainer for Linux's /dev/random driver.

Excellent, I can ask instead of going to read the source!

Does the code managing /dev/random make any effort to detect hardware RNGs where available and use those to feed its pool? That way an available proper" random source is feeding the pool as early as possible, before any user-space tool pumping data from a generator to the pool could be started. It is increasingly common for chipsets/CPUs to have some form of HWRNG circuitry built in.

Or is that deemed an over-complication (and potential point of failure) for something that is not currently available on most devices? I'm thinking of chipsets like the SoC used in the RPi which has a built-in HWRNG that is easily accessible once the appropriate module is loaded, and recent Intel CPUs which have one (though I don't know if that is as easy to access ATM).

is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy

I've wondered if this is something we can at least partially address by adding a property to those assigned via DHCP or similar protocols so as well as telling a new device what address it should respond to (and the usual other properties such as name resolution settings and potentially hostname and so forth) would there be room in the protocol to include a small block of random data? If the network setup is done early enough during boot then there will be at least some entropy in the pool before other process start needing it.

Of course this would require that the device handing out addresses and names had a sufficient entropy source of its own, potentially a HWRNG, in order to be able to provide this random data at the rate needed by the prevailing network conditions (the worst case being at if all the hosts on a large subnet pop online at the same time due to recovery from a power-cut and so all want their block of bits at the same time). Also it wouldn't help devices that might not have any network access on first boot but might still need to generate keys ready for when access is available.

Insecurities in the Linux /dev/random

Related Stories