Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1689861 > unrolled thread

[RFC PATCH v12 0/4] /dev/random - a new approach

Back to article view | Back to linux.kernel

Contents

  [RFC PATCH v12 0/4] /dev/random - a new approach Stephan Müller <smueller@chronox.de> - 2017-07-18 10:20 +0200
    [RFC PATCH v12 4/4] LRNG - enable compile Stephan Müller <smueller@chronox.de> - 2017-07-18 10:20 +0200
      Re: [RFC PATCH v12 4/4] LRNG - enable compile Arnd Bergmann <arnd@arndb.de> - 2017-07-18 11:00 +0200
        Re: [RFC PATCH v12 4/4] LRNG - enable compile Stephan Müller <smueller@chronox.de> - 2017-07-18 11:00 +0200
    Re: [RFC PATCH v12 3/4] Linux Random Number Generator Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2017-07-18 10:40 +0200
      Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-18 10:50 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2017-07-18 11:00 +0200
          Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-18 16:40 +0200
            Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-18 23:10 +0200
              Re: [RFC PATCH v12 3/4] Linux Random Number Generator Sandy Harris <sandyinchina@gmail.com> - 2017-07-19 03:10 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-19 04:00 +0200
                  Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-19 08:30 +0200
                  Re: [RFC PATCH v12 3/4] Linux Random Number Generator Pavel Machek <pavel@ucw.cz> - 2017-07-30 12:50 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Sandy Harris <sandyinchina@gmail.com> - 2017-07-23 20:10 +0200
                  Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-23 23:50 +0200
              Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-19 08:30 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2017-07-19 08:40 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-19 19:30 +0200
                  Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-20 21:10 +0200
                    Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-21 05:10 +0200
                      Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-21 11:00 +0200
                        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-21 17:20 +0200
                        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Arnd Bergmann <arnd@arndb.de> - 2017-07-21 17:20 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2017-07-18 11:00 +0200

Page 1 of 2  [1] 2  Next page →

#1689861 — [RFC PATCH v12 0/4] /dev/random - a new approach

Hi,

after distributing patches for the Linux-RNG - a new approach for the last
half year, I would like to submit this RFC for inclusion into the kernel.

The following patch set provides a different approach to /dev/random which
I call Linux Random Number Generator (LRNG) to collect entropy within the Linux
kernel. The main improvements compared to the legacy /dev/random is to provide
sufficient entropy during boot time as well as in virtual environments and when
using SSDs. A secondary design goal is to limit the impact of the entropy
collection on massive parallel systems and also allow the use accelerated
cryptographic primitives. Also, all steps of the entropic data processing are
testable.

The design and implementation is driven by a set of goals described in [1]
that the LRNG completely implements. Furthermore, [1] includes a
comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
AIS20/31.

Booting the patch with the kernel command line option
"dyndbg=file drivers/char/lrng* +p" generates logs indicating the operation
of the LRNG. Each log is pre-pended with "lrng:".

The LRNG has a flexible design by allowing an easy replacement of the
deterministic random number generator component. For the request of inclusion
into the kernel, the scope of the LRNG is limited compared to the previous
patch sets. The following components are not part of the patch set and are
intended for a separate submission:

- FIPS 140-2 continuous random number generator test -- the LRNG is therefore
  not compliant with FIPS 140-2 requirements.

- Support for using the SP800-90A DRBG.

[1] http://www.chronox.de/lrng.html

Changes (compared to v11 of the previous patch set):

* use PTR_ERR_OR_ZERO as suggested by Julia Lawall

* fixed coccocinelle warnings

* fixed cppcheck style hints

* streamlined add_interrupt_randomness

* all DRNG-specific code is re-allocated to the C files specific to the
  respective DRNG

* rename all macros from DRBG -> DRNG

* rename all functions from *drbg* -> *drng*

* functions grouped into pdrng and sdrng processing for easier reading

* Use Jitter RNG to seed even the init RNG for entropy at earliest boot time
  which implies that the very first random number generated by the LRNG is
  seeded with the Jitter RNG:
[    0.029839] lrng: Jitter RNG working on current system
[    0.030000] lrng: obtained 32 bits of entropy from Jitter RNG noise source

* incorporate wait_for_random_bytes from Jason A. Donenfeld

* incorporate invalidate_batched_entropy from Jason A. Donenfeld

* incorporate debug logs for unseeded DRNGs from Jason A. Donenfeld including
  rate limiting from Ted Ts'o

* rename lrng_standalone.c -> lrng_chacha20.c

* bug fix edge condition during reseed on NUMA systems

* enable stuck test during early boot

* When waiting for "good" random numbers, the following concept applies:
	- kernel space: reaching the minimally seeded level triggers wakeup
	- user space: reaching the fully seeded level triggers wakeup

* Use RDSEED for seeding operations and RDRAND as a fallback as suggested by
  DJ Johnston (note, the final fallback to use a high-resolution timer is
  implicitly present by using the time stamp unconditional for each reseed).

* conserve entropy in output function of primary DRNG

Stephan Mueller (4):
  crypto: make Jitter RNG directly accessible
  random: conditionally compile code depending on LRNG
  Linux Random Number Generator
  LRNG - enable compile

 crypto/jitterentropy.c         |   33 +-
 drivers/char/Kconfig           |   10 +
 drivers/char/Makefile          |   10 +-
 drivers/char/lrng_base.c       | 2297 ++++++++++++++++++++++++++++++++++++++++
 drivers/char/lrng_chacha20.c   |  291 +++++
 include/crypto/jitterentropy.h |   80 ++
 include/linux/genhd.h          |    5 +
 7 files changed, 2694 insertions(+), 32 deletions(-)
 create mode 100644 drivers/char/lrng_base.c
 create mode 100644 drivers/char/lrng_chacha20.c
 create mode 100644 include/crypto/jitterentropy.h

