Copyright © 2013 jsd

*   Contents

1  Some Questions
2  Discussion
3  Background and Context
4  Some Experiments
5  References

Observations and Questions Concerning
Linux /dev/random and /dev/urandom

John Denker

1  Some Questions

Here are some specific observations and questions about the code in drivers/char/random.c. Line numbers refer to release 3.11.

  1. The device incorporates several thousand bits of buffers. Buffering is needed, because the demand for entropy can be very bursty. So far so good.

    However, this leaves us with a basic question about architecture and strategy, because the device is operated in such a way that the buffers are almost always empty or nearly so. Observations indicate that the input pool is almost always at or below 192 bits, and the other pools are almost always at zero.

    That is not enough entropy for expected uses such as cutting PGP keys. This seems to conflict with the stated purpose of /dev/random, and the purpose of having buffers within the device.

  2. The input pool performs multiple functions, including mixing, storage, and concentration via hashing. So far so good.

    In contrast, the output pool associated with /dev/random does not need to perform any of those functions. It therefore seems odd that it has the same complex structure as the input pool. It needs no mixing and no hashing, because (unlike the input pool) it is being fed from a source of concentrated, high-grade randomness, i.e. an entropy density of 8 bits per byte. It seems one could get rid of this pool entirely, thereby improving memory usage and computational efficiency, with no harm to security, indeed no downside at all.

  3. Similarly, the pool associated with /dev/urandom does not need to perform any mixing, and needs considerably less storage than it presently uses. That’s because in effect, it operates as a PRNG based on using SHA1 in counter mode, using the pool as an enormous counter. In contrast, simple, efficient, well-understood counters (with suitable anti-backtracking) would seem more logical than not-well-characterized polynomials whose security seems to be based on the assertion that «the irreducible factors of a random large-degree polynomial over GF(2) are more than large enough that periodicity is not a concern.»
  4. The hashing that goes on in /dev/urandom contains some feedback, to provide anti-backtracking. This is good.
  5. The entropy-estimates returned via the /proc interface and the ioctl interface include only the entropy in the input buffer, to the exclusion of the /dev/random output buffer. This gives rise to unreliable estimates if/whenever the output buffer contains nonzero entropy.
  6. Please explain the reasoning on line 820. An engineering decision needs to be made concerning how much entropy to reserve. I see no reason why the right answer is in any way related to the wakeup threshold. It would make somewhat more sense to use half of the poolsize or more. It would make even more sense to use an adaptive strategy, based on cooperative resource-sharing, I have code that does this, leading to a pool that is almost always full (rather than almost always nearly empty).

    Rationale: It is desirable to have a reasonably large amount of entropy stored in the driver’s “input pool”. That’s because the demand for high-grade randomness (via /dev/random) is very bursty. When cutting a key, there is commonly a sudden demand for several hundred bits, if not more. Therefore, in the common situation where there is a steady moderate load on /dev/urandom and a bursty load on /dev/random, the current code has a serious performance problem, due to not enough stored entropy. Increasing the reserved entropy would greatly improve the usefulness of /dev/random and would have no impact on /dev/urandom.

    To say the same thing the other way, right now there is no maximum on the amount of entropy that /dev/urandom can take from the “input pool” whenever the pool entropy is more than twice the wakeup threshold. There should be a much lower limit. Making the entropy density of /dev/urandom any higher than it needs to be just wastes entropy. It does not materially increase the security of /dev/urandom, and it harms /dev/random.

    I have code that deals with this, using an adaptive, cooperative resource-sharing approach. The result is that the input pool is almost always full, rather than almost always nearly empty.

  7. Please explain the logic on line 832. The “min” argument to extract_entropy is supposed to guarantee that updates occur in batches, where the batch-size is large enough so that the adversary cannot figure out what happened. See reference 1 for why batching is important. It is understandable that the wakeup threshold should be no less than the batch size, but I see no reason why these two quantities should be numerically equal in general, much less that why the code should make no distinction between them even at the conceptual lvel. Note that the wakeup threshold can be changed at runtime by a privileged user; it seems a compiled-in constant might make more sense. A value of 20 bytes (160 bits) is reasonably conventional; see reference 1.
  8. On line 802 we find the extract_entropy() function. However, this function is commonly applied to the nonblocking pool, which almost never contains any entropy whatsoever, so the function name must be considered somewhat less than reliably informative. The comments e.g. on line 796 are equally misleading and unhelpful. The word “entropy” must not be used as a synonym for “randomness”, especially if one’s notion of randomness includes pseudo-randomness.
  9. There is no guaranteed lower bound on the rate at which the /dev/random output pool will be reseeded. In other words, there is no guarantee on how quickly it will recover from compromise. In particular, if there is a demand on /dev/random that exceeds the rate at which entropy is available, the available entropy in the “input pool” will be chronically low, and /dev/urandom will never be reseeded.

    It would seem there needs to be some sort of load-balancing, so that /dev/urandom gets enough entropy to reseed itself sufficiently often. See reference 1 for why this is important.

    Fixing this is not a trivial exercise, but I have some code that seems to be a significant improvement.

  10. The semantics of “nbytes” seems broken, either in the way it is calculated on line 818 or in how it is used. Early on, nbytes is compared to the amount already in the buffer, as if it were the target amount we want to have after the transfer. Later, nbytes is interpreted as an amount to transfer. Among other things, this means it is impossible to transfer "a little bit more" to an already mostly-full pool.

    There is no documentation as to the semantics of "nbytes". Furthermore, the variable name exhibits a classic poor programming practice. It tells us that "n" is measured in "bytes", but it tells us nothing about the semantics of "n". It is important to keep track of the units of measurement, as the Mars Climate Orbiter mission discovered – but that is not the whole story. By way of analogy, kinetic energy, potential energy, lagrangians, torque, and lots of other things can all be measured in the same units, but the semantics is very different.

    My best guess is that the code needs to do a subtraction to calculate the amount to be added. If this is not right, somebody should please explain what is going on.

  11. If I set the read wakeup threshold to 1000, sometimes /dev/random blocks when there is reportedly still more than 500 bits of entropy in the input pool, according to /proc/sys/kernel/random/entropy_avail. This means that .../entropy_avail is not a reliable estimate of how much entropy is actually available.

    On the other hand, sometimes reading from /dev/random can drain the entropy_avail all the way to zero.

    I do not understand what I am seeing here.

  12. On line 976 , the call to extract_buf() is not associate with a call to account(). If this is not a bug, please explain why every other extract_buff() is associated with an account(), but this one is not.
  13. The comment on line 819 seems to be backwards. As you can see from the code on the next line, the notion of reserved entropy applies when the operation is not “limited” i.e. when it is non-blocking.
  14. The DEBUG printout on line 816 almost certainly doesn’t mean what it says.
  15. How come extract_entropy_user() does not have a FIPS section, while the seemingly similar extract_entropy() does?
  16. It appears that the ioctl interface is not documented in random.c nor on the manpage Linux random(4).
  17. It appears the the semantics of writing to /dev/random is not documented in random.c nor on the Linux manpage random(4).

