LKML Archive on lore.kernel.org
 help / color / Atom feed
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
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

  parent 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
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 [this message]
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-=wjPTVJNtynBMUbcnChUu=11f=VK=ASkw+4TUU7MEpiugA@mail.gmail.com' \
    --to=torvalds@linux-foundation.org \
    --cc=a.darwish@linutronix.de \
    --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