From: "Alexander E. Patrakov" <email@example.com> To: Linus Torvalds <firstname.lastname@example.org>, Thomas Gleixner <email@example.com>, "Ahmed S. Darwish" <firstname.lastname@example.org> Cc: LKML <email@example.com>, Theodore Ts'o <firstname.lastname@example.org>, Nicholas Mc Guire <email@example.com>, the arch/x86 maintainers <firstname.lastname@example.org>, Andy Lutomirski <email@example.com>, Kees Cook <firstname.lastname@example.org>, Stephan Mueller <email@example.com> Subject: Re: x86/random: Speculation to the rescue Date: Sun, 29 Sep 2019 13:05:15 +0500 [thread overview] Message-ID: <firstname.lastname@example.org> (raw) In-Reply-To: <CAHk-=wgjC01UaoV35PZvGPnrQ812SRGPoV7Xp63BBFxAsJjvrg@mail.gmail.com> 29.09.2019 04:53, Linus Torvalds пишет: > On Sat, Sep 28, 2019 at 3:24 PM Thomas Gleixner <email@example.com> wrote: >> >> Nicholas presented the idea to (ab)use speculative execution for random >> number generation years ago at the Real-Time Linux Workshop: > > What you describe is just a particularly simple version of the jitter > entropy. Not very reliable. > > But hey, here's a made-up patch. It basically does jitter entropy, but > it uses a more complex load than the fibonacci LFSR folding: it calls > "schedule()" in a loop, and it sets up a timer to fire. > > And then it mixes in the TSC in that loop. > > And to be fairly conservative, it then credits one bit of entropy for > every timer tick. Not because the timer itself would be all that > unpredictable, but because the interaction between the timer and the > loop is going to be pretty damn unpredictable. This looks quite similar to the refactoring proposed earlier by Stephan Müller in his paper: https://www.chronox.de/lrng/doc/lrng.pdf . Indeed, he makes a good argument that the timing of device interrupts is right now the main actual source of entropy in Linux, at the end of Section 1.1: """ The discussion shows that the noise sources of block devices and HIDs are a derivative of the interrupt noise source. All events used as entropy source recorded by the block device and HID noise source are delivered to the Linux kernel via interrupts. """ Now your patch adds the timer interrupt (while the schedule() loop is running) to the mix, essentially in the same setup as proposed. > > Ok, I'm handwaving. But I do claim it really is fairly conservative to > think that a cycle counter would give one bit of entropy when you time > over a timer actually happening. The way that loop is written, we do > guarantee that we'll mix in the TSC value both before and after the > timer actually happened. We never look at the difference of TSC > values, because the mixing makes that uninteresting, but the code does > start out with verifying that "yes, the TSC really is changing rapidly > enough to be meaningful". > > So if we want to do jitter entropy, I'd much rather do something like > this that actually has a known fairly complex load with timers and > scheduling. > > And even if absolutely no actual other process is running, the timer > itself is still going to cause perturbations. And the "schedule()" > call is more complicated than the LFSR is anyway. > > It does wait for one second the old way before it starts doing this. > > Whatever. I'm entirely convinced this won't make everybody happy > anyway, but it's _one_ approach to handle the issue. > > Ahmed - would you be willing to test this on your problem case (with > the ext4 optimization re-enabled, of course)? > > And Thomas - mind double-checking that I didn't do anything > questionable with the timer code.. > > And this goes without saying - this patch is ENTIRELY untested. Apart > from making people upset for the lack of rigor, it might do > unspeakable crimes against your pets. You have been warned. > > Linus > -- Alexander E. Patrakov
next prev parent reply other threads:[~2019-09-29 8:05 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 [this message] 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 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 \ --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 \ --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).