-- 
2.9.4

[toc] | [next] | [standalone]

#1689864 — [RFC PATCH v12 4/4] LRNG - enable compile

Add LRNG compilation support.

CC: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
CC: Arnd Bergmann <arnd@arndb.de>
CC: Jason A. Donenfeld <Jason@zx2c4.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/Kconfig  | 10 ++++++++++
 drivers/char/Makefile | 10 +++++++++-
 2 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/drivers/char/Kconfig b/drivers/char/Kconfig
index ccd239a..88cc472 100644
--- a/drivers/char/Kconfig
+++ b/drivers/char/Kconfig
@@ -587,5 +587,15 @@ config TILE_SROM
 
 source "drivers/char/xillybus/Kconfig"
 
+config LRNG
+	bool "Linux Random Number Generator"
+	select CRYPTO_DRBG_MENU
+	select CRYPTO_CMAC if CRYPTO_DRBG_CTR
+	help
+	  The Linux Random Number Generator (LRNG) is the replacement
+	  of the legacy /dev/random provided with drivers/char/random.c.
+	  It generates entropy from different noise sources and
+	  delivers significant entropy during boot.
+
 endmenu
 
diff --git a/drivers/char/Makefile b/drivers/char/Makefile
index 53e3372..87e06ec 100644
--- a/drivers/char/Makefile
+++ b/drivers/char/Makefile
@@ -2,7 +2,15 @@
 # Makefile for the kernel character device drivers.
 #
 
-obj-y				+= mem.o random.o
+obj-y				+= mem.o
+
+ifeq ($(CONFIG_LRNG),y)
+  obj-$(CONFIG_LRNG)		+= lrng.o
+  lrng-y			+= lrng_base.o lrng_chacha20.o
+else
+  obj-y				+= random.o
+endif
+
 obj-$(CONFIG_TTY_PRINTK)	+= ttyprintk.o
 obj-y				+= misc.o
 obj-$(CONFIG_ATARI_DSP56K)	+= dsp56k.o
-- 
2.9.4

[toc] | [prev] | [next] | [standalone]

#1689888 — Re: [RFC PATCH v12 4/4] LRNG - enable compile

On Tue, Jul 18, 2017 at 9:59 AM, Stephan Müller <smueller@chronox.de> wrote:
> Add LRNG compilation support.
>
> diff --git a/drivers/char/Makefile b/drivers/char/Makefile
> index 53e3372..87e06ec 100644
> --- a/drivers/char/Makefile
> +++ b/drivers/char/Makefile
> @@ -2,7 +2,15 @@
>  # Makefile for the kernel character device drivers.
>  #
>
> -obj-y                          += mem.o random.o
> +obj-y                          += mem.o
> +
> +ifeq ($(CONFIG_LRNG),y)
> +  obj-$(CONFIG_LRNG)           += lrng.o
> +  lrng-y                       += lrng_base.o lrng_chacha20.o
> +else
> +  obj-y                                += random.o
> +endif

I think you can write the same in a more readable way without the
intermediate object:

ifdef CONFIG_LRNG
  obj-y                       += lrng_base.o lrng_chacha20.o
else
  obj-y                       += random.o
endif

      Arnd

[toc] | [prev] | [next] | [standalone]

#1689891 — Re: [RFC PATCH v12 4/4] LRNG - enable compile

Am Dienstag, 18. Juli 2017, 10:51:41 CEST schrieb Arnd Bergmann:

Hi Arnd,

> On Tue, Jul 18, 2017 at 9:59 AM, Stephan Müller <smueller@chronox.de> wrote:
> > Add LRNG compilation support.
> > 
> > diff --git a/drivers/char/Makefile b/drivers/char/Makefile
> > index 53e3372..87e06ec 100644
> > --- a/drivers/char/Makefile
> > +++ b/drivers/char/Makefile
> > @@ -2,7 +2,15 @@
> > 
> >  # Makefile for the kernel character device drivers.
> >  #
> > 
> > -obj-y                          += mem.o random.o
> > +obj-y                          += mem.o
> > +
> > +ifeq ($(CONFIG_LRNG),y)
> > +  obj-$(CONFIG_LRNG)           += lrng.o
> > +  lrng-y                       += lrng_base.o lrng_chacha20.o
> > +else
> > +  obj-y                                += random.o
> > +endif
> 
> I think you can write the same in a more readable way without the
> intermediate object:
> 
> ifdef CONFIG_LRNG
>   obj-y                       += lrng_base.o lrng_chacha20.o
> else
>   obj-y                       += random.o
> endif

Thank you for the hint, it will be included.
> 
>       Arnd


Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1689871 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Tue, Jul 18, 2017 at 09:59:09AM +0200, Stephan Müller wrote:
> The LRNG with the following properties:
> 
> * noise source: interrupts timing with fast boot time seeding
> 
> * lockless LFSR to collect raw entropy
> 
> * use of standalone ChaCha20 based RNG with the option to use a
>   different DRNG selectable at compile time
> 
> * "atomic" seeding of secondary DRBG to ensure full entropy
>   transport
> 
> * instantiate one DRNG per NUMA node
> 
> Further details including the rationale for the design choices and
> properties of the LRNG together with testing is provided at [1].
> In addition, the documentation explains the conducted regression
> tests to verify that the LRNG is API and ABI compatible with the
> legacy /dev/random implementation.
> 
> [1] http://www.chronox.de/lrng.html

external references do not last as long as the kernel change log does :(

Also a "wholesale" replacement of random.c is a major thing, why not
just submit patches to fix it up to add the needed changes you feel are
necessary?  We don't like to have major changes like this, that's not
how kernel development is done.

thanks,

greg k-h

[toc] | [prev] | [next] | [standalone]

#1689878 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:

Hi Greg,

> external references do not last as long as the kernel change log does :(

What would be the best way to cite a 50+ page document? I got a suggestion to 
include the ASCII version of the document into Documentation/ -- but for the 
first inclusion request, I was not sure whether to add such large document.
> 
> Also a "wholesale" replacement of random.c is a major thing, why not
> just submit patches to fix it up to add the needed changes you feel are
> necessary?  We don't like to have major changes like this, that's not
> how kernel development is done.

I have to admit that I tried that over the last years. I sent numerous small 
cleanup patches (not changing any logic) and larger patches (with logic 
changes). Even after pinging, I hardly got a response to any of my patches, 
let alone that patches were accepted.

I have stated the core concerns I have with random.c in [1]. To remedy these 
core concerns, major changes to random.c are needed. With the past experience, 
I would doubt that I get the changes into random.c.

[1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1689892 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Tue, Jul 18, 2017 at 10:45:12AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:
> 
> Hi Greg,
> 
> > external references do not last as long as the kernel change log does :(
> 
> What would be the best way to cite a 50+ page document? I got a suggestion to 
> include the ASCII version of the document into Documentation/ -- but for the 
> first inclusion request, I was not sure whether to add such large document.
> > 
> > Also a "wholesale" replacement of random.c is a major thing, why not
> > just submit patches to fix it up to add the needed changes you feel are
> > necessary?  We don't like to have major changes like this, that's not
> > how kernel development is done.
> 
> I have to admit that I tried that over the last years. I sent numerous small 
> cleanup patches (not changing any logic) and larger patches (with logic 
> changes). Even after pinging, I hardly got a response to any of my patches, 
> let alone that patches were accepted.

Changing core kernel code is hard, really hard, for good reason.  I
don't recall seeing a patch series from you that addressed minor things
that you might have complaints about, why not send them again?

> I have stated the core concerns I have with random.c in [1]. To remedy these 
> core concerns, major changes to random.c are needed. With the past experience, 
> I would doubt that I get the changes into random.c.
> 
> [1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Evolution is the correct way to do this, kernel development relies on
that.  We don't do the "use this totally different and untested file
instead!" method.

thanks,

greg k-h

[toc] | [prev] | [next] | [standalone]

#1690330 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Dienstag, 18. Juli 2017, 10:52:12 CEST schrieb Greg Kroah-Hartman:

Hi Greg,

> 
> > I have stated the core concerns I have with random.c in [1]. To remedy
> > these core concerns, major changes to random.c are needed. With the past
> > experience, I would doubt that I get the changes into random.c.
> > 
> > [1] https://www.spinics.net/lists/linux-crypto/msg26316.html
> 
> Evolution is the correct way to do this, kernel development relies on
> that.  We don't do the "use this totally different and untested file
> instead!" method.

I am not sure I understand your reply. The offered patch set does not rip out 
existing code. It adds a replacement implementation which can be enabled 
during compile time. Yet it is even disabled per default (and thus the legacy 
code is compiled).

I see such a development approach in numerous different kernel core areas: 
memory allocators (SLAB, SLOB, SLUB), process schedulers, IRQ schedulers.

What is so different for the realm of RNGs?

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1690650 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Tue, Jul 18, 2017 at 04:37:11PM +0200, Stephan Müller wrote:
> > 
> > > I have stated the core concerns I have with random.c in [1]. To remedy
> > > these core concerns, major changes to random.c are needed. With the past
> > > experience, I would doubt that I get the changes into random.c.
> > > 
> > > [1] https://www.spinics.net/lists/linux-crypto/msg26316.html
> > 
> > Evolution is the correct way to do this, kernel development relies on
> > that.  We don't do the "use this totally different and untested file
> > instead!" method.
> 
> I am not sure I understand your reply. The offered patch set does not rip out 
> existing code. It adds a replacement implementation which can be enabled 
> during compile time. Yet it is even disabled per default (and thus the legacy 
> code is compiled).

I've been trying to take the best features and suggestions from your
proposal and integrating them into /dev/random already.  Things that
I've chosen not take is basically because I disbelieve that the Jitter
RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
access to Intel chip architects, who has expressed unease) more than
you.  (No hard feelings).

So I have been trying to do the evolution thing already.  

> I see such a development approach in numerous different kernel core areas: 
> memory allocators (SLAB, SLOB, SLUB), process schedulers, IRQ schedulers.

But we don't have two VFS layers or two MM layers.  We also don't have
two implementations of printk.

I'm obviously biased, but I don't see I see the Raison d'Etre for
merging LRNG into the kernel.

						- Ted

[toc] | [prev] | [next] | [standalone]

#1690865 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o <tytso@mit.edu> wrote:

> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.

A good approach.

> Things that I've chosen not take is basically because I disbelieve
> that the Jitter RNG is valid. ...

The biggest problem with random(4) is that you cannot generate good
output without a good seed & just after boot, especially first boot on
a new system, you may not have enough entropy. A user space process
cannot do it soon enough and all the in-kernel solutions (unless you
have a hardware RNG) pose difficulties.

The only really good solution I know of is to find a way to provide a
chunk of randomness early in the boot process. John Denker has a good
discussion of doing this by modifying the kernel image & Ted talks of
doing it via the boot loader. Neither looks remarkably easy. Other
approaches like making the kernel read a seed file or passing a
parameter on the kernel command line have been suggested but, if I
recall right, rejected.

As I see it, the questions about Jitter, or any other in-kernel
generator based on timing, are whether it is good enough to be useful
until we have one of the above solutions or useful as a
defense-in-depth trick after we have one. I'd say yes to both.

There's been a lot of analysis. Stephan has a detailed rationale & a
lot of test data in his papers & the Havege papers also discuss
getting entropy from timer operations. I'd say the best paper is
McGuire et al:
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

There is enough there to convince me that grabbing some (256?) bits
from such a generator early in the initialization is worthwhile.

> So I have been trying to do the evolution thing already.
> ...

> I'm obviously biased, but I don't see I see the Raison d'Etre for
> merging LRNG into the kernel.

Nor I.

[toc] | [prev] | [next] | [standalone]

#1690906 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Tue, Jul 18, 2017 at 09:00:10PM -0400, Sandy Harris wrote:
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. Neither looks remarkably easy. Other
> approaches like making the kernel read a seed file or passing a
> parameter on the kernel command line have been suggested but, if I
> recall right, rejected.

It's actually not that _hard_ to modify the boot loader.  It's not
finicky work like, say, adding support for metadata checksums or xattr
deduplication to ext4.  It's actually mostly plumbing.  It's just that
we haven't found a lot of people willing to do it as paid work, and
the hobbyists haven't been interested.

> As I see it, the questions about Jitter, or any other in-kernel
> generator based on timing, are whether it is good enough to be useful
> until we have one of the above solutions or useful as a
> defense-in-depth trick after we have one. I'd say yes to both.
> 
> There's been a lot of analysis. Stephan has a detailed rationale & a
> lot of test data in his papers & the Havege papers also discuss
> getting entropy from timer operations. I'd say the best paper is
> McGuire et al:
> https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

So here's the problem that I have with most of these analyses.  Most
of them are done using the x86 as the CPU.  This is true of the
McGuire, Okech, and Schiesser paper you've cited above.  But things
are largely irrelevant on the x86, because we have RDRAND.  And while
I like to mix in environmental noise before generating personal
long-term public keys.  I'm actually mostly OK with relying on RDRAND
for initializing the seeds for hash table to protect against network
denial of service attacks.  (Which is currently the first user of the
not-yet-initialized CRNG on my laptop during kernel boot.)

The real problem is with the non-x86 systems that don't have a
hardware RNG, and there depending timing events which don't depend on
external devices is much more dodgy.  Remember that on most embedded
devices there is only a single oscillator driving the entire system.
It's not like you even have multiple crystal oscillators beating
against one another.

So if you are only depending on CPU timing loops, you basically have a
very complex state machine, driven by a single oscillator, and you're
trying to kid yourself that you're getting entropy out the other end.
How is that any different from using AES in counter mode and claiming
because you don't know the seed, that it's "true randomness"?  It
certainly passes all of the statistical tests!

Hence, we have to rely on external events outside of the CPU and so we
need to depend on interrupt timing --- and that's what we do in
drivers/char/random.c already!  You can debate whether we are being
too conservative with when we judge that we've collective enough
unpredictability to count it as a "bit" of randomness.  So it's
trivially easy to turn the knob and make sure the CRNG gets
initialized more quickly using fewer interrupt timings, and boom!
Problem solved.

Simply turning the knob to make our entropy estimator more lax makes
people uncomfortable, and since they don't have access to the internal
microarchitecture of the CPU, they take comfort in the fact that it's
really, really complicated, and so something like the Jitter RNG
*must* be a more secure way to do things.  But that's really an illusion.

If the real unpredictability is really coming from the interrupts
changing the state of the CPU microarchitecture, the real question is
how many interrupts do you need before you consider things
"unpredictable" to an adequate level of security?  Arguing that we
should turn down the "interrupts per bit of entropy" in
drivers/char/random.c is a much more honest way of having that
discussion.

					- Ted

P.S.  In the McGuire paper you cited, it assumes that the system is
fully booted and there are multiple processes running which are
influencing the kernel scheduler.  This makes the paper **not** an
applicable at all.  So if you think that is the most compelling
analysis, I'm definitely not impressed....

[toc] | [prev] | [next] | [standalone]

#1691017 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Mittwoch, 19. Juli 2017, 03:51:33 CEST schrieb Theodore Ts'o:

Hi Theodore,

> If the real unpredictability is really coming from the interrupts
> changing the state of the CPU microarchitecture, the real question is
> how many interrupts do you need before you consider things
> "unpredictable" to an adequate level of security?  Arguing that we
> should turn down the "interrupts per bit of entropy" in
> drivers/char/random.c is a much more honest way of having that
> discussion.

Please answer on the concerns given in [1] which explains that we cannot allow 
turning that knob in the current implementation.

[1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1699509 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

[Multipart message — attachments visible in raw view] — view raw

Hi!

On Tue 2017-07-18 21:51:33, Theodore Ts'o wrote:
> On Tue, Jul 18, 2017 at 09:00:10PM -0400, Sandy Harris wrote:
> > The only really good solution I know of is to find a way to provide a
> > chunk of randomness early in the boot process. John Denker has a good
> > discussion of doing this by modifying the kernel image & Ted talks of
> > doing it via the boot loader. Neither looks remarkably easy. Other
> > approaches like making the kernel read a seed file or passing a
> > parameter on the kernel command line have been suggested but, if I
> > recall right, rejected.
> 
> It's actually not that _hard_ to modify the boot loader.  It's not
> finicky work like, say, adding support for metadata checksums or xattr
> deduplication to ext4.  It's actually mostly plumbing.  It's just that
> we haven't found a lot of people willing to do it as paid work, and
> the hobbyists haven't been interested.

Modifying the boot loader sources is not hard, right.

Deploying the modified boot loader is another story; these are
bootloaders -- they normally don't need updating, so they are often
not easy to update, or maybe updating them is risky.

Anyway, if you want to pay for some bootloader modifications... I'm
working for a company that can help :-). (Sometimes I use
pavel@denx.de address.)

									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[toc] | [prev] | [next] | [standalone]

#1694347 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Sandy Harris <sandyinchina@gmail.com> wrote:

> The biggest problem with random(4) is that you cannot generate good
> output without a good seed & just after boot, ...
>
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. ...

Would it be enough to have a kernel module that does more-or-less what
the current shell scripts do, but earlier in the boot process? Throw
the stored data into the random(4) driver at module init time & update
it periodically later. This would not help much for first boot on a
new system, unless its store could be updated during install; Denker's
point that you need each system provisioned differently is important.
However it looks like it would be enough on other boots.

It also looks like it might be easier to implement & test. In
particular it is an isolated do-one-thing-well tool; the programmer
only needs to worry about his or her module, not several different
boot loaders or the procedures that distros have for CD images or
manufacturers for device setup.

[toc] | [prev] | [next] | [standalone]

#1694360 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Sun, Jul 23, 2017 at 02:05:38PM -0400, Sandy Harris wrote:
> Sandy Harris <sandyinchina@gmail.com> wrote:
> 
> > The biggest problem with random(4) is that you cannot generate good
> > output without a good seed & just after boot, ...
> >
> > The only really good solution I know of is to find a way to provide a
> > chunk of randomness early in the boot process. John Denker has a good
> > discussion of doing this by modifying the kernel image & Ted talks of
> > doing it via the boot loader. ...
> 
> Would it be enough to have a kernel module that does more-or-less what
> the current shell scripts do, but earlier in the boot process? Throw
> the stored data into the random(4) driver at module init time & update
> it periodically later. This would not help much for first boot on a
> new system, unless its store could be updated during install; Denker's
> point that you need each system provisioned differently is important.
> However it looks like it would be enough on other boots.

There are two things that make this hard.  The first is progamming
environment for, say, the GRUB bootloader, is very different from that
of, say, a System V init script.  The second is that it's not obvious
where you can safely store the information across boots.

For a specific architecture --- say, a PC desktop/server using a MBR
or GPT partition table, it's not that hard.  At which point, if you
want to assume that you are using a distribution kernel which is using
an initial ramdisk, you might not even need a kernel module; you could
just do it in the initrd before systemd gets a chance to run, and then
you can do it as a straight-forward shell script.  So that's actually
not hard, and not that different from what we have today.

It won't solve the problem for, say a Tails system, where you could be
booting off of a DVD (in which case you might not have any place to
store state), or a USB or SD card.  That's *also* not hard, but you
end up having to have a different solution for that case.

> It also looks like it might be easier to implement & test. In
> particular it is an isolated do-one-thing-well tool; the programmer
> only needs to worry about his or her module, not several different
> boot loaders or the procedures that distros have for CD images or
> manufacturers for device setup.

Unfortunately, you *do* still have to worry about multiple partition
tables, and potential places where the entropy could be stored.  The
solution for MBR, GPT, and Tails will all have to be slightly
different.

Again, none of this is terribly tricky work.  There are lots of fiddly
details, and if you get it right for one configuration, you will still
have to do something else for the next configuration.  So it's a lot
of grunt work, and since you can't come up for one solution that will
solve it for all systems, it won't be terribly glorious.

Note that you can also solve this problem by diddling the systemd unit
files, if you can make sure that you can fix the dependencies such
that the entropy setup is the very thing that happens after root file
system is mounted read/write, and before anything that might try to
generate keys is allowed to run.  That's going to be roughly the same
level of coverage as a kernel module and doesn't require trying to
store it in some partition-table unique place, but instead you have to
learn a lot of about systemd unit file configuration.

Cheers,

						- Ted

[toc] | [prev] | [next] | [standalone]

#1691010 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Dienstag, 18. Juli 2017, 23:08:16 CEST schrieb Theodore Ts'o:

Hi Theodore,
> 
> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.  Things that
> I've chosen not take is basically because I disbelieve that the Jitter
> RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
> access to Intel chip architects, who has expressed unease) more than
> you.  (No hard feelings).

I am unsure why you always point to the Jitter RNG. This is one noise source 
to keep or to remove -- at least it provides more data during early boot than 
any other noise source we currently have.

In the email [1] I have expressed the core concerns I see -- none of them 
address the need to keep the Jitter RNG as one noise source. To address those, 
a very deep dive into random.c needs to be made.

Such deep dive has the potential to be disruptive. Therefore, doesn't it make 
more sense to have such conceptual changes rather covered in a separate 
implementation?

[1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1691030 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 23:08:16 CEST schrieb Theodore Ts'o:
> 
> Hi Theodore,
> > 
> > I've been trying to take the best features and suggestions from your
> > proposal and integrating them into /dev/random already.  Things that
> > I've chosen not take is basically because I disbelieve that the Jitter
> > RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
> > access to Intel chip architects, who has expressed unease) more than
> > you.  (No hard feelings).
> 
> I am unsure why you always point to the Jitter RNG. This is one noise source 
> to keep or to remove -- at least it provides more data during early boot than 
> any other noise source we currently have.
> 
> In the email [1] I have expressed the core concerns I see -- none of them 
> address the need to keep the Jitter RNG as one noise source. To address those, 
> a very deep dive into random.c needs to be made.
> 
> Such deep dive has the potential to be disruptive. Therefore, doesn't it make 
> more sense to have such conceptual changes rather covered in a separate 
> implementation?

No, it makes more sense to send individual patches addressing your
concerns to the existing random driver.  Again, that's how
kernel development has always worked.

thanks,

greg k-h

[toc] | [prev] | [next] | [standalone]

#1692047 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> In the email [1] I have expressed the core concerns I see -- none of them 
> address the need to keep the Jitter RNG as one noise source. To address those, 
> a very deep dive into random.c needs to be made.

That's simply not true.  The other issues besides the Jitter RNG are
really nits.

One of your complaints is the fact that we collect both interrupt
timing and HID/block timings.  First of all, we could eliminate the
HID/block timings since in practice we get the vast majority of our
entropy from the interrupt timing.  I keep it because we have a real
theoretical basis for their being unpredictability from the HID/block
timings.  For example, [1].

[1] http://world.std.com/~dtd/random/forward.pdf

The fact that there might be double count from the perspective of
entropy is not really an issue because we do a "fast mix" of 64
interrupts before we mix into the primary interrupt pool.  And when we
do mix into the primary pool we count that only as a single bit of
entropy.  The reason why I'm being super cautious here is because some
of these interrupts might be timer interrupts, or come from other
sources that might be correlated to the clock interrupt.  The
conservative assumption here is that at least one of the interrupts
out of 64, on average, will come from something that the adversary can
not anticipate, such as coming from a NIC or wireless device, and that
we will get at least one bit's worth of unpredictability.

The fact that we also mix in the jiffies plus the keyboard/mouse scan
code, is something that happens immediately.  So even if you think we
should not count the fast mix interrupt count, the fact that we mix
the timing values from 64 interrupts before we credit the entropy
counter by a single bit is sufficiently conservative; we're talking
about 1/64th of a bit here.

But if you **really** think mixing in the timing of the HID event
(gathered via a different mechanism --- jiffies vs cycle counter, and
including the the keyboard scan), a patch to disable
add_keyboard_randomness() is pretty trivial.  It doesn't justify a
complete rewrite of the random core.

(BTW, granted this is anecdata, but on my laptop, the CRNG is fully
initialized before systemd has even started and before the root file
system is mounted.  And after that point the entropy initialization
only matters for the legacy apps that use /dev/random, which doesn't
even exist in your proposed RNG, since everything just uses a
ChaCha20-based CRNG.)


Another one of your complaints is a straw-man argument ("I understand
that this pathological case is not present for the legacy
/dev/random...").  First of all, how we do entropy estimation after
the CRNG boot is far less important, because the primary recommended
interface is /dev/urandom or better yet getrandom(2).  Secondly, we
*don't* allow transfer of small quantums of entropy.  There is a
minimum transfer limit of 64 bits, and that can easily be increased to
128 bits if one really cared.  I've never really considered recovery
from state compromise to be that important, but if one did care,
increasing that limit is a two line patch.


I could go on, but the bottom line is that, quite frankly, I don't
consider your criticsms to be particular compelling or convincing.

Regards,

						- Ted

[toc] | [prev] | [next] | [standalone]

#1693179 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Mittwoch, 19. Juli 2017, 19:26:03 CEST schrieb Theodore Ts'o:

Hi Theodore,

> On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> > In the email [1] I have expressed the core concerns I see -- none of them
> > address the need to keep the Jitter RNG as one noise source. To address
> > those, a very deep dive into random.c needs to be made.
> 
> That's simply not true.  The other issues besides the Jitter RNG are
> really nits.
> 
> One of your complaints is the fact that we collect both interrupt
> timing and HID/block timings.  First of all, we could eliminate the
> HID/block timings since in practice we get the vast majority of our
> entropy from the interrupt timing.  I keep it because we have a real
> theoretical basis for their being unpredictability from the HID/block
> timings.  For example, [1].
> 
> [1] http://world.std.com/~dtd/random/forward.pdf
> 
> The fact that there might be double count from the perspective of
> entropy is not really an issue because we do a "fast mix" of 64
> interrupts before we mix into the primary interrupt pool.  And when we
> do mix into the primary pool we count that only as a single bit of
> entropy.  The reason why I'm being super cautious here is because some
> of these interrupts might be timer interrupts, or come from other
> sources that might be correlated to the clock interrupt.  The
> conservative assumption here is that at least one of the interrupts
> out of 64, on average, will come from something that the adversary can
> not anticipate, such as coming from a NIC or wireless device, and that
> we will get at least one bit's worth of unpredictability.
> 
> The fact that we also mix in the jiffies plus the keyboard/mouse scan
> code, is something that happens immediately.  So even if you think we
> should not count the fast mix interrupt count, the fact that we mix
> the timing values from 64 interrupts before we credit the entropy
> counter by a single bit is sufficiently conservative; we're talking
> about 1/64th of a bit here.

I concur with your rationale where de-facto the correlation is effect is 
diminished and eliminated with the fast_pool and the minimal entropy 
estimation of interrupts.

But it does not address my concern. Maybe I was not clear, please allow me to 
explain it again.

We have lots of entropy in the system which is discarded by the aforementioned 
approach (if a high-res timer is present -- without it all bets are off anyway 
and this should be covered in a separate discussion). At boot time, this issue 
is fixed by injecting 256 interrupts in the CRNG and consider it seeded.

But at runtime, were we still need entropy to reseed the CRNG and to supply /
dev/random. The accounting of entropy at runtime is much too conservative 
compared to any types of measurements that were conducted on bare metal or 
virtualized environment or on different architectures (if requested, I can 
surely share the test code and results in addition to already published 
studies -- see [1] table 1, 2 and 3 with figure 3.2 to get an idea). As long 
as a high-resolution time stamp is present, interrupts do provide much more 
than 1/64th bit of entropy per occurrence.

[1] http://www.chronox.de/lrng/doc/lrng.pdf

The implementation that was precisely outlined above present in random.c 
however does not allow revaluing the amount of entropy present in interrupts 
to a higher level simply because then the correlation issue kicks in.

Thus, when we want to re-value the interrupts with a higher level of entropy, 
we need to take out the high-resolution time stamp (and thus the more or less 
sole effective entropy provider for add_[disk|input]_randomness).

You mentioned that you are super conservative for interrupts due to timer 
interrupts. In all measurements on the different systems I conducted, I have 
not seen that the timer triggers an interrupt picked up by 
add_interrupt_randomness. For the sake of discussion, let us assume that such 
timer interrupts are present for a worst-case assessment. Such timer 
interrupts by nature should occur very periodically. Thus, it should be easy 
to detect them. IMHO the suggested stuck test in the LRNG exactly covers that 
scenario: only if the 1st, 2nd and 3rd derivative of the time stamp is non-
zero, the interrupt time stamp is considered to deliver entropy.

Thus, when revaluing the interrupt entropy, and removing the high-res timer 
from HID/block devices, the entropy heuristic in add_timer_randomness can go.

As we have no formal model about entropy to begin with, we can only assume and 
hope we underestimate entropy with the entropy heuristic. Thus, a precise 
entropy update with the asymptotic calculation in credit_entropy_bits may also 
not really be helpful and could be discarded.

> 
> But if you **really** think mixing in the timing of the HID event
> (gathered via a different mechanism --- jiffies vs cycle counter, and
> including the the keyboard scan), a patch to disable
> add_keyboard_randomness() is pretty trivial.  It doesn't justify a
> complete rewrite of the random core.
> 
> (BTW, granted this is anecdata, but on my laptop, the CRNG is fully
> initialized before systemd has even started and before the root file
> system is mounted.

Agreed, I see that too. And as mentioned above, this is how I think it is 
appropriate. This behavior is very similar to what I see on my LRNG.

> And after that point the entropy initialization
> only matters for the legacy apps that use /dev/random, which doesn't
> even exist in your proposed RNG, since everything just uses a
> ChaCha20-based CRNG.)
> 

I am not sure I understand the last statement. The blocking_pool (or the 
ChaCha20 DRNG in my LRNG) feeding /dev/random is simply a deterministic RNG 
with prediction resistance (in SP800-90A-speak). I.e. when one random bit 
shall be generated, one bit of entropy from the noise sources needs to go in.

Whether you have a blocking_pool or a normal DRNG to feed /dev/random does not 
matter as long as it only delivers as many bits as went in as entropy.
> 
> Another one of your complaints is a straw-man argument ("I understand
> that this pathological case is not present for the legacy
> /dev/random...").  First of all, how we do entropy estimation after
> the CRNG boot is far less important, because the primary recommended
> interface is /dev/urandom or better yet getrandom(2).  Secondly, we
> *don't* allow transfer of small quantums of entropy.  There is a
> minimum transfer limit of 64 bits, and that can easily be increased to
> 128 bits if one really cared.  I've never really considered recovery
> from state compromise to be that important, but if one did care,
> increasing that limit is a two line patch.

_xfer_secondary_pool says:

        /* pull at least as much as a wakeup */
        bytes = max_t(int, bytes, random_read_wakeup_bits / 8);

This determines the minimum amount. random_read_wakeup_bits can be changed by 
user space:

        {
                .procname       = "read_wakeup_threshold",
                .data           = &random_read_wakeup_bits,
                .maxlen         = sizeof(int),
                .mode           = 0644,
                .proc_handler   = proc_dointvec_minmax,
                .extra1         = &min_read_thresh,
                .extra2         = &max_read_thresh,
        },

min_read_thresh is 8.

Thus, the minimum amount of transfer is 1 byte as far as I read. I concur, 
however, that the default is 64 (bits).

This is what I would suggest to have changed to, say, the absolute minimum of 
64 or 128 bits.



Finally, I still think it is helpful to allow (not mandate) to involve the 
kernel crypto API for the DRNG maintenance (i.e. the supplier for /dev/random 
and /dev/urandom). The reason is that now more and more DRNG implementations 
in hardware pop up. Why not allowing them to be used. I.e. random.c would only 
contain the logic to manage entropy but uses the DRNG requested by a user.

In addition allowing a replacement of the DRNG component (at compile time at 
least) may get us away from having a separate DRNG solution in the kernel 
crypto API. Some users want their chosen or a standardized DRNG to deliver 
random numbers. Thus, we have several DRNGs in the kernel crypto API which are 
seeded by get_random_bytes. Or in user space, many folks need their own DRNG 
in user space in addition to the kernel. IMHO this is all a waste. If we could 
use the user-requested DRNG when producing random numbers for get_random_bytes 
or /dev/urandom or getrandom.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1693358 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

On Thu, Jul 20, 2017 at 09:00:02PM +0200, Stephan Müller wrote:
> I concur with your rationale where de-facto the correlation is effect is 
> diminished and eliminated with the fast_pool and the minimal entropy 
> estimation of interrupts.
> 
> But it does not address my concern. Maybe I was not clear, please allow me to 
> explain it again.
> 
> We have lots of entropy in the system which is discarded by the aforementioned 
> approach (if a high-res timer is present -- without it all bets are off anyway 
> and this should be covered in a separate discussion). At boot time, this issue 
> is fixed by injecting 256 interrupts in the CRNG and consider it seeded.
> 
> But at runtime, were we still need entropy to reseed the CRNG and to supply /
> dev/random. The accounting of entropy at runtime is much too conservative...

Practically no one uses /dev/random.  It's essentially a deprecated
interface; the primary interfaces that have been recommended for well
over a decade is /dev/urandom, and now, getrandom(2).  We only need
384 bits of randomness every 5 minutes to reseed the CRNG, and that's
plenty even given the very conservative entropy estimation currently
being used.

This was deliberate.  I care a lot more that we get the initial
boot-time CRNG initialization right on ARM32 and MIPS embedded
devices, far, far, more than I care about making plenty of
information-theoretic entropy available at /dev/random on an x86
system.  Further, I haven't seen an argument for the use case where
this would be valuable.

If you don't think they count because ARM32 and MIPS don't have a
high-res timer, then you have very different priorities than I do.  I
will point out that numerically there are huge number of these devices
--- and very, very few users of /dev/random.

> You mentioned that you are super conservative for interrupts due to timer 
> interrupts. In all measurements on the different systems I conducted, I have 
> not seen that the timer triggers an interrupt picked up by 
> add_interrupt_randomness.

Um, the timer is the largest number of interrupts on my system.  Compare:

            CPU0       CPU1       CPU2       CPU3
 LOC:    6396552    6038865    6558646    6057102   Local timer interrupts

with the number of disk related interrupts:

 120:      21492     139284      40513    1705886   PCI-MSI 376832-edge      ahci[0000:00:17.0]

... and add_interrupt_randomness() gets called for **every**
interrupt.  On an mostly idle machine (I was in meetings most of
today) it's not surprising that time interrupts dominate.  That
doesn't matter for me as much because I don't really care about
/dev/random performance.  What's is **far** more important is that the
entropy estimations behave correctly, across all of Linux's
architectures, while the kernel is going through startup, before CRNG
is declared initialized.

> As we have no formal model about entropy to begin with, we can only assume and 
> hope we underestimate entropy with the entropy heuristic.

Yes, and that's why I use an ultra-conservative estimate.  If we start
using a more aggressive hueristic, we open ourselves up to potentially
very severe security bugs --- and for what?  What's the cost benefit
ratio here which makes this a worthwhile thing to risk?

> Finally, I still think it is helpful to allow (not mandate) to involve the 
> kernel crypto API for the DRNG maintenance (i.e. the supplier for /dev/random 
> and /dev/urandom). The reason is that now more and more DRNG implementations 
> in hardware pop up. Why not allowing them to be used. I.e. random.c would only 
> contain the logic to manage entropy but uses the DRNG requested by a user.

We *do* allow them to be used.  And we support a large number of
hardware random number generators already.  See drivers/char/hw_random.

BTW, I theorize that this is why the companies that could do the
bootloader random seen work haven't bothered.  Most of their products
have a TPM or equivalent, and with modern kernel the hw_random
interface now has a kernel thread that will automatically fill the
/dev/random entropy pool from the hw_random device.  So this all works
already, today, without needing a userspace rngd (which used to be
required).

> In addition allowing a replacement of the DRNG component (at compile time at 
> least) may get us away from having a separate DRNG solution in the kernel 
> crypto API. Some users want their chosen or a standardized DRNG to deliver 
> random numbers. Thus, we have several DRNGs in the kernel crypto API which are 
> seeded by get_random_bytes. Or in user space, many folks need their own DRNG 
> in user space in addition to the kernel. IMHO this is all a waste. If we could 
> use the user-requested DRNG when producing random numbers for get_random_bytes 
> or /dev/urandom or getrandom.

To be honest, I've never understood why that's there in the crypto API
at all.  But adding more ways to switch out the DRNG for /dev/random
doesn't solve that problem; in fact it's moving things in the wrong
direction.

Cheers,

						- Ted

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web