From: David Laight <David.Laight@ACULAB.COM>
To: 'Linus Torvalds' <torvalds@linux-foundation.org>,
"Theodore Y. Ts'o" <tytso@mit.edu>
Cc: "Ahmed S. Darwish" <darwish.07@gmail.com>,
Lennart Poettering <mzxreary@0pointer.de>,
"Eric W. Biederman" <ebiederm@xmission.com>,
"Alexander E. Patrakov" <patrakov@gmail.com>,
Michael Kerrisk <mtk.manpages@gmail.com>,
lkml <linux-kernel@vger.kernel.org>,
"linux-ext4@vger.kernel.org" <linux-ext4@vger.kernel.org>,
"linux-man@vger.kernel.org" <linux-man@vger.kernel.org>
Subject: RE: [PATCH RFC v4 1/1] random: WARN on large getrandom() waits and introduce getrandom2()
Date: Mon, 23 Sep 2019 11:55:17 +0000 [thread overview]
Message-ID: <619e578cdfad4dca904eb9db9bf626c0@AcuMS.aculab.com> (raw)
In-Reply-To: <CAHk-=wjTbpcyVevsy3g-syB5v9gk_rR-yRFrUAvTL8NFuGfCrw@mail.gmail.com>
From: Linus Torvalds
> Sent: 19 September 2019 21:04
...
> Note small detail above: I changed the ^= to a +=. Addition tends to
> be better (due to carry between bits) when there might be bit
> commonalities. Particularly with something like a cycle count where
> two xors can mostly cancel out previous bits rather than move bits
> around in the word.
There is code in one on the kernel RNG that XORs together the output
of 3 LFSR (CRC) generators.
I think it is used for 'low quality' randomness and reseeded from the main RNG.
Using XOR makes the entire generator 'linear' and thus trivially reversible.
With a relatively small number of consecutive outputs you can determine the state
of all 3 LFSR.
Merge the results with addition and the process is immensely harder.
I've also wondered whether the RC4 generator is a useful entropy store?
It has a lot of state and you can fairly easily feed in values that might (or
might not) contain any randomness without losing any stored entropy.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
next prev parent reply other threads:[~2019-09-23 11:55 UTC|newest]
Thread overview: 45+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <CAHk-=whW_AB0pZ0u6P9uVSWpqeb5t2NCX_sMpZNGy8shPDyDNg@mail.gmail.com>
[not found] ` <CAHk-=wi_yXK5KSmRhgNRSmJSD55x+2-pRdZZPOT8Fm1B8w6jUw@mail.gmail.com>
[not found] ` <20190911173624.GI2740@mit.edu>
[not found] ` <20190912034421.GA2085@darwi-home-pc>
[not found] ` <20190912082530.GA27365@mit.edu>
[not found] ` <CAHk-=wjyH910+JRBdZf_Y9G54c1M=LBF8NKXB6vJcm9XjLnRfg@mail.gmail.com>
[not found] ` <20190914122500.GA1425@darwi-home-pc>
[not found] ` <008f17bc-102b-e762-a17c-e2766d48f515@gmail.com>
[not found] ` <20190915052242.GG19710@mit.edu>
[not found] ` <CAHk-=wgg2T=3KxrO-BY3nHJgMEyApjnO3cwbQb_0vxsn9qKN8Q@mail.gmail.com>
2019-09-18 21:15 ` [PATCH RFC v4 0/1] random: WARN on large getrandom() waits and introduce getrandom2() Ahmed S. Darwish
2019-09-18 21:17 ` [PATCH RFC v4 1/1] " Ahmed S. Darwish
2019-09-18 23:57 ` Linus Torvalds
2019-09-19 14:34 ` Theodore Y. Ts'o
2019-09-19 15:20 ` Linus Torvalds
2019-09-19 15:50 ` Linus Torvalds
2019-09-20 13:13 ` Theodore Y. Ts'o
2019-09-19 20:04 ` Linus Torvalds
2019-09-19 20:45 ` Alexander E. Patrakov
2019-09-19 21:47 ` Linus Torvalds
2019-09-19 22:23 ` Alexander E. Patrakov
2019-09-19 23:44 ` Alexander E. Patrakov
2019-09-20 13:16 ` Theodore Y. Ts'o
2019-09-23 11:55 ` David Laight [this message]
2019-09-20 13:08 ` Theodore Y. Ts'o
2019-09-20 13:46 ` Ahmed S. Darwish
2019-09-20 14:33 ` Andy Lutomirski
2019-09-20 16:29 ` Linus Torvalds
2019-09-20 17:52 ` Andy Lutomirski
2019-09-20 18:09 ` Linus Torvalds
2019-09-20 18:16 ` Willy Tarreau
2019-09-20 19:12 ` Andy Lutomirski
2019-09-20 19:51 ` Linus Torvalds
2019-09-20 20:11 ` Alexander E. Patrakov
2019-09-20 20:17 ` Matthew Garrett
2019-09-20 20:51 ` Andy Lutomirski
2019-09-20 22:44 ` Linus Torvalds
2019-09-20 23:30 ` Andy Lutomirski
2019-09-21 3:05 ` Willy Tarreau
2019-09-21 6:07 ` Florian Weimer
2019-09-23 18:33 ` Andy Lutomirski
2019-09-26 21:11 ` Ahmed S. Darwish
2019-09-20 18:12 ` Willy Tarreau
2019-09-20 19:22 ` Andy Lutomirski
2019-09-20 19:37 ` Willy Tarreau
2019-09-20 19:52 ` Andy Lutomirski
2019-09-20 20:02 ` Linus Torvalds
2019-09-20 18:15 ` Alexander E. Patrakov
2019-09-20 18:29 ` Andy Lutomirski
2019-09-20 17:26 ` Willy Tarreau
2019-09-20 17:56 ` Ahmed S. Darwish
2019-09-26 20:42 ` [PATCH v5 0/1] random: getrandom(2): warn on large CRNG waits, introduce new flags Ahmed S. Darwish
2019-09-26 20:44 ` [PATCH v5 1/1] " Ahmed S. Darwish
2019-09-26 21:39 ` Andy Lutomirski
2019-09-28 9:30 ` Ahmed S. Darwish
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=619e578cdfad4dca904eb9db9bf626c0@AcuMS.aculab.com \
--to=david.laight@aculab.com \
--cc=darwish.07@gmail.com \
--cc=ebiederm@xmission.com \
--cc=linux-ext4@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-man@vger.kernel.org \
--cc=mtk.manpages@gmail.com \
--cc=mzxreary@0pointer.de \
--cc=patrakov@gmail.com \
--cc=torvalds@linux-foundation.org \
--cc=tytso@mit.edu \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).