Adding CPU randomness to the entropy pool
Kernel developers, or at least the maintainers of the random subsystem, are always on the lookout for sources of unpredictability for use in the random number pool. In particular, there are a number of scenarios where good random numbers are needed and the available pool is lacking in quality—embedded systems, early in the boot process, virtual machines, etc.—so new sources that can alleviate the problem are generally welcome. However, there is always the question of how much entropy is truly provided by these sources, which is a difficult problem to solve. Two recent patches would contribute unpredictable sources, but take a different approaches with regard to adding to the store of entropy.
The kernel has two separate interfaces for random number generation: /dev/random and /dev/urandom. They are supposed to be used for different purposes, with /dev/random only providing as many bits of randomness as bits of entropy have been added to the pool—blocking if insufficient entropy is available. It is meant to be used for long-lived keys (e.g. the SSH key for the system), while /dev/urandom provides cryptographic-strength pseudo-random numbers without the entropy requirement (and, thus, no blocking). Data read from either device comes from the same pool, but the entropy requirement is only applied for reads from /dev/random.
Unpredictable events measured by the kernel (that cannot be observed by an adversary) make up the input to the entropy pool from which the random numbers are generated. Various kinds of interrupts are used (e.g. intra-key timing from the keyboard, sometimes disk or network device intra-interrupt timing, and so on) and their values are mixed into the pool. As that is done, an estimate of how many bits of entropy are being contributed is added to the entropy count. That estimate is hopefully conservative enough that it underestimates the amount of true entropy in the pool, while trying not to make it impossible to generate a reasonable number of random bits in a reasonable time.
An even more conservative approach would be to add unpredictable data to the pool without crediting any entropy. That is already done with some sources in today's kernel, such as when adding unpredictable device-specific data using add_device_randomness(). There is value in adding "zero credit" (i.e. no entropy contributed) unpredictability to the pool. Any data that is added perturbs the state of the pool, which will change the values produced by /dev/urandom. In some situations, the same random numbers would be produced boot after boot if there were no unpredictable data added.
CPU randomness
"Zero credit" is the approach Jörn Engel took with his CPU randomness patch. It mixes uninitialized stack values with unpredictable values like jiffies into its own pool, then mixes that pool into the normal entropy pool periodically. It clearly adds unpredictability into the pool, but how much entropy it provides is hard or impossible to determine, so Engel gives it no entropy credit.
The patch gathers its info from two kernel locations: the scheduler and the slab allocator. It uses an uninitialized four-element array (input) on the stack and XORs various values into it to produce the input to the private pool. The values used are jiffies, the value of the time stamp counter (TSC), the address where the scheduler and allocator functions will return, a value specific to that invocation of the scheduler or allocator, and the address of the input array itself. It is similar in some ways to the gathering that is done for interrupts for the global pool. This collection and mixing is done quite frequently (whenever need_resched() or __do_kmalloc() are called), then the private pool is combined with normal pool at most once per second.
Perhaps surprisingly, Engel's tests showed no measurable impact on kernel performance. For the private pool, he is using a custom mixing algorithm that is faster than fast_mix() that is used on the global pool, but provides worse mixing. The normal path is used when mixing the private pool into the global.
Engel's focus is on "generating high-quality randomness as
soon as possible and with low cost to the system
". In particular,
he is targeting embedded systems:
While the values being used seem unpredictable, Ted Ts'o questioned whether an "attacker with deep
knowledge of how the kernel was compiled and what memory allocations
get done during the boot sequence
" would be able to successfully
predict some of the values. For many kernel deployments (e.g. distribution
kernels), an attacker will be able to get that deep knowledge fairly
easily. Ts'o thought Engel's approach had promise for
improving the /dev/urandom output, but agreed with the approach of
not crediting entropy (thus not affecting how much data is available from
/dev/random).
CPU jitter
Another approach was suggested by Stephan Müller in his CPU Jitter random number generator (RNG) patch
set. It was met with more skepticism, at least partly because it
does add to the entropy count. Ts'o and others are not convinced
that sufficiently knowledgeable attackers couldn't predict the output.
Müller's reliance on statistical techniques in his paper to
measure the entropy pool and RNG output is also a cause
for some skepticism. But, according to Müller,
the statistical measures are just a "necessary baseline
"
before he gets into "measuring the actual noise coming out of the
noise sources
".
Müller's method is to measure the jitter in the amount of time it takes the
CPU to perform a set of operations.
When entropy is needed, the driver repeatedly runs two "noise sources": a
memory accessing routine that "will add to the timing variations due
to an unknown amount of CPU wait states added when accessing memory
"
and a timestamp folding operation that is "deliberately
inefficient
", which requires the function to be built with no
optimization (-O0). The folding operation turns a 64-bit timestamp
into one bit that is XORed into the driver's entropy pool. The jitter in
the timing
of those two operations is also mixed
into that entropy pool one bit at a time. Once the required entropy is
available, random numbers derived from that are returned.
While the timing is unpredictable, due to a number of the factors Müller cites in his paper and patchset, it still amounts to a pseudo-random number generator (PRNG), according to H. Peter Anvin:
He goes on to say that independent clocks in a system would provide a source of quantum noise that could potentially be used to increase the entropy count, but that such clocks are rare on today's systems as clocks are typically slaved from the same source using phase-locked loops to keep them synchronized. Thus, using jitter (or Engel's CPU randomness) for mixing into the pool is reasonable, Anvin continued, but not for entropy credit:
It would be nice to assume that since there is no discernible pattern to the output, there must be an underlying entropy-adding event at play. But that is not enough for Ts'o, Anvin, and others to be convinced. Back in October, when the CPU Jitter RNG was first introduced, Ts'o replied at length to the patch and explained the problem he saw:
He also went on to describe ways that Müller could convince him that there is real random noise being generated:
If you think it is from DRAM timing, first try accessing the same memory location in kernel code with the interrupts off, over and over again, so that the memory is pinned into L1 cache. You should be able to get consistent results. If you can, then if you then try to read from DRAM with the L1 and L2 caches disabled, and with interrupts turned off, etc, and see if you get consistent results or inconsistent results. If you get consistent results in both cases, then your hypothesis is disproven. If you get consistent results with the memory pinned in L1 cache, and inconsistent results when the L1 and L2 cache are disabled, then maybe the timing of DRAM reads really are introducing entropy. But the point is you need to test each part of the system in isolation, so you can point at a specific part of the system and say, *that*'s where at least some uncertainty which an adversary can not reverse engineer, and here is the physical process from which the [chaotic] air patterns, or quantum effects, etc., which is hypothesized to cause the uncertainty.
Müller has done most or all of the testing Ts'o suggested as reported in his paper. The results seem to bear out some kind of random noise in both the memory access and folding operations. But Anvin's opinion that the jitter in modern CPUs just represents a complicated PRNG space seems to have held the day. Perhaps a further look at the testing results is in order.
The reliance of the jitter RNG on a high-resolution timer makes it unsuitable for Engel's embedded use case (as some of those systems lack such a timer), so it's not at all clear where things go from here. Ts'o is not opposed to adding something as a zero-entropy source to try to get better /dev/urandom numbers earlier in the boot. Since Engel's solution is both simpler and does not rely on a high-resolution timer, it may well get the nod.
Index entries for this article | |
---|---|
Kernel | Random numbers |
Kernel | Security/Random number generation |
Security | Linux kernel |
Security | Random number generation |
(Log in to post comments)
Voodoo coding
Posted Feb 21, 2014 0:00 UTC (Fri) by cesarb (subscriber, #6266) [Link]
If your code requires -O0, you're doing something wrong.
Instead of using -O0, it's better to use compiler barriers, like OPTIMIZER_HIDE_VAR (see https://git.kernel.org/linus/fe8c8a126806fe).
In fact, someone else on the thread made that same suggestion.
haveged
Posted Feb 21, 2014 11:24 UTC (Fri) by man_ls (guest, #15091) [Link]
How does this compare to haveged? Having looked into it some time ago, where it was IIRC the only available option, it would be great if the article mentioned how it compared to it, if at all.
Adding CPU randomness to the entropy pool
Posted Feb 22, 2014 2:42 UTC (Sat) by warmcat (guest, #26416) [Link]
There's no test that will definitively measure 'randomness', only tests that might identify aspects that are not random. If you pass all those tests, it does not mean it's unpredictable just that your tests did not hit the nail that may be sticking up somewhere.
Statistical and correlation tests like dieharder are useful but it's possible a totally predictable prng could pass the whole suite.
So this is a really hard problem...
Adding CPU randomness to the entropy pool
Posted Feb 22, 2014 16:09 UTC (Sat) by raven667 (subscriber, #5198) [Link]
Adding CPU randomness to the entropy pool
Posted Feb 22, 2014 23:46 UTC (Sat) by warmcat (guest, #26416) [Link]
For demodulation of radio signals the kind of coding and the ratio of the signal to the noise decide what will be possible. Crapping on the signal with a square wave that has no entropy is also able to mess up demodulation so it proves nothing about your generator quality.
It seems the only way is to have reasonable stories about where the randomness is ultimately supposed to be coming from, what steps you took to sample it and reject outside influence, why the rate you are sampling it is slower than the underlying mechanism that creates the unpredictability for all cases (temperature, idle machine for the one in the article etc), why the result will be completely unbiased sampling between 0 and 1, then check it through the statistical test suites and publish the results.
At least for assessing the generator, tricks like passing it through a hash first just hide information about problems and biases in the generator itself are just making it harder to believe the underlying quality is high.