Linux RNG Flaws

`Linux RNG flaws   
  
CVE-2018-1108  
  
  
There are several issues in drivers/char/random.c, in particular related to the  
behavior of the /dev/urandom RNG during and shortly after boot.  
  
I'm sending this to <a href="mailto:[email protected]" title="" class="" rel="nofollow">[email protected]</a> and Theodore Ts'o for now; it might make  
sense to also add Jason Donenfeld, since he's done some work around boot  
randomness?  
  
== Discarded early randomness, including device randomness ==  
A comment above rand_initialize() explains:  
  
/*  
* Note that setup_arch() may call add_device_randomness()  
* long before we get here. This allows seeding of the pools  
* with some platform dependent data very early in the boot  
* process. But it limits our options here. We must use  
* statically allocated structures that already have all  
* initializations complete at compile time. We should also  
* take care not to overwrite the precious per platform data  
* we were given.  
*/  
  
In other words, the intent is that none of the early randomness, in particular  
device randomness, should be discarded.  
  
rand_initialize() starts by "initializing" the input_pool and the blocking_pool  
by mixing some extra entropy into them (real time, multiple time stamp counters  
and the utsname); it doesn't clear the pools to avoid clobbering existing  
entropy.  
The primary_crng, however, is fully reinitialized, discarding its existing  
state.  
  
In the crng_init==0 stage, entropy from various in-kernel sources, including  
device randomness and interrupt randomness, is fed into the primary_crng  
directly, but not into the input_pool.  
  
Therefore, the entropy that was collected in the crng_init==0 stage will  
disappear during rand_initialize().  
  
AFAICS device randomness is discarded since  
commit ee7998c50c26 ("random: do not ignore early device randomness"); before  
that, only interrupt randomness and hardware generator randomness were discarded  
this way.  
  
== RNG is treated as cryptographically safe too early ==  
Multiple callers, including sys_getrandom(..., flags=0), attempt to wait for the  
RNG to become cryptographically safe before reading from it by checking for  
crng_ready() and waiting if necessary. However, crng_ready() only checks for  
`crng_init > 0`, and `crng_init==1` does not imply that the RNG is  
cryptographically safe.  
  
Interrupt randomness is mixed in a fast pool of size 16 bytes, and every 64  
interrupts, the fast pool is flushed into the primary_crng. That's 1/4 byte per  
interrupt in the fast load accounting.  
OTOH, device randomness is piped straight into the primary_crng and accounted  
with one byte per written byte.  
As soon as 64 bytes have been written into the primary_crng, the RNG moves to  
crng_init==1.  
This accounting is very unbalanced.  
  
The device entropy fed into the kernel in this way includes:  
  
- DMI table  
- kernel command line string  
- MAC addresses of network devices  
- USB device serial, product, and manufacturers (all as strings)  
  
On a system I'm testing on, in practice, the RNG just reads the DMI table and  
then, since the DMI table is way bigger than 64 bytes, immediately moves to  
crng_init==1 without using even a single sample of interrupt randomness.  
  
The worst part of this (one device entropy sample being enough to move to  
crng_init==1) was AFAICS introduced in  
commit ee7998c50c26 ("random: do not ignore early device randomness"), first in  
v4.14.  
  
== Interaction between kernel and entropy-persisting userspace is broken ==  
A comment above the kernel code suggests:  
  
* Ensuring unpredictability at system startup  
* ============================================  
*  
* When any operating system starts up, it will go through a sequence  
* of actions that are fairly predictable by an adversary, especially  
* if the start-up does not involve interaction with a human operator.  
* This reduces the actual number of bits of unpredictability in the  
* entropy pool below the value in entropy_count. In order to  
* counteract this effect, it helps to carry information in the  
* entropy pool across shut-downs and start-ups. To do this, put the  
* following lines an appropriate script which is run during the boot  
* sequence:  
*  
* echo "Initializing random number generator..."  
* random_seed=/var/run/random-seed  
* # Carry a random seed from start-up to start-up  
* # Load and then save the whole entropy pool  
* if [ -f $random_seed ]; then  
* cat $random_seed >/dev/urandom  
* else  
* touch $random_seed  
* fi  
* chmod 600 $random_seed  
* dd if=/dev/urandom of=$random_seed count=1 bs=512  
*  
* and the following lines in an appropriate script which is run as  
* the system is shutdown:  
[...]  
* Effectively, these commands cause the contents of the entropy pool  
* to be saved at shut-down time and reloaded into the entropy pool at  
* start-up. (The 'dd' in the addition to the bootup script is to  
* make sure that /etc/random-seed is different for every start-up,  
* even if the system crashes without executing rc.0.) Even with  
* complete knowledge of the start-up activities, predicting the state  
* of the entropy pool requires knowledge of the previous history of  
* the system.  
  
Counterintuitively, after such a startup script has executed, the seed data  
reloaded by the script probably won't actually influence data that is read from  
/dev/urandom directly afterwards:  
  
- If the seed data is loaded with crng_init < 2, the seed data written into the  
input_pool will not flow into the primary_crng or into the NUMA CRNGs until  
`crng_init == 2`.  
- If the seed data is loaded with `crng_init == 2`, the seed data written into  
the input_pool will only propagate into the primary_crng, and from there into  
the NUMA CRNGs, with delays of 5 minutes (!) each (CRNG_RESEED_INTERVAL).  
  
This has two consequences:  
  
- Services that seed their own RNG from /dev/urandom shortly after the seed  
data has been loaded into the kernel RNG will probably only use boot entropy;  
the RNG seeds used by such services will be independent from the persistent  
seed.  
- The data written back to the seed file by the boot script will be independent  
from the previous persistent seed; if the system is shut down uncleanly  
(without running the shutdown script) and then powered up again, the  
persistent seed file will only contain entropy collected during the previous  
boot.  
  
  
== No entropy is fed into NUMA CRNGs between rand_initialize() initcall and crng_init==2 ==  
When the RNG subsystem is initialized using the early_initcall hook  
rand_initialize, the NUMA CRNGs (introduced in  
commit 1e7f583af67b ("random: make /dev/urandom scalable for silly userspace programs"),  
first in v4.8) are initialized using entropy from the primary_crng after it has  
been reinitialized from the input_pool. This entropy is:  
  
- If crng_init==0: Real time, some cycle counters, utsname (all from  
init_std_data() and crng_initialize()), and potentially events from  
add_timer_randomness() if any have happened at that point.  
- If crng_init==1: Real time, some cycle counters, utsname, all timer  
randomness that has happened up to the rand_initialize() call, and any  
device/timer/hardware-rng/interrupt randomness that may have come in between  
the time crng_init became 1 and the rand_initialize() call, and are not still  
batched.  
  
In the crng_init==0 case, the primary_crng will be fed with entropy until  
crng_init==1; but in either case, no more entropy can reach the NUMA CRNGs until  
crng_init==2, even though the kernel will assume that the NUMA CRNGs are  
cryptographically safe once crng_init==1.  
  
In other words, /dev/urandom reads will return data whose entropy only comes  
from timing samples in the first few dozen milliseconds of system boot for  
(depending on the system) minutes after the system has booted.  
  
  
== initcall can propagate entropy into primary and NUMA CRNGs while crng_init==1 ==  
My understanding of the intent behind the crng_init states is as follows:  
  
- state 0: early startup; want to get entropy into the RNG quickly  
- state 1: buffer up 128 bits of entropy to prevent an attacker with access  
to multiple RNG samples across system boot from continuously brute-forcing  
the RNG input in small chunks  
- state 2: feed all the buffered entropy into the RNG at once, then continue  
feeding entropy into the RNG every 5 minutes  
  
If this interpretation is correct, it is problematic that, if the  
rand_initialize() initcall happens while crng_init==1, entropy from the input  
pool is propagated into the primary RNG and the NUMA CRNGs: If this happens, the  
amount of entropy that is fed into the user-accessible RNGs at once is, in the  
theoretical worst case, halved.  
  
  
== Impact ==  
I have spent a few days attempting to figure out how bad these issues are.  
I believe that on an Intel Grass Canyon system, with RDRAND disabled,  
ASLR disabled, fast boot enabled, no connected devices, with boot on power,  
some frequency scaling options disabled, and the fan set to maximum,  
it should be possible to express the entropy in the used RDTSC samples in around  
105 bits or less. (I'm not sure which parts of this configuration actually  
influence the amount of entropy; but ASLR certainly does influence it, since the  
one interrupt sample that is fed into the RNG before the RNG initialization  
contains an instruction pointer.)  
  
From eight boots, the initial TSC samples (in hex):  
11ea2f6f6,11ea54523,11e6337b9,11ea1100c,11e9e66d6,11e9d5165,11e7d1742,11e9e4a9d  
  
The deltas between following TSC samples (in hex; each block of numbers  
corresponds to one boot):  
  
479a b214a34 3021c16 9fccbb d7 7d 6e 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 51c7 a a a a a a 5 a a a 5  
  
47b8 b205fb6 3025a4b 9fd990 dc 7d 69 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 519a f a a a a a 5 a a a 5  
  
479a b23b02b 3023930 9f89f9 d7 7d 6e 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 523a f a a a a a 5 a a a 5  
  
47b3 b2053b8 30223be 9fc76b dc 7d 69 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 51e0 a a a a a a 5 a a a 5  
  
4565 b2096ac 3021b30 9fa22c d2 7d 6e 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 5208 f a 5 a a a a a 5 a a  
  
47ae b20cab4 301e7d2 9fb82a d2 7d 6e 69 6e 69 69 69 69 69 6e 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 51ea a a a a a a a 5 a a a  
  
4795 b21227f 30218e2 9ffe66 d2 7d 6e 69 6e 69 69 69 69 69 6e 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 551e f 5 a a a a a 5 a a a  
  
4795 b2242bd 30230fc 9fb6ae d7 7d 69 69 73 69 69 69 69 69 69 69 73 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6e 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 5140 f a a a 5 a a a a 5 a  
  
On top of that, there is entropy from the ktime_get_real() call in  
init_std_data(); the amount of entropy from that depends on how precisely an  
attacker knows the system boot time.  
  
  
This bug is subject to a 90 day disclosure deadline. After 90 days elapse  
or a patch has been made broadly available, the bug report will become  
visible to the public.  
  
  
  
Found by: jannh  
  
`