Re: x86/random: Speculation to the rescue

From: Linus Torvalds <torvalds@linux-foundation.org>
To: "Ahmed S. Darwish" <darwish.07@gmail.com>
Cc: Thomas Gleixner <tglx@linutronix.de>,
	a.darwish@linutronix.de, LKML <linux-kernel@vger.kernel.org>,
	"Theodore Ts'o" <tytso@mit.edu>,
	Nicholas Mc Guire <hofrat@opentech.at>,
	"the arch/x86 maintainers" <x86@kernel.org>,
	Andy Lutomirski <luto@kernel.org>,
	Kees Cook <keescook@chromium.org>
Subject: Re: x86/random: Speculation to the rescue
Date: Tue, 1 Oct 2019 10:25:08 -0700	[thread overview]
Message-ID: <CAHk-=wjPTVJNtynBMUbcnChUu=11f=VK=ASkw+4TUU7MEpiugA@mail.gmail.com> (raw)
In-Reply-To: <20191001161448.GA1918@darwi-home-pc>

On Tue, Oct 1, 2019 at 9:15 AM Ahmed S. Darwish <darwish.07@gmail.com> wrote:
>
> To test the quality of the new jitter code, I added a small patch on
> top to disable all other sources of randomness except the new jitter
> entropy code, [1] and made quick tests on the quality of getrandom(0).

You also need to make sure to disable rdrand. Even if we don't trust
it, we always mix it in.

> Using the "ent" tool, [2] also used to test randomness in the Stephen
> Müller LRNG paper, on a 500000-byte file, produced the following
> results:

Entropy is hard to estimate, for roughly the same reasons it's hard to generate.

The entropy estimation is entirely bvroken by the whitening we do:
first we do the LFSR to mix things into the pools, then we whiten it
when we mix it between the input pool and the final pool, and then we
whiten it once more when we extract it when reading.

So the end result of urandom will look random to all the entropy tools
regardless of what the starting point is. Because we use good hashes
for whitening, and do all the updating of the pools while extracing,
the end result had better look perfect.

The only way to even make an educated estimate of actual entropy would
be to print out the raw state of the input pool when we do that "crng
init done".

And then you would have to automate some "reboot machine thousands of
times" and start looking for patterns.

And even then you'd only have a few thousand starting points that we
_claim_ have at least 128 bits of entropy in, and you'd have a really
hard time to prove that is the case.

You might prove that we are doing something very very wrong and don't
have even remotely close to 128 bits of randomness, but just 5 bits of
actual entropy or whatever - _that_ kind of pattern is easy to see.

But even then /dev/urandom as a _stream_ should look fine. Only the
(multiple, repeated) initial states in the input pool would show the
lack of entropy.

And you'd really have to reboot things for real. And not in a VM
either. Just repeating the entropy initialization wouldn't show the
pattern (unless it's even more broken) because the base TSC values
would be changing.

Entropy really is hard. It's hard to generate, and it's hard to measure.

              Linus