2  Discussion

Typically /dev/urandom consumes either too much entropy or not enough entropy. Observations indicate that in the typical case, there is a moderately high demand on /dev/urandom. Then, if the available entropy is above the reserve, /dev/urandom gobbles up essentially all new incoming entropy (not all at once, but sooner or later, in batches). This is too much. On the other hand, if the available entropy is below the reserve, /dev/random uses none of the entropy, which is too little.

In other words, the normal load on /dev/urandom is tantamount to a denial-of-service attack on /dev/random, because the reserved available entropy – 128 bits – is not enough for ordinary applications, which tend to place a brief but sudden high demand on /dev/random, demanding several hundred bits all at once.

Conversely, a rather modest load on /dev/random is tantamount to a denial-of-service attack on /dev/urandom, insofar as it means that /dev/urandom will never get reseeded, i.e. will never recover from compromise.

The existing version is partly yarrow-like and partly not. It is yarrow-like in the sense that it performs updates in batches, with a substantial minimum batch-size. It is non-yarrow-like in that it presents far too much load on the upstream source of entropy.

I have some code that makes it possible to do resource-sharing.

3  Background and Context

Reference 2 asserts that /dev/random is “not robust” but their definition of “robust” has not met with universal acceptance.

I disagree with the assertion that it is «perhaps impossible» to to obtain a proper estimate of the entropy-content of a source. A constructive counterexample is provided in reference 3.

4  Some Experiments

Figure 1 records some observations of the behavior of /dev/random.

Figure 1: Reported Available Entropy versus Time

Here are the conditions of the experiment:

I don’t understand the details, but all evidence suggests that the exec consumes 256 bits from /dev/urandom. You can see this clearly in the figure, in the section from time t=0 to t=180 seconds. Every time there is an exec, the reported entropy drops. The amount of drop is shown by the red dots in figure 1. The entropy is measured immediately before and immediately after each exec, so it is hard to imagine that there is any other explanation for the drop.

The initial condition – i.e. a relatively high entropy at t=0 – would be highly unusual for a system not running turbid.

In contrast, the section from time t=180 seconds onward should be considered the normal situation for a system not running turbid. There is something in the kernel – I don’t know what – that is contributing entropy to the /dev/random pool at the rate of approximately 1.2 bits per second. You can see this in the slight upward slope of the graph. Meanwhile, the long-term average entropy-output via /dev/urandom exceeds the long-term intropy-input. The result is that the available entropy in the pool is (a) very small and (b) exhibits a sawtooth pattern. As soon as the pool entropy gets above 192 bits, the next time there is any load the entropy drops by 64 bits, dropping down to slightly more than 128 bits. In more detail, if you read the code in drivers/char/random.c, you discover that the magnitude of the drop, i.e. the height of the tooth, is equal to the “read_wakeup_threshold” which is normally 64 bits but can be changed at runtime via /proc/sys/kernel/random/read_wakeup_threshold. The lower bound of the sawtooth is twice this number.

The device would be in some ways better and in no ways worse if the lower bound were higher, several thousand bits higher.

We should also consider a situation not shown in the diagram, namely a situation where there is a small long-term demand on /dev/random. This could easily exceed the long-term entropy-input. This would cause the process reading /dev/random to be rate-limited, which is undesirable but not fatal. What’s worse is that in this situation exactly zero bits of entropy would be used for /dev/urandom. The PRNG will never get rekeyed.

5  References

J. Kelsey, B. Schneier, and N. Ferguson,
“Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator”,
in Sixth Annual Workshop on Selected Areas in Cryptography, Springer Verlag, August (1999).

Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergnaud, and Daniel Wichs
“Security Analysis of Pseudo-Random Number Generators with Input:
/dev/random is not Robust”

John Denker,
“Turbid : A High-Entropy Randomness Generator”

Copyright © 2013 jsd