Hi Herbert, Ted,
The venerable Linux /dev/random served users of cryptographic mechanisms well
for a long time. Its behavior is well understood to deliver entropic data. In
the last years, however, the Linux /dev/random showed signs of age where it has
challenges to cope with modern computing environments ranging from tiny embedded
systems, over new hardware resources such as SSDs, up to massive parallel
systems as well as virtualized environments.
With the experience gained during numerous studies of /dev/random, entropy
assessments of different noise source designs and assessing entropy behavior in
virtual machines and other special environments, I felt to do something about
it.
I developed a different approach, 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. Finally massive performance
improvements are visible at /dev/urandom / get_random_bytes.
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.
Please find in [1] the full design discussion covering qualitative assessments
of the entropy collection and entropy flow. Furthermore, a full testing of the
data collection and data processing is performed. The testing focuses on the
calculation of different types of minimum entropy values of raw noise data.
All used test code and supportive tools are provided with [2]. The testing
is concluded with a comparison to the legacy /dev/random implementation
regarding performance and delivery time of entropic random data.
To support a proper review of the code without interfering with the current
functionality, the attached patch adds the LRNG to the cryptodev-2.6 tree as
an option. The patches do not replace or even alter the legacy /dev/random
implementation but allows the user to enable the LRNG at compile time. If it is
enabled, the legacy /dev/random implementation is not compiled. On the other
hand, if the LRNG support is disabled, the legacy /dev/random code is
compiled unchanged. With this approach you see that the LRNG is API and ABI
compatible with the legacy implementation.
Stability tests were executed on 64 and 32 bit systems where the test KVM with 4
vCPUs on 4 hyperthreads compiled the Linux kernel with make -j4 over and over
for half a day. In addition, parallel cat /dev/urandom > /dev/null were
exercised for a couple of hours. Also, stability tests by generating 500
million interrupts were performed.
[1] http://www.chronox.de/lrng/doc/lrng.pdf
[2] http://www.chronox.de/lrng.html
Stephan Mueller (6):
crypto: DRBG - externalize DRBG functions for LRNG
random: conditionally compile code depending on LRNG
crypto: Linux Random Number Generator
crypto: LRNG - enable compile
crypto: LRNG - hook LRNG into interrupt handler
hyperv IRQ handler: trigger LRNG
crypto/Kconfig | 10 +
crypto/Makefile | 1 +
crypto/drbg.c | 11 +-
crypto/lrng.c | 1803 ++++++++++++++++++++++++++++++++++++++++++++++++
drivers/char/random.c | 8 +
drivers/hv/vmbus_drv.c | 3 +
include/crypto/drbg.h | 7 +
include/linux/genhd.h | 5 +
include/linux/random.h | 8 +
kernel/irq/handle.c | 1 +
10 files changed, 1851 insertions(+), 6 deletions(-)
create mode 100644 crypto/lrng.c
--
2.5.5
,
Ciao
Stephan
The LRNG places a callback into the interrupt handler to be triggered
for each interrupt. With this callback, entropy is collected.
Signed-off-by: Stephan Mueller <[email protected]>
---
kernel/irq/handle.c | 1 +
1 file changed, 1 insertion(+)
diff --git a/kernel/irq/handle.c b/kernel/irq/handle.c
index a15b548..8d64e37 100644
--- a/kernel/irq/handle.c
+++ b/kernel/irq/handle.c
@@ -175,6 +175,7 @@ irqreturn_t handle_irq_event_percpu(struct irq_desc *desc)
}
add_interrupt_randomness(irq, flags);
+ lrng_irq_process();
if (!noirqdebug)
note_interrupt(desc, retval);
--
2.5.5
Add LRNG compilation support.
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/Kconfig | 10 ++++++++++
crypto/Makefile | 1 +
2 files changed, 11 insertions(+)
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 93a1fdc..938f2dc 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1587,6 +1587,16 @@ config CRYPTO_JITTERENTROPY
random numbers. This Jitterentropy RNG registers with
the kernel crypto API and can be used by any caller.
+config CRYPTO_LRNG
+ bool "Linux Random Number Generator"
+ select CRYPTO_DRBG_MENU
+ 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. The LRNG only
+ works with the presence of a high-resolution timer.
+
config CRYPTO_USER_API
tristate
diff --git a/crypto/Makefile b/crypto/Makefile
index 4f4ef7e..7f91c8e 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -114,6 +114,7 @@ obj-$(CONFIG_CRYPTO_DRBG) += drbg.o
obj-$(CONFIG_CRYPTO_JITTERENTROPY) += jitterentropy_rng.o
CFLAGS_jitterentropy.o = -O0
jitterentropy_rng-y := jitterentropy.o jitterentropy-kcapi.o
+obj-$(CONFIG_CRYPTO_LRNG) += lrng.o
obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
obj-$(CONFIG_CRYPTO_GHASH) += ghash-generic.o
obj-$(CONFIG_CRYPTO_USER_API) += af_alg.o
--
2.5.5
The Hyper-V Linux Integration Services use the VMBus implementation for
communication with the Hypervisor. VMBus registers its own interrupt
handler that completely bypasses the common Linux interrupt handling.
The interrupt handler is now added the invocation of the LRNG IRQ
collection function to also benefit from entropy under Hyper-V.
If the implementation of the VMBus and its subordinate drivers is
changed such that they resemble the Xen implementation where the
received IRQs are forwarded to the standard Linux interrupt handling
logic, this patch should be dropped.
Signed-off-by: Stephan Mueller <[email protected]>
---
drivers/hv/vmbus_drv.c | 3 +++
1 file changed, 3 insertions(+)
diff --git a/drivers/hv/vmbus_drv.c b/drivers/hv/vmbus_drv.c
index 64713ff..afa2de0 100644
--- a/drivers/hv/vmbus_drv.c
+++ b/drivers/hv/vmbus_drv.c
@@ -41,6 +41,7 @@
#include <linux/ptrace.h>
#include <linux/screen_info.h>
#include <linux/kdebug.h>
+#include <linux/random.h>
#include "hyperv_vmbus.h"
static struct acpi_device *hv_acpi_dev;
@@ -801,6 +802,8 @@ static void vmbus_isr(void)
else
tasklet_schedule(hv_context.msg_dpc[cpu]);
}
+
+ lrng_irq_process();
}
--
2.5.5
When selecting the LRNG for compilation, disable the legacy /dev/random
implementation.
The LRNG is a drop-in replacement for the legacy /dev/random which
implements the same in-kernel and user space API. Only the hooks of
/dev/random into other parts of the kernel need to be disabled.
Signed-off-by: Stephan Mueller <[email protected]>
---
drivers/char/random.c | 8 ++++++++
include/linux/genhd.h | 5 +++++
include/linux/random.h | 8 ++++++++
3 files changed, 21 insertions(+)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index b583e53..92c2174 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -267,6 +267,8 @@
#include <asm/irq_regs.h>
#include <asm/io.h>
+#ifndef CONFIG_CRYPTO_LRNG
+
#define CREATE_TRACE_POINTS
#include <trace/events/random.h>
@@ -1620,6 +1622,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
}
return urandom_read(NULL, buf, count, NULL);
}
+#endif /* CONFIG_CRYPTO_LRNG */
/***************************************************************
* Random UUID interface
@@ -1647,6 +1650,7 @@ EXPORT_SYMBOL(generate_random_uuid);
*
********************************************************************/
+#ifndef CONFIG_CRYPTO_LRNG
#ifdef CONFIG_SYSCTL
#include <linux/sysctl.h>
@@ -1784,6 +1788,8 @@ struct ctl_table random_table[] = {
};
#endif /* CONFIG_SYSCTL */
+#endif /* CONFIG_CRYPTO_LRNG */
+
static u32 random_int_secret[MD5_MESSAGE_BYTES / 4] ____cacheline_aligned;
int random_int_secret_init(void)
@@ -1859,6 +1865,7 @@ randomize_range(unsigned long start, unsigned long end, unsigned long len)
return PAGE_ALIGN(get_random_int() % range + start);
}
+#ifndef CONFIG_CRYPTO_LRNG
/* Interface for in-kernel drivers of true hardware RNGs.
* Those devices may produce endless random bits and will be throttled
* when our pool is full.
@@ -1878,3 +1885,4 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
credit_entropy_bits(poolp, entropy);
}
EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);
+#endif /* CONFIG_CRYPTO_LRNG */
diff --git a/include/linux/genhd.h b/include/linux/genhd.h
index 5c70676..962c82f 100644
--- a/include/linux/genhd.h
+++ b/include/linux/genhd.h
@@ -450,8 +450,13 @@ extern void disk_flush_events(struct gendisk *disk, unsigned int mask);
extern unsigned int disk_clear_events(struct gendisk *disk, unsigned int mask);
/* drivers/char/random.c */
+#ifdef CONFIG_CRYPTO_LRNG
+#define add_disk_randomness(disk) do {} while (0)
+#define rand_initialize_disk(disk) do {} while (0)
+#else
extern void add_disk_randomness(struct gendisk *disk);
extern void rand_initialize_disk(struct gendisk *disk);
+#endif
static inline sector_t get_start_sect(struct block_device *bdev)
{
diff --git a/include/linux/random.h b/include/linux/random.h
index 9c29122..5527bab 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -17,10 +17,18 @@ struct random_ready_callback {
struct module *owner;
};
+#ifdef CONFIG_CRYPTO_LRNG
+#define add_device_randomness(buf, nbytes) do {} while (0)
+#define add_input_randomness(type, code, value) do {} while (0)
+#define add_interrupt_randomness(irq, irq_flags) do {} while (0)
+extern void lrng_irq_process(void);
+#else /* CONFIG_CRYPTO_LRNG */
extern void add_device_randomness(const void *, unsigned int);
extern void add_input_randomness(unsigned int type, unsigned int code,
unsigned int value);
extern void add_interrupt_randomness(int irq, int irq_flags);
+#define lrng_irq_process()
+#endif /* CONFIG_CRYPTO_LRNG */
extern void get_random_bytes(void *buf, int nbytes);
extern int add_random_ready_callback(struct random_ready_callback *rdy);
--
2.5.5
The LRNG with all its properties is documented in [1]. This
documentation covers the functional discussion as well as testing of all
aspects of entropy processing. 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
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/lrng.c | 1803 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 1803 insertions(+)
create mode 100644 crypto/lrng.c
diff --git a/crypto/lrng.c b/crypto/lrng.c
new file mode 100644
index 0000000..f0aa999
--- /dev/null
+++ b/crypto/lrng.c
@@ -0,0 +1,1803 @@
+/*
+ * Linux Random Number Generator (LRNG)
+ *
+ * Documentation and test code: http://www.chronox.de/lrng.html
+ *
+ * Copyright (C) 2016, Stephan Mueller <[email protected]>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, and the entire permission notice in its entirety,
+ * including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ * products derived from this software without specific prior
+ * written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions. (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#include <linux/timex.h>
+#include <linux/percpu.h>
+#include <linux/module.h>
+#include <linux/init.h>
+#include <linux/fs.h>
+#include <linux/spinlock.h>
+#include <linux/kthread.h>
+#include <linux/random.h>
+#include <linux/workqueue.h>
+#include <linux/poll.h>
+#include <linux/cryptohash.h>
+#include <linux/syscalls.h>
+
+#include <crypto/drbg.h>
+
+/* debug macro */
+#define DRIVER_NAME "lrng"
+#if 0
+#define dbg(fmt, ...) pr_info(DRIVER_NAME": " fmt, ##__VA_ARGS__)
+#else
+#define dbg(fmt, ...)
+#endif
+
+/*
+ * Define one DRBG out of each type with 256 bits of security strength.
+ *
+ * This definition is allowed to be changed.
+ */
+#ifdef CONFIG_CRYPTO_DRBG_HMAC
+# if 0
+# define LRNG_DRBG_BLOCKLEN_BYTES 64
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "drbg_nopr_hmac_sha512" /* HMAC DRBG SHA-512 */
+# else
+# define LRNG_DRBG_BLOCKLEN_BYTES 32
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "drbg_nopr_hmac_sha256" /* HMAC DRBG SHA-256 */
+# endif
+#elif defined CONFIG_CRYPTO_DRBG_HASH
+# if 0
+# define LRNG_DRBG_BLOCKLEN_BYTES 64
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "drbg_nopr_sha512" /* Hash DRBG SHA-512 */
+# else
+# define LRNG_DRBG_BLOCKLEN_BYTES 32
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "drbg_nopr_sha256" /* Hash DRBG SHA-256 */
+# endif
+#elif defined CONFIG_CRYPTO_DRBG_CTR
+# define LRNG_DRBG_BLOCKLEN_BYTES 16
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "drbg_nopr_ctr_aes256" /* CTR DRBG AES-256 */
+#else
+# error "LRNG requires the presence of a DRBG"
+#endif
+
+/* Primary DRBG state handle */
+struct lrng_pdrbg {
+ struct drbg_state *pdrbg; /* DRBG handle */
+ bool pdrbg_fully_seeded; /* Is DRBG fully seeded? */
+ bool pdrbg_min_seeded; /* Is DRBG minimally seeded? */
+ u32 pdrbg_entropy_bits; /* Is DRBG entropy level */
+ struct work_struct lrng_seed_work; /* (re)seed work queue */
+};
+
+/* Secondary DRBG state handle */
+struct lrng_sdrbg {
+ struct drbg_state *sdrbg; /* DRBG handle */
+ atomic_t requests; /* Number of DRBG requests */
+ unsigned long last_seeded; /* Last time it was seeded */
+};
+
+#define LRNG_DRBG_BLOCKLEN_BITS (LRNG_DRBG_BLOCKLEN_BYTES * 8)
+#define LRNG_DRBG_SECURITY_STRENGTH_BITS (LRNG_DRBG_SECURITY_STRENGTH_BYTES * 8)
+
+/*
+ * SP800-90A defines a maximum request size of 1<<16 bytes. The given value is
+ * considered a safer margin. This applies to secondary DRBG.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_DRBG_MAX_REQSIZE (1<<12)
+
+/*
+ * SP800-90A defines a maximum number of requests between reseeds of 1<<48.
+ * The given value is considered a much safer margin, balancing requests for
+ * frequent reseeds with the need to conserve entropy. This value MUST NOT be
+ * larger than INT_MAX because it is used in an atomic_t. This applies to
+ * secondary DRBG.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_DRBG_RESEED_THRESH (1<<12)
+
+/* Status information about IRQ noise source */
+struct lrng_irq_info {
+ atomic_t num_events; /* Number of non-stuck IRQs since last read */
+ atomic_t num_events_thresh; /* Reseed threshold */
+ atomic_t pool_ptr; /* Ptr into pool for next IRQ bit injection */
+ u32 irq_pool_reader; /* Current word of pool to be read */
+ atomic_t last_time; /* Stuck test: time of previous IRQ */
+ atomic_t last_delta; /* Stuck test: delta of previous IRQ */
+ atomic_t last_delta2; /* Stuck test: 2. time derivation of prev IRQ */
+ atomic_t reseed_in_progress; /* Flag for on executing reseed */
+ atomic_t crngt_ctr; /* FIPS 140-2 CRNGT counter */
+};
+
+/*
+ * According to FIPS 140-2 IG 9.8, our C threshold is at 3 back to back stuck
+ * values. It should be highly unlikely that we see three consecutive
+ * identical time stamps.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_FIPS_CRNGT 3
+
+/*
+ * This is the entropy pool used by the slow noise source. Its size should
+ * be at least as large as the interrupt entropy estimate.
+ *
+ * LRNG_POOL_SIZE is allowed to be changed.
+ */
+struct lrng_pool {
+#define LRNG_POOL_SIZE 128
+#define LRNG_POOL_WORD_BYTES (sizeof(atomic_t))
+#define LRNG_POOL_SIZE_BYTES (LRNG_POOL_SIZE * LRNG_POOL_WORD_BYTES)
+#define LRNG_POOL_SIZE_BITS (LRNG_POOL_SIZE_BYTES * 8)
+#define LRNG_POOL_WORD_BITS (LRNG_POOL_WORD_BYTES * 8)
+ atomic_t pool[LRNG_POOL_SIZE]; /* Pool holing the slow noise */
+ struct lrng_irq_info irq_info; /* IRQ noise source status info */
+};
+
+/*
+ * Number of interrupts to be recorded to assume that DRBG security strength
+ * bits of entropy are received. Dividing a DRBG security strength of 256 by
+ * this value gives the entropy value for one interrupt (i.e. a folded one bit).
+ * The default value implies that we have 256 / 288 = 0.89 bits of entropy per
+ * interrupt.
+ * Note: a value below the DRBG security strength should not be defined as this
+ * may imply the DRBG can never be fully seeded in case other noise
+ * sources are unavailable.
+ * Note 2: This value must be multiples of LRNG_POOL_WORD_BYTES
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_IRQ_ENTROPY_BYTES \
+ (LRNG_DRBG_SECURITY_STRENGTH_BYTES + LRNG_POOL_WORD_BYTES)
+#define LRNG_IRQ_ENTROPY_BITS (LRNG_IRQ_ENTROPY_BYTES * 8)
+
+/*
+ * Leave given number of data bits in entropy pool to serve /dev/random while
+ * /dev/urandom is stressed. This value must be a multiple of
+ * LRNG_IRQ_ENTROPY_BITS to allow /dev/random to benefit from it completely.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_EMERG_POOLSIZE (LRNG_IRQ_ENTROPY_BITS * 2)
+
+/*
+ * Min required seed entropy is 112 bits as per FIPS 140-2 and AIS20/31.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_MIN_SEED_ENTROPY_BITS 112
+
+/*
+ * LRNG_MIN_SEED_ENTROPY_BITS rounded up to next LRNG_POOL_WORD multiple.
+ *
+ * This value must be changed with the following considerations:
+ * If LRNG_MIN_SEED_ENTROPY_BITS, LRNG_IRQ_ENTROPY_BITS or LRNG_POOL_WORD_BITS
+ * is changed, make sure LRNG_IRQ_MIN_NUM is changed such that
+ * (LRNG_MIN_SEED_ENTROPY_BITS * LRNG_IRQ_ENTROPY_BITS /
+ * LRNG_DRBG_SECURITY_STRENGTH_BITS) is rounded up to the next full
+ * LRNG_POOL_WORD_BITS multiple.
+ */
+#define LRNG_IRQ_MIN_NUM (LRNG_POOL_WORD_BITS * 4)
+
+static struct lrng_pdrbg lrng_pdrbg = { 0 };
+static DEFINE_SPINLOCK(lrng_pdrbg_lock); /* Lock for lrng_pdrbg and members */
+
+static struct lrng_sdrbg lrng_sdrbg = { .sdrbg = NULL,
+ .requests = ATOMIC_INIT(1),
+ .last_seeded = 0 };
+static DEFINE_SPINLOCK(lrng_sdrbg_lock); /* Lock for lrng_sdrbg and members */
+
+static struct lrng_pool lrng_pool = {
+ .irq_info = {
+ .num_events = ATOMIC_INIT(0),
+ .num_events_thresh = ATOMIC_INIT(LRNG_POOL_WORD_BITS),
+ .pool_ptr = ATOMIC_INIT(0),
+ .irq_pool_reader = 0,
+ .last_time = ATOMIC_INIT(0),
+ .last_delta = ATOMIC_INIT(0),
+ .last_delta2 = ATOMIC_INIT(0),
+ .reseed_in_progress = ATOMIC_INIT(0),
+ .crngt_ctr = ATOMIC_INIT(LRNG_FIPS_CRNGT),
+ },
+};
+
+static LIST_HEAD(lrng_ready_list);
+static DEFINE_SPINLOCK(lrng_ready_list_lock);
+
+static struct crypto_rng *lrng_jent;
+static DEFINE_SPINLOCK(lrng_jent_lock); /* Lock for r/w lrng_jent */
+
+static atomic_t lrng_pdrbg_avail = ATOMIC_INIT(0);
+static atomic_t lrng_initrng_bytes = ATOMIC_INIT(0);
+static DEFINE_SPINLOCK(lrng_init_rng_lock); /* Lock the init RNG state */
+
+static DECLARE_WAIT_QUEUE_HEAD(lrng_read_wait);
+static DECLARE_WAIT_QUEUE_HEAD(lrng_write_wait);
+static DECLARE_WAIT_QUEUE_HEAD(lrng_pdrbg_init_wait);
+static struct fasync_struct *fasync;
+
+/*
+ * Estimated entropy of data is a 32th of LRNG_DRBG_SECURITY_STRENGTH_BITS.
+ * As we have no ability to review the implementation of those noise sources,
+ * it is prudent to have a conservative estimate here.
+ */
+static u32 archrandom = LRNG_DRBG_SECURITY_STRENGTH_BITS>>5;
+module_param(archrandom, uint, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
+MODULE_PARM_DESC(archrandom, "Entropy in bits of 256 data bits from CPU noise source (e.g. RDRAND)");
+
+/*
+ * Estimated entropy of data is half of datasize
+ * LRNG_DRBG_SECURITY_STRENGTH_BITS. This is to prevent this noise source
+ * monopolizing the slow noise source.
+ */
+static u32 jitterrng = LRNG_DRBG_SECURITY_STRENGTH_BITS>>1;
+module_param(jitterrng, uint, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
+MODULE_PARM_DESC(jitterrng, "Entropy in bits of of 256 data bits from Jitter RNG noise source");
+
+/*
+ * If the entropy count falls under this number of bits, then we
+ * should wake up processes which are selecting or polling on write
+ * access to /dev/random.
+ * The value is set to a fourth of the LRNG_POOL_SIZE_BITS.
+ */
+static u32 lrng_write_wakeup_bits = LRNG_POOL_SIZE_BITS / 4;
+
+/*
+ * The minimum number of bits of entropy before we wake up a read on
+ * /dev/random. Should be enough to do a significant reseed where
+ * it is technically possible that the entropy estimate is to be above the
+ * DRBG security strength.
+ */
+static u32 lrng_read_wakeup_bits = LRNG_IRQ_ENTROPY_BITS;
+
+/*
+ * Maximum number of seconds between DRBG reseed intervals of the secondary
+ * DRBG. Note, this is enforced with the next request of random numbers from
+ * the secondary DRBG. Setting this value to zero implies a reseeding attempt
+ * before every generated random number.
+ */
+static int lrng_sdrbg_reseed_max_time = 600;
+
+/********************************** Helper ***********************************/
+
+static inline u32 atomic_read_u32(atomic_t *v)
+{
+ return (u32)atomic_read(v);
+}
+
+static inline u32 atomic_xchg_u32(atomic_t *v, u32 x)
+{
+ return (u32)atomic_xchg(v, x);
+}
+
+/* Is the entropy pool fill level too low and is the DRBG not fully seeded? */
+static inline bool lrng_need_entropy(void)
+{
+ return ((atomic_read_u32(&lrng_pool.irq_info.num_events) <
+ lrng_write_wakeup_bits) &&
+ lrng_pdrbg.pdrbg_entropy_bits <
+ LRNG_DRBG_SECURITY_STRENGTH_BITS);
+}
+
+/* Is the entropy pool filled for /dev/random pull or DRBG fully seeded? */
+static inline bool lrng_have_entropy_full(void)
+{
+ return ((atomic_read_u32(&lrng_pool.irq_info.num_events) >=
+ lrng_read_wakeup_bits) ||
+ lrng_pdrbg.pdrbg_entropy_bits >=
+ LRNG_DRBG_SECURITY_STRENGTH_BITS);
+}
+
+/*********************** Fast soise source processing ************************/
+
+static void lrng_jent_alloc(void)
+{
+ struct crypto_rng *jent = crypto_alloc_rng("jitterentropy_rng", 0, 0);
+ unsigned long flags;
+
+ if (IS_ERR(jent))
+ jitterrng = 0;
+ else {
+ spin_lock_irqsave(&lrng_jent_lock, flags);
+ if (!lrng_jent && jitterrng)
+ lrng_jent = jent;
+ else
+ crypto_free_rng(jent);
+ spin_unlock_irqrestore(&lrng_jent_lock, flags);
+ }
+ dbg("Jitter RNG allocated: %s\n", (lrng_jent) ? "success" : "failure");
+}
+
+static void lrng_jent_release(void)
+{
+ unsigned long flags;
+
+ spin_lock_irqsave(&lrng_jent_lock, flags);
+ if (!lrng_jent)
+ goto unlock;
+ crypto_free_rng(lrng_jent);
+ lrng_jent = NULL;
+ dbg("Jitter RNG released\n");
+
+unlock:
+ spin_unlock_irqrestore(&lrng_jent_lock, flags);
+}
+
+/**
+ * Get Jitter RNG entropy
+ *
+ * @outbuf buffer to store entropy of size LRNG_DRBG_SECURITY_STRENGTH_BYTES
+ * @return > 0 on success where value provides the added entropy in bits
+ * 0 if no fast source was available
+ */
+static u32 lrng_get_jent(u8 *outbuf)
+{
+ int ret;
+ u32 ent_bits = jitterrng;
+ unsigned long flags;
+
+ /* Jitter RNG is enabled to be used and deallocated --> allocate it */
+ if (!lrng_jent && ent_bits)
+ lrng_jent_alloc();
+
+ /* Jitter RNG is disabled at runtime and allocated --> deallocate it */
+ if (lrng_jent && !ent_bits) {
+ lrng_jent_release();
+ return 0;
+ }
+
+ spin_lock_irqsave(&lrng_jent_lock, flags);
+ if (!lrng_jent) {
+ spin_unlock_irqrestore(&lrng_jent_lock, flags);
+ return 0;
+ }
+ ret = crypto_rng_get_bytes(lrng_jent, outbuf,
+ LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+ spin_unlock_irqrestore(&lrng_jent_lock, flags);
+
+ if (ret) {
+ dbg("Jitter RNG failed with %d\n", ret);
+ return 0;
+ }
+
+ /* Obtain entropy statement -- cap entropy to buffer size in bits */
+ ent_bits = min_t(u32, ent_bits, LRNG_DRBG_SECURITY_STRENGTH_BITS);
+ dbg("obtained %u bits of entropy from Jitter RNG noise source\n",
+ ent_bits);
+ return ent_bits;
+}
+
+/**
+ * Get CPU noise source entropy
+ *
+ * @outbuf buffer to store entropy of size LRNG_DRBG_SECURITY_STRENGTH_BYTES
+ * @return > 0 on success where value provides the added entropy in bits
+ * 0 if no fast source was available
+ */
+static inline u32 lrng_get_arch(u8 *outbuf)
+{
+ u32 i;
+ u32 ent_bits = archrandom;
+
+ /* operate on full blocks */
+ BUILD_BUG_ON(LRNG_DRBG_SECURITY_STRENGTH_BYTES % sizeof(unsigned long));
+
+ if (!ent_bits)
+ return 0;
+
+ for (i = 0;
+ i < (LRNG_DRBG_SECURITY_STRENGTH_BYTES / sizeof(unsigned long));
+ i += 2) {
+ if (!arch_get_random_long((unsigned long *)outbuf)) {
+ archrandom = 0;
+ return 0;
+ }
+ outbuf += sizeof(unsigned long);
+ }
+
+ /* Obtain entropy statement -- cap entropy to buffer size in bits */
+ ent_bits = min_t(u32, ent_bits, LRNG_DRBG_SECURITY_STRENGTH_BITS);
+ dbg("obtained %u bits of entropy from CPU RNG noise source\n",
+ ent_bits);
+ return ent_bits;
+}
+
+/********************* IRQ slow noise source processing **********************/
+
+/**
+ * Hot code path - This function XORs all bits with each other. Effectively
+ * it calculates the parity of the given value.
+ *
+ * The implementation is taken from
+ * https://graphics.stanford.edu/~seander/bithacks.html
+ *
+ * @x value to be collapsed to one bit
+ * @return collapsed value
+ */
+static inline u32 lrng_xor_all_bits(u32 x)
+{
+ x ^= x >> 1;
+ x ^= x >> 2;
+ x = (x & 0x11111111U) * 0x11111111U;
+
+ return (x >> 28) & 1;
+}
+
+/**
+ * Hot code path - Stuck test by checking the:
+ * 1st derivation of the event occurrence (time delta)
+ * 2nd derivation of the event occurrence (delta of time deltas)
+ * 3rd derivation of the event occurrence (delta of delta of time deltas)
+ *
+ * All values must always be non-zero. This is also the FIPS 140-2 CRNGT.
+ *
+ * @irq_info Reference to IRQ information
+ * @now Event time
+ * @return 0 event occurrence not stuck (good bit)
+ * 1 event occurrence stuck (reject bit)
+ */
+static int lrng_irq_stuck(struct lrng_irq_info *irq_info, u32 now_time)
+{
+ u32 delta = now_time - atomic_xchg_u32(&irq_info->last_time, now_time);
+ int delta2 = delta - atomic_xchg_u32(&irq_info->last_delta, delta);
+ int delta3 = delta2 - atomic_xchg(&irq_info->last_delta2, delta2);
+
+#ifdef CONFIG_CRYPTO_FIPS
+ if (fips_enabled) {
+ if (!delta) {
+ if (atomic_dec_and_test(&irq_info->crngt_ctr))
+ panic(DRIVER_NAME": FIPS 140-2 continuous random number generator test failed\n");
+ } else
+ atomic_set(&irq_info->crngt_ctr, LRNG_FIPS_CRNGT);
+ }
+#endif
+
+ if (!delta || !delta2 || !delta3)
+ return 1;
+
+ return 0;
+}
+
+/**
+ * Hot code path - Callback for interrupt handler triggering entropy collection.
+ */
+void lrng_irq_process(void)
+{
+ u32 now_time = random_get_entropy();
+ struct lrng_irq_info *irq_info = &lrng_pool.irq_info;
+ u32 folded_bit = lrng_xor_all_bits(now_time);
+ u32 pool_ptr, irq_num = 0;
+
+ /*
+ * If obtained measurement is not stuck, advance pool_ptr to XOR
+ * new folded bit into new location.
+ */
+ if (!lrng_irq_stuck(irq_info, now_time)) {
+ pool_ptr = (u32)atomic_add_return(1, &irq_info->pool_ptr);
+ irq_num = (u32)atomic_add_return(1, &irq_info->num_events);
+ } else
+ pool_ptr = atomic_read_u32(&irq_info->pool_ptr);
+
+ pool_ptr %= LRNG_POOL_SIZE_BITS;
+
+ /*
+ * Mix in the folded bit into the bit location pointed to by
+ * pool_ptr. The bit location is calculated by finding the right
+ * pool word (pool_ptr / LRNG_POOL_WORD_BITS) and the right bit
+ * location in the word where the bit should be XORed into
+ * (pool_ptr % LRNG_POOL_WORD_BITS).
+ */
+ atomic_xor(folded_bit << (pool_ptr % LRNG_POOL_WORD_BITS),
+ &lrng_pool.pool[pool_ptr / LRNG_POOL_WORD_BITS]);
+
+ /* Should we wake readers? */
+ if (irq_num == lrng_read_wakeup_bits) {
+ wake_up_interruptible(&lrng_read_wait);
+ kill_fasync(&fasync, SIGIO, POLL_IN);
+ }
+
+ /*
+ * Once the primary DRBG is fully seeded, the interrupt noise sources
+ * will not trigger any reseeding any more.
+ */
+ if (lrng_pdrbg.pdrbg_fully_seeded)
+ return;
+
+ /* Only trigger the DRBG reseed if we have collected enough IRQs. */
+ if (atomic_read_u32(&lrng_pool.irq_info.num_events) <
+ atomic_read_u32(&lrng_pool.irq_info.num_events_thresh))
+ return;
+
+ /* Only try to reseed if the DRBG is alive. */
+ if (!atomic_read(&lrng_pdrbg_avail))
+ return;
+
+ /* Ensure that the seeding only occurs once at any given time. */
+ if (atomic_cmpxchg(&lrng_pool.irq_info.reseed_in_progress, 0, 1))
+ return;
+
+ /* Seed the DRBG with IRQ noise. */
+ schedule_work(&lrng_pdrbg.lrng_seed_work);
+}
+EXPORT_SYMBOL(lrng_irq_process);
+
+/**
+ * Read the entropy pool out for use. The caller must ensure this function
+ * is only called once at a time. "noinline" needed for SystemTap testing.
+ *
+ * @outbuf buffer to store data in
+ * @outbuflen size of outbuf -- if not multiple of LRNG_POOL_WORD_BITS we will
+ * return a number of bits rounded down to nearest
+ * LRNG_POOL_WORD_BITS
+ * @requested_entropy_bits requested bits of entropy -- the function will return
+ * at least this amount of entropy if available
+ * @drain boolean indicating that that all entropy of pool can be used
+ * (otherwise some emergency amount of entropy is left)
+ * @return estimated entropy from the IRQs that went into the pool since last
+ * readout.
+ */
+static noinline u32 lrng_get_pool(u8 *outbuf, u32 outbuflen,
+ u32 requested_entropy_bits, bool drain)
+{
+ u32 i, irq_num_events_used, irq_num_event_back, ent_bits, words_to_copy;
+ /* How many interrupts are in buffer? */
+ u32 irq_num_events = atomic_xchg_u32(&lrng_pool.irq_info.num_events, 0);
+
+ irq_num_events = min_t(u32, irq_num_events, LRNG_POOL_SIZE_BITS);
+
+ /* Translate requested entropy bits into data bits */
+ requested_entropy_bits = (requested_entropy_bits *
+ LRNG_IRQ_ENTROPY_BITS) /
+ LRNG_DRBG_SECURITY_STRENGTH_BITS;
+ /* Round up such that we are able to collect requested entropy */
+ requested_entropy_bits += LRNG_POOL_WORD_BITS - 1;
+
+ /* How many interrupts do we need to and can we use? */
+ BUILD_BUG_ON(LRNG_EMERG_POOLSIZE % LRNG_IRQ_ENTROPY_BITS);
+ if (drain)
+ irq_num_events_used = min_t(u32, irq_num_events,
+ requested_entropy_bits);
+ else
+ irq_num_events_used = min_t(u32,
+ (irq_num_events -
+ min_t(u32, LRNG_EMERG_POOLSIZE, irq_num_events)),
+ requested_entropy_bits);
+ /* Translate entropy in number of complete words to be read */
+ words_to_copy = irq_num_events_used / LRNG_POOL_WORD_BITS;
+ irq_num_events_used = words_to_copy * LRNG_POOL_WORD_BITS;
+ BUG_ON(irq_num_events_used > outbuflen<<3);
+
+ /* Read out the words from the pool */
+ for (i = lrng_pool.irq_info.irq_pool_reader;
+ i < (lrng_pool.irq_info.irq_pool_reader + words_to_copy); i++) {
+ BUILD_BUG_ON(LRNG_POOL_SIZE_BYTES % sizeof(atomic_t));
+ /* write the result from atomic_read directly into buffer */
+ *((u32 *)outbuf) =
+ atomic_read(&lrng_pool.pool[(i % LRNG_POOL_SIZE)]);
+ outbuf += sizeof(atomic_t);
+ }
+
+ /* SystemTap: IRQ Raw Entropy Hook line */
+ /* There may be new events that came in while we processed this logic */
+ irq_num_events += atomic_xchg_u32(&lrng_pool.irq_info.num_events, 0);
+ /* Cap the number of events we say we have left to not reuse events */
+ irq_num_event_back = min_t(u32, irq_num_events - irq_num_events_used,
+ LRNG_POOL_SIZE_BITS - irq_num_events_used);
+ /* Add the unused interrupt number back to the state variable */
+ atomic_add(irq_num_event_back, &lrng_pool.irq_info.num_events);
+
+ /* Advance the read pointer */
+ lrng_pool.irq_info.irq_pool_reader += words_to_copy;
+ lrng_pool.irq_info.irq_pool_reader %= LRNG_POOL_SIZE;
+
+ /* Turn event numbers into entropy statement */
+ ent_bits = min_t(int, LRNG_POOL_SIZE_BITS,
+ ((irq_num_events_used * LRNG_DRBG_SECURITY_STRENGTH_BITS) /
+ LRNG_IRQ_ENTROPY_BITS));
+ dbg("obtained %u bits of entropy from newly collected interrupts - not using %u interrupts\n",
+ ent_bits, irq_num_event_back);
+ return ent_bits;
+}
+
+/****************************** DRBG processing *******************************/
+
+/* Helper to seed the DRBG */
+static inline int lrng_drbg_seed_helper(struct drbg_state *drbg,
+ const u8 *inbuf, u32 inbuflen)
+{
+ LIST_HEAD(seedlist);
+ struct drbg_string data;
+
+ drbg_string_fill(&data, inbuf, inbuflen);
+ list_add_tail(&data.list, &seedlist);
+ return drbg->d_ops->update(drbg, &seedlist, drbg->seeded);
+}
+
+/* Helper to generate random numbers from the DRBG */
+static inline int lrng_drbg_generate_helper(struct drbg_state *drbg, u8 *outbuf,
+ u32 outbuflen)
+{
+ return drbg->d_ops->generate(drbg, outbuf, outbuflen, NULL);
+}
+
+/**
+ * Ping all kernel internal callers waiting until the DRBG is fully
+ * seeded that the DRBG is now fully seeded.
+ */
+static void lrng_process_ready_list(void)
+{
+ unsigned long flags;
+ struct random_ready_callback *rdy, *tmp;
+
+ spin_lock_irqsave(&lrng_ready_list_lock, flags);
+ list_for_each_entry_safe(rdy, tmp, &lrng_ready_list, list) {
+ struct module *owner = rdy->owner;
+
+ list_del_init(&rdy->list);
+ rdy->func(rdy);
+ module_put(owner);
+ }
+ spin_unlock_irqrestore(&lrng_ready_list_lock, flags);
+}
+
+/**
+ * Set the slow noise source reseed trigger threshold. The initial threshold
+ * is set to the minimum data size that can be read from the pool: a word. Upon
+ * reaching this value, the next seed threshold of 112 bits is set followed
+ * by 256 bits.
+ *
+ * @entropy_bits size of entropy currently injected into DRBG
+ */
+static void lrng_pdrbg_init_ops(u32 entropy_bits)
+{
+ if (lrng_pdrbg.pdrbg_fully_seeded)
+ return;
+
+ BUILD_BUG_ON(LRNG_IRQ_MIN_NUM % LRNG_POOL_WORD_BITS);
+ BUILD_BUG_ON((LRNG_MIN_SEED_ENTROPY_BITS * LRNG_IRQ_ENTROPY_BITS /
+ LRNG_DRBG_SECURITY_STRENGTH_BITS) > LRNG_IRQ_MIN_NUM);
+
+ /* DRBG is seeded with full security strength */
+ if (entropy_bits >= LRNG_DRBG_SECURITY_STRENGTH_BITS) {
+ lrng_pdrbg.pdrbg_fully_seeded = true;
+ lrng_pdrbg.pdrbg_min_seeded = true;
+ pr_info(DRIVER_NAME": primary DRBG fully seeded\n");
+ lrng_process_ready_list();
+ wake_up_all(&lrng_pdrbg_init_wait);
+ } else if (!lrng_pdrbg.pdrbg_min_seeded) {
+ /* DRBG is seeded with at least 112 bits of entropy */
+ if (entropy_bits >= LRNG_MIN_SEED_ENTROPY_BITS) {
+ lrng_pdrbg.pdrbg_min_seeded = true;
+ pr_info(DRIVER_NAME": primary DRBG minimally seeded\n");
+ atomic_set(&lrng_pool.irq_info.num_events_thresh,
+ LRNG_IRQ_ENTROPY_BITS);
+ /* DRBG is seeded with at least LRNG_POOL_WORD_BITS data bits */
+ } else if (entropy_bits >= (LRNG_POOL_WORD_BITS *
+ LRNG_DRBG_SECURITY_STRENGTH_BITS) /
+ LRNG_IRQ_ENTROPY_BITS) {
+ pr_info(DRIVER_NAME": primary DRBG initially seeded\n");
+ atomic_set(&lrng_pool.irq_info.num_events_thresh,
+ LRNG_IRQ_MIN_NUM);
+ }
+ }
+}
+
+/* Caller must hold lrng_pdrbg_lock */
+static int lrng_pdrbg_generate(u8 *outbuf, u32 outbuflen, bool fullentropy)
+{
+ struct drbg_state *drbg = lrng_pdrbg.pdrbg;
+ int ret;
+
+ /* /dev/random only works from a fully seeded DRBG */
+ if (fullentropy && !lrng_pdrbg.pdrbg_fully_seeded)
+ return 0;
+
+ /*
+ * Only deliver as many bytes as the DRBG is seeded with except during
+ * initialization to provide a first seed to the secondary DRBG.
+ */
+ if (lrng_pdrbg.pdrbg_min_seeded)
+ outbuflen = min_t(u32, outbuflen,
+ lrng_pdrbg.pdrbg_entropy_bits>>3);
+ ret = lrng_drbg_generate_helper(drbg, outbuf, outbuflen);
+ if (ret != outbuflen) {
+ pr_warn(DRIVER_NAME": getting random data from primary DRBG failed (%d)\n",
+ ret);
+ return ret;
+ }
+ if (lrng_pdrbg.pdrbg_entropy_bits > (u32)(ret<<3))
+ lrng_pdrbg.pdrbg_entropy_bits -= ret<<3;
+ else
+ lrng_pdrbg.pdrbg_entropy_bits = 0;
+ dbg("obtained %d bytes of random data from primary DRBG\n", ret);
+ dbg("primary DRBG entropy level at %u bits\n",
+ lrng_pdrbg.pdrbg_entropy_bits);
+ return ret;
+}
+
+/**
+ * Inject data into the primary DRBG with a given entropy value. The function
+ * calls the DRBG's update function. This function also generates random data
+ * if requested by caller. The caller is only returned the amount of random
+ * data that is at most equal to the amount of entropy that just seeded the
+ * DRBG.
+ *
+ * @inbuf buffer to inject
+ * @inbuflen length of inbuf
+ * @entropy_bits entropy value of the data in inbuf in bits
+ * @outbuf buffer to fill immediately after seeding to get full entropy
+ * @outbuflen length of outbuf
+ * @fullentropy start /dev/random output only after the DRBG was fully seeded
+ * @return number of bytes written to outbuf, 0 if outbuf is not supplied,
+ * or < 0 in case of error
+ */
+static int lrng_pdrbg_inject(const u8 *inbuf, u32 inbuflen, u32 entropy_bits,
+ u8 *outbuf, u32 outbuflen, bool fullentropy)
+{
+ struct drbg_state *drbg = lrng_pdrbg.pdrbg;
+ int ret;
+ unsigned long flags;
+
+ /* cap the maximum entropy value to the provided data length */
+ entropy_bits = min_t(u32, entropy_bits, inbuflen<<3);
+
+ spin_lock_irqsave(&lrng_pdrbg_lock, flags);
+ ret = lrng_drbg_seed_helper(drbg, inbuf, inbuflen);
+ if (ret < 0) {
+ pr_warn(DRIVER_NAME": (re)seeding of primary DRBG failed\n");
+ goto unlock;
+ }
+ dbg("inject %u bytes with %u bits of entropy into primary DRBG\n",
+ inbuflen, entropy_bits);
+ drbg->seeded = true;
+
+ /* Adjust the fill level indicator to at most the DRBG sec strength */
+ lrng_pdrbg.pdrbg_entropy_bits =
+ min_t(u32, lrng_pdrbg.pdrbg_entropy_bits + entropy_bits,
+ LRNG_DRBG_SECURITY_STRENGTH_BITS);
+ lrng_pdrbg_init_ops(lrng_pdrbg.pdrbg_entropy_bits);
+
+ if (outbuf && outbuflen)
+ ret = lrng_pdrbg_generate(outbuf, outbuflen, fullentropy);
+
+unlock:
+ spin_unlock_irqrestore(&lrng_pdrbg_lock, flags);
+
+ if (lrng_have_entropy_full()) {
+ /* Wake readers */
+ wake_up_interruptible(&lrng_read_wait);
+ kill_fasync(&fasync, SIGIO, POLL_IN);
+ }
+
+ return ret;
+}
+
+/**
+ * Seed the DRBG from the internal noise sources.
+ */
+static int lrng_pdrbg_seed_internal(u8 *outbuf, u32 outbuflen, bool fullentropy)
+{
+ u8 entropy_buf[LRNG_DRBG_SECURITY_STRENGTH_BYTES * 2 +
+ LRNG_IRQ_ENTROPY_BYTES];
+ u32 total_entropy_bits;
+ int ret;
+
+ /* No reseeding if sufficient entropy in primary DRBG */
+ if (lrng_pdrbg.pdrbg_entropy_bits >= outbuflen<<3) {
+ unsigned long flags;
+
+ spin_lock_irqsave(&lrng_pdrbg_lock, flags);
+ ret = lrng_pdrbg_generate(outbuf, outbuflen, fullentropy);
+ spin_unlock_irqrestore(&lrng_pdrbg_lock, flags);
+ if (ret == outbuflen)
+ goto out;
+ }
+
+ /*
+ * The pool should be large enough to allow fully seeding the DRBG with
+ * its security strength if fast noise sources are not available.
+ */
+ BUILD_BUG_ON(LRNG_POOL_SIZE_BYTES < LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+ BUILD_BUG_ON(LRNG_DRBG_SECURITY_STRENGTH_BYTES % LRNG_POOL_WORD_BYTES);
+ /* entropy pool is read word-wise */
+ BUILD_BUG_ON(LRNG_IRQ_ENTROPY_BYTES % LRNG_POOL_WORD_BYTES);
+ BUILD_BUG_ON(LRNG_IRQ_ENTROPY_BYTES > LRNG_POOL_SIZE_BYTES);
+
+ /*
+ * Concatenate the output of the noise sources. This would be the
+ * spot to add an entropy extractor logic if desired. Note, this
+ * entirety should have the ability to collect entropy equal or larger
+ * than the DRBG strength to be able to feed /dev/random.
+ */
+ total_entropy_bits = lrng_get_jent(entropy_buf);
+ total_entropy_bits += lrng_get_arch(entropy_buf +
+ LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+ /* drain the pool completely during init and when /dev/random calls */
+ total_entropy_bits += lrng_get_pool(
+ entropy_buf + (LRNG_DRBG_SECURITY_STRENGTH_BYTES * 2),
+ LRNG_IRQ_ENTROPY_BYTES,
+ LRNG_DRBG_SECURITY_STRENGTH_BITS - total_entropy_bits,
+ fullentropy || !lrng_pdrbg.pdrbg_fully_seeded);
+
+ dbg("reseed primary DRBG from internal noise sources with %u bits of entropy\n",
+ total_entropy_bits);
+
+ ret = lrng_pdrbg_inject(entropy_buf, sizeof(entropy_buf),
+ total_entropy_bits,
+ outbuf, outbuflen, fullentropy);
+ memzero_explicit(entropy_buf, sizeof(entropy_buf));
+
+out:
+ /* Allow the seeding operation to be called again */
+ atomic_set(&lrng_pool.irq_info.reseed_in_progress, 0);
+
+ return ret;
+}
+
+/**
+ * Inject a data buffer into the secondary DRBG
+ *
+ * @inbuf buffer with data to inject
+ * @inbuflen buffer length
+ * @internal did random data originate from internal sources? Update the
+ * reseed threshold and the reseed timer when seeded with entropic
+ * data from noise sources to prevent unprivileged users from
+ * stopping reseeding the secondary DRBG with entropic data.
+ */
+static void lrng_sdrbg_inject(u8 *inbuf, u32 inbuflen, bool internal)
+{
+ unsigned long flags;
+
+ BUILD_BUG_ON(LRNG_DRBG_RESEED_THRESH > INT_MAX);
+ dbg("seeding secondary DRBG with %u bytes\n", inbuflen);
+ spin_lock_irqsave(&lrng_pdrbg_lock, flags);
+ if (lrng_drbg_seed_helper(lrng_sdrbg.sdrbg, inbuf, inbuflen) < 0) {
+ pr_warn(DRIVER_NAME": seeding of secondary DRBG failed\n");
+ atomic_set(&lrng_sdrbg.requests, 1);
+ } else if (internal) {
+ dbg("secondary DRBG stats since last seeding: %lu secs; generate calls: %d\n",
+ (jiffies - lrng_sdrbg.last_seeded) / HZ,
+ (LRNG_DRBG_RESEED_THRESH -
+ atomic_read(&lrng_sdrbg.requests)));
+ lrng_sdrbg.last_seeded = jiffies;
+ atomic_set(&lrng_sdrbg.requests, LRNG_DRBG_RESEED_THRESH);
+ }
+ spin_unlock_irqrestore(&lrng_pdrbg_lock, flags);
+}
+
+/**
+ * Try to seed the secondary DRBG
+ *
+ * @seedfunc function to use to seed and obtain random data from primary DRBG
+ */
+static void lrng_sdrbg_seed(
+ int (*seed_func)(u8 *outbuf, u32 outbuflen, bool fullentropy))
+{
+ u8 seedbuf[LRNG_DRBG_SECURITY_STRENGTH_BYTES];
+ int ret;
+
+ dbg("reseed of secondary DRBG triggered\n");
+ ret = seed_func(seedbuf, LRNG_DRBG_SECURITY_STRENGTH_BYTES, false);
+ /* Update the DRBG state even though we received zero random data */
+ if (ret < 0) {
+ /*
+ * Try to reseed at next round - note if EINPROGRESS is returned
+ * the request counter may fall below zero in case of parallel
+ * operations. We accept such "underflow" temporarily as the
+ * counter will be set back to a positive number in the course
+ * of the reseed. For these few generate operations under
+ * heavy parallel strain of /dev/urandom we therefore exceed
+ * the LRNG_DRBG_RESEED_THRESH threshold.
+ */
+ if (ret != -EINPROGRESS)
+ atomic_set(&lrng_sdrbg.requests, 1);
+ return;
+ }
+
+ lrng_sdrbg_inject(seedbuf, ret, true);
+ memzero_explicit(seedbuf, ret);
+}
+
+/**
+ * DRBG reseed trigger: Kernel thread handler triggered by the schedule_work()
+ */
+static void lrng_pdrbg_seed_work(struct work_struct *dummy)
+{
+ dbg("reseed triggered by interrupt noise source\n");
+ lrng_sdrbg_seed(lrng_pdrbg_seed_internal);
+}
+
+/**
+ * DRBG reseed trigger: Synchronous reseed request
+ */
+static int lrng_pdrbg_seed(u8 *outbuf, u32 outbuflen, bool fullentropy)
+{
+ /* Ensure that the seeding only occurs once at any given time */
+ if (atomic_cmpxchg(&lrng_pool.irq_info.reseed_in_progress, 0, 1))
+ return -EINPROGRESS;
+ return lrng_pdrbg_seed_internal(outbuf, outbuflen, fullentropy);
+}
+
+/**
+ * Allocation of the DRBG state
+ */
+static struct drbg_state *lrng_drbg_alloc(void)
+{
+ struct drbg_state *drbg = NULL;
+ int coreref = -1;
+ bool pr = false;
+ int ret = 0;
+
+ drbg_convert_tfm_core(LRNG_DRBG_CORE, &coreref, &pr);
+ if (coreref < 0)
+ return NULL;
+
+ drbg = kzalloc(sizeof(struct drbg_state), GFP_KERNEL);
+ if (!drbg)
+ return NULL;
+
+ drbg->core = &drbg_cores[coreref];
+ drbg->seeded = false;
+ ret = drbg_alloc_state(drbg);
+ if (ret)
+ goto err;
+
+ ret = drbg->d_ops->crypto_init(drbg);
+ if (ret == 0)
+ return drbg;
+
+ drbg_dealloc_state(drbg);
+err:
+ kfree(drbg);
+ return NULL;
+}
+
+static int lrng_drbgs_alloc(void)
+{
+ unsigned long flags;
+ struct drbg_state *pdrbg, *sdrbg;
+
+ if (lrng_pdrbg.pdrbg && lrng_sdrbg.sdrbg)
+ return 0;
+
+ pdrbg = lrng_drbg_alloc();
+ if (!pdrbg)
+ return -EFAULT;
+ sdrbg = lrng_drbg_alloc();
+ if (!sdrbg) {
+ drbg_dealloc_state(pdrbg);
+ kfree(pdrbg);
+ return -EFAULT;
+ }
+
+ spin_lock_irqsave(&lrng_pdrbg_lock, flags);
+ if (lrng_pdrbg.pdrbg) {
+ drbg_dealloc_state(pdrbg);
+ kfree(pdrbg);
+ } else {
+ lrng_pdrbg.pdrbg = pdrbg;
+ INIT_WORK(&lrng_pdrbg.lrng_seed_work, lrng_pdrbg_seed_work);
+ pr_info(DRIVER_NAME": primary DRBG with %s core allocated\n",
+ lrng_pdrbg.pdrbg->core->backend_cra_name);
+ }
+ spin_unlock_irqrestore(&lrng_pdrbg_lock, flags);
+
+ spin_lock_irqsave(&lrng_sdrbg_lock, flags);
+ if (lrng_sdrbg.sdrbg) {
+ drbg_dealloc_state(sdrbg);
+ kfree(sdrbg);
+ } else {
+ lrng_sdrbg.sdrbg = sdrbg;
+ pr_info(DRIVER_NAME": secondary DRBG with %s core allocated\n",
+ lrng_sdrbg.sdrbg->core->backend_cra_name);
+ }
+ spin_unlock_irqrestore(&lrng_sdrbg_lock, flags);
+
+ return 0;
+}
+
+/**
+ * Obtain random data from DRBG with information theoretical entropy by
+ * triggering a reseed. The primary DRBG will only return as many random
+ * bytes as it was seeded with.
+ *
+ * @outbuf buffer to store the random data in
+ * @outbuflen length of outbuf
+ * @return: < 0 on error
+ * >= 0 the number of bytes that were obtained
+ */
+static int lrng_pdrbg_get(u8 *outbuf, u32 outbuflen)
+{
+ int ret;
+
+ if (!outbuf || !outbuflen)
+ return 0;
+
+ /* DRBG is not yet available */
+ if (!atomic_read(&lrng_pdrbg_avail))
+ return 0;
+
+ ret = lrng_pdrbg_seed(outbuf, outbuflen, true);
+ dbg("read %u bytes of full entropy data from primary DRBG\n", ret);
+
+ /* Shall we wake up user space writers? */
+ if (lrng_need_entropy()) {
+ wake_up_interruptible(&lrng_write_wait);
+ kill_fasync(&fasync, SIGIO, POLL_OUT);
+ }
+
+ return ret;
+}
+
+/**
+ * Initial RNG provides random data with as much entropy as we have
+ * at boot time until the DRBG becomes available during late_initcall() but
+ * before user space boots. When the DRBG is initialized, the initial RNG
+ * is retired.
+ *
+ * Note: until retirement of this RNG, the system did not generate too much
+ * entropy yet. Hence, a proven DRNG like a DRBG is not necessary here anyway.
+ *
+ * The RNG is using the following as noise source:
+ * * high resolution time stamps
+ * * the collected IRQ state
+ * * CPU noise source if available
+ *
+ * Input/output: it is a drop-in replacement for lrng_sdrbg_get.
+ */
+static u32 lrng_init_state[SHA_WORKSPACE_WORDS];
+static int lrng_init_rng(u8 *outbuf, u32 outbuflen)
+{
+ u32 hash[SHA_DIGEST_WORDS];
+ u32 outbuflen_orig = outbuflen;
+ u32 workspace[SHA_WORKSPACE_WORDS];
+
+ BUILD_BUG_ON(sizeof(lrng_init_state[0]) != LRNG_POOL_WORD_BYTES);
+
+ sha_init(hash);
+ while (outbuflen) {
+ unsigned int arch;
+ u32 i;
+ u32 todo = min_t(u32, outbuflen,
+ SHA_WORKSPACE_WORDS * sizeof(u32));
+
+ for (i = 0; i < SHA_WORKSPACE_WORDS; i++) {
+ if (arch_get_random_int(&arch))
+ lrng_init_state[i] ^= arch;
+ lrng_init_state[i] ^= random_get_entropy();
+ if (i < LRNG_POOL_SIZE)
+ lrng_init_state[i] ^=
+ atomic_read_u32(&lrng_pool.pool[i]);
+ }
+ sha_transform(hash, (u8 *)&lrng_init_state, workspace);
+ /* Mix generated data back in for backtracking resistance */
+ for (i = 0; i < SHA_DIGEST_WORDS; i++)
+ lrng_init_state[i] ^= hash[0];
+
+ memcpy(outbuf, hash, todo);
+ outbuf += todo;
+ outbuflen -= todo;
+ atomic_add(todo, &lrng_initrng_bytes);
+ }
+ memzero_explicit(hash, sizeof(hash));
+ memzero_explicit(workspace, sizeof(workspace));
+
+ return outbuflen_orig;
+}
+
+/**
+ * Get random data out of the secondary DRBG which is reseeded frequently. In
+ * the worst case, the DRBG may generate random numbers without being reseeded
+ * for LRNG_DRBG_RESEED_THRESH requests times LRNG_DRBG_MAX_REQSIZE bytes.
+ *
+ * If the DRBG is not yet initialized, use the initial RNG output.
+ *
+ * @outbuf buffer for storing random data
+ * @outbuflen length of outbuf
+ * @return < 0 in error case (DRBG geeneration or update failed)
+ * >=0 returning the returned number of bytes
+ */
+static int lrng_sdrbg_get(u8 *outbuf, u32 outbuflen)
+{
+ u32 processed = 0;
+ struct drbg_state *drbg = lrng_sdrbg.sdrbg;
+ unsigned long flags;
+ int ret;
+
+ if (!outbuf || !outbuflen)
+ return 0;
+
+ outbuflen = min_t(size_t, outbuflen, INT_MAX);
+
+ /* DRBG is not yet available */
+ if (!atomic_read(&lrng_pdrbg_avail)) {
+ spin_lock_irqsave(&lrng_init_rng_lock, flags);
+ /* Prevent race with lrng_init */
+ if (!atomic_read(&lrng_pdrbg_avail)) {
+ ret = lrng_init_rng(outbuf, outbuflen);
+ spin_unlock_irqrestore(&lrng_init_rng_lock, flags);
+ return ret;
+ }
+ spin_unlock_irqrestore(&lrng_init_rng_lock, flags);
+ }
+
+ while (outbuflen) {
+ unsigned long now = jiffies;
+ u32 todo = min_t(u32, outbuflen, LRNG_DRBG_MAX_REQSIZE);
+
+ if (atomic_dec_and_test(&lrng_sdrbg.requests) ||
+ time_after(now, lrng_sdrbg.last_seeded +
+ lrng_sdrbg_reseed_max_time * HZ))
+ lrng_sdrbg_seed(lrng_pdrbg_seed);
+
+ spin_lock_irqsave(&lrng_sdrbg_lock, flags);
+ ret = lrng_drbg_generate_helper(drbg, outbuf + processed, todo);
+ spin_unlock_irqrestore(&lrng_sdrbg_lock, flags);
+ if (ret <= 0) {
+ pr_warn(DRIVER_NAME": getting random data from secondary DRBG failed (%d)\n",
+ ret);
+ return -EFAULT;
+ }
+ processed += ret;
+ outbuflen -= ret;
+ }
+
+ return processed;
+}
+
+/************************** LRNG kernel interfaces ***************************/
+
+void get_random_bytes(void *buf, int nbytes)
+{
+ lrng_sdrbg_get((u8 *)buf, (u32)nbytes);
+}
+EXPORT_SYMBOL(get_random_bytes);
+
+/**
+ * This function will use the architecture-specific hardware random
+ * number generator if it is available. The arch-specific hw RNG will
+ * almost certainly be faster than what we can do in software, but it
+ * is impossible to verify that it is implemented securely (as
+ * opposed, to, say, the AES encryption of a sequence number using a
+ * key known by the NSA). So it's useful if we need the speed, but
+ * only if we're willing to trust the hardware manufacturer not to
+ * have put in a back door.
+ *
+ * @buf buffer allocated by caller to store the random data in
+ * @nbytes length of outbuf
+ */
+void get_random_bytes_arch(void *buf, int nbytes)
+{
+ u8 *p = buf;
+
+ while (nbytes) {
+ unsigned long v;
+ int chunk = min_t(int, nbytes, sizeof(unsigned long));
+
+ if (!arch_get_random_long(&v))
+ break;
+
+ memcpy(p, &v, chunk);
+ p += chunk;
+ nbytes -= chunk;
+ }
+
+ if (nbytes)
+ lrng_sdrbg_get((u8 *)p, (u32)nbytes);
+}
+EXPORT_SYMBOL(get_random_bytes_arch);
+
+/**
+ * Interface for in-kernel drivers of true hardware RNGs.
+ * Those devices may produce endless random bits and will be throttled
+ * when our pool is full.
+ *
+ * @buffer buffer holding the entropic data from HW noise sources to be used to
+ * (re)seed the DRBG.
+ * @count length of buffer
+ * @entropy_bits amount of entropy in buffer (value is in bits)
+ */
+void add_hwgenerator_randomness(const char *buffer, size_t count,
+ size_t entropy_bits)
+{
+ /* DRBG is not yet online */
+ if (!atomic_read(&lrng_pdrbg_avail))
+ return;
+ /*
+ * Suspend writing if we are fully loaded with entropy.
+ * We'll be woken up again once below lrng_write_wakeup_thresh,
+ * or when the calling thread is about to terminate.
+ */
+ wait_event_interruptible(lrng_write_wait,
+ kthread_should_stop() || lrng_need_entropy());
+ lrng_pdrbg_inject(buffer, count, entropy_bits, NULL, 0, false);
+}
+EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);
+
+/**
+ * Delete a previously registered readiness callback function.
+ */
+void del_random_ready_callback(struct random_ready_callback *rdy)
+{
+ unsigned long flags;
+ struct module *owner = NULL;
+
+ spin_lock_irqsave(&lrng_ready_list_lock, flags);
+ if (!list_empty(&rdy->list)) {
+ list_del_init(&rdy->list);
+ owner = rdy->owner;
+ }
+ spin_unlock_irqrestore(&lrng_ready_list_lock, flags);
+
+ module_put(owner);
+}
+EXPORT_SYMBOL(del_random_ready_callback);
+
+/**
+ * Add a callback function that will be invoked when the DRBG is fully seeded.
+ *
+ * returns: 0 if callback is successfully added
+ * -EALREADY if pool is already initialised (callback not called)
+ * -ENOENT if module for callback is not alive
+ */
+int add_random_ready_callback(struct random_ready_callback *rdy)
+{
+ struct module *owner;
+ unsigned long flags;
+ int err = -EALREADY;
+
+ if (likely(lrng_pdrbg.pdrbg_fully_seeded))
+ return err;
+
+ owner = rdy->owner;
+ if (!try_module_get(owner))
+ return -ENOENT;
+
+ spin_lock_irqsave(&lrng_ready_list_lock, flags);
+ if (lrng_pdrbg.pdrbg_fully_seeded)
+ goto out;
+
+ owner = NULL;
+
+ list_add(&rdy->list, &lrng_ready_list);
+ err = 0;
+
+out:
+ spin_unlock_irqrestore(&lrng_ready_list_lock, flags);
+
+ module_put(owner);
+
+ return err;
+}
+EXPORT_SYMBOL(add_random_ready_callback);
+
+/************************ LRNG user space interfaces *************************/
+
+static ssize_t lrng_read_common(char __user *buf, size_t nbytes,
+ int (*lrng_read_random)(u8 *outbuf, u32 outbuflen))
+{
+ ssize_t ret = 0;
+ u8 tmpbuf[LRNG_DRBG_BLOCKLEN_BYTES];
+ u8 *tmp_large = NULL;
+ u8 *tmp = tmpbuf;
+ u32 tmplen = sizeof(tmpbuf);
+
+ if (nbytes == 0)
+ return 0;
+
+ /*
+ * Satisfy large read requests -- as the common case are smaller
+ * request sizes, such as 16 or 32 bytes, avoid a kmalloc overhead for
+ * those by using the stack variable of tmpbuf.
+ */
+ if (nbytes > LRNG_DRBG_BLOCKLEN_BYTES) {
+ tmplen = min_t(u32, nbytes, LRNG_DRBG_MAX_REQSIZE);
+ tmp_large = kmalloc(tmplen, GFP_KERNEL);
+ if (!tmp_large)
+ tmplen = sizeof(tmpbuf);
+ else
+ tmp = tmp_large;
+ }
+
+ while (nbytes) {
+ u32 todo = min_t(u32, nbytes, tmplen);
+ int rc = 0;
+
+ if (tmp_large && need_resched()) {
+ if (signal_pending(current)) {
+ if (ret == 0)
+ ret = -ERESTARTSYS;
+ break;
+ }
+ schedule();
+ }
+
+ rc = lrng_read_random(tmp, todo);
+ if (rc <= 0)
+ break;
+ if (copy_to_user(buf, tmp, rc)) {
+ ret = -EFAULT;
+ break;
+ }
+
+ nbytes -= rc;
+ buf += rc;
+ ret += rc;
+ }
+
+ /* Wipe data just returned from memory */
+ if (tmp_large)
+ kzfree(tmp_large);
+ else
+ memzero_explicit(tmpbuf, sizeof(tmpbuf));
+
+ return ret;
+}
+
+static ssize_t
+lrng_pdrbg_read_common(int nonblock, char __user *buf, size_t nbytes)
+{
+ ssize_t n;
+
+ if (nbytes == 0)
+ return 0;
+
+ nbytes = min_t(u32, nbytes, LRNG_DRBG_BLOCKLEN_BYTES);
+ while (1) {
+ n = lrng_read_common(buf, nbytes, lrng_pdrbg_get);
+ if (n < 0)
+ return n;
+ if (n > 0)
+ return n;
+
+ /* No entropy available. Maybe wait and retry. */
+ if (nonblock)
+ return -EAGAIN;
+
+ wait_event_interruptible(lrng_read_wait,
+ lrng_have_entropy_full());
+ if (signal_pending(current))
+ return -ERESTARTSYS;
+ }
+}
+
+static ssize_t lrng_pdrbg_read(struct file *file, char __user *buf,
+ size_t nbytes, loff_t *ppos)
+{
+ return lrng_pdrbg_read_common(file->f_flags & O_NONBLOCK, buf, nbytes);
+}
+
+static unsigned int lrng_pdrbg_poll(struct file *file, poll_table *wait)
+{
+ unsigned int mask;
+
+ poll_wait(file, &lrng_read_wait, wait);
+ poll_wait(file, &lrng_write_wait, wait);
+ mask = 0;
+ if (lrng_have_entropy_full())
+ mask |= POLLIN | POLLRDNORM;
+ if (lrng_need_entropy())
+ mask |= POLLOUT | POLLWRNORM;
+ return mask;
+}
+
+static ssize_t lrng_drbg_write_common(const char __user *buffer, size_t count,
+ u32 entropy_bits, bool sdrbg)
+{
+ ssize_t ret = 0;
+ u8 buf[64];
+ const char __user *p = buffer;
+
+ if (!atomic_read(&lrng_pdrbg_avail))
+ return -EAGAIN;
+
+ count = min_t(size_t, count, INT_MAX);
+ while (count > 0) {
+ size_t bytes = min_t(size_t, count, sizeof(buf));
+ u32 ent = min_t(u32, bytes<<3, entropy_bits);
+
+ if (copy_from_user(&buf, p, bytes))
+ return -EFAULT;
+ /* Inject data into primary DRBG */
+ lrng_pdrbg_inject(buf, bytes, ent, NULL, 0, false);
+ /* Data from /dev/[|u]random is injected into secondary DRBG */
+ if (sdrbg)
+ lrng_sdrbg_inject(buf, bytes, false);
+
+ count -= bytes;
+ p += bytes;
+ ret += bytes;
+ entropy_bits -= ent;
+
+ cond_resched();
+ }
+
+ return ret;
+}
+
+static ssize_t lrng_sdrbg_read(struct file *file, char __user *buf,
+ size_t nbytes, loff_t *ppos)
+{
+ return lrng_read_common(buf, nbytes, lrng_sdrbg_get);
+}
+
+static ssize_t lrng_drbg_write(struct file *file, const char __user *buffer,
+ size_t count, loff_t *ppos)
+{
+ return lrng_drbg_write_common(buffer, count, 0, true);
+}
+
+static long lrng_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
+{
+ int size, ent_count;
+ int __user *p = (int __user *)arg;
+
+ switch (cmd) {
+ case RNDGETENTCNT:
+ ent_count = atomic_read(&lrng_pool.irq_info.num_events);
+ if (put_user(ent_count, p))
+ return -EFAULT;
+ return 0;
+ case RNDADDTOENTCNT:
+ if (!capable(CAP_SYS_ADMIN))
+ return -EPERM;
+ if (get_user(ent_count, p))
+ return -EFAULT;
+ if (ent_count < 0) {
+ /* ensure that entropy count cannot go below zero */
+ ent_count = -ent_count;
+ ent_count = min(ent_count,
+ atomic_read(&lrng_pool.irq_info.num_events));
+ atomic_sub(ent_count, &lrng_pool.irq_info.num_events);
+ } else {
+ ent_count = min_t(int, ent_count, LRNG_POOL_SIZE_BITS);
+ atomic_add(ent_count, &lrng_pool.irq_info.num_events);
+ }
+ return 0;
+ case RNDADDENTROPY:
+ if (!capable(CAP_SYS_ADMIN))
+ return -EPERM;
+ if (get_user(ent_count, p++))
+ return -EFAULT;
+ if (ent_count < 0)
+ return -EINVAL;
+ if (get_user(size, p++))
+ return -EFAULT;
+ if (size < 0)
+ return -EINVAL;
+ /* there cannot be more entropy than data */
+ ent_count = min(ent_count, size);
+ /* ent_count is in bytes, but lrng_drbg_write requires bits */
+ return lrng_drbg_write_common((const char __user *)p, size,
+ ent_count<<3, false);
+ case RNDZAPENTCNT:
+ case RNDCLEARPOOL:
+ /* Clear the entropy pool counter. */
+ if (!capable(CAP_SYS_ADMIN))
+ return -EPERM;
+ atomic_set(&lrng_pool.irq_info.num_events, 0);
+ return 0;
+ default:
+ return -EINVAL;
+ }
+}
+
+static int lrng_fasync(int fd, struct file *filp, int on)
+{
+ return fasync_helper(fd, filp, on, &fasync);
+}
+
+const struct file_operations random_fops = {
+ .read = lrng_pdrbg_read,
+ .write = lrng_drbg_write,
+ .poll = lrng_pdrbg_poll,
+ .unlocked_ioctl = lrng_ioctl,
+ .fasync = lrng_fasync,
+ .llseek = noop_llseek,
+};
+
+const struct file_operations urandom_fops = {
+ .read = lrng_sdrbg_read,
+ .write = lrng_drbg_write,
+ .unlocked_ioctl = lrng_ioctl,
+ .fasync = lrng_fasync,
+ .llseek = noop_llseek,
+};
+
+SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
+ unsigned int, flags)
+{
+ if (flags & ~(GRND_NONBLOCK|GRND_RANDOM))
+ return -EINVAL;
+
+ if (count > INT_MAX)
+ count = INT_MAX;
+
+ if (flags & GRND_RANDOM)
+ return lrng_pdrbg_read_common(flags & GRND_NONBLOCK, buf,
+ count);
+
+ if (unlikely(!lrng_pdrbg.pdrbg_fully_seeded)) {
+ if (flags & GRND_NONBLOCK)
+ return -EAGAIN;
+ wait_event_interruptible(lrng_pdrbg_init_wait,
+ lrng_pdrbg.pdrbg_fully_seeded);
+ if (signal_pending(current))
+ return -ERESTARTSYS;
+ }
+ return lrng_sdrbg_read(NULL, buf, count, NULL);
+}
+
+/*************************** LRNG proc interfaces ****************************/
+
+#ifdef CONFIG_SYSCTL
+
+#include <linux/sysctl.h>
+
+static int lrng_min_read_thresh = LRNG_POOL_WORD_BITS;
+static int lrng_min_write_thresh;
+static int lrng_max_read_thresh = LRNG_POOL_SIZE_BITS;
+static int lrng_max_write_thresh = LRNG_POOL_SIZE_BITS;
+static char lrng_sysctl_bootid[16];
+static int lrng_sdrbg_reseed_max_min;
+
+/*
+ * This function is used to return both the bootid UUID, and random
+ * UUID. The difference is in whether table->data is NULL; if it is,
+ * then a new UUID is generated and returned to the user.
+ *
+ * If the user accesses this via the proc interface, the UUID will be
+ * returned as an ASCII string in the standard UUID format; if via the
+ * sysctl system call, as 16 bytes of binary data.
+ */
+static int lrng_proc_do_uuid(struct ctl_table *table, int write,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ struct ctl_table fake_table;
+ unsigned char buf[64], tmp_uuid[16], *uuid;
+
+ uuid = table->data;
+ if (!uuid) {
+ uuid = tmp_uuid;
+ generate_random_uuid(uuid);
+ } else {
+ static DEFINE_SPINLOCK(bootid_spinlock);
+
+ spin_lock(&bootid_spinlock);
+ if (!uuid[8])
+ generate_random_uuid(uuid);
+ spin_unlock(&bootid_spinlock);
+ }
+
+ sprintf(buf, "%pU", uuid);
+
+ fake_table.data = buf;
+ fake_table.maxlen = sizeof(buf);
+
+ return proc_dostring(&fake_table, write, buffer, lenp, ppos);
+}
+
+static int lrng_proc_do_type(struct ctl_table *table, int write,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ struct ctl_table fake_table;
+ unsigned char buf[30];
+
+ snprintf(buf, sizeof(buf), "%s: %s",
+#ifdef CONFIG_CRYPTO_DRBG_HMAC
+ "HMAC DRBG",
+#elif defined CONFIG_CRYPTO_DRBG_CTR
+ "CTR DRBG",
+#elif defined CONFIG_CRYPTO_DRBG_HASH
+ "HASH DRBG",
+#else
+ "unknown",
+#endif
+ lrng_pdrbg.pdrbg->core->backend_cra_name);
+
+ fake_table.data = buf;
+ fake_table.maxlen = sizeof(buf);
+
+ return proc_dostring(&fake_table, write, buffer, lenp, ppos);
+}
+
+/* Return entropy available scaled to integral bits */
+static int lrng_proc_do_entropy(struct ctl_table *table, int write,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ struct ctl_table fake_table;
+ int entropy_count;
+
+ entropy_count = atomic_read((atomic_t *)table->data);
+ if (table->extra2)
+ entropy_count = min_t(int, entropy_count,
+ *(int *)table->extra2);
+
+ fake_table.data = &entropy_count;
+ fake_table.maxlen = sizeof(entropy_count);
+
+ return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
+}
+
+static int lrng_proc_drbg_seed(struct ctl_table *table, int write,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ struct ctl_table fake_table;
+ int drbg_seeded = 0;
+ bool *seeded = (bool *)table->data;
+
+ if (*seeded)
+ drbg_seeded = 1;
+
+ fake_table.data = &drbg_seeded;
+ fake_table.maxlen = sizeof(drbg_seeded);
+
+ return proc_dointvec(&fake_table, write, buffer, lenp, ppos);
+}
+
+static int lrng_sysctl_poolsize = LRNG_POOL_SIZE_BITS;
+static int pdrbg_security_strength = LRNG_DRBG_SECURITY_STRENGTH_BYTES;
+extern struct ctl_table random_table[];
+struct ctl_table random_table[] = {
+ {
+ .procname = "poolsize",
+ .data = &lrng_sysctl_poolsize,
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = proc_dointvec,
+ },
+ {
+ .procname = "entropy_avail",
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = lrng_proc_do_entropy,
+ .data = &lrng_pool.irq_info.num_events,
+ .extra2 = &lrng_max_write_thresh,
+ },
+ {
+ .procname = "read_wakeup_threshold",
+ .data = &lrng_read_wakeup_bits,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec_minmax,
+ .extra1 = &lrng_min_read_thresh,
+ .extra2 = &lrng_max_read_thresh,
+ },
+ {
+ .procname = "write_wakeup_threshold",
+ .data = &lrng_write_wakeup_bits,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec_minmax,
+ .extra1 = &lrng_min_write_thresh,
+ .extra2 = &lrng_max_write_thresh,
+ },
+ {
+ .procname = "boot_id",
+ .data = &lrng_sysctl_bootid,
+ .maxlen = 16,
+ .mode = 0444,
+ .proc_handler = lrng_proc_do_uuid,
+ },
+ {
+ .procname = "uuid",
+ .maxlen = 16,
+ .mode = 0444,
+ .proc_handler = lrng_proc_do_uuid,
+ },
+ {
+ .procname = "urandom_min_reseed_secs",
+ .data = &lrng_sdrbg_reseed_max_time,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec,
+ .extra1 = &lrng_sdrbg_reseed_max_min,
+ },
+ {
+ .procname = "drbg_fully_seeded",
+ .data = &lrng_pdrbg.pdrbg_fully_seeded,
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = lrng_proc_drbg_seed,
+ },
+ {
+ .procname = "drbg_minimally_seeded",
+ .data = &lrng_pdrbg.pdrbg_min_seeded,
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = lrng_proc_drbg_seed,
+ },
+ {
+ .procname = "drbg_type",
+ .maxlen = 30,
+ .mode = 0444,
+ .proc_handler = lrng_proc_do_type,
+ },
+ {
+ .procname = "drbg_security_strength",
+ .data = &pdrbg_security_strength,
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = proc_dointvec,
+ },
+ { }
+};
+#endif /* CONFIG_SYSCTL */
+
+/***************************** Initialize DRBG *******************************/
+
+static int __init lrng_init(void)
+{
+ unsigned long flags;
+
+ BUG_ON(lrng_drbgs_alloc());
+ BUG_ON(LRNG_DRBG_BLOCKLEN_BYTES !=
+ lrng_pdrbg.pdrbg->core->blocklen_bytes);
+ BUG_ON(LRNG_DRBG_SECURITY_STRENGTH_BYTES !=
+ drbg_sec_strength(lrng_pdrbg.pdrbg->core->flags));
+
+ /* This RNG does not work if no high-resolution timer is available */
+ BUG_ON(!random_get_entropy() && !random_get_entropy());
+
+ /*
+ * As we use the IRQ entropic input data processed by the init RNG
+ * again during lrng_pdrbg_seed_internal, we must not claim that
+ * the init RNG state has any entropy when injecting its contents as
+ * an initial seed into the DRBG.
+ */
+ spin_lock_irqsave(&lrng_init_rng_lock, flags);
+ lrng_pdrbg_inject((u8 *)&lrng_init_state,
+ SHA_WORKSPACE_WORDS * sizeof(lrng_init_state[0]),
+ 0, NULL, 0, false);
+ lrng_sdrbg_seed(lrng_pdrbg_seed);
+ atomic_inc(&lrng_pdrbg_avail);
+ memzero_explicit(&lrng_init_state,
+ SHA_WORKSPACE_WORDS * sizeof(lrng_init_state[0]));
+ spin_unlock_irqrestore(&lrng_init_rng_lock, flags);
+ pr_info(DRIVER_NAME": deactivating initial RNG - %d bytes delivered",
+ atomic_read(&lrng_initrng_bytes));
+ return 0;
+}
+
+/* A late init implies that more interrupts are collected for initial seeding */
+late_initcall(lrng_init);
+
+MODULE_LICENSE("Dual BSD/GPL");
+MODULE_AUTHOR("Stephan Mueller <[email protected]>");
+MODULE_DESCRIPTION("Linux Random Number Generator");
--
2.5.5
This patch allows several DRBG functions to be called by the LRNG kernel
code paths outside the drbg.c file.
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/drbg.c | 11 +++++------
include/crypto/drbg.h | 7 +++++++
2 files changed, 12 insertions(+), 6 deletions(-)
diff --git a/crypto/drbg.c b/crypto/drbg.c
index 0a3538f..c339a2e 100644
--- a/crypto/drbg.c
+++ b/crypto/drbg.c
@@ -113,7 +113,7 @@
* the SHA256 / AES 256 over other ciphers. Thus, the favored
* DRBGs are the latest entries in this array.
*/
-static const struct drbg_core drbg_cores[] = {
+struct drbg_core drbg_cores[] = {
#ifdef CONFIG_CRYPTO_DRBG_CTR
{
.flags = DRBG_CTR | DRBG_STRENGTH128,
@@ -205,7 +205,7 @@ static int drbg_uninstantiate(struct drbg_state *drbg);
* Return: normalized strength in *bytes* value or 32 as default
* to counter programming errors
*/
-static inline unsigned short drbg_sec_strength(drbg_flag_t flags)
+unsigned short drbg_sec_strength(drbg_flag_t flags)
{
switch (flags & DRBG_STRENGTH_MASK) {
case DRBG_STRENGTH128:
@@ -1140,7 +1140,7 @@ static int drbg_seed(struct drbg_state *drbg, struct drbg_string *pers,
}
/* Free all substructures in a DRBG state without the DRBG state structure */
-static inline void drbg_dealloc_state(struct drbg_state *drbg)
+void drbg_dealloc_state(struct drbg_state *drbg)
{
if (!drbg)
return;
@@ -1159,7 +1159,7 @@ static inline void drbg_dealloc_state(struct drbg_state *drbg)
* Allocate all sub-structures for a DRBG state.
* The DRBG state structure must already be allocated.
*/
-static inline int drbg_alloc_state(struct drbg_state *drbg)
+int drbg_alloc_state(struct drbg_state *drbg)
{
int ret = -ENOMEM;
unsigned int sb_size = 0;
@@ -1682,8 +1682,7 @@ static int drbg_kcapi_sym(struct drbg_state *drbg, const unsigned char *key,
*
* return: flags
*/
-static inline void drbg_convert_tfm_core(const char *cra_driver_name,
- int *coreref, bool *pr)
+void drbg_convert_tfm_core(const char *cra_driver_name, int *coreref, bool *pr)
{
int i = 0;
size_t start = 0;
diff --git a/include/crypto/drbg.h b/include/crypto/drbg.h
index d961b2b..d24ec22 100644
--- a/include/crypto/drbg.h
+++ b/include/crypto/drbg.h
@@ -268,4 +268,11 @@ enum drbg_prefixes {
DRBG_PREFIX3
};
+extern int drbg_alloc_state(struct drbg_state *drbg);
+extern void drbg_dealloc_state(struct drbg_state *drbg);
+extern void drbg_convert_tfm_core(const char *cra_driver_name, int *coreref,
+ bool *pr);
+extern struct drbg_core drbg_cores[];
+extern unsigned short drbg_sec_strength(drbg_flag_t flags);
+
#endif /* _DRBG_H */
--
2.5.5
On Thu, Apr 21, 2016 at 11:11 AM, Stephan Mueller <[email protected]> wrote:
> Hi Herbert, Ted,
>
> The venerable Linux /dev/random served users of cryptographic mechanisms well
> for a long time. Its behavior is well understood to deliver entropic data. In
> the last years, however, the Linux /dev/random showed signs of age where it has
> challenges to cope with modern computing environments ranging from tiny embedded
> systems, over new hardware resources such as SSDs, up to massive parallel
> systems as well as virtualized environments.
>
> With the experience gained during numerous studies of /dev/random, entropy
> assessments of different noise source designs and assessing entropy behavior in
> virtual machines and other special environments, I felt to do something about
> it.
> I developed a different approach, 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. Finally massive performance
> improvements are visible at /dev/urandom / get_random_bytes.
[quote from pdf]
> ... DRBG is “minimally” seeded with 112^6 bits of entropy.
> This is commonly achieved even before user space is initiated.
Unfortunately one of the issues of the /dev/urandom interface is the
fact that it may start providing random numbers even before the
seeding is complete. From the above quote, I understand that this
issue is not addressed by the new interface. That's a serious
limitation (of the current and inherited by the new implementation),
since most/all newly deployed systems from "cloud" images generate
keys using /dev/urandom (for sshd for example) on boot, and it is
unknown to these applications whether they operate with uninitialized
seed.
While one could argue for using /dev/random, the unpredictability of
the delay it incurs is prohibitive for any practical use. Thus I'd
expect any new interface to provide a better /dev/urandom, by ensuring
that the kernel seed buffer is fully seeded prior to switching to
userspace.
About the rest of the design, I think it is quite clean. I think the
DRBG choice is quite natural given the NIST recommendations, but have
you considered using a stream cipher instead like chacha20 which in
most of cases it would outperform the DRBG based on AES?
regards,
Nikos
Am Donnerstag, 21. April 2016, 15:03:37 schrieb Nikos Mavrogiannopoulos:
Hi Nikos,
> On Thu, Apr 21, 2016 at 11:11 AM, Stephan Mueller <[email protected]>
wrote:
> > Hi Herbert, Ted,
> >
> > The venerable Linux /dev/random served users of cryptographic mechanisms
> > well for a long time. Its behavior is well understood to deliver entropic
> > data. In the last years, however, the Linux /dev/random showed signs of
> > age where it has challenges to cope with modern computing environments
> > ranging from tiny embedded systems, over new hardware resources such as
> > SSDs, up to massive parallel systems as well as virtualized environments.
> >
> > With the experience gained during numerous studies of /dev/random, entropy
> > assessments of different noise source designs and assessing entropy
> > behavior in virtual machines and other special environments, I felt to do
> > something about it.
> > I developed a different approach, 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. Finally massive performance improvements are visible at
> > /dev/urandom / get_random_bytes.
>
> [quote from pdf]
>
> > ... DRBG is “minimally” seeded with 112^6 bits of entropy.
> > This is commonly achieved even before user space is initiated.
>
> Unfortunately one of the issues of the /dev/urandom interface is the
> fact that it may start providing random numbers even before the
> seeding is complete. From the above quote, I understand that this
> issue is not addressed by the new interface. That's a serious
> limitation (of the current and inherited by the new implementation),
> since most/all newly deployed systems from "cloud" images generate
> keys using /dev/urandom (for sshd for example) on boot, and it is
> unknown to these applications whether they operate with uninitialized
> seed.
That limitation is addressed with the getrandom system call. This call will
block until the initial seeding is provided. After the initial seeding,
getrandom behaves like /dev/urandom. This behavior is implemented alredy with
the legacy /dev/random and is preserved with the LRNG.
>
> While one could argue for using /dev/random, the unpredictability of
> the delay it incurs is prohibitive for any practical use. Thus I'd
> expect any new interface to provide a better /dev/urandom, by ensuring
> that the kernel seed buffer is fully seeded prior to switching to
> userspace.
>
> About the rest of the design, I think it is quite clean. I think the
> DRBG choice is quite natural given the NIST recommendations, but have
> you considered using a stream cipher instead like chacha20 which in
> most of cases it would outperform the DRBG based on AES?
This can easily be covered by changing the DRBG implementation -- the current
DRBG implementation in the kernel crypto API is implemented to operate like a
"block chaining mode" on top of the raw cipher. Thus, such change can be
easily rolled in.
Ciao
Stephan
Am Donnerstag, 21. April 2016, 15:03:37 schrieb Nikos Mavrogiannopoulos:
Hi Nikos,
>
> [quote from pdf]
>
> > ... DRBG is “minimally” seeded with 112^6 bits of entropy.
> > This is commonly achieved even before user space is initiated.
>
> Unfortunately one of the issues of the /dev/urandom interface is the
> fact that it may start providing random numbers even before the
> seeding is complete. From the above quote, I understand that this
> issue is not addressed by the new interface. That's a serious
> limitation (of the current and inherited by the new implementation),
> since most/all newly deployed systems from "cloud" images generate
> keys using /dev/urandom (for sshd for example) on boot, and it is
> unknown to these applications whether they operate with uninitialized
> seed.
One more item to consider: If you do not want to change to use getrandom(2),
the LRNG provides you with another means. You may use the
/proc/sys/kernel/random/drbg_minimally_seeded or drbg_fully_seeded booleans.
If you poll on those, you will obtain the indication whether the secondary
DRBG feeding /dev/random is seeded with 112 bits (drbg_minimally_seeded or 256
bits (drbg_fully_seeded).
Those two booleans are exported for exactly that purpose: allow user space to
know about initial seeding status of the LRNG.
Ciao
Stephan
I still have a massive problem with the claims that the "Jitter" RNG
provides any amount of entropy. Just because you and I might not be
able to analyze it doesn't mean that somebody else couldn't. After
all, DUAL-EC DRNG was very complicated and hard to analyze. So would
be something like
AES(NSA_KEY, COUNTER++)
Very hard to analyze indeed. Shall we run statistical tests? They'll
pass with flying colors.
Secure? Not so much.
- Ted
Am Donnerstag, 21. April 2016, 22:51:55 schrieb Theodore Ts'o:
Hi Theodore,
> I still have a massive problem with the claims that the "Jitter" RNG
> provides any amount of entropy. Just because you and I might not be
> able to analyze it doesn't mean that somebody else couldn't. After
> all, DUAL-EC DRNG was very complicated and hard to analyze. So would
> be something like
>
> AES(NSA_KEY, COUNTER++)
>
> Very hard to analyze indeed. Shall we run statistical tests? They'll
> pass with flying colors.
>
> Secure? Not so much.
If you are concerned with that RNG, we can easily drop it from the LRNG. The
testing documented in the writeup disable the Jitter RNG to ensure that only
the LRNG IRQ collection is tested.
The conclusions regarding timeliness of the seeding, the prevention of
draining the entropy pool are performed without the Jitter RNG which implies
that the Jitter RNG can be dropped without harm.
Ciao
Stephan
On Thu, Apr 21, 2016 at 10:51 PM, Theodore Ts'o <[email protected]> wrote:
> I still have a massive problem with the claims that the "Jitter" RNG
> provides any amount of entropy. Just because you and I might not be
> able to analyze it doesn't mean that somebody else couldn't. After
> all, DUAL-EC DRNG was very complicated and hard to analyze. So would
> be something like
>
> AES(NSA_KEY, COUNTER++)
>
> Very hard to analyze indeed. Shall we run statistical tests? They'll
> pass with flying colors.
>
> Secure? Not so much.
>
> - Ted
Jitter, havege and my maxwell(8) all claim to get entropy from
variations in timing of simple calculations, and the docs for
all three give arguments that there really is some entropy
there.
Some of those arguments are quite strong. Mine are in
the PDF at:
https://github.com/sandy-harris/maxwell
I find any of those plausible as an external RNG feeding
random(4), though a hardware RNG or Turbid is preferable.
Hi!
> Please find in [1] the full design discussion covering qualitative assessments
> of the entropy collection and entropy flow. Furthermore, a full
> testing of the
I don't get it.
# The
# idea is that only after obtaining LRNG_POOL_SIZE_BITS healthy bits,
# the
#entropy pool is completely changed with new bits. Yet, the stuck bit
# is not
# discarded as it may still contain some entropy. Hence, it is simply
# XORed
# with the previous bit as the XOR operation maintains the entropy since
# the previous time stamp and the current time stamp are not dependent
# on each other.
So you are relying on high-resolution timestamps. Ok. then you do kind
of the check on the timestamps... ok, why not. But then you mix in the
data regardless, saying that "they are not dependent" and thus can't
hurt.
But you already know they _are_ dependent, that's what your stuck test
told you:
# Thus, the stuck test
# ensures that:
# (a) variations exist in the time deltas,
# (b) variations of time deltas do not have a simple repeating pattern,
# and
# (c) variations do not have a linearly changing patterns (e.g. 1 - 2 -
# 4 - 7
# - 11 - 16).
Now. I could imagine cases where interrupts are correlated... like
some hardware may generate two interrupts for each event or something
like that...
What goes on if high resolution timer is not available?
Best regards,
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Am Sonntag, 24. April 2016, 17:21:09 schrieb Pavel Machek:
Hi Pavel,
> Hi!
>
> > Please find in [1] the full design discussion covering qualitative
> > assessments of the entropy collection and entropy flow. Furthermore, a
> > full
> > testing of the
>
> I don't get it.
>
> # The
> # idea is that only after obtaining LRNG_POOL_SIZE_BITS healthy bits,
> # the
> #entropy pool is completely changed with new bits. Yet, the stuck bit
> # is not
> # discarded as it may still contain some entropy. Hence, it is simply
> # XORed
> # with the previous bit as the XOR operation maintains the entropy since
> # the previous time stamp and the current time stamp are not dependent
> # on each other.
>
> So you are relying on high-resolution timestamps. Ok. then you do kind
> of the check on the timestamps... ok, why not. But then you mix in the
> data regardless, saying that "they are not dependent" and thus can't
> hurt.
>
> But you already know they _are_ dependent, that's what your stuck test
> told you:
The stuck test says that there is a pattern, but not that the pattern shows a
dependency.
>
> # Thus, the stuck test
> # ensures that:
> # (a) variations exist in the time deltas,
> # (b) variations of time deltas do not have a simple repeating pattern,
> # and
> # (c) variations do not have a linearly changing patterns (e.g. 1 - 2 -
> # 4 - 7
> # - 11 - 16).
>
>
> Now. I could imagine cases where interrupts are correlated... like
> some hardware may generate two interrupts for each event or something
> like that...
But I see what you are referring to and I think you have a valid point in a
worst case assessment.
Thus, any stuck value should not be mixed into the pool.
I have changed the code accordingly.
>
> What goes on if high resolution timer is not available?
See lrng_init:
/* This RNG does not work if no high-resolution timer is available */
BUG_ON(!random_get_entropy() && !random_get_entropy());
If there is no high-resolution timer, the LRNG will not produce good entropic
random numbers. The current kernel code implements high-resolution timers for
all but the following architectures where neither random_get_entropy nor
get_cycles are implemented:
- AVR32
- CRIS
- FR-V
- H8300
- Hexagon
- M32R
- METAG
- Microblaze
- SPARC 32
- Score
- SH
- UM
- Unicore32
- Xtensa
Thus, for all large-scale architectures, the LRNG would be applicable.
Please note that also the legacy /dev/random will have hard time to obtain
entropy for these environments. The majority of the entropy comes from high-
resolution time stamps. If you do not have them and you rely on Jiffies, an
attacker has the ability to predict the events mixed into the pools with a
high accuracy. Please remember the outcry when MIPS was identified to have no
get_cycles about two or three years back.
Though, the patch I offer leaves the legacy /dev/random in peace for those
architectures to not touch the status quo.
Ciao
Stephan
Hi!
> > So you are relying on high-resolution timestamps. Ok. then you do kind
> > of the check on the timestamps... ok, why not. But then you mix in the
> > data regardless, saying that "they are not dependent" and thus can't
> > hurt.
> >
> > But you already know they _are_ dependent, that's what your stuck test
> > told you:
>
> The stuck test says that there is a pattern, but not that the pattern shows a
> dependency.
...
> > Now. I could imagine cases where interrupts are correlated... like
> > some hardware may generate two interrupts for each event or something
> > like that...
>
> But I see what you are referring to and I think you have a valid point in a
> worst case assessment.
>
> Thus, any stuck value should not be mixed into the pool.
Thanks.
> /* This RNG does not work if no high-resolution timer is available */
> BUG_ON(!random_get_entropy() && !random_get_entropy());
Heh, does this cause BUG() with 2^-64 probability? :-).
> If there is no high-resolution timer, the LRNG will not produce good entropic
> random numbers. The current kernel code implements high-resolution timers for
> all but the following architectures where neither random_get_entropy nor
> get_cycles are implemented:
Ok, what about stuff like Intel 486 (no RDTSC)?
> Thus, for all large-scale architectures, the LRNG would be applicable.
>
> Please note that also the legacy /dev/random will have hard time to obtain
> entropy for these environments. The majority of the entropy comes
> from high-
Understood.
> Though, the patch I offer leaves the legacy /dev/random in peace for those
> architectures to not touch the status quo.
Well -- that's the major problem -- right? Makes it tricky to tell
what changed, and we had two RNGs to maintain.
Best regards,
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Am Sonntag, 24. April 2016, 23:25:00 schrieb Pavel Machek:
Hi Pavel,
> > /* This RNG does not work if no high-resolution timer is available */
> > BUG_ON(!random_get_entropy() && !random_get_entropy());
>
> Heh, does this cause BUG() with 2^-64 probability? :-).
No, but for the listed arches, get_cycles would return 0. And I only call the
function twice to not be tripped by a potential wrap around at the time of
calling.
>
> > If there is no high-resolution timer, the LRNG will not produce good
> > entropic random numbers. The current kernel code implements
> > high-resolution timers for all but the following architectures where
> > neither random_get_entropy nor
> > get_cycles are implemented:
> Ok, what about stuff like Intel 486 (no RDTSC)?
>
> > Thus, for all large-scale architectures, the LRNG would be applicable.
> >
> > Please note that also the legacy /dev/random will have hard time to obtain
> > entropy for these environments. The majority of the entropy comes
> > from high-
>
> Understood.
>
> > Though, the patch I offer leaves the legacy /dev/random in peace for those
> > architectures to not touch the status quo.
>
> Well -- that's the major problem -- right? Makes it tricky to tell
> what changed, and we had two RNGs to maintain.
I would rather think that even the legacy /dev/random should not return any
values in those environments. The random numbers that are returned on these
systems are bogus, considering that the only noise source that could deliver
some entropy excluding timestamps (if you trust the user) are the HID event
values. And for those listed systems, I doubt very much that they are used in
a desktop environment where you have a console.
If everybody agrees, I can surely add some logic to make the LRNG working on
those systems. But those additions cannot be subjected to a thorough entropy
analysis. Yet I feel that this is wrong.
My goal with the LRNG is to provide a new design using proven techniques that
is forward looking. I am aware that the design does not work in circumstances
where the high-res timer is not present. But do we have to settle on the least
common denominator knowing that this one will not really work to begin with?
Ciao
Stephan
On Thu, Apr 21, 2016 at 5:16 PM, Stephan Mueller <[email protected]> wrote:
>> > ... DRBG is “minimally” seeded with 112^6 bits of entropy.
>> > This is commonly achieved even before user space is initiated.
>>
>> Unfortunately one of the issues of the /dev/urandom interface is the
>> fact that it may start providing random numbers even before the
>> seeding is complete. From the above quote, I understand that this
>> issue is not addressed by the new interface. That's a serious
>> limitation (of the current and inherited by the new implementation),
>> since most/all newly deployed systems from "cloud" images generate
>> keys using /dev/urandom (for sshd for example) on boot, and it is
>> unknown to these applications whether they operate with uninitialized
>> seed.
> One more item to consider: If you do not want to change to use getrandom(2),
> the LRNG provides you with another means.
The main problem is not about willing to switch to getrandom() or not,
but finding any system where getrandom() exists. Today due to libc not
having the call, we can only use /dev/urandom and applications would
most likely continue to do so long time after getrandom() is
introduced to libc.
regards,
Nikos
Am Montag, 25. April 2016, 09:55:14 schrieb Nikos Mavrogiannopoulos:
Hi Nikos,
> On Thu, Apr 21, 2016 at 5:16 PM, Stephan Mueller <[email protected]>
wrote:
> >> > ... DRBG is “minimally” seeded with 112^6 bits of entropy.
> >> > This is commonly achieved even before user space is initiated.
> >>
> >> Unfortunately one of the issues of the /dev/urandom interface is the
> >> fact that it may start providing random numbers even before the
> >> seeding is complete. From the above quote, I understand that this
> >> issue is not addressed by the new interface. That's a serious
> >> limitation (of the current and inherited by the new implementation),
> >> since most/all newly deployed systems from "cloud" images generate
> >> keys using /dev/urandom (for sshd for example) on boot, and it is
> >> unknown to these applications whether they operate with uninitialized
> >> seed.
> >
> > One more item to consider: If you do not want to change to use
> > getrandom(2), the LRNG provides you with another means.
>
> The main problem is not about willing to switch to getrandom() or not,
> but finding any system where getrandom() exists. Today due to libc not
> having the call, we can only use /dev/urandom and applications would
> most likely continue to do so long time after getrandom() is
> introduced to libc.
Implement the syscall yourself with syscall(). If you get ENOSYS back, revert
to your old logic of seeding from /dev/urandom.
If you know you are on kernels >= 3.14, you could use the following steps in
your library:
- poll /proc/sys/kernel/random/entropy_avail in spaces of, say, one second and
block your seeding process until that value becomes non-zero
- if you unblock, seed from /dev/urandom and you have the guarantee of having
a /dev/urandom seeded with 128 bits.
>
> regards,
> Nikos
Ciao
Stephan
On Mon, Apr 25, 2016 at 10:02 AM, Stephan Mueller <[email protected]> wrote:
>> > One more item to consider: If you do not want to change to use
>> > getrandom(2), the LRNG provides you with another means.
>> The main problem is not about willing to switch to getrandom() or not,
>> but finding any system where getrandom() exists. Today due to libc not
>> having the call, we can only use /dev/urandom and applications would
>> most likely continue to do so long time after getrandom() is
>> introduced to libc.
> Implement the syscall yourself with syscall(). If you get ENOSYS back, revert
> to your old logic of seeding from /dev/urandom.
That's far from a solution and I wouldn't recommend to anyone doing
that. We cannot expect each and every program to do glibc's job. The
purpose of a system call like getrandom is to simplify the complex use
of /dev/urandom and eliminate it, not to make code handling randomness
in applications even worse.
regards,
Nikos
On Mon, Apr 25, 2016 at 10:23:51AM +0200, Nikos Mavrogiannopoulos wrote:
> That's far from a solution and I wouldn't recommend to anyone doing
> that. We cannot expect each and every program to do glibc's job. The
> purpose of a system call like getrandom is to simplify the complex use
> of /dev/urandom and eliminate it, not to make code handling randomness
> in applications even worse.
Yes, but if glibc is falling down on the job and refusing to export
the system call (I think for political reasons; it's a Linux-only
interface, so Hurd wouldn't have it), then the only solution is to
either use syscall directly (it's not hard for getrandom, since we're
not using 64-bit arguments which gets tricky for some architectures),
or as Peter Avin has suggested, maybe kernel developers will have to
start releasing the libinux library, and then teaching application
authors to add -linux to their linker lines.
- Ted