Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
MIME-Version: 1.0
References: <alpine.DEB.2.21.1909290010500.2636@nanos.tec.linutronix.de>
In-Reply-To: <alpine.DEB.2.21.1909290010500.2636@nanos.tec.linutronix.de>
From:   Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sat, 28 Sep 2019 16:53:52 -0700
Message-ID: <CAHk-=wgjC01UaoV35PZvGPnrQ812SRGPoV7Xp63BBFxAsJjvrg@mail.gmail.com>
Subject: Re: x86/random: Speculation to the rescue
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>
Content-Type: multipart/mixed; boundary="000000000000f65c4e0593a5b7bc"
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

--000000000000f65c4e0593a5b7bc
Content-Type: text/plain; charset="UTF-8"

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

--000000000000f65c4e0593a5b7bc
Content-Type: text/x-patch; charset="US-ASCII"; name="patch.diff"
Content-Disposition: attachment; filename="patch.diff"
Content-Transfer-Encoding: base64
Content-ID: <f_k147oizl0>
X-Attachment-Id: f_k147oizl0

IGRyaXZlcnMvY2hhci9yYW5kb20uYyB8IDYyICsrKysrKysrKysrKysrKysrKysrKysrKysrKysr
KysrKysrKysrKysrKysrKysrKy0KIDEgZmlsZSBjaGFuZ2VkLCA2MSBpbnNlcnRpb25zKCspLCAx
IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL2RyaXZlcnMvY2hhci9yYW5kb20uYyBiL2RyaXZl
cnMvY2hhci9yYW5kb20uYwppbmRleCBkM2JlZWQwODRjMGEuLmRlNDM0ZmViODczYSAxMDA2NDQK
LS0tIGEvZHJpdmVycy9jaGFyL3JhbmRvbS5jCisrKyBiL2RyaXZlcnMvY2hhci9yYW5kb20uYwpA
QCAtMTczMiw2ICsxNzMyLDU2IEBAIHZvaWQgZ2V0X3JhbmRvbV9ieXRlcyh2b2lkICpidWYsIGlu
dCBuYnl0ZXMpCiB9CiBFWFBPUlRfU1lNQk9MKGdldF9yYW5kb21fYnl0ZXMpOwogCisKKy8qCisg
KiBFYWNoIHRpbWUgdGhlIHRpbWVyIGZpcmVzLCB3ZSBleHBlY3QgdGhhdCB3ZSBnb3QgYW4gdW5w
cmVkaWN0YWJsZQorICoganVtcCBpbiB0aGUgY3ljbGUgY291bnRlci4gRXZlbiBpZiB0aGUgdGlt
ZXIgaXMgcnVubmluZyBvbiBhbm90aGVyCisgKiBDUFUsIHRoZSB0aW1lciBhY3Rpdml0eSB3aWxs
IGJlIHRvdWNoaW5nIHRoZSBzdGFjayBvZiB0aGUgQ1BVIHRoYXQgaXMKKyAqIGdlbmVyYXRpbmcg
ZW50cm9weS4uCisgKgorICogTm90ZSB0aGF0IHdlIGRvbid0IHJlLWFybSB0aGUgdGltZXIgaW4g
dGhlIHRpbWVyIGl0c2VsZiAtIHdlIGFyZQorICogaGFwcHkgdG8gYmUgc2NoZWR1bGVkIGF3YXks
IHNpbmNlIHRoYXQganVzdCBtYWtlcyB0aGUgbG9hZCBtb3JlCisgKiBjb21wbGV4LCBidXQgd2Ug
ZG8gbm90IHdhbnQgdGhlIHRpbWVyIHRvIGtlZXAgdGlja2luZyB1bmxlc3MgdGhlCisgKiBlbnRy
b3B5IGxvb3AgaXMgcnVubmluZy4KKyAqCisgKiBTbyB0aGUgcmUtYXJtaW5nIGFsd2F5cyBoYXBw
ZW5zIGluIHRoZSBlbnRyb3B5IGxvb3AgaXRzZWxmLgorICovCitzdGF0aWMgdm9pZCBlbnRyb3B5
X3RpbWVyKHN0cnVjdCB0aW1lcl9saXN0ICp0KQoreworCWNyZWRpdF9lbnRyb3B5X2JpdHMoJmlu
cHV0X3Bvb2wsIDEpOworfQorCisvKgorICogSWYgd2UgaGF2ZSBhbiBhY3R1YWwgY3ljbGUgY291
bnRlciwgc2VlIGlmIHdlIGNhbgorICogZ2VuZXJhdGUgZW5vdWdoIGVudHJvcHkgd2l0aCB0aW1p
bmcgbm9pc2UKKyAqLworc3RhdGljIHZvaWQgdHJ5X3RvX2dlbmVyYXRlX2VudHJvcHkodm9pZCkK
K3sKKwlzdHJ1Y3QgeworCQl1bnNpZ25lZCBsb25nIG5vdzsKKwkJc3RydWN0IHRpbWVyX2xpc3Qg
dGltZXI7CisJfSBzdGFjazsKKworCXN0YWNrLm5vdyA9IHJhbmRvbV9nZXRfZW50cm9weSgpOwor
CisJLyogU2xvdyBjb3VudGVyIC0gb3Igbm9uZS4gRG9uJ3QgZXZlbiBib3RoZXIgKi8KKwlpZiAo
c3RhY2subm93ID09IHJhbmRvbV9nZXRfZW50cm9weSgpKQorCQlyZXR1cm47CisKKwl0aW1lcl9z
ZXR1cF9vbl9zdGFjaygmc3RhY2sudGltZXIsIGVudHJvcHlfdGltZXIsIDApOworCXdoaWxlICgh
Y3JuZ19yZWFkeSgpKSB7CisJCWlmICghdGltZXJfcGVuZGluZygmc3RhY2sudGltZXIpKQorCQkJ
bW9kX3RpbWVyKCZzdGFjay50aW1lciwgamlmZmllcysxKTsKKwkJbWl4X3Bvb2xfYnl0ZXMoJmlu
cHV0X3Bvb2wsICZzdGFjay5ub3csIHNpemVvZihzdGFjay5ub3cpKTsKKwkJc2NoZWR1bGUoKTsK
KwkJc3RhY2subm93ID0gcmFuZG9tX2dldF9lbnRyb3B5KCk7CisJfQorCisJZGVsX3RpbWVyX3N5
bmMoJnN0YWNrLnRpbWVyKTsKKwlkZXN0cm95X3RpbWVyX29uX3N0YWNrKCZzdGFjay50aW1lcik7
CisJbWl4X3Bvb2xfYnl0ZXMoJmlucHV0X3Bvb2wsICZzdGFjay5ub3csIHNpemVvZihzdGFjay5u
b3cpKTsKK30KKwogLyoKICAqIFdhaXQgZm9yIHRoZSB1cmFuZG9tIHBvb2wgdG8gYmUgc2VlZGVk
IGFuZCB0aHVzIGd1YXJhbnRlZWQgdG8gc3VwcGx5CiAgKiBjcnlwdG9ncmFwaGljYWxseSBzZWN1
cmUgcmFuZG9tIG51bWJlcnMuIFRoaXMgYXBwbGllcyB0bzogdGhlIC9kZXYvdXJhbmRvbQpAQCAt
MTc0Niw3ICsxNzk2LDE3IEBAIGludCB3YWl0X2Zvcl9yYW5kb21fYnl0ZXModm9pZCkKIHsKIAlp
ZiAobGlrZWx5KGNybmdfcmVhZHkoKSkpCiAJCXJldHVybiAwOwotCXJldHVybiB3YWl0X2V2ZW50
X2ludGVycnVwdGlibGUoY3JuZ19pbml0X3dhaXQsIGNybmdfcmVhZHkoKSk7CisKKwlkbyB7CisJ
CWludCByZXQ7CisJCXJldCA9IHdhaXRfZXZlbnRfaW50ZXJydXB0aWJsZV90aW1lb3V0KGNybmdf
aW5pdF93YWl0LCBjcm5nX3JlYWR5KCksIEhaKTsKKwkJaWYgKHJldCkKKwkJCXJldHVybiByZXQg
PiAwID8gMCA6IHJldDsKKworCQl0cnlfdG9fZ2VuZXJhdGVfZW50cm9weSgpOworCX0gd2hpbGUg
KCFjcm5nX3JlYWR5KCkpOworCisJcmV0dXJuIDA7CiB9CiBFWFBPUlRfU1lNQk9MKHdhaXRfZm9y
X3JhbmRvbV9ieXRlcyk7CiAK
--000000000000f65c4e0593a5b7bc--