LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Linus Torvalds <torvalds@linux-foundation.org>
To: Thomas Gleixner <tglx@linutronix.de>,
	"Ahmed S. Darwish" <darwish.07@gmail.com>
Cc: 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: Sat, 28 Sep 2019 16:53:52 -0700
Message-ID: <CAHk-=wgjC01UaoV35PZvGPnrQ812SRGPoV7Xp63BBFxAsJjvrg@mail.gmail.com> (raw)
In-Reply-To: <alpine.DEB.2.21.1909290010500.2636@nanos.tec.linutronix.de>


[-- Attachment #1: Type: text/plain, Size: 2272 bytes --]

On Sat, Sep 28, 2019 at 3:24 PM Thomas Gleixner <tglx@linutronix.de> 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.

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

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2412 bytes --]

 drivers/char/random.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 61 insertions(+), 1 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d3beed084c0a..de434feb873a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1732,6 +1732,56 @@ void get_random_bytes(void *buf, int nbytes)
 }
 EXPORT_SYMBOL(get_random_bytes);
 
+
+/*
+ * Each time the timer fires, we expect that we got an unpredictable
+ * jump in the cycle counter. Even if the timer is running on another
+ * CPU, the timer activity will be touching the stack of the CPU that is
+ * generating entropy..
+ *
+ * Note that we don't re-arm the timer in the timer itself - we are
+ * happy to be scheduled away, since that just makes the load more
+ * complex, but we do not want the timer to keep ticking unless the
+ * entropy loop is running.
+ *
+ * So the re-arming always happens in the entropy loop itself.
+ */
+static void entropy_timer(struct timer_list *t)
+{
+	credit_entropy_bits(&input_pool, 1);
+}
+
+/*
+ * If we have an actual cycle counter, see if we can
+ * generate enough entropy with timing noise
+ */
+static void try_to_generate_entropy(void)
+{
+	struct {
+		unsigned long now;
+		struct timer_list timer;
+	} stack;
+
+	stack.now = random_get_entropy();
+
+	/* Slow counter - or none. Don't even bother */
+	if (stack.now == random_get_entropy())
+		return;
+
+	timer_setup_on_stack(&stack.timer, entropy_timer, 0);
+	while (!crng_ready()) {
+		if (!timer_pending(&stack.timer))
+			mod_timer(&stack.timer, jiffies+1);
+		mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+		schedule();
+		stack.now = random_get_entropy();
+	}
+
+	del_timer_sync(&stack.timer);
+	destroy_timer_on_stack(&stack.timer);
+	mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+}
+
 /*
  * Wait for the urandom pool to be seeded and thus guaranteed to supply
  * cryptographically secure random numbers. This applies to: the /dev/urandom
@@ -1746,7 +1796,17 @@ int wait_for_random_bytes(void)
 {
 	if (likely(crng_ready()))
 		return 0;
-	return wait_event_interruptible(crng_init_wait, crng_ready());
+
+	do {
+		int ret;
+		ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
+		if (ret)
+			return ret > 0 ? 0 : ret;
+
+		try_to_generate_entropy();
+	} while (!crng_ready());
+
+	return 0;
 }
 EXPORT_SYMBOL(wait_for_random_bytes);
 

  reply index

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 [this message]
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
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='CAHk-=wgjC01UaoV35PZvGPnrQ812SRGPoV7Xp63BBFxAsJjvrg@mail.gmail.com' \
    --to=torvalds@linux-foundation.org \
    --cc=darwish.07@gmail.com \
    --cc=hofrat@opentech.at \
    --cc=keescook@chromium.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luto@kernel.org \
    --cc=tglx@linutronix.de \
    --cc=tytso@mit.edu \
    --cc=x86@kernel.org \
    /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

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lkml.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lkml.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lkml.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lkml.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lkml.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lkml.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lkml.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lkml.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lkml.kernel.org/lkml/8 lkml/git/8.git
	git clone --mirror https://lkml.kernel.org/lkml/9 lkml/git/9.git
	git clone --mirror https://lkml.kernel.org/lkml/10 lkml/git/10.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lkml.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git