From: Thomas Gleixner <email@example.com> To: David Laight <David.Laight@ACULAB.COM> Cc: 'Linus Torvalds' <firstname.lastname@example.org>, "Theodore Y. Ts'o" <email@example.com>, "Ahmed S. Darwish" <firstname.lastname@example.org>, LKML <email@example.com>, Nicholas Mc Guire <firstname.lastname@example.org>, the arch/x86 maintainers <email@example.com>, Andy Lutomirski <firstname.lastname@example.org>, Kees Cook <email@example.com> Subject: RE: x86/random: Speculation to the rescue Date: Tue, 15 Oct 2019 23:50:33 +0200 (CEST) [thread overview] Message-ID: <alpine.DEB.firstname.lastname@example.org> (raw) In-Reply-To: <41646d76683844e7baf068bed35891ad@AcuMS.aculab.com> David, On Tue, 1 Oct 2019, David Laight wrote: > From: Linus Torvalds > > Sent: 30 September 2019 17:16 > > > > On Mon, Sep 30, 2019 at 6:16 AM Theodore Y. Ts'o <email@example.com> 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. I surely agree with Linus that simple architectures could have a more or less predictable or at least searchable behaviour. If we talk about complex x86 CPUs, I tend to disagree. Even the Intel architects cannot explain why the following scenario is not deterministic at all: Single CPU No NMIs No MCEs No DMAs in the background, nothing. CPU frequency is identical to TSC frequency volatile int foo; local_irq_disable(); start = rdtscp(); for (i = 0; i < 100000; i++) foo++; end = rdtscp(); local_irq_enable(); Repeat that loop as often as you wish and observe the end - start delta. You'll see min <= delta <= N * min where N is something >= 2. The actual value of N depends on the micro architecture, but is not identical on two systems and not even identical on the same system after boot and 1e6 iterations of the above. Aside of the fact that N is insane big there is absolutely no pattern in the delta value even over a large number of runs. > 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. See above and read Nicholas paper. It's simply not that likely on anything halfways modern. > 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. The variations between systems are going to be larger as any minimal tolerance in the components have an influence. But even between two boots on a 'noiseless' embedded system factors like temperature, PLL lock times, swing in times of voltage regulators and other tiny details create non-deterministic behaviour. In my former life as a hardware engineer I had to analyze such issues deeply as they create serious trouble for some application scenarios, but those systems where based on very trivial and truly deterministic silicon parts. No commodity hardware vendor will ever go the extra mile to address these things as the effort required to get them under control is exponential vs. the effect. Whether that's enough to create true entropy is a different question, but I do not agree with the upfront dismissal of a potentially useful entropy source. I'm in no way saying that this should be used as the sole source of entropy, but I definitely want to explore the inherent non-determinism of modern OoO machines further. The results are way too interesting to ignore them and amazingly fast at least with the algorithm which I used in my initial post which started this whole discussion. I let that thing run on a testbox for the last two weeks while I was on vacation and gathered 32768 random bits via that debugfs hack every 100ms, i.e. a total of 1.2e7 samples amounting to ~4e11 bits. The analysis is still running, but so far it holds up. Thanks, tglx
next prev parent reply other threads:[~2019-10-15 21:50 UTC|newest] Thread overview: 37+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-09-28 22:24 Thomas Gleixner 2019-09-28 23:53 ` Linus Torvalds 2019-09-29 7:40 ` Thomas Gleixner 2019-09-29 8:05 ` Alexander E. Patrakov 2019-09-30 1:16 ` Linus Torvalds 2019-09-30 2:59 ` Linus Torvalds 2019-09-30 6:10 ` Borislav Petkov 2019-09-30 16:06 ` Linus Torvalds 2019-10-01 13:51 ` Borislav Petkov 2019-10-01 17:14 ` Linus Torvalds 2019-10-01 17:50 ` [PATCH] char/random: Add a newline at the end of the file Borislav Petkov 2019-09-30 18:05 ` x86/random: Speculation to the rescue Kees Cook 2019-09-30 3:37 ` Theodore Y. Ts'o 2019-09-30 13:16 ` Theodore Y. Ts'o 2019-09-30 16:15 ` Linus Torvalds 2019-09-30 16:32 ` Peter Zijlstra 2019-09-30 17:03 ` Linus Torvalds 2019-10-01 10:28 ` David Laight 2019-10-15 21:50 ` Thomas Gleixner [this message] 2019-10-01 16:15 ` Ahmed S. Darwish 2019-10-01 16:37 ` Kees Cook 2019-10-01 17:18 ` Ahmed S. Darwish 2019-10-01 17:25 ` Linus Torvalds 2019-10-06 12:07 ` Pavel Machek 2019-10-02 12:01 ` Theodore Y. Ts'o 2019-10-06 11:41 ` Pavel Machek 2019-10-06 17:26 ` Linus Torvalds 2019-10-06 17:35 ` Pavel Machek 2019-10-06 18:06 ` Linus Torvalds 2019-10-06 18:21 ` Pavel Machek 2019-10-06 18:26 ` Linus Torvalds 2019-10-07 11:47 ` Theodore Y. Ts'o 2019-10-07 22:18 ` Pavel Machek 2019-10-08 11:33 ` David Laight 2019-10-09 8:02 ` Pavel Machek 2019-10-09 9:37 ` David Laight 2019-10-01 2:14 hgntkwis
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=alpine.DEB.firstname.lastname@example.org \ --email@example.com \ --cc=David.Laight@ACULAB.COM \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ --subject='RE: x86/random: Speculation to the rescue' \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).