Re: early x86 unseeded randomness

From: Thomas Gleixner
Date: Tue Aug 15 2017 - 06:47:56 EST


On Tue, 15 Aug 2017, Ingo Molnar wrote:
> * Willy Tarreau <w@xxxxxx> wrote:
>
> > Nowadays we could use similar methods using RDTSC providing more accurate
> > counting. This doesn't provide a lot of entropy of course, given that a
> > 2 GHz machine will at most count 31 bits there. But I tend to think that
> > what matters during early boot is to transform something highly predictable
> > into something unlikely to be predicted (ie: an exploit having to scan 2^31
> > possible addresses will not be really usable). It's also possible to do the
> > same with the PIT0 counter ticking at 18.2 Hz without any correlation with
> > the RTC by the way, and roughly provide 25 more bits. And if you expect
> > that the BIOS has emitted a 800 Hz beep at boot, you could still have a
> > divider of 1491 in PIT2 providing 10 more bits, though with a bit of
> > correlation with PIT0 since they use the same 1.19 MHz source. These
> > methods increase the boot time by up to one second though, but my point
> > here is that when you have nothing it's always a bit better.
>
> One other thing besides trying to extract entropy via timing would be to utilize
> more of the machine's environment in seeding the random number generator.
>
> For example on x86 the E820 table is available very early on and its addresses
> could be mixed into the random pool. An external attacker often would not know the
> precise hardware configuration.
>
> Likewise the boot parameters string could be mixed into the initial random pool as
> well - and this way distributions could create per installation seed simply by
> appending a random number to the boot string.
>
> Both methods should be very fast and robust.

Actually using RDTSC is not the worst approach. See:

https://lwn.net/images/conf/rtlws11/random-hardware.pdf

Below is a stupid implementation of that. Here are the resulting numbers
from a dozen of boot cycles:

10a3e7af4890c0ae
e7b08c8c18e6d5d9
951e12c77f79e000
ad88753ad11c9b80
db2d4dce466a3da4
b328c76d4e67368d
642edf2265e0c8a7
ef45a9f9326249d0
13e01119498797a6
0a537c8751e0349e
eb67c02dc09326dd
037d4b332020538d
793fbfda06718c69
2231535c514769e5

This mechanism could also be used to seed the random generator.

Thanks,

tglx

8<-------------------

--- a/arch/x86/kernel/tsc.c
+++ b/arch/x86/kernel/tsc.c
@@ -1360,3 +1360,19 @@ unsigned long calibrate_delay_is_known(v
return 0;
}
#endif
+
+u64 __init tsc_early_random(void)
+{
+ u64 uninitialized_var(res);
+ int i;
+
+ if (!boot_cpu_has(X86_FEATURE_TSC))
+ return res;
+
+ res ^= rdtsc();
+ for (i = 0; i < BITS_PER_LONG; i++) {
+ res ^= ((rdtsc() & 0x04) >> 2) << i;
+ udelay(2);
+ }
+ return res;
+}