RE: x86/random: Speculation to the rescue

From: David Laight <David.Laight@ACULAB.COM>
To: 'Linus Torvalds' <torvalds@linux-foundation.org>,
	"Theodore Y. Ts'o" <tytso@mit.edu>
Cc: Thomas Gleixner <tglx@linutronix.de>,
	"Ahmed S. Darwish" <darwish.07@gmail.com>,
	LKML <linux-kernel@vger.kernel.org>,
	"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:28:07 +0000	[thread overview]
Message-ID: <41646d76683844e7baf068bed35891ad@AcuMS.aculab.com> (raw)
In-Reply-To: <CAHk-=wg7YAx_+CDe6fUqApPD_ghP18H9sPnJWWUg32pQ4pU82g@mail.gmail.com>

From: Linus Torvalds
> Sent: 30 September 2019 17:16
> 
> On Mon, Sep 30, 2019 at 6:16 AM Theodore Y. Ts'o <tytso@mit.edu> wrote:
> >
> > Which is to say, I'm still worried that people with deep access to the
> > implementation details of a CPU might be able to reverse engineer what
> > a jitter entropy scheme produces.  This is why I'd be curious to see
> > the results when someone tries to attack a jitter scheme on a fully
> > open, simple architecture such as RISC-V.
> 
> Oh, I agree.
> 
> One of the reasons I didn't like some of the other jitter entropy
> things was that they seemed to rely _entirely_ on just purely
> low-level CPU unpredictability. I think that exists, but I think it
> makes for problems for really simple cores.
> 
> Timing over a bigger thing and an actual interrupt (even if it's
> "just" a timer interrupt, which is arguably much closer to the CPU and
> has a much higher likelihood of having common frequency domains with
> the cycle counter etc) means that I'm pretty damn convinced that a big
> complex CPU will absolutely see issues, even if it has big caches.

Agreed, you need something that is actually non-deterministic.
While 'speculation' is difficult to predict, it is actually fully deterministic.
Until you get some perturbation from an outside source the cpu state
(including caches and DRAM) is likely to be the same on every boot.
For a desktop (etc) PC booting from a disk (even SSD) you'll get some variation.
Boot an embedded system from onboard flash and every boot could
well be the same (or one of a small number of results).

Synchronising a signal between frequency domains might generate
some 'randomness', but maybe not if both come from the same PLL.

Even if there are variations, they may not be large enough to give
a lot of variations in the state.
The variations between systems could also be a lot larger than the
variations within a system.

If there are 'only' 2^32 variations an exhaustive search might be
possible to find an ssh key.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)