Date:   Sun, 17 Nov 2019 23:55:24 +0100
From:   Stephan Müller <smueller@...onox.de>
To:     Andy Lutomirski <luto@...capital.net>
Cc:     Arnd Bergmann <arnd@...db.de>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        linux-crypto@...r.kernel.org, LKML <linux-kernel@...r.kernel.org>,
        linux-api@...r.kernel.org,
        "Eric W. Biederman" <ebiederm@...ssion.com>,
        "Alexander E. Patrakov" <patrakov@...il.com>,
        "Ahmed S. Darwish" <darwish.07@...il.com>,
        "Theodore Y. Ts'o" <tytso@....edu>, Willy Tarreau <w@....eu>,
        Matthew Garrett <mjg59@...f.ucam.org>,
        Vito Caputo <vcaputo@...garu.com>,
        Andreas Dilger <adilger.kernel@...ger.ca>,
        Jan Kara <jack@...e.cz>, Ray Strode <rstrode@...hat.com>,
        William Jon McCann <mccann@....edu>,
        zhangjs <zachary@...shancloud.com>,
        Andy Lutomirski <luto@...nel.org>,
        Florian Weimer <fweimer@...hat.com>,
        Lennart Poettering <mzxreary@...inter.de>,
        Nicolai Stange <nstange@...e.de>,
        "Peter, Matthias" <matthias.peter@....bund.de>,
        Marcelo Henrique Cerri <marcelo.cerri@...onical.com>,
        Roman Drahtmueller <draht@...altsekun.de>,
        Neil Horman <nhorman@...hat.com>
Subject: Re: [PATCH v25 12/12] LRNG - add interface for gathering of raw entropy

Am Samstag, 16. November 2019, 17:51:24 CET schrieb Andy Lutomirski:

Hi Andy,

> > On Nov 16, 2019, at 1:40 AM, Stephan Müller <smueller@...onox.de> wrote:
> > 
> > The test interface allows a privileged process to capture the raw
> > unconditioned noise that is collected by the LRNG for statistical
> > analysis. Extracted noise data is not used to seed the LRNG. This
> > is a test interface and not appropriate for production systems.
> > Yet, the interface is considered to be sufficiently secured for
> > production systems.
> > 
> > Access to the data is given through the lrng_raw debugfs file. The
> > data buffer should be multiples of sizeof(u32) to fill the entire
> > buffer. Using the option lrng_testing.boot_test=1 the raw noise of
> > the first 1000 entropy events since boot can be sampled.
> > 
> > This test interface allows generating the data required for
> > analysis whether the LRNG is in compliance with SP800-90B
> > sections 3.1.3 and 3.1.4.
> > 
> > CC: "Eric W. Biederman" <ebiederm@...ssion.com>
> > CC: "Alexander E. Patrakov" <patrakov@...il.com>
> > CC: "Ahmed S. Darwish" <darwish.07@...il.com>
> > CC: "Theodore Y. Ts'o" <tytso@....edu>
> > CC: Willy Tarreau <w@....eu>
> > CC: Matthew Garrett <mjg59@...f.ucam.org>
> > CC: Vito Caputo <vcaputo@...garu.com>
> > CC: Andreas Dilger <adilger.kernel@...ger.ca>
> > CC: Jan Kara <jack@...e.cz>
> > CC: Ray Strode <rstrode@...hat.com>
> > CC: William Jon McCann <mccann@....edu>
> > CC: zhangjs <zachary@...shancloud.com>
> > CC: Andy Lutomirski <luto@...nel.org>
> > CC: Florian Weimer <fweimer@...hat.com>
> > CC: Lennart Poettering <mzxreary@...inter.de>
> > CC: Nicolai Stange <nstange@...e.de>
> > Reviewed-by: Roman Drahtmueller <draht@...altsekun.de>
> > Tested-by: Roman Drahtmüller <draht@...altsekun.de>
> > Tested-by: Marcelo Henrique Cerri <marcelo.cerri@...onical.com>
> > Tested-by: Neil Horman <nhorman@...hat.com>
> > Signed-off-by: Stephan Mueller <smueller@...onox.de>
> > ---
> > drivers/char/lrng/Kconfig        |  16 ++
> > drivers/char/lrng/Makefile       |   1 +
> > drivers/char/lrng/lrng_testing.c | 324 +++++++++++++++++++++++++++++++
> > 3 files changed, 341 insertions(+)
> > create mode 100644 drivers/char/lrng/lrng_testing.c
> > 
> > diff --git a/drivers/char/lrng/Kconfig b/drivers/char/lrng/Kconfig
> > index e6ca3acc1e48..4ccc710832ef 100644
> > --- a/drivers/char/lrng/Kconfig
> > +++ b/drivers/char/lrng/Kconfig
> > @@ -169,4 +169,20 @@ config LRNG_APT_CUTOFF
> > 
> >    default 325 if !LRNG_APT_BROKEN
> >    default 32 if LRNG_APT_BROKEN
> > 
> > +config LRNG_TESTING
> > +    bool "Enable entropy test interface to LRNG noise source"
> > +    select CONFIG_DEBUG_FS
> > +    help
> > +      The test interface allows a privileged process to capture
> > +      the raw unconditioned noise that is collected by the LRNG
> > +      for statistical analysis. Extracted noise data is not used
> > +      to seed the LRNG.
> > +
> > +      The raw noise data can be obtained using the lrng_raw
> > +      debugfs file. Using the option lrng_testing.boot_test=1
> > +      the raw noise of the first 1000 entropy events since boot
> > +      can be sampled.
> > +
> > +      If unsure, say N.
> > +
> > endif # LRNG
> > diff --git a/drivers/char/lrng/Makefile b/drivers/char/lrng/Makefile
> > index 0713e9c0aa6e..c0b6cc4301fe 100644
> > --- a/drivers/char/lrng/Makefile
> > +++ b/drivers/char/lrng/Makefile
> > @@ -16,3 +16,4 @@ obj-$(CONFIG_LRNG_KCAPI)    += lrng_kcapi.o
> > obj-$(CONFIG_LRNG_JENT)        += lrng_jent.o
> > obj-$(CONFIG_LRNG_TRNG_SUPPORT)    += lrng_trng.o
> > obj-$(CONFIG_LRNG_HEALTH_TESTS)    += lrng_health.o
> > +obj-$(CONFIG_LRNG_TESTING)    += lrng_testing.o
> > diff --git a/drivers/char/lrng/lrng_testing.c
> > b/drivers/char/lrng/lrng_testing.c new file mode 100644
> > index 000000000000..5c33d3bd2172
> > --- /dev/null
> > +++ b/drivers/char/lrng/lrng_testing.c
> > @@ -0,0 +1,324 @@
> > +// SPDX-License-Identifier: GPL-2.0 OR BSD-2-Clause
> > +/*
> > + * Linux Random Number Generator (LRNG) Raw entropy collection tool
> > + *
> > + * Copyright (C) 2019, Stephan Mueller <smueller@...onox.de>
> > + */
> > +
> > +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
> > +
> > +#include <linux/atomic.h>
> > +#include <linux/bug.h>
> > +#include <linux/debugfs.h>
> > +#include <linux/module.h>
> > +#include <linux/sched.h>
> > +#include <linux/sched/signal.h>
> > +#include <linux/slab.h>
> > +#include <linux/string.h>
> > +#include <linux/types.h>
> > +#include <linux/uaccess.h>
> > +#include <linux/workqueue.h>
> > +#include <asm/errno.h>
> > +
> > +#include "lrng_internal.h"
> > +
> > +#define LRNG_TESTING_RINGBUFFER_SIZE    1024
> > +#define LRNG_TESTING_RINGBUFFER_MASK    (LRNG_TESTING_RINGBUFFER_SIZE -
> > 1)
> > +
> > +static u32 lrng_testing_rb[LRNG_TESTING_RINGBUFFER_SIZE];
> > +static atomic_t lrng_rb_reader = ATOMIC_INIT(0);
> > +static atomic_t lrng_rb_writer = ATOMIC_INIT(0);
> > +static atomic_t lrng_rb_first_in = ATOMIC_INIT(0);
> > +static atomic_t lrng_testing_enabled = ATOMIC_INIT(0);
> > +
> > +static DECLARE_WAIT_QUEUE_HEAD(lrng_raw_read_wait);
> > +
> > +static u32 boot_test = 0;
> > +module_param(boot_test, uint, 0644);
> > +MODULE_PARM_DESC(boot_test, "Enable gathering boot time entropy of the
> > first" +                " entropy events");
> > +
> > +static inline void lrng_raw_entropy_reset(void)
> > +{
> > +    atomic_set(&lrng_rb_reader, 0);
> > +    atomic_set(&lrng_rb_writer, 0);
> > +    atomic_set(&lrng_rb_first_in, 0);
> > +}
> > +
> > +static void lrng_raw_entropy_init(void)
> > +{
> > +    /*
> > +     * The boot time testing implies we have a running test. If the
> > +     * caller wants to clear it, he has to unset the boot_test flag
> > +     * at runtime via sysfs to enable regular runtime testing
> > +     */
> > +    if (boot_test)
> > +        return;
> > +
> > +    lrng_raw_entropy_reset();
> > +    atomic_set(&lrng_testing_enabled, 1);
> > +    pr_warn("Enabling raw entropy collection\n");
> > +}
> > +
> > +static void lrng_raw_entropy_fini(void)
> > +{
> > +    if (boot_test)
> > +        return;
> > +
> > +    lrng_raw_entropy_reset();
> > +    atomic_set(&lrng_testing_enabled, 0);
> > +    pr_warn("Disabling raw entropy collection\n");
> > +}
> > +
> > +bool lrng_raw_entropy_store(u32 value)
> > +{
> > +    unsigned int write_ptr;
> > +    unsigned int read_ptr;
> > +
> > +    if (!atomic_read(&lrng_testing_enabled) && !boot_test)
> > +        return false;
> > +
> > +    write_ptr = (unsigned int)atomic_add_return_relaxed(1,
> > &lrng_rb_writer); +    read_ptr = (unsigned
> > int)atomic_read(&lrng_rb_reader);

Before answering your comments, please allow me to clarify the following:

This entire code is intended to obtain take raw unconditioned noise data that 
needs to be extracted from the kernel to user space to allow it to be further 
analyzed. This is also why it is mentioned in the Kconfig selection that in 
doubt one should select N and that this code is not intended for production 
kernels although this code should be secure enough to be present in production 
kernels.

For example, raw unconditioned noise data needs to be processed by the 
complicated math outlined in chapter 6 of [1]. For that, there is a tool 
available, see [2]. For that tool, data is needed that is obtained with the 
getrawentropy tool available with [3] where this tool obtains the data from 
the SysFS file that is implemented with this C file.

In addition, [1] even needs the data from the very first 1000 interrupts after 
boot. Hence, the LRNG needs to be able to store that data until user space can 
pick it up (see the boot_test variable).

The assessment resulting from this can be reviewed at [4] section 3.2 In 
particular, the numbers provided at the end of sections 3.2.3 and 3.2.4 are 
obtained with this interface. 

Other examples where such raw unconditioned noise data is needed for further 
analysis is [5], especially chapter 6.

This testing has nothing to do with the runtime testing provided with the 
patch set 11. All data that ends up here is not available to the LRNG and will 
not contribute to any entropy collection.

See the following:

static inline void lrng_time_process(void)
{
...
	if (lrng_raw_entropy_store(now_time))
		return;


bool lrng_raw_entropy_store(u32 value)
{
...
	if (!atomic_read(&lrng_testing_enabled) && !boot_test)
		return false;
...
	return true;

> 
> Am I correct in assuming that this function can be called concurrently in
> different threads or CPUs?

Yes, because it is called indirectly by add_interrupt_randomness.
> > +
> > +    /*
> > +     * Disable entropy testing for boot time testing after ring buffer
> > +     * is filled.
> > +     */
> > +    if (boot_test && write_ptr > LRNG_TESTING_RINGBUFFER_SIZE) {
> > +        pr_warn_once("Boot time entropy collection test disabled\n");
> > +        return false;
> > +    }
> > +
> > +    if (boot_test && !atomic_read(&lrng_rb_first_in))
> > +        pr_warn("Boot time entropy collection test enabled\n");
> > +
> > +    lrng_testing_rb[write_ptr & LRNG_TESTING_RINGBUFFER_MASK] = value;
> 
> You’re writing *somewhere*, but not necessarily to the first open slot.

The idea is that there is a reader pointer and a writer pointer where the 
reader always must be smaller or equal to the writer (modulo the size of the 
ring buffer). So, I do not care where the writer ptr is.

All I need is that:

1. reader and writer ptr must start with the same value at boot time (e.g. 0)

2. reader ptr is always <= writer ptr in order for data to be read.

With these two conditions, when pulling data from the buffer, I need to pull 
always the data from the reader ptr until the reader ptr reaches the writer 
pointer.

Note, the reader/writer pointers are always set to 0 at the beginning of a new 
read request from user space.

> 
> > +
> > +    /* We got at least one event, enable the reader now. */
> > +    atomic_set(&lrng_rb_first_in, 1);
> 
> But not necessarily in position 0.

Yes, this is perfectly ok.
> 
> > +
> > +    if (wq_has_sleeper(&lrng_raw_read_wait))
> > +        wake_up_interruptible(&lrng_raw_read_wait);
> > +
> > +    /*
> > +     * Our writer is taking over the reader - this means the reader
> > +     * one full ring buffer available. Thus we "push" the reader ahead
> > +     * to guarantee that he will be able to consume the full ring.
> > +     */
> > +    if (!boot_test &&
> > +        ((write_ptr & LRNG_TESTING_RINGBUFFER_MASK) ==
> > +        (read_ptr & LRNG_TESTING_RINGBUFFER_MASK)))
> > +        atomic_inc_return_relaxed(&lrng_rb_reader);
> 
> Because you did a relaxed increment above, you don’t actually know this.
> Maybe it’s okay, but this is way too subtle.

You are absolutely correct, there should be no relaxed atomic operation. We 
should take the atomic_inc above and here.

I fixed this.
> 
> I think you should have a mutex for the read side and put all the
> complicated accounting inside the mutex.  If the reader can’t figure out
> that the read pointer is too far behind the write pointer, then fix the
> reader.

Done - the writer now only writes the data and generates the boot log if the 
boot time raw entropy gathering is enabled.
> 
> I also don’t see how the reader is supposed to know how much data has
> actually been written.  You don’t have any variable that says “all words up
> to X have been written”.

With the two rules above, I think the reader knows that: all data between the 
reader ptr and the writer ptr modulo the size of the ring buffer.

But I simplified the code now, the code now only copies the data out if the 
reader <= writer modulo the ring buffer size. In this case, if the writer is 
much faster, then we loose some values.

With the old code, we simply would have lost it too, but just a bit later.
> 
> I think you should stop trying to make the write side wait free.
> Instead,
> consider either using a lock or making it unreliable.  For the former, just
> skip taking the lock if testing is off. For the latter, read write_ptr,
> write (using WRITE_ONCE) your data, then cmpxchg the write ptr from the
> value you read to that value plus one.  And make sure that the reader never
> tries to read the first unwritten slot, i.e. never let the reader catch all
> the way up.

I have followed the locking approach as we need to get correct data.
> 
> I’m also curious why you need entirely different infrastructure for testing
> as for normal operation.

I hope with the explanation above, the question is answered.


> > +
> > +    return true;
> > +}
> > +
> > +static inline bool lrng_raw_have_data(void)
> > +{
> > +    unsigned int read_ptr = (unsigned int)atomic_read(&lrng_rb_reader);
> > +    unsigned int write_ptr = (unsigned int)atomic_read(&lrng_rb_writer);
> > +
> > +    return (atomic_read(&lrng_rb_first_in) &&
> > +        (write_ptr & LRNG_TESTING_RINGBUFFER_MASK) !=
> > +         (read_ptr & LRNG_TESTING_RINGBUFFER_MASK));
> > +}
> > +
> > +static int lrng_raw_entropy_reader(u8 *outbuf, u32 outbuflen)
> > +{
> > +    int collected_data = 0;
> > +
> > +    if (!atomic_read(&lrng_testing_enabled) && !boot_test)
> > +        return -EAGAIN;
> > +
> > +    if (!atomic_read(&lrng_rb_first_in)) {
> > +        wait_event_interruptible(lrng_raw_read_wait,
> > +                     lrng_raw_have_data());
> > +        if (signal_pending(current))
> > +            return -ERESTARTSYS;
> > +    }
> > +
> > +    while (outbuflen) {
> > +        unsigned int read_ptr =
> > +            (unsigned int)atomic_add_return_relaxed(
> > +                            1, &lrng_rb_reader);
> > +        unsigned int write_ptr =
> > +            (unsigned int)atomic_read(&lrng_rb_writer);
> > +
> > +        /*
> > +         * For boot time testing, only output one round of ring buffer.
> > +         */
> > +        if (boot_test && read_ptr > LRNG_TESTING_RINGBUFFER_SIZE) {
> > +            collected_data = -ENOMSG;
> > +            goto out;
> > +        }
> > +
> > +        /* We reached the writer */
> > +        if (!boot_test && ((write_ptr & LRNG_TESTING_RINGBUFFER_MASK) ==
> > +            (read_ptr & LRNG_TESTING_RINGBUFFER_MASK))) {
> > +
> 
> This is wrong. The fact that you haven’t reached the writer does not imply
> that you’re about to read valid data.

As I changed the code by using your locking suggestion. With that I think the 
code should now always read correct data. I will send an updated patch set 
tomorrow.

Thank you for your review.


[1] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf

[2] https://github.com/usnistgov/SP800-90B_EntropyAssessment

[3] http://www.chronox.de/lrng/lrng-tests-20191116.tar.xz - see the sp80090b 
directory for details

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

[5] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/
LinuxRNG/LinuxRNG_EN.pdf


Ciao
Stephan

Powered by blists - more mailing lists