[PATCH v4 0/5] /dev/random - a new approach

[PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Hi Herbert, Ted,

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

Changes v4:
* port to 4.7-rc1
* Use classical twisted LFSR approach to collect entropic data as requested by
  George Spelvin. The LFSR is based on a primitive and irreducible polynomial
  whose taps are not too close to the location the current byte is mixed in.
  Primitive polynomials for other entropy pool sizes are offered in the code.
* The reading of the entropy pool is performed with a hash. The hash can be
  specified at compile time. The pre-defined hashes are the same as used for
  the DRBG type (e.g. a SHA256 Hash DRBG implies the use of SHA-256, an AES256
  CTR DRBG implies the use of CMAC-AES).
* Addition of the example defines for a CTR DRBG with AES128 which can be
  enabled during compile time.
* Entropy estimate: one bit of entropy per interrupt. In case a system does
  not have a high-resolution timer, apply 1/10th bit of entropy per interrupt.
  The interrupt estimates can be changed arbitrarily at compile time.
* Use kmalloc_node for the per-NUMA node secondary DRBGs.
* Add boot time entropy tests discussed in section 3.4.3 [1].
* Align all buffers that are processed by the kernel crypto API to an 8 byte
  boundary. This boundary covers all currently existing cipher implementations.

Changes v3:
* Convert debug printk to pr_debug as suggested by Joe Perches
* Add missing \n as suggested by Joe Perches
* Do not mix in struck IRQ measurements as requested by Pavel Machek
* Add handling logic for systems without high-res timer as suggested by Pavel
  Machek -- it uses ideas from the add_interrupt_randomness of the legacy
  /dev/random implementation
* add per NUMA node secondary DRBGs as suggested by Andi Kleen -- the
  explanation of how the logic works is given in section 2.1.1 of my
  documentation [1], especially how the initial seeding is performed.

Changes v2:
* Removal of the Jitter RNG fast noise source as requested by Ted
* Addition of processing of add_input_randomness as suggested by Ted
* Update documentation and testing in [1] to cover the updates
* Addition of a SystemTap script to test add_input_randomness
* To clarify the question whether sufficient entropy is present during boot
  I added one more test in 3.3.1 [1] which demonstrates the providing of
  sufficient entropy during initialization. In the worst case of no fast noise
  sources, in the worst case of a virtual machine with only very few hardware
  devices, the testing shows that the secondary DRBG is fully seeded with 256
  bits of entropy before user space injects the random data obtained
  during shutdown of the previous boot (i.e. the requirement phrased by the
  legacy /dev/random implementation). As the writing of the random data into
  /dev/random by user space will happen before any cryptographic service
  is initialized in user space, this test demonstrates that sufficient
  entropy is already present in the LRNG at the time user space requires it
  for seeding cryptographic daemons. Note, this test result was obtained
  for different architectures, such as x86 64 bit, x86 32 bit, ARM 32 bit and
  MIPS 32 bit.

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

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

Stephan Mueller (5):
  crypto: DRBG - externalize DRBG functions for LRNG
  random: conditionally compile code depending on LRNG
  crypto: Linux Random Number Generator
  crypto: LRNG - enable compile
  random: add interrupt callback to VMBus IRQ handler

 crypto/Kconfig         |   10 +
 crypto/Makefile        |    1 +
 crypto/drbg.c          |   11 +-
 crypto/lrng.c          | 1981 ++++++++++++++++++++++++++++++++++++++++++++++++
 drivers/char/random.c  |    9 +
 drivers/hv/vmbus_drv.c |    3 +
 include/crypto/drbg.h  |    7 +
 include/linux/genhd.h  |    5 +
 include/linux/random.h |    7 +-
 9 files changed, 2027 insertions(+), 7 deletions(-)
 create mode 100644 crypto/lrng.c

-- 
2.7.2

[PATCH v4 1/5] crypto: DRBG - externalize DRBG functions for LRNG

[Stephan Mueller]

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 <smueller@chronox.de>
---
 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.7.2

[PATCH v4 2/5] random: conditionally compile code depending on LRNG

[Stephan Mueller]

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 <smueller@chronox.de>
---
 drivers/char/random.c  | 8 ++++++++
 include/linux/genhd.h  | 5 +++++
 include/linux/random.h | 7 ++++++-
 3 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0158d3b..ef89c0e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -268,6 +268,8 @@
 #include <asm/irq_regs.h>
 #include <asm/io.h>
 
+#ifndef CONFIG_CRYPTO_LRNG
+
 #define CREATE_TRACE_POINTS
 #include <trace/events/random.h>
 
@@ -1621,6 +1623,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 	}
 	return urandom_read(NULL, buf, count, NULL);
 }
+#endif	/* CONFIG_CRYPTO_LRNG */
 
 /********************************************************************
  *
@@ -1628,6 +1631,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
  *
  ********************************************************************/
 
+#ifndef CONFIG_CRYPTO_LRNG
 #ifdef CONFIG_SYSCTL
 
 #include <linux/sysctl.h>
@@ -1765,6 +1769,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)
@@ -1840,6 +1846,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.
@@ -1859,3 +1866,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 359a8e4..24cfb99 100644
--- a/include/linux/genhd.h
+++ b/include/linux/genhd.h
@@ -433,8 +433,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 e47e533..8773dfc 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -17,10 +17,15 @@ struct random_ready_callback {
 	struct module *owner;
 };
 
-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);
+#ifdef CONFIG_CRYPTO_LRNG
+#define add_device_randomness(buf, nbytes) do {} while (0)
+#else	/* CONFIG_CRYPTO_LRNG */
+extern void add_device_randomness(const void *, unsigned int);
+#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.7.2

[PATCH v4 3/5] crypto: Linux Random Number Generator

[Stephan Mueller]

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 <smueller@chronox.de>
---
 crypto/lrng.c | 1981 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 1981 insertions(+)
 create mode 100644 crypto/lrng.c

diff --git a/crypto/lrng.c b/crypto/lrng.c
new file mode 100644
index 0000000..b2d83fc
--- /dev/null
+++ b/crypto/lrng.c
@@ -0,0 +1,1981 @@
+/*
+ * Linux Random Number Generator (LRNG)
+ *
+ * Documentation and test code: http://www.chronox.de/lrng.html
+ *
+ * Copyright (C) 2016, Stephan Mueller <smueller@chronox.de>
+ *
+ * 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.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#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 <linux/uuid.h>
+
+#include <crypto/drbg.h>
+
+/*
+ * Define a DRBG plus a hash / MAC used to extract data from the entropy pool.
+ * For LRNG_HASH_NAME you can use a hash or a MAC (HMAC or CMAC) of your choice
+ * (Note, you should use the suggested selections below -- using SHA-1 or MD5
+ * is not wise). The idea is that the used cipher primitive can be selected to
+ * be the same as used for the DRBG. I.e. the LRNG only uses one cipher
+ * primitive using the same cipher implementation with the options offered in
+ * the following. This means, if the CTR DRBG is selected and AES-NI is present,
+ * both the CTR DRBG and the selected cmac(aes) use AES-NI.
+ *
+ * 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 */
+#  define LRNG_HASH_NAME "sha512"
+# 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 */
+#  define LRNG_HASH_NAME "sha256"
+# 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 */
+#  define LRNG_HASH_NAME "sha512"
+# 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 */
+#  define LRNG_HASH_NAME "sha256"
+# endif
+#elif defined CONFIG_CRYPTO_DRBG_CTR
+# define LRNG_HASH_NAME "cmac(aes)"
+# ifndef CONFIG_CRYPTO_CMAC
+#  error "CMAC support not compiled"
+# endif
+# if 0
+#  define LRNG_DRBG_BLOCKLEN_BYTES 16
+#  define LRNG_DRBG_SECURITY_STRENGTH_BYTES 16
+#  define LRNG_DRBG_CORE "drbg_nopr_ctr_aes128"		/* CTR DRBG AES-128 */
+# else
+#  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 */
+# endif
+#else
+# error "LRNG requires the presence of a DRBG"
+#endif
+
+#define LRNG_DRBG_SECURITY_STRENGTH_BITS (LRNG_DRBG_SECURITY_STRENGTH_BYTES * 8)
+
+/* Alignmask which should cover all cipher implementations */
+#define LRNG_KCAPI_ALIGN 8
+
+/* 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 */
+	spinlock_t lock;
+};
+
+/* 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 */
+	bool fully_seeded;		/* Is DRBG fully seeded? */
+	spinlock_t lock;
+};
+
+/*
+ * 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 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 */
+	bool irq_highres_timer;	/* Is high-resolution timer available? */
+	u32 irq_entropy_bits;	/* LRNG_IRQ_ENTROPY_BITS? */
+};
+
+struct lrng_hash_info {
+	struct shash_desc shash;
+	char ctx[];
+};
+
+/*
+ * 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.
+ *
+ * The pool array is aligned to 8 bytes to comfort the kernel crypto API cipher
+ * implementations: for some accelerated implementations, we need an alignment
+ * to avoid a realignment which involes memcpy(). The alignment to 8 bytes
+ * should satisfy all crypto implementations.
+ *
+ * LRNG_POOL_SIZE is allowed to be changed only if the taps for the LFSR are
+ * changed as well. The size must be in powers of 2 due to the mask handling in
+ * lrng_pool_lfsr which uses AND instead of modulo.
+ *
+ * The polynomials for the LFSR are taken from the following URL
+ * which lists primitive polynomials
+ * http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf. The first
+ * polynomial is from "Primitive Binary Polynomials" by Wayne Stahnke (1993)
+ * and is primitive as well as irreducible.
+ *
+ * Note, the tap values are smaller by one compared to the documentation because
+ * they are used as an index into an array where the index starts by zero.
+ *
+ * All polynomials were also checked to be primitive with magma.
+ */
+static u32 const lrng_lfsr_polynomial[] =
+	{ 127, 28, 26, 1 };			/* 128 words by Stahnke */
+	/* { 255, 253, 250, 245 }; */		/* 256 words */
+	/* { 511, 509, 506, 503 }; */		/* 512 words */
+	/* { 1023, 1014, 1001, 1000 }; */	/* 1024 words */
+	/* { 2047, 2034, 2033, 2028 }; */	/* 2048 words */
+	/* { 4095, 4094, 4080, 4068 }; */	/* 4096 words */
+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] __aligned(LRNG_KCAPI_ALIGN); /* Pool */
+	atomic_t pool_ptr;	/* Ptr into pool for next IRQ word injection */
+	atomic_t input_rotate;	/* rotate for LFSR */
+	u32 last_numa_node;	/* Last NUMA node */
+	struct lrng_hash_info *lrng_hash;
+	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.
+ * 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.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_IRQ_ENTROPY_BYTES (LRNG_DRBG_SECURITY_STRENGTH_BYTES)
+#define LRNG_IRQ_ENTROPY_BITS (LRNG_IRQ_ENTROPY_BYTES * 8)
+
+/*
+ * Leave given amount of entropy in bits entropy pool to serve /dev/random while
+ * /dev/urandom is stressed.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_EMERG_ENTROPY (LRNG_DRBG_SECURITY_STRENGTH_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
+
+#define LRNG_INIT_ENTROPY_BITS 32
+/*
+ * Oversampling factor of IRQ events to obtain
+ * LRNG_DRBG_SECURITY_STRENGTH_BYTES. This factor is used when a
+ * high-resolution time stamp is not available. In this case, jiffies and
+ * register contents are used to fill the entropy pool. These noise sources
+ * are much less entropic than the high-resolution timer. The entropy content
+ * is the entropy content assumed with LRNG_IRQ_ENTROPY_BYTES divided by
+ * LRNG_IRQ_OVERSAMPLING_FACTOR.
+ *
+ * This value is allowed to be changed.
+ */
+#define LRNG_IRQ_OVERSAMPLING_FACTOR 10
+
+static struct lrng_pdrbg lrng_pdrbg = {
+	.lock = __SPIN_LOCK_UNLOCKED(lrng.pdrbg.lock)
+};
+
+static struct lrng_sdrbg **lrng_sdrbg __read_mostly;
+
+static struct lrng_pool lrng_pool = {
+	.irq_info = {
+		.crngt_ctr = ATOMIC_INIT(LRNG_FIPS_CRNGT),
+	},
+};
+
+static LIST_HEAD(lrng_ready_list);
+static DEFINE_SPINLOCK(lrng_ready_list_lock);
+
+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)");
+
+/*
+ * 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 ************************/
+
+/**
+ * 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);
+	pr_debug("obtained %u bits of entropy from CPU RNG noise source\n",
+		 ent_bits);
+	return ent_bits;
+}
+
+/************************ Slow noise source processing ************************/
+
+/*
+ * Implement a (modified) twisted Generalized Feedback Shift Register. (See M.
+ * Matsumoto & Y. Kurita, 1992.  Twisted GFSR generators. ACM Transactions on
+ * Modeling and Computer Simulation 2(3):179-194.  Also see M. Matsumoto & Y.
+ * Kurita, 1994.  Twisted GFSR generators II.  ACM Transactions on Modeling and
+ * Computer Simulation 4:254-266).
+ */
+static u32 const lrng_twist_table[8] = {
+	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
+	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
+
+/**
+ * Hot code path - inject data into entropy pool using LFSR
+ */
+static void lrng_pool_lfsr(const u8 *buf, u32 buflen)
+{
+	u32 mask = (LRNG_POOL_SIZE - 1);
+
+	while (buflen--) {
+		u32 ptr = (u32)atomic_add_return(1, &lrng_pool.pool_ptr) & mask;
+		/*
+		 * Add 7 bits of rotation to the pool. At the beginning of the
+		 * pool, add an extra 7 bits rotation, so that successive passes
+		 * spread the input bits across the pool evenly.
+		 */
+		u32 input_rotate = (u32)atomic_add_return((ptr ? 7 : 14),
+						&lrng_pool.input_rotate) & 31;
+		u32 word = rol32(*buf++, input_rotate);
+
+		BUILD_BUG_ON(LRNG_POOL_SIZE - 1 != lrng_lfsr_polynomial[0]);
+		word ^= atomic_read_u32(&lrng_pool.pool[ptr]);
+		word ^= atomic_read_u32(&lrng_pool.pool[
+				(ptr + lrng_lfsr_polynomial[0]) & mask]);
+		word ^= atomic_read_u32(&lrng_pool.pool[
+				(ptr + lrng_lfsr_polynomial[1]) & mask]);
+		word ^= atomic_read_u32(&lrng_pool.pool[
+				(ptr + lrng_lfsr_polynomial[2]) & mask]);
+		word ^= atomic_read_u32(&lrng_pool.pool[
+				(ptr + lrng_lfsr_polynomial[3]) & mask]);
+
+		word = (word >> 3) ^ lrng_twist_table[word & 7];
+		atomic_set(&lrng_pool.pool[ptr], word);
+	}
+}
+
+/**
+ * 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("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 - mix data into entropy pool
+ */
+static inline void lrng_pool_mixin(const u8 *buf, u32 buflen, u32 irq_num)
+{
+	lrng_pool_lfsr(buf, buflen);
+
+	/* Should we wake readers? */
+	if (irq_num == lrng_read_wakeup_bits) {
+		wake_up_interruptible(&lrng_read_wait);
+		kill_fasync(&fasync, SIGIO, POLL_IN);
+	}
+
+	/* Only try to reseed if the DRBG is alive. */
+	if (!atomic_read(&lrng_pdrbg_avail))
+		return;
+
+	/*
+	 * Once all secondary DRBGs are fully seeded, the interrupt noise
+	 * sources will not trigger any reseeding any more.
+	 */
+	if (lrng_sdrbg[lrng_pool.last_numa_node]->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;
+
+	/* 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);
+}
+
+/**
+ * Hot code path - Callback for interrupt handler
+ */
+void add_interrupt_randomness(int irq, int irq_flags)
+{
+	u32 now_time = random_get_entropy();
+	struct lrng_irq_info *irq_info = &lrng_pool.irq_info;
+	u32 irq_num = (u32)atomic_add_return(1, &irq_info->num_events);
+
+	if (lrng_pool.irq_info.irq_highres_timer) {
+		if (lrng_irq_stuck(irq_info, now_time))
+			return;
+		lrng_pool_mixin((u8 *)&now_time, sizeof(now_time), irq_num);
+	} else {
+		struct pt_regs *regs = get_irq_regs();
+		static atomic_t reg_idx = ATOMIC_INIT(0);
+
+		struct {
+			long jiffies;
+			int irq;
+			int irq_flags;
+			u64 ip;
+			u32 curr_reg;
+		} data;
+
+		data.jiffies = jiffies;
+		data.irq = irq;
+		data.irq_flags = irq_flags;
+		if (regs) {
+			u32 *ptr = (u32 *)regs;
+
+			data.ip = instruction_pointer(regs);
+			if (atomic_read(&reg_idx) >=
+					sizeof(struct pt_regs) / sizeof(u32))
+				atomic_set(&reg_idx, 0);
+			data.curr_reg = *(ptr + atomic_add_return(1, &reg_idx));
+		}
+
+		lrng_pool_mixin((u8 *)&data, sizeof(data), irq_num);
+	}
+}
+EXPORT_SYMBOL(add_interrupt_randomness);
+
+/**
+ * Callback for HID layer
+ */
+void add_input_randomness(unsigned int type, unsigned int code,
+			  unsigned int value)
+{
+	static unsigned char last_value;
+
+	struct {
+		unsigned int val;
+	} data;
+
+	/* ignore autorepeat and the like */
+	if (value == last_value)
+		return;
+
+	last_value = value;
+
+	data.val = (type << 4) ^ code ^ (code >> 4) ^ value;
+	lrng_pool_mixin((u8 *)&data, sizeof(data), 0);
+}
+EXPORT_SYMBOL_GPL(add_input_randomness);
+
+static inline u32 lrng_entropy_to_data(u32 entropy_bits)
+{
+	return ((entropy_bits * lrng_pool.irq_info.irq_entropy_bits) /
+		LRNG_DRBG_SECURITY_STRENGTH_BITS);
+}
+
+static inline u32 lrng_data_to_entropy(u32 irqnum)
+{
+	return ((irqnum * LRNG_DRBG_SECURITY_STRENGTH_BITS) /
+		lrng_pool.irq_info.irq_entropy_bits);
+}
+
+/**
+ * Read the entropy pool out for use. The caller must ensure this function
+ * is only called once at a time.
+ *
+ * This function handles the translation from the number of received interrupts
+ * into an entropy statement. The conversion depends on LRNG_IRQ_ENTROPY_BYTES
+ * which defines how many interrupts must be received to obtain 256 bits of
+ * entropy. With this value, the function lrng_data_to_entropy converts a given
+ * data size (received interrupts, requested amount of data, etc.) into an
+ * entropy statement. lrng_entropy_to_data does the reverse.
+ *
+ * Both functions are agnostic about the type of data: when the number of
+ * interrupts is processed by these functions, the resulting entropy value is in
+ * bits as we assume the entropy of interrupts is measured in bits. When data is
+ * processed, the entropy value is in bytes as the data is measured in bytes.
+ *
+ * @outbuf buffer to store data in with size LRNG_DRBG_SECURITY_STRENGTH_BYTES
+ * @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 u32 lrng_get_pool(u8 *outbuf, u32 requested_entropy_bits, bool drain)
+{
+	u32 i, avail_entropy_bytes, irq_num_events_used, irq_num_event_back;
+	/* How many unused interrupts are in entropy pool? */
+	u32 irq_num_events = atomic_xchg_u32(&lrng_pool.irq_info.num_events, 0);
+	/* Convert available interrupts into entropy statement */
+	u32 avail_entropy_bits = lrng_data_to_entropy(irq_num_events);
+	struct shash_desc *shash = &lrng_pool.lrng_hash->shash;
+	u32 digestsize = crypto_shash_digestsize(shash->tfm);
+	u8 digest[digestsize] __aligned(LRNG_KCAPI_ALIGN);
+
+	/* Cap available entropy to pool size */
+	avail_entropy_bits =
+			min_t(u32, avail_entropy_bits, LRNG_POOL_SIZE_BITS);
+
+	/* How much entropy we need to and can we use? */
+	if (drain)
+		avail_entropy_bits = min_t(u32, avail_entropy_bits,
+					   requested_entropy_bits);
+	else
+		avail_entropy_bits = min_t(u32, (avail_entropy_bits -
+			 min_t(u32, LRNG_EMERG_ENTROPY, avail_entropy_bits)),
+						requested_entropy_bits);
+
+	/* Hash is a compression function: we generate entropy amount of data */
+	avail_entropy_bits = round_down(avail_entropy_bits, 8);
+	avail_entropy_bytes = avail_entropy_bits >> 3;
+	BUG_ON(avail_entropy_bytes > LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+
+	/* Hash the entire entropy pool */
+	for (i = 0; i < LRNG_DRBG_SECURITY_STRENGTH_BYTES; i += digestsize) {
+		u32 tocopy = min_t(u32, avail_entropy_bytes, digestsize);
+
+		if (crypto_shash_digest(shash, (u8 *)lrng_pool.pool,
+					LRNG_POOL_SIZE_BYTES, digest))
+			return 0;
+
+		/* Mix read data back into pool for backtracking resistance */
+		lrng_pool_lfsr(digest, digestsize);
+		/* Copy the data out to the caller */
+		memcpy(outbuf + i, digest, tocopy);
+		avail_entropy_bytes -= tocopy;
+		if (!avail_entropy_bytes)
+			break;
+	}
+	memzero_explicit(digest, digestsize);
+
+	/* 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);
+	/* Convert used entropy into interrupt number for subtraction */
+	irq_num_events_used = lrng_entropy_to_data(avail_entropy_bits);
+	/* 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);
+
+	/* Obtain entropy statement in bits from the used entropy */
+	pr_debug("obtained %u bits of entropy from %u newly collected interrupts - not using %u interrupts\n",
+		 avail_entropy_bits, irq_num_events_used, irq_num_event_back);
+
+	return avail_entropy_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;
+
+	/* 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("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("primary DRBG minimally seeded\n");
+			atomic_set(&lrng_pool.irq_info.num_events_thresh,
+				   lrng_entropy_to_data(
+					LRNG_DRBG_SECURITY_STRENGTH_BITS));
+
+		/* DRBG is seeded with at least LRNG_INIT_ENTROPY_BITS bits */
+		} else if (entropy_bits >= LRNG_INIT_ENTROPY_BITS) {
+			pr_info("primary DRBG initially seeded\n");
+			atomic_set(&lrng_pool.irq_info.num_events_thresh,
+				   lrng_entropy_to_data(
+					LRNG_MIN_SEED_ENTROPY_BITS));
+		}
+	}
+}
+
+/* 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);
+	else
+		outbuflen = min_t(u32, outbuflen,
+				  LRNG_MIN_SEED_ENTROPY_BITS>>3);
+
+	ret = lrng_drbg_generate_helper(drbg, outbuf, outbuflen);
+	if (ret != outbuflen) {
+		pr_warn("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;
+	pr_debug("obtained %d bytes of random data from primary DRBG\n", ret);
+	pr_debug("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("(re)seeding of primary DRBG failed\n");
+		goto unlock;
+	}
+	pr_debug("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,
+				    bool drain)
+{
+	u8 entropy_buf[LRNG_DRBG_SECURITY_STRENGTH_BYTES * 2]
+						__aligned(LRNG_KCAPI_ALIGN);
+	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;
+	}
+
+	/*
+	 * 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_arch(entropy_buf);
+
+	/*
+	 * drain the pool completely during init and when /dev/random calls.
+	 *
+	 * lrng_get_pool must be guaranteed to be called with multiples of 8
+	 * (bits) of entropy as it can only operate byte-wise.
+	 */
+	total_entropy_bits += lrng_get_pool(
+		entropy_buf + LRNG_DRBG_SECURITY_STRENGTH_BYTES,
+		LRNG_DRBG_SECURITY_STRENGTH_BITS -
+			round_down(total_entropy_bits, 8), drain);
+
+	pr_debug("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
+ *
+ * @sdrbg reference to 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(struct lrng_sdrbg *sdrbg,
+			      u8 *inbuf, u32 inbuflen, bool internal)
+{
+	unsigned long flags;
+
+	BUILD_BUG_ON(LRNG_DRBG_RESEED_THRESH > INT_MAX);
+	pr_debug("seeding secondary DRBG with %u bytes\n", inbuflen);
+	spin_lock_irqsave(&sdrbg->lock, flags);
+	if (lrng_drbg_seed_helper(sdrbg->sdrbg, inbuf, inbuflen) < 0) {
+		pr_warn("seeding of secondary DRBG failed\n");
+		atomic_set(&sdrbg->requests, 1);
+	} else if (internal) {
+		pr_debug("secondary DRBG stats since last seeding: %lu secs; generate calls: %d\n",
+			 (jiffies - sdrbg->last_seeded) / HZ,
+			 (LRNG_DRBG_RESEED_THRESH -
+			  atomic_read(&sdrbg->requests)));
+		sdrbg->last_seeded = jiffies;
+		atomic_set(&sdrbg->requests, LRNG_DRBG_RESEED_THRESH);
+	}
+	spin_unlock_irqrestore(&sdrbg->lock, flags);
+}
+
+/**
+ * Try to seed the secondary DRBG
+ *
+ * @sdrbg reference to secondary DRBG
+ * @seedfunc function to use to seed and obtain random data from primary DRBG
+ */
+static void lrng_sdrbg_seed(struct lrng_sdrbg *sdrbg,
+	int (*seed_func)(u8 *outbuf, u32 outbuflen, bool fullentropy,
+			 bool drain))
+{
+	u8 seedbuf[LRNG_DRBG_SECURITY_STRENGTH_BYTES];
+	int ret;
+
+	BUILD_BUG_ON(LRNG_MIN_SEED_ENTROPY_BITS >
+		     LRNG_DRBG_SECURITY_STRENGTH_BITS);
+
+	pr_debug("reseed of secondary DRBG triggered\n");
+	ret = seed_func(seedbuf, LRNG_DRBG_SECURITY_STRENGTH_BYTES, false,
+			!sdrbg->fully_seeded);
+	/* 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(&sdrbg->requests, 1);
+		return;
+	}
+
+	lrng_sdrbg_inject(sdrbg, seedbuf, ret, true);
+	memzero_explicit(seedbuf, ret);
+
+	if (ret >= LRNG_DRBG_SECURITY_STRENGTH_BYTES)
+		sdrbg->fully_seeded = true;
+}
+
+/**
+ * DRBG reseed trigger: Kernel thread handler triggered by the schedule_work()
+ */
+static void lrng_pdrbg_seed_work(struct work_struct *dummy)
+{
+	u32 node;
+
+	for (node = 0; node <= lrng_pool.last_numa_node; node++) {
+		struct lrng_sdrbg *sdrbg = lrng_sdrbg[node];
+
+		if (!sdrbg->fully_seeded) {
+			pr_debug("reseed triggered by interrupt noise source for secondary DRBG on NUMA node %d\n", node);
+			lrng_sdrbg_seed(sdrbg, lrng_pdrbg_seed_internal);
+			if (node && sdrbg->fully_seeded) {
+				/* Prevent reseed storm */
+				sdrbg->last_seeded += node * 100 * HZ;
+				/* Prevent draining of pool on idle systems */
+				lrng_sdrbg_reseed_max_time += 100;
+			}
+			return;
+		}
+	}
+}
+
+/**
+ * DRBG reseed trigger: Synchronous reseed request
+ */
+static int lrng_pdrbg_seed(u8 *outbuf, u32 outbuflen, bool fullentropy,
+			   bool drain)
+{
+	/* 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, drain);
+}
+
+/**
+ * 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, true);
+	pr_debug("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));
+
+		/* Update init RNG state with CPU RNG and timer data */
+		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();
+		}
+		/* SHA-1 update using the init RNG state */
+		sha_transform(hash, (u8 *)&lrng_init_state, workspace);
+
+		/* SHA-1 update with all words of the entropy pool */
+		BUILD_BUG_ON(LRNG_POOL_SIZE % 16);
+		for (i = 0; i < LRNG_POOL_SIZE; i += 16)
+			sha_transform(hash, (u8 *)(lrng_pool.pool + i),
+				      workspace);
+
+		/* Mix generated data into state for backtracking resistance */
+		for (i = 0; i < SHA_DIGEST_WORDS; i++)
+			lrng_init_state[i] ^= hash[i];
+
+		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;
+}
+
+static inline struct lrng_sdrbg *lrng_get_current_sdrbg(void)
+{
+	struct lrng_sdrbg *sdrbg = lrng_sdrbg[numa_node_id()];
+
+	return (sdrbg->fully_seeded) ? sdrbg : lrng_sdrbg[0];
+}
+
+/**
+ * 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 generation or update failed)
+ *	   >=0 returning the returned number of bytes
+ */
+static int lrng_sdrbg_get(u8 *outbuf, u32 outbuflen)
+{
+	u32 processed = 0;
+	struct 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);
+	}
+
+	sdrbg = lrng_get_current_sdrbg();
+	while (outbuflen) {
+		unsigned long now = jiffies;
+		u32 todo = min_t(u32, outbuflen, LRNG_DRBG_MAX_REQSIZE);
+
+		if (atomic_dec_and_test(&sdrbg->requests) ||
+		    time_after(now, sdrbg->last_seeded +
+			       lrng_sdrbg_reseed_max_time * HZ))
+			lrng_sdrbg_seed(sdrbg, lrng_pdrbg_seed);
+
+		spin_lock_irqsave(&sdrbg->lock, flags);
+		ret = lrng_drbg_generate_helper(sdrbg->sdrbg,
+						outbuf + processed, todo);
+		spin_unlock_irqrestore(&sdrbg->lock, flags);
+		if (ret <= 0) {
+			pr_warn("getting random data from secondary DRBG failed (%d)\n",
+				ret);
+			return -EFAULT;
+		}
+		processed += ret;
+		outbuflen -= ret;
+	}
+
+	return processed;
+}
+
+/**
+ * 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;
+	u32 node;
+	u32 num_nodes = num_possible_nodes();
+
+	pdrbg = lrng_drbg_alloc();
+	if (!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("primary DRBG with %s core allocated\n",
+			lrng_pdrbg.pdrbg->core->backend_cra_name);
+	}
+
+	lrng_pool.last_numa_node = num_nodes - 1;
+
+	spin_unlock_irqrestore(&lrng_pdrbg.lock, flags);
+
+	lrng_sdrbg = kmalloc_array(sizeof(void *), num_nodes,
+				   GFP_KERNEL|__GFP_NOFAIL);
+	for (node = 0; node < num_nodes; node++) {
+		struct lrng_sdrbg *sdrbg;
+
+		sdrbg = kmalloc_node(sizeof(struct lrng_sdrbg),
+				     GFP_KERNEL|__GFP_NOFAIL, node);
+		if (!sdrbg)
+			goto err;
+		memset(sdrbg, 0, sizeof(lrng_sdrbg));
+		lrng_sdrbg[node] = sdrbg;
+
+		sdrbg->sdrbg = lrng_drbg_alloc();
+		if (!sdrbg->sdrbg)
+			goto err;
+
+		atomic_set(&sdrbg->requests, 1);
+		spin_lock_init(&sdrbg->lock);
+		sdrbg->last_seeded = jiffies;
+		sdrbg->fully_seeded = false;
+
+		pr_info("secondary DRBG with %s core for NUMA node %d allocated\n",
+			sdrbg->sdrbg->core->backend_cra_name, node);
+	}
+
+	return 0;
+
+err:
+	for (node = 0; node < num_nodes; node++) {
+		struct lrng_sdrbg *sdrbg = lrng_sdrbg[node];
+
+		if (sdrbg) {
+			if (sdrbg->sdrbg)
+				drbg_dealloc_state(sdrbg->sdrbg);
+			kfree(sdrbg);
+		}
+	}
+	kfree(lrng_sdrbg);
+
+	drbg_dealloc_state(pdrbg);
+	kfree(pdrbg);
+
+	return -EFAULT;
+}
+
+static int lrng_alloc(void)
+{
+	struct lrng_hash_info *lrng_hash;
+	struct crypto_shash *tfm;
+	int size;
+	int ret = lrng_drbgs_alloc();
+	u8 key[LRNG_DRBG_SECURITY_STRENGTH_BYTES] __aligned(LRNG_KCAPI_ALIGN);
+
+	if (ret)
+		return ret;
+
+	tfm = crypto_alloc_shash(LRNG_HASH_NAME, 0, 0);
+	if (IS_ERR(tfm)) {
+		pr_err("could not allocate hash %s\n", LRNG_HASH_NAME);
+		return PTR_ERR(tfm);
+	}
+
+	size = sizeof(struct lrng_hash_info) + crypto_shash_descsize(tfm);
+	lrng_hash = kmalloc(size, GFP_KERNEL);
+	if (!lrng_hash) {
+		crypto_free_shash(tfm);
+		return -ENOMEM;
+	}
+
+	lrng_hash->shash.tfm = tfm;
+	lrng_hash->shash.flags = 0x0;
+
+	/* If the used hash is no MAC, ignore the ENOSYS return code */
+	lrng_init_rng(key, sizeof(key));
+	ret = crypto_shash_setkey(tfm, key, sizeof(key));
+	memzero_explicit(key, sizeof(key));
+	if (ret && ret != -ENOSYS) {
+		pr_err("could not set the key for MAC\n");
+		return ret;
+	}
+
+	lrng_pool.lrng_hash = lrng_hash;
+	pr_info("hash %s for reading entropy pool allocated\n", LRNG_HASH_NAME);
+
+	return 0;
+}
+
+/************************** 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] __aligned(LRNG_KCAPI_ALIGN);
+	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 + LRNG_KCAPI_ALIGN, GFP_KERNEL);
+		if (!tmp_large)
+			tmplen = sizeof(tmpbuf);
+		else
+			tmp = PTR_ALIGN(tmp_large, LRNG_KCAPI_ALIGN);
+	}
+
+	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)
+{
+	if (nbytes == 0)
+		return 0;
+
+	nbytes = min_t(u32, nbytes, LRNG_DRBG_BLOCKLEN_BYTES);
+	while (1) {
+		ssize_t n;
+
+		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] __aligned(LRNG_KCAPI_ALIGN);
+	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) {
+			u32 node;
+			int num_nodes = num_possible_nodes();
+
+			for (node = 0; node < num_nodes; node++)
+				lrng_sdrbg_inject(lrng_sdrbg[node], 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[70];
+
+	snprintf(buf, sizeof(buf), "%s: %s\nentropy pool read hash: %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, LRNG_HASH_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 = lrng_data_to_entropy(
+				atomic_read_u32((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_bool(struct ctl_table *table, int write,
+			  void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	struct ctl_table fake_table;
+	int loc_boolean = 0;
+	bool *boolean = (bool *)table->data;
+
+	if (*boolean)
+		loc_boolean = 1;
+
+	fake_table.data = &loc_boolean;
+	fake_table.maxlen = sizeof(loc_boolean);
+
+	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_bool,
+	},
+	{
+		.procname	= "drbg_minimally_seeded",
+		.data		= &lrng_pdrbg.pdrbg_min_seeded,
+		.maxlen		= sizeof(int),
+		.mode		= 0444,
+		.proc_handler	= lrng_proc_bool,
+	},
+	{
+		.procname	= "lrng_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,
+	},
+	{
+		.procname	= "high_resolution_timer",
+		.data		= &lrng_pool.irq_info.irq_highres_timer,
+		.maxlen		= sizeof(int),
+		.mode		= 0444,
+		.proc_handler	= lrng_proc_bool,
+	},
+	{ }
+};
+#endif /* CONFIG_SYSCTL */
+
+/***************************** Initialize DRBG *******************************/
+
+static int __init lrng_init(void)
+{
+	unsigned long flags;
+
+	BUG_ON(lrng_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));
+
+	/*
+	 * 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);
+
+	if (random_get_entropy() || random_get_entropy()) {
+		lrng_pool.irq_info.irq_highres_timer = true;
+		lrng_pool.irq_info.irq_entropy_bits = LRNG_IRQ_ENTROPY_BITS;
+	} else {
+		lrng_pool.irq_info.irq_entropy_bits =
+			LRNG_IRQ_ENTROPY_BITS * LRNG_IRQ_OVERSAMPLING_FACTOR;
+		if (fips_enabled) {
+			pr_warn("LRNG not suitable for FIPS 140-2 use cases\n");
+			WARN_ON(1);
+		}
+		pr_warn("operating without high-resolution timer and applying IRQ oversampling factor %u\n",
+			LRNG_IRQ_OVERSAMPLING_FACTOR);
+	}
+	atomic_set(&lrng_pool.irq_info.num_events_thresh,
+		   lrng_entropy_to_data(LRNG_INIT_ENTROPY_BITS));
+
+	lrng_pdrbg_inject((u8 *)&lrng_init_state,
+			  SHA_WORKSPACE_WORDS * sizeof(lrng_init_state[0]),
+			  0, NULL, 0, false);
+	lrng_sdrbg_seed(lrng_sdrbg[0], 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("deactivating initial RNG - %d bytes delivered\n",
+		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 <smueller@chronox.de>");
+MODULE_DESCRIPTION("Linux Random Number Generator");
-- 
2.7.2

[PATCH v4 4/5] crypto: LRNG - enable compile

[Stephan Mueller]

Add LRNG compilation support.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 crypto/Kconfig  | 10 ++++++++++
 crypto/Makefile |  1 +
 2 files changed, 11 insertions(+)

diff --git a/crypto/Kconfig b/crypto/Kconfig
index 1d33beb..9aaf96c 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1588,6 +1588,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.7.2

[PATCH v4 5/5] random: add interrupt callback to VMBus IRQ handler

[Stephan Mueller]

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.
This implies that the interrupt entropy collector is not triggered.

This patch adds the interrupt entropy collection callback into the VMBus
interrupt handler function.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c  | 1 +
 drivers/hv/vmbus_drv.c | 3 +++
 2 files changed, 4 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index ef89c0e..ac74716 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -948,6 +948,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	/* award one bit for the contents of the fast pool */
 	credit_entropy_bits(r, credit + 1);
 }
+EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
 #ifdef CONFIG_BLOCK
 void add_disk_randomness(struct gendisk *disk)
diff --git a/drivers/hv/vmbus_drv.c b/drivers/hv/vmbus_drv.c
index 952f20f..e82f7e1 100644
--- a/drivers/hv/vmbus_drv.c
+++ b/drivers/hv/vmbus_drv.c
@@ -42,6 +42,7 @@
 #include <linux/screen_info.h>
 #include <linux/kdebug.h>
 #include <linux/efi.h>
+#include <linux/random.h>
 #include "hyperv_vmbus.h"
 
 static struct acpi_device  *hv_acpi_dev;
@@ -806,6 +807,8 @@ static void vmbus_isr(void)
 		else
 			tasklet_schedule(hv_context.msg_dpc[cpu]);
 	}
+
+	add_interrupt_randomness(HYPERVISOR_CALLBACK_VECTOR, 0);
 }
 
 
-- 
2.7.2

Re: [PATCH v4 0/5] /dev/random - a new approach

[George Spelvin]

I'll be a while going through this.

I was thinking about our earlier discussion where I was hammering on
the point that compressing entropy too early is a mistake, and just
now realized that I should have given you credit for my recent 4.7-rc1
patch 2a18da7a.  The hash function ("good, fast AND cheap!") introduced
there exploits that point: using a larger hash state (and postponing
compression to the final size) dramatically reduces the requirements on
the hash mixing function.

I wasn't conscious of it at the time, but I just now realized that
explaining it clarified the point in my mind, which led to applying
the principle in other situations.

So thank you!

Re: [PATCH v4 0/5] /dev/random - a new approach

[David Jaša]

Hello Stephan,

Did you consider blocking urandom output or returning error until
initialized? Given the speed of initialization you report, it shouldn't
break any userspace apps while making sure that nobody uses predictable
pseudoranom numbers.

I was considering asking for patch (or even trying to write it myself)
to make current urandom block/fail when not initialized but that would
surely have to be off by default over "never break userspace" rule (even
if it means way too easy security problem with both random and urandom).
Properties of your urandom implementation makes this point moot and it
could make the random/urandom wars over.

Best Regards,

David Jaša

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Mittwoch, 15. Juni 2016, 18:17:43 schrieb David Jaša:

Hi David,

> Hello Stephan,
> 
> Did you consider blocking urandom output or returning error until
> initialized? Given the speed of initialization you report, it shouldn't
> break any userspace apps while making sure that nobody uses predictable
> pseudoranom numbers.

My LRNG will definitely touch the beginning of the initramfs booting until it 
is fully seeded. As these days the initramfs is driven by systemd which always 
pulls from /dev/urandom, we cannot block as this would block systemd. In Ted's 
last patch, he mentioned that he tried to make /dev/urandom block which caused 
user space pain.

But if you use the getrandom system call, it works like /dev/urandom but 
blocks until the DRBG behind /dev/urandom is fully initialized.
> 
> I was considering asking for patch (or even trying to write it myself)
> to make current urandom block/fail when not initialized but that would
> surely have to be off by default over "never break userspace" rule (even
> if it means way too easy security problem with both random and urandom).
> Properties of your urandom implementation makes this point moot and it
> could make the random/urandom wars over.

That patch unfortunately will not work. But if you are interested in that 
blocking /dev/urandom behavior for your application, use getrandom.

> 
> Best Regards,
> 
> David Jaša


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[David Jaša]

Hi Stephan,

thank you for your thorough reply,

On St, 2016-06-15 at 18:58 +0200, Stephan Mueller wrote:
> Am Mittwoch, 15. Juni 2016, 18:17:43 schrieb David Jaša:
> 
> Hi David,
> 
> > Hello Stephan,
> > 
> > Did you consider blocking urandom output or returning error until
> > initialized? Given the speed of initialization you report, it shouldn't
> > break any userspace apps while making sure that nobody uses predictable
> > pseudoranom numbers.
> 
> My LRNG will definitely touch the beginning of the initramfs booting until it 
> is fully seeded. As these days the initramfs is driven by systemd which always 
> pulls from /dev/urandom, we cannot block as this would block systemd. In Ted's 
> last patch, he mentioned that he tried to make /dev/urandom block which caused 
> user space pain.

I was thinking along the lines that "almost every important package
supports FreeBSD as well where they have to handle the condition so
option to switch to Rather Break Than Generate Weak Keys would be nice"
- but I didn't expect that systemd could be a roadblock here. :-/

I was also thinking of little devices where OpenWRT or proprietary
Linux-based systems run that ended up with predictable keys way too
ofter (or as in OpenWRT's case, with cumbersome tutorials how to
generate keys elsewhere).

> 
> But if you use the getrandom system call, it works like /dev/urandom but 
> blocks until the DRBG behind /dev/urandom is fully initialized.
> > 
> > I was considering asking for patch (or even trying to write it myself)
> > to make current urandom block/fail when not initialized but that would
> > surely have to be off by default over "never break userspace" rule (even
> > if it means way too easy security problem with both random and urandom).
> > Properties of your urandom implementation makes this point moot and it
> > could make the random/urandom wars over.
> 
> That patch unfortunately will not work. But if you are interested in that 
> blocking /dev/urandom behavior for your application, use getrandom.
> 

I'm QA with a touch of sysadmin so the numbers of apps to fix is large
and I don't have neither control over the projects nor abilities to
patch them all myself. :)

> > 
> > Best Regards,
> > 
> > David Jaša
> 
> 
> Ciao
> Stephan

BTW when looking at an old BSI's issue with Linux urandom that Jarod
Wilson tried to solve with this series:
https://www.spinics.net/lists/linux-crypto/msg06113.html
I was thinking:
1) wouldn't it help for large urandom consumers if kernel created a DRBG
instance for each of them? It would likely enhance performance and solve
BSI's concern of predicting what numbers could other urandom consumers
obtain at cost of memory footprint
and then, after reading paper associated with this series:
2) did you evaluate use of intermediate DRBG fed by primary generator to
instantiate per-node DRBG's? It would allow initialization of all
secondary DRBGs right after primary generator initialization.

Cheers,

David

Re: [PATCH v4 0/5] /dev/random - a new approach

[Sandy Harris]

David Jaša <djasa@redhat.com> wrote:

>
> BTW when looking at an old BSI's issue with Linux urandom that Jarod
> Wilson tried to solve with this series:
> https://www.spinics.net/lists/linux-crypto/msg06113.html
> I was thinking:
> 1) wouldn't it help for large urandom consumers if kernel created a DRBG
> instance for each of them? It would likely enhance performance and solve
> BSI's concern of predicting what numbers could other urandom consumers
> obtain at cost of memory footprint
> and then, after reading paper associated with this series:
> 2) did you evaluate use of intermediate DRBG fed by primary generator to
> instantiate per-node DRBG's? It would allow initialization of all
> secondary DRBGs right after primary generator initialization.

Theodore Ts'o, the random maintainer, already has a patch that
seems to deal with this issue. He has posted more than one
version & I'm not sure this is the best or latest, but ...
https://lkml.org/lkml/2016/5/30/22

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Freitag, 17. Juni 2016, 11:26:23 schrieb Sandy Harris:

Hi Sandy,

> David Jaša <djasa@redhat.com> wrote:
> > BTW when looking at an old BSI's issue with Linux urandom that Jarod
> > Wilson tried to solve with this series:
> > https://www.spinics.net/lists/linux-crypto/msg06113.html
> > I was thinking:
> > 1) wouldn't it help for large urandom consumers if kernel created a DRBG
> > instance for each of them? It would likely enhance performance and solve
> > BSI's concern of predicting what numbers could other urandom consumers
> > obtain at cost of memory footprint
> > and then, after reading paper associated with this series:
> > 2) did you evaluate use of intermediate DRBG fed by primary generator to
> > instantiate per-node DRBG's? It would allow initialization of all
> > secondary DRBGs right after primary generator initialization.
> 
> Theodore Ts'o, the random maintainer, already has a patch that
> seems to deal with this issue. He has posted more than one
> version & I'm not sure this is the best or latest, but ...
> https://lkml.org/lkml/2016/5/30/22

His latest patch set that he mentioned to appear in 4.8 covers a per-NUMA DRNG 
where there is a "primary" /dev/urandom DRNG where secondary DRNGs for the 
NUMA nodes are spawned from.


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Freitag, 17. Juni 2016, 15:56:13 schrieb David Jaša:

Hi David,

> Hi Stephan,
> 
> thank you for your thorough reply,
> 
> On St, 2016-06-15 at 18:58 +0200, Stephan Mueller wrote:
> > Am Mittwoch, 15. Juni 2016, 18:17:43 schrieb David Jaša:
> > 
> > Hi David,
> > 
> > > Hello Stephan,
> > > 
> > > Did you consider blocking urandom output or returning error until
> > > initialized? Given the speed of initialization you report, it shouldn't
> > > break any userspace apps while making sure that nobody uses predictable
> > > pseudoranom numbers.
> > 
> > My LRNG will definitely touch the beginning of the initramfs booting until
> > it is fully seeded. As these days the initramfs is driven by systemd
> > which always pulls from /dev/urandom, we cannot block as this would block
> > systemd. In Ted's last patch, he mentioned that he tried to make
> > /dev/urandom block which caused user space pain.
> 
> I was thinking along the lines that "almost every important package
> supports FreeBSD as well where they have to handle the condition so
> option to switch to Rather Break Than Generate Weak Keys would be nice"
> - but I didn't expect that systemd could be a roadblock here. :-/
> 
> I was also thinking of little devices where OpenWRT or proprietary
> Linux-based systems run that ended up with predictable keys way too
> ofter (or as in OpenWRT's case, with cumbersome tutorials how to
> generate keys elsewhere).

I have some ideas on how to handle that issue -- let me run some tests and I 
will report back.
> 
> > But if you use the getrandom system call, it works like /dev/urandom but
> > blocks until the DRBG behind /dev/urandom is fully initialized.
> > 
> > > I was considering asking for patch (or even trying to write it myself)
> > > to make current urandom block/fail when not initialized but that would
> > > surely have to be off by default over "never break userspace" rule (even
> > > if it means way too easy security problem with both random and urandom).
> > > Properties of your urandom implementation makes this point moot and it
> > > could make the random/urandom wars over.
> > 
> > That patch unfortunately will not work. But if you are interested in that
> > blocking /dev/urandom behavior for your application, use getrandom.
> 
> I'm QA with a touch of sysadmin so the numbers of apps to fix is large
> and I don't have neither control over the projects nor abilities to
> patch them all myself. :)

Sure, I can understand that :-)
> 
> > > Best Regards,
> > > 
> > > David Jaša
> > 
> > Ciao
> > Stephan
> 
> BTW when looking at an old BSI's issue with Linux urandom that Jarod
> Wilson tried to solve with this series:
> https://www.spinics.net/lists/linux-crypto/msg06113.html
> I was thinking:
> 1) wouldn't it help for large urandom consumers if kernel created a DRBG
> instance for each of them? It would likely enhance performance and solve
> BSI's concern of predicting what numbers could other urandom consumers
> obtain at cost of memory footprint

That issue is partly solved with my patch set: I have one DRBG per NUMA node 
where all DRBG instances are equally treated. Surely that patch could be 
expanded on a per-CPU instance. But let us try to use the per-NUMA 
implementation and see whether that helps.

Besides, the legacy /dev/urandom delivers about 12 MB/s on my system whereas 
the DRBG delivers more than 800MB/s. So, we have quite some performance 
improvement.

Note, Ted's patch has a similar implementation.

> and then, after reading paper associated with this series:
> 2) did you evaluate use of intermediate DRBG fed by primary generator to
> instantiate per-node DRBG's? It would allow initialization of all
> secondary DRBGs right after primary generator initialization.

That is exactly what I do.
> 
> Cheers,
> 
> David


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Theodore Ts'o]

On Fri, Jun 17, 2016 at 03:56:13PM +0200, David Jaša wrote:
> I was thinking along the lines that "almost every important package
> supports FreeBSD as well where they have to handle the condition so
> option to switch to Rather Break Than Generate Weak Keys would be nice"
> - but I didn't expect that systemd could be a roadblock here. :-/

It wasn't just systemd; it also broke OpenWRT and Ubuntu Quantal
systems from booting.

> I was also thinking of little devices where OpenWRT or proprietary
> Linux-based systems run that ended up with predictable keys way too
> ofter (or as in OpenWRT's case, with cumbersome tutorials how to
> generate keys elsewhere).

OpenWRT and other embedded devices (a) generally use a single master
oscillator to drive everything, and (b) often use RISC architectures
such as MIPS.

Which means that arguments of the form ``the Intel L1 / L2 cache
architecture is ****soooo**** complicated that no human could possibly
figure out how they would affect timing calculations, and besides, my
generator passes FIPS 140-2 tests (never mind AES(NSA_KEY, CNTR++)
also passes the FIPS 140-2 statistical tests)'' --- which I normally
have trouble believing --- are even harder for me to believe.

At the end of the day, with these devices you really badly need a
hardware RNG.  We can't generate randomness out of thin air.  The only
thing you really can do requires user space help, which is to generate
keys lazily, or as late as possible, so you can gather as much entropy
as you can --- and to feed in measurements from the WiFi (RSSI
measurements, MAC addresses seen, etc.)  This won't help much if you
have an FBI van parked outside your house trying to carry out a
TEMPEST attack, but hopefully it provides some protection against a
remote attacker who isn't try to carry out an on-premises attack.

Cheers,

						- Ted

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:

Hi Theodore,

> 
> At the end of the day, with these devices you really badly need a
> hardware RNG.  We can't generate randomness out of thin air.  The only
> thing you really can do requires user space help, which is to generate
> keys lazily, or as late as possible, so you can gather as much entropy
> as you can --- and to feed in measurements from the WiFi (RSSI
> measurements, MAC addresses seen, etc.)  This won't help much if you
> have an FBI van parked outside your house trying to carry out a
> TEMPEST attack, but hopefully it provides some protection against a
> remote attacker who isn't try to carry out an on-premises attack.

All my measurements on such small systems like MIPS or smaller/older ARMs do 
not seem to support that statement :-)

Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-18 12:31, Stephan Mueller wrote:
> Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:
>
> Hi Theodore,
>
>>
>> At the end of the day, with these devices you really badly need a
>> hardware RNG.  We can't generate randomness out of thin air.  The only
>> thing you really can do requires user space help, which is to generate
>> keys lazily, or as late as possible, so you can gather as much entropy
>> as you can --- and to feed in measurements from the WiFi (RSSI
>> measurements, MAC addresses seen, etc.)  This won't help much if you
>> have an FBI van parked outside your house trying to carry out a
>> TEMPEST attack, but hopefully it provides some protection against a
>> remote attacker who isn't try to carry out an on-premises attack.
>
> All my measurements on such small systems like MIPS or smaller/older ARMs do
> not seem to support that statement :-)
Was this on real hardware, or in a virtual machine/emulator?  Because if 
it's not on real hardware, you're harvesting entropy from the host 
system, not the emulated one.  While I haven't done this with MIPS or 
ARM systems, I've taken similar measurements on SPARC64, x86_64, and 
PPC64 systems comparing real hardware and emulated hardware, and the 
emulated hardware _always_ has higher entropy, even when running the 
emulator on an identical CPU to the one being emulated and using KVM 
acceleration and passing through all the devices possible.

Even if you were testing on real hardware, I'm still rather dubious, as 
every single test I've ever done on any hardware (SPARC, PPC, x86, ARM, 
and even PA-RISC) indicates that you can't harvest entropy as 
effectively from a smaller CPU compared to a large one, and this effect 
is significantly more pronounced on RISC systems.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Montag, 20. Juni 2016, 13:07:32 schrieb Austin S. Hemmelgarn:

Hi Austin,

> On 2016-06-18 12:31, Stephan Mueller wrote:
> > Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:
> > 
> > Hi Theodore,
> > 
> >> At the end of the day, with these devices you really badly need a
> >> hardware RNG.  We can't generate randomness out of thin air.  The only
> >> thing you really can do requires user space help, which is to generate
> >> keys lazily, or as late as possible, so you can gather as much entropy
> >> as you can --- and to feed in measurements from the WiFi (RSSI
> >> measurements, MAC addresses seen, etc.)  This won't help much if you
> >> have an FBI van parked outside your house trying to carry out a
> >> TEMPEST attack, but hopefully it provides some protection against a
> >> remote attacker who isn't try to carry out an on-premises attack.
> > 
> > All my measurements on such small systems like MIPS or smaller/older ARMs
> > do not seem to support that statement :-)
> 
> Was this on real hardware, or in a virtual machine/emulator?  Because if
> it's not on real hardware, you're harvesting entropy from the host
> system, not the emulated one.  While I haven't done this with MIPS or
> ARM systems, I've taken similar measurements on SPARC64, x86_64, and
> PPC64 systems comparing real hardware and emulated hardware, and the
> emulated hardware _always_ has higher entropy, even when running the
> emulator on an identical CPU to the one being emulated and using KVM
> acceleration and passing through all the devices possible.
> 
> Even if you were testing on real hardware, I'm still rather dubious, as
> every single test I've ever done on any hardware (SPARC, PPC, x86, ARM,
> and even PA-RISC) indicates that you can't harvest entropy as
> effectively from a smaller CPU compared to a large one, and this effect
> is significantly more pronounced on RISC systems.

It was on real hardware. As part of my Jitter RNG project, I tested all major 
CPUs from small to big -- see Appendix F [1]. For MIPS/ARM, see the trailing 
part of the big table.

[1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf

Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-20 14:32, Stephan Mueller wrote:
> Am Montag, 20. Juni 2016, 13:07:32 schrieb Austin S. Hemmelgarn:
>
> Hi Austin,
>
>> On 2016-06-18 12:31, Stephan Mueller wrote:
>>> Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:
>>>
>>> Hi Theodore,
>>>
>>>> At the end of the day, with these devices you really badly need a
>>>> hardware RNG.  We can't generate randomness out of thin air.  The only
>>>> thing you really can do requires user space help, which is to generate
>>>> keys lazily, or as late as possible, so you can gather as much entropy
>>>> as you can --- and to feed in measurements from the WiFi (RSSI
>>>> measurements, MAC addresses seen, etc.)  This won't help much if you
>>>> have an FBI van parked outside your house trying to carry out a
>>>> TEMPEST attack, but hopefully it provides some protection against a
>>>> remote attacker who isn't try to carry out an on-premises attack.
>>>
>>> All my measurements on such small systems like MIPS or smaller/older ARMs
>>> do not seem to support that statement :-)
>>
>> Was this on real hardware, or in a virtual machine/emulator?  Because if
>> it's not on real hardware, you're harvesting entropy from the host
>> system, not the emulated one.  While I haven't done this with MIPS or
>> ARM systems, I've taken similar measurements on SPARC64, x86_64, and
>> PPC64 systems comparing real hardware and emulated hardware, and the
>> emulated hardware _always_ has higher entropy, even when running the
>> emulator on an identical CPU to the one being emulated and using KVM
>> acceleration and passing through all the devices possible.
>>
>> Even if you were testing on real hardware, I'm still rather dubious, as
>> every single test I've ever done on any hardware (SPARC, PPC, x86, ARM,
>> and even PA-RISC) indicates that you can't harvest entropy as
>> effectively from a smaller CPU compared to a large one, and this effect
>> is significantly more pronounced on RISC systems.
>
> It was on real hardware. As part of my Jitter RNG project, I tested all major
> CPUs from small to big -- see Appendix F [1]. For MIPS/ARM, see the trailing
> part of the big table.
>
> [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf

Specific things I notice about this:
1. QEMU systems are reporting higher values than almost anything else 
with the same ISA.  This makes sense, but you don't appear to have 
accounted for the fact that you can't trust almost any of the entropy in 
a VM unless you have absolute trust in the host system, because the host 
system can do whatever the hell it wants to you, including manipulating 
timings directly (with a little patience and some time spent working on 
it, you could probably get those number to show whatever you want just 
by manipulating scheduling parameters on the host OS for the VM software).
2. Quite a few systems have a rather distressingly low lower bound and 
still get accepted by your algorithm (a number of the S/390 systems, and 
a handful of the AMD processors in particular).
3. Your statement at the bottom of the table that 'all test systems at 
least un-optimized have a lower bound of 1 bit' is refuted by your own 
data, I count at least 2 data points where this is not the case.  One of 
them is mentioned at the bottom as an outlier, and you have data to back 
this up listed in the table, but the other (MIPS 4Kec v4.8) is the only 
system of that specific type that you tested, and thus can't be claimed 
as an outlier.
4. You state the S/390 systems gave different results when run 
un-optimized, but don't provide any data regarding this.
5. You discount the Pentium Celeron Mobile CPU as old and therefore not 
worth worrying about.  Linux still runs on 80486 and other 'ancient' 
systems, and there are people using it on such systems.  You need to 
account for this usage.
6. You have a significant lack of data regarding embedded systems, which 
is one of the two biggest segments of Linux's market share.  You list no 
results for any pre-ARMv6 systems (Linux still runs on and is regularly 
used on ARMv4 CPU's, and it's worth also pointing out that the values on 
the ARMv6 systems are themselves below average), any MIPS systems other 
than 24k and 4k (which is not a good representation of modern embedded 
usage), any SPARC CPU's other than UltraSPARC (ideally you should have 
results on at least a couple of LEON systems as well), no tight-embedded 
PPC chips (PPC 440 processors are very widely used, as are the 7xx and 
970 families, and Freescale's e series), and only one set of results for 
a tight-embedded x86 CPU (the Via Nano, you should ideally also have 
results on things like an Intel Quark).  Overall, your test system 
selection is not entirely representative of actual Linux usage (yeah, 
ther'es a lot of x86 servers out there running Linux, there's at least 
as many embedded systems running it too though, even without including 
Android).
7. The RISC CPU's that you actually tested have more consistency within 
a particular type than the CISC CPU's.  Many of them do have higher 
values than the CISC CPU's, but a majority of the ones I see listed 
which have such high values are either old systems not designed for low 
latency, or relatively big SMP systems (which will have higher entropy 
because of larger numbers of IRQ's, as well as other factors).

Re: [PATCH v4 0/5] /dev/random - a new approach

[Tomas Mraz]

On Út, 2016-06-21 at 09:05 -0400, Austin S. Hemmelgarn wrote:
> On 2016-06-20 14:32, Stephan Mueller wrote:
> > 
> > [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf
> Specific things I notice about this:
> 1. QEMU systems are reporting higher values than almost anything
> else 
> with the same ISA.  This makes sense, but you don't appear to have 
> accounted for the fact that you can't trust almost any of the entropy
> in 
> a VM unless you have absolute trust in the host system, because the
> host 
> system can do whatever the hell it wants to you, including
> manipulating 
> timings directly (with a little patience and some time spent working
> on 
> it, you could probably get those number to show whatever you want
> just 
> by manipulating scheduling parameters on the host OS for the VM
> software).

You have to trust the host for anything, not just for the entropy in
timings. This is completely invalid argument unless you can present a
method that one guest can manipulate timings in other guest in such a
way that _removes_ the inherent entropy from the host.

-- 
Tomas Mraz
No matter how far down the wrong road you've gone, turn back.
                                              Turkish proverb
(You'll never know whether the road is wrong though.)

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 09:19, Tomas Mraz wrote:
> On Út, 2016-06-21 at 09:05 -0400, Austin S. Hemmelgarn wrote:
>> On 2016-06-20 14:32, Stephan Mueller wrote:
>>>
>>> [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf
>> Specific things I notice about this:
>> 1. QEMU systems are reporting higher values than almost anything
>> else
>> with the same ISA.  This makes sense, but you don't appear to have
>> accounted for the fact that you can't trust almost any of the entropy
>> in
>> a VM unless you have absolute trust in the host system, because the
>> host
>> system can do whatever the hell it wants to you, including
>> manipulating
>> timings directly (with a little patience and some time spent working
>> on
>> it, you could probably get those number to show whatever you want
>> just
>> by manipulating scheduling parameters on the host OS for the VM
>> software).
>
> You have to trust the host for anything, not just for the entropy in
> timings. This is completely invalid argument unless you can present a
> method that one guest can manipulate timings in other guest in such a
> way that _removes_ the inherent entropy from the host.
When dealing with almost any type 2 hypervisor, it is fully possible for 
a user other than the one running the hypervisor to manipulate 
scheduling such that entropy is reduced.  This does not imply that the 
user who is doing this has any other control over the target VM, and 
importantly, often does not require administrative access on the host, 
only regular user access.  Such an attack is very difficult to effect 
outside of a clean-room environment, but is still possible.  You can't 
use this to force generation of arbitrary data, but you can definitely 
starve a VM for entropy.  By nature, something that relies on interrupt 
timings will be more impacted by such an attack than something that does 
not.

In most cases, such an attack will be a DoS attack on the host as well 
(as that's the simplest way to do this).  This is less of an issue with 
proper practices on a type 1 hypervisor, but is still possible there too 
(although pulling this off on at least Xen when you have proper VCPU 
isolation is functionally impossible without administrative access to 
the control domain).

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 13:18:33 schrieb Austin S. Hemmelgarn:

Hi Austin,

> > You have to trust the host for anything, not just for the entropy in
> > timings. This is completely invalid argument unless you can present a
> > method that one guest can manipulate timings in other guest in such a
> > way that _removes_ the inherent entropy from the host.
> 
> When dealing with almost any type 2 hypervisor, it is fully possible for
> a user other than the one running the hypervisor to manipulate
> scheduling such that entropy is reduced.  This does not imply that the

Please re-read the document: Jitter RNG does not rest on scheduling.


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 13:23, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 13:18:33 schrieb Austin S. Hemmelgarn:
>
> Hi Austin,
>
>>> You have to trust the host for anything, not just for the entropy in
>>> timings. This is completely invalid argument unless you can present a
>>> method that one guest can manipulate timings in other guest in such a
>>> way that _removes_ the inherent entropy from the host.
>>
>> When dealing with almost any type 2 hypervisor, it is fully possible for
>> a user other than the one running the hypervisor to manipulate
>> scheduling such that entropy is reduced.  This does not imply that the
>
> Please re-read the document: Jitter RNG does not rest on scheduling.
If you are running inside a VM, your interrupt timings depend on the 
hpyervisor's scheduling, period.  You may not directly rely on 
scheduling from the OS you are running on, but if you are doing anything 
timing related in a VM, you are at the mercy of the scheduling used by 
the hypervisor and whatever host OS that may be running on.

In the attack I"m describing, the malicious user is not manipulating the 
guest OS's scheduling, they are manipulating the host system's scheduling.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 13:54:13 schrieb Austin S. Hemmelgarn:

Hi Austin,

> On 2016-06-21 13:23, Stephan Mueller wrote:
> > Am Dienstag, 21. Juni 2016, 13:18:33 schrieb Austin S. Hemmelgarn:
> > 
> > Hi Austin,
> > 
> >>> You have to trust the host for anything, not just for the entropy in
> >>> timings. This is completely invalid argument unless you can present a
> >>> method that one guest can manipulate timings in other guest in such a
> >>> way that _removes_ the inherent entropy from the host.
> >> 
> >> When dealing with almost any type 2 hypervisor, it is fully possible for
> >> a user other than the one running the hypervisor to manipulate
> >> scheduling such that entropy is reduced.  This does not imply that the
> > 
> > Please re-read the document: Jitter RNG does not rest on scheduling.
> 
> If you are running inside a VM, your interrupt timings depend on the

The RNG does not rest on interrupts either.

> hpyervisor's scheduling, period.  You may not directly rely on
> scheduling from the OS you are running on, but if you are doing anything
> timing related in a VM, you are at the mercy of the scheduling used by
> the hypervisor and whatever host OS that may be running on.
> 
> In the attack I"m describing, the malicious user is not manipulating the
> guest OS's scheduling, they are manipulating the host system's scheduling.


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 09:05:55 schrieb Austin S. Hemmelgarn:

Hi Austin,

> On 2016-06-20 14:32, Stephan Mueller wrote:
> > Am Montag, 20. Juni 2016, 13:07:32 schrieb Austin S. Hemmelgarn:
> > 
> > Hi Austin,
> > 
> >> On 2016-06-18 12:31, Stephan Mueller wrote:
> >>> Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:
> >>> 
> >>> Hi Theodore,
> >>> 
> >>>> At the end of the day, with these devices you really badly need a
> >>>> hardware RNG.  We can't generate randomness out of thin air.  The only
> >>>> thing you really can do requires user space help, which is to generate
> >>>> keys lazily, or as late as possible, so you can gather as much entropy
> >>>> as you can --- and to feed in measurements from the WiFi (RSSI
> >>>> measurements, MAC addresses seen, etc.)  This won't help much if you
> >>>> have an FBI van parked outside your house trying to carry out a
> >>>> TEMPEST attack, but hopefully it provides some protection against a
> >>>> remote attacker who isn't try to carry out an on-premises attack.
> >>> 
> >>> All my measurements on such small systems like MIPS or smaller/older
> >>> ARMs
> >>> do not seem to support that statement :-)
> >> 
> >> Was this on real hardware, or in a virtual machine/emulator?  Because if
> >> it's not on real hardware, you're harvesting entropy from the host
> >> system, not the emulated one.  While I haven't done this with MIPS or
> >> ARM systems, I've taken similar measurements on SPARC64, x86_64, and
> >> PPC64 systems comparing real hardware and emulated hardware, and the
> >> emulated hardware _always_ has higher entropy, even when running the
> >> emulator on an identical CPU to the one being emulated and using KVM
> >> acceleration and passing through all the devices possible.
> >> 
> >> Even if you were testing on real hardware, I'm still rather dubious, as
> >> every single test I've ever done on any hardware (SPARC, PPC, x86, ARM,
> >> and even PA-RISC) indicates that you can't harvest entropy as
> >> effectively from a smaller CPU compared to a large one, and this effect
> >> is significantly more pronounced on RISC systems.
> > 
> > It was on real hardware. As part of my Jitter RNG project, I tested all
> > major CPUs from small to big -- see Appendix F [1]. For MIPS/ARM, see the
> > trailing part of the big table.
> > 
> > [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf
> 
> Specific things I notice about this:
> 1. QEMU systems are reporting higher values than almost anything else
> with the same ISA.  This makes sense, but you don't appear to have
> accounted for the fact that you can't trust almost any of the entropy in
> a VM unless you have absolute trust in the host system, because the host
> system can do whatever the hell it wants to you, including manipulating
> timings directly (with a little patience and some time spent working on
> it, you could probably get those number to show whatever you want just
> by manipulating scheduling parameters on the host OS for the VM software).

I am not sure where you see QEMU systems listed there.

> 2. Quite a few systems have a rather distressingly low lower bound and
> still get accepted by your algorithm (a number of the S/390 systems, and
> a handful of the AMD processors in particular).

I am aware of that, but please read the entire documentation where the lower 
and upper boundary comes from and how the Jitter RNG really operates. There 
you will see that the lower boundary is just that: it will not be lower, but 
the common case is the upper boundary.

Furthermore, the use case of the Jitter RNG is to support the DRBG seeding 
with a very high reseed interval.

> 3. Your statement at the bottom of the table that 'all test systems at
> least un-optimized have a lower bound of 1 bit' is refuted by your own
> data, I count at least 2 data points where this is not the case.  One of
> them is mentioned at the bottom as an outlier, and you have data to back
> this up listed in the table, but the other (MIPS 4Kec v4.8) is the only
> system of that specific type that you tested, and thus can't be claimed
> as an outlier.

You are right, I have added more and more test results to the table without 
updating the statement below. I will fix that.

But note, that there is a list below that statement providing explanations 
already. So, it is just that one statement that needs updating.

> 4. You state the S/390 systems gave different results when run
> un-optimized, but don't provide any data regarding this.

The pointer to appendix F.46 was supposed to cover that issue.

> 5. You discount the Pentium Celeron Mobile CPU as old and therefore not
> worth worrying about.  Linux still runs on 80486 and other 'ancient'
> systems, and there are people using it on such systems.  You need to
> account for this usage.

I do not account for that in the documentation. In real life though, I 
certainly do -- see how the Jitter RNG is used in the kernel.

> 6. You have a significant lack of data regarding embedded systems, which
> is one of the two biggest segments of Linux's market share.  You list no
> results for any pre-ARMv6 systems (Linux still runs on and is regularly
> used on ARMv4 CPU's, and it's worth also pointing out that the values on
> the ARMv6 systems are themselves below average), any MIPS systems other
> than 24k and 4k (which is not a good representation of modern embedded
> usage), any SPARC CPU's other than UltraSPARC (ideally you should have
> results on at least a couple of LEON systems as well), no tight-embedded
> PPC chips (PPC 440 processors are very widely used, as are the 7xx and
> 970 families, and Freescale's e series), and only one set of results for
> a tight-embedded x86 CPU (the Via Nano, you should ideally also have
> results on things like an Intel Quark).  Overall, your test system
> selection is not entirely representative of actual Linux usage (yeah,
> ther'es a lot of x86 servers out there running Linux, there's at least
> as many embedded systems running it too though, even without including
> Android).

Perfectly valid argument. But I programmed that RNG as a hobby -- I do not 
have the funds to buy all devices there are.

And http://www.chronox.de/jent.html asks for help -- if you have those 
devices, please help and simply execute one application and return the data to 
me.

> 7. The RISC CPU's that you actually tested have more consistency within
> a particular type than the CISC CPU's.  Many of them do have higher
> values than the CISC CPU's, but a majority of the ones I see listed
> which have such high values are either old systems not designed for low
> latency, or relatively big SMP systems (which will have higher entropy
> because of larger numbers of IRQ's, as well as other factors).

Ok, run the tests on the systems you like and return the results to me.


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 09:20, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 09:05:55 schrieb Austin S. Hemmelgarn:
>
> Hi Austin,
>
>> On 2016-06-20 14:32, Stephan Mueller wrote:
>>> Am Montag, 20. Juni 2016, 13:07:32 schrieb Austin S. Hemmelgarn:
>>>
>>> Hi Austin,
>>>
>>>> On 2016-06-18 12:31, Stephan Mueller wrote:
>>>>> Am Samstag, 18. Juni 2016, 10:44:08 schrieb Theodore Ts'o:
>>>>>
>>>>> Hi Theodore,
>>>>>
>>>>>> At the end of the day, with these devices you really badly need a
>>>>>> hardware RNG.  We can't generate randomness out of thin air.  The only
>>>>>> thing you really can do requires user space help, which is to generate
>>>>>> keys lazily, or as late as possible, so you can gather as much entropy
>>>>>> as you can --- and to feed in measurements from the WiFi (RSSI
>>>>>> measurements, MAC addresses seen, etc.)  This won't help much if you
>>>>>> have an FBI van parked outside your house trying to carry out a
>>>>>> TEMPEST attack, but hopefully it provides some protection against a
>>>>>> remote attacker who isn't try to carry out an on-premises attack.
>>>>>
>>>>> All my measurements on such small systems like MIPS or smaller/older
>>>>> ARMs
>>>>> do not seem to support that statement :-)
>>>>
>>>> Was this on real hardware, or in a virtual machine/emulator?  Because if
>>>> it's not on real hardware, you're harvesting entropy from the host
>>>> system, not the emulated one.  While I haven't done this with MIPS or
>>>> ARM systems, I've taken similar measurements on SPARC64, x86_64, and
>>>> PPC64 systems comparing real hardware and emulated hardware, and the
>>>> emulated hardware _always_ has higher entropy, even when running the
>>>> emulator on an identical CPU to the one being emulated and using KVM
>>>> acceleration and passing through all the devices possible.
>>>>
>>>> Even if you were testing on real hardware, I'm still rather dubious, as
>>>> every single test I've ever done on any hardware (SPARC, PPC, x86, ARM,
>>>> and even PA-RISC) indicates that you can't harvest entropy as
>>>> effectively from a smaller CPU compared to a large one, and this effect
>>>> is significantly more pronounced on RISC systems.
>>>
>>> It was on real hardware. As part of my Jitter RNG project, I tested all
>>> major CPUs from small to big -- see Appendix F [1]. For MIPS/ARM, see the
>>> trailing part of the big table.
>>>
>>> [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf
>>
>> Specific things I notice about this:
>> 1. QEMU systems are reporting higher values than almost anything else
>> with the same ISA.  This makes sense, but you don't appear to have
>> accounted for the fact that you can't trust almost any of the entropy in
>> a VM unless you have absolute trust in the host system, because the host
>> system can do whatever the hell it wants to you, including manipulating
>> timings directly (with a little patience and some time spent working on
>> it, you could probably get those number to show whatever you want just
>> by manipulating scheduling parameters on the host OS for the VM software).
>
> I am not sure where you see QEMU systems listed there.
That would be the ones which list 'QEMU Virtual CPU version X.Y' as the 
CPU string.  The only things that return that in the CPUID data are 
either QEMU itself, or software that is based on QEMU.
>
>> 2. Quite a few systems have a rather distressingly low lower bound and
>> still get accepted by your algorithm (a number of the S/390 systems, and
>> a handful of the AMD processors in particular).
>
> I am aware of that, but please read the entire documentation where the lower
> and upper boundary comes from and how the Jitter RNG really operates. There
> you will see that the lower boundary is just that: it will not be lower, but
> the common case is the upper boundary.
Talking about the common case is all well and good, but the lower bound 
still needs to be taken into account.  If the test results aren't 
uniformly distributed within that interval, or even following a typical 
Gaussian distribution within it (which is what I and many other people 
would probably assume without the data later in the appendix), then you 
really need to mention this _before_ the table itself.  Such information 
is very important, and not everyone has time to read everything.
>
> Furthermore, the use case of the Jitter RNG is to support the DRBG seeding
> with a very high reseed interval.
>
>> 3. Your statement at the bottom of the table that 'all test systems at
>> least un-optimized have a lower bound of 1 bit' is refuted by your own
>> data, I count at least 2 data points where this is not the case.  One of
>> them is mentioned at the bottom as an outlier, and you have data to back
>> this up listed in the table, but the other (MIPS 4Kec v4.8) is the only
>> system of that specific type that you tested, and thus can't be claimed
>> as an outlier.
>
> You are right, I have added more and more test results to the table without
> updating the statement below. I will fix that.
>
> But note, that there is a list below that statement providing explanations
> already. So, it is just that one statement that needs updating.
>
>> 4. You state the S/390 systems gave different results when run
>> un-optimized, but don't provide any data regarding this.
>
> The pointer to appendix F.46 was supposed to cover that issue.
Apologies for not reading that part thoroughly, you might want to add 
those results to the table too.
>
>> 5. You discount the Pentium Celeron Mobile CPU as old and therefore not
>> worth worrying about.  Linux still runs on 80486 and other 'ancient'
>> systems, and there are people using it on such systems.  You need to
>> account for this usage.
>
> I do not account for that in the documentation. In real life though, I
> certainly do -- see how the Jitter RNG is used in the kernel.
Then you shouldn't be pushing the documentation as what appears to be 
your sole argument for including it in the kernel.
>
>> 6. You have a significant lack of data regarding embedded systems, which
>> is one of the two biggest segments of Linux's market share.  You list no
>> results for any pre-ARMv6 systems (Linux still runs on and is regularly
>> used on ARMv4 CPU's, and it's worth also pointing out that the values on
>> the ARMv6 systems are themselves below average), any MIPS systems other
>> than 24k and 4k (which is not a good representation of modern embedded
>> usage), any SPARC CPU's other than UltraSPARC (ideally you should have
>> results on at least a couple of LEON systems as well), no tight-embedded
>> PPC chips (PPC 440 processors are very widely used, as are the 7xx and
>> 970 families, and Freescale's e series), and only one set of results for
>> a tight-embedded x86 CPU (the Via Nano, you should ideally also have
>> results on things like an Intel Quark).  Overall, your test system
>> selection is not entirely representative of actual Linux usage (yeah,
>> ther'es a lot of x86 servers out there running Linux, there's at least
>> as many embedded systems running it too though, even without including
>> Android).
>
> Perfectly valid argument. But I programmed that RNG as a hobby -- I do not
> have the funds to buy all devices there are.
I'm not complaining as much about the lack of data for such devices as I 
am about you stating that it will work fine for such devices when you 
have so little data to support those claims.  Many of the devices you 
have listed that can be reasonably assumed to be embedded systems are 
relatively modern ones that most people would think of (smart-phones and 
similar).  Such systems have almost as much if not more interrupts as 
many desktop and server systems, so the entropy values there actually do 
make some sense.  Not everything has this luxury.  Think for example of 
a router.  All it will generally have interrupts from is the timer 
interrupt (which should functionally have near zero entropy because it's 
monotonic most of the time) and the networking hardware, and quite 
often, many of the good routers operate their NIC's in polling mode, 
which means very few interrupts (which indirectly is part of the issue 
with some server systems too), and therefore will have little to no 
entropy there either.  This is an issue with the current system too, but 
you have almost zero data on such systems systems yourself, so you can't 
argue that it makes things better for them.
>
> And http://www.chronox.de/jent.html asks for help -- if you have those
> devices, please help and simply execute one application and return the data to
> me.
>
>> 7. The RISC CPU's that you actually tested have more consistency within
>> a particular type than the CISC CPU's.  Many of them do have higher
>> values than the CISC CPU's, but a majority of the ones I see listed
>> which have such high values are either old systems not designed for low
>> latency, or relatively big SMP systems (which will have higher entropy
>> because of larger numbers of IRQ's, as well as other factors).
>
> Ok, run the tests on the systems you like and return the results to me.
I would love to, but sadly the only system I have that isn't an x86 box 
that actually boots at all right now is an almost 2 decade old PA-RISC 
box that barely runs Linux, and the number of people who would be 
interested in the results from that can probably be counted on one hand.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 13:51:15 schrieb Austin S. Hemmelgarn:

Hi Austin,

> 
> >> 2. Quite a few systems have a rather distressingly low lower bound and
> >> still get accepted by your algorithm (a number of the S/390 systems, and
> >> a handful of the AMD processors in particular).
> > 
> > I am aware of that, but please read the entire documentation where the
> > lower and upper boundary comes from and how the Jitter RNG really
> > operates. There you will see that the lower boundary is just that: it
> > will not be lower, but the common case is the upper boundary.
> 
> Talking about the common case is all well and good, but the lower bound
> still needs to be taken into account.  If the test results aren't
> uniformly distributed within that interval, or even following a typical
> Gaussian distribution within it (which is what I and many other people
> would probably assume without the data later in the appendix), then you
> really need to mention this _before_ the table itself.  Such information
> is very important, and not everyone has time to read everything.

Then read chapter 5 as mentioned above the table. What you read was an 
appendix that is supposed to supplement to that chapter and not a full-fledged 
documentation.

And quickly glancing over that table to make a judgment is not helpful for 
such topic.

> 
> >> 5. You discount the Pentium Celeron Mobile CPU as old and therefore not
> >> worth worrying about.  Linux still runs on 80486 and other 'ancient'
> >> systems, and there are people using it on such systems.  You need to
> >> account for this usage.
> > 
> > I do not account for that in the documentation. In real life though, I
> > certainly do -- see how the Jitter RNG is used in the kernel.
> 
> Then you shouldn't be pushing the documentation as what appears to be
> your sole argument for including it in the kernel.

I understand you read Appendix F -- but that document is 150+ pages in size 
with quite a bit of information and you judge it based on an appendix 
providing supplemental data?

Note, I pointed you to this appendix at the starting question where you wanted 
to see test results on execution timing variations on ARM and MIPS.
> 
> >> 6. You have a significant lack of data regarding embedded systems, which
> >> is one of the two biggest segments of Linux's market share.  You list no
> >> results for any pre-ARMv6 systems (Linux still runs on and is regularly
> >> used on ARMv4 CPU's, and it's worth also pointing out that the values on
> >> the ARMv6 systems are themselves below average), any MIPS systems other
> >> than 24k and 4k (which is not a good representation of modern embedded
> >> usage), any SPARC CPU's other than UltraSPARC (ideally you should have
> >> results on at least a couple of LEON systems as well), no tight-embedded
> >> PPC chips (PPC 440 processors are very widely used, as are the 7xx and
> >> 970 families, and Freescale's e series), and only one set of results for
> >> a tight-embedded x86 CPU (the Via Nano, you should ideally also have
> >> results on things like an Intel Quark).  Overall, your test system
> >> selection is not entirely representative of actual Linux usage (yeah,
> >> ther'es a lot of x86 servers out there running Linux, there's at least
> >> as many embedded systems running it too though, even without including
> >> Android).
> > 
> > Perfectly valid argument. But I programmed that RNG as a hobby -- I do not
> > have the funds to buy all devices there are.
> 
> I'm not complaining as much about the lack of data for such devices as I
> am about you stating that it will work fine for such devices when you
> have so little data to support those claims.  Many of the devices you

Little data, interesting statement for results on 200+ systems including all 
major CPU arches all showing information leading in the same directions.

> have listed that can be reasonably assumed to be embedded systems are
> relatively modern ones that most people would think of (smart-phones and
> similar).  Such systems have almost as much if not more interrupts as
> many desktop and server systems, so the entropy values there actually do

Please re-read the documentation: the testing and the test analysis remove 
outliers from interrupts and such to get a worst-case testing.

> make some sense.  Not everything has this luxury.  Think for example of
> a router.  All it will generally have interrupts from is the timer
> interrupt (which should functionally have near zero entropy because it's
> monotonic most of the time) and the networking hardware, and quite
> often, many of the good routers operate their NIC's in polling mode,
> which means very few interrupts (which indirectly is part of the issue
> with some server systems too), and therefore will have little to no
> entropy there either.  This is an issue with the current system too, but
> you have almost zero data on such systems systems yourself, so you can't
> argue that it makes things better for them.

It would be good to read the documentation in full -- the RNG does not rest on 
interrupts.

Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 14:04, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 13:51:15 schrieb Austin S. Hemmelgarn:
>>>> 6. You have a significant lack of data regarding embedded systems, which
>>>> is one of the two biggest segments of Linux's market share.  You list no
>>>> results for any pre-ARMv6 systems (Linux still runs on and is regularly
>>>> used on ARMv4 CPU's, and it's worth also pointing out that the values on
>>>> the ARMv6 systems are themselves below average), any MIPS systems other
>>>> than 24k and 4k (which is not a good representation of modern embedded
>>>> usage), any SPARC CPU's other than UltraSPARC (ideally you should have
>>>> results on at least a couple of LEON systems as well), no tight-embedded
>>>> PPC chips (PPC 440 processors are very widely used, as are the 7xx and
>>>> 970 families, and Freescale's e series), and only one set of results for
>>>> a tight-embedded x86 CPU (the Via Nano, you should ideally also have
>>>> results on things like an Intel Quark).  Overall, your test system
>>>> selection is not entirely representative of actual Linux usage (yeah,
>>>> ther'es a lot of x86 servers out there running Linux, there's at least
>>>> as many embedded systems running it too though, even without including
>>>> Android).
>>>
>>> Perfectly valid argument. But I programmed that RNG as a hobby -- I do not
>>> have the funds to buy all devices there are.
>>
>> I'm not complaining as much about the lack of data for such devices as I
>> am about you stating that it will work fine for such devices when you
>> have so little data to support those claims.  Many of the devices you
>
> Little data, interesting statement for results on 200+ systems including all
> major CPU arches all showing information leading in the same directions.

Let me try rephrasing this to make it a bit clearer:
1. You have lots of data on server systems.
2. You have a significant amount of data on desktop/workstation type 
systems.
3. You have very little data on embedded systems.

and here are your arguments:
A. This works well on server systems.
B. This works well on desktop systems.
C. This works well on embedded systems.

Arguments A and B are substantiated directly by points 1 and 2. 
Argument C is not substantiated thoroughly because of point 3.
My complaint is about argument C given point 3.

I'm not saying you have insufficient data to support argument A or B, 
only that you have insufficient data to support argument C.

Android barely counts as an embedded system anymore, as many Android 
phones can outperform most inexpensive desktop and laptop systems, and 
even some rather expensive laptops.  This leaves the only systems that 
can be assumed without further information to be representative of 
embedded boards to be the ones running Genode, and possibly the MIPS 
systems, which is a total of about 10 results out of hundreds for 
servers and desktops/workstations.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 15:31:07 schrieb Austin S. Hemmelgarn:

Hi Austin,

> > Little data, interesting statement for results on 200+ systems including
> > all major CPU arches all showing information leading in the same
> > directions.
> Let me try rephrasing this to make it a bit clearer:
> 1. You have lots of data on server systems.
> 2. You have a significant amount of data on desktop/workstation type
> systems.
> 3. You have very little data on embedded systems.
> 
> and here are your arguments:
> A. This works well on server systems.
> B. This works well on desktop systems.
> C. This works well on embedded systems.
> 
> Arguments A and B are substantiated directly by points 1 and 2.
> Argument C is not substantiated thoroughly because of point 3.
> My complaint is about argument C given point 3.

Then let me rephrase what I try to say: my RNG rests on the intrinsic 
functionality of CPUs. When I show that such intrinsic behavior is present in 
various architectures I show that there is a common ground for the basis of 
the RNG.

I tested on all CPUs of all large scale architectures (including the 
architectures that are commonly used for embedded devices) and demonstrated 
that the fundamental phenomenon the RNG rests on is present in all 
architectures.

I do not care about the form factor of the test system server, desktop or 
embedded systems nor do I care about the number of attached devices -- the 
form factor and number of attached devices is the differentiator of what you 
call embedded vs server vs desktop.

Heck, I have written a test that executes the RNG on bare metal (without OS 
and with only a keyboard as device present -- i.e no interrupts are received 
apart from a keyboard), which demonstrates that the phenomenon is present.

Furthermore, chapter 6 of my document analyzes the root cause of the RNG and 
here you see clearly that it has nothing to do with the size of the CPU or its 
attached devices or the size of RAM.

The massive number of x86 tests shall demonstrate the common theme I see: the 
newer the CPU the larger the phenomenon is the RNG rests on.

I use different OSes (including microkernel systems) for testing to 
demonstrate that the OS does not materially change the test results.
> 
> I'm not saying you have insufficient data to support argument A or B,
> only that you have insufficient data to support argument C.

And I think that this statement is not correct. But I would always welcome 
more testing.
> 
> Android barely counts as an embedded system anymore, as many Android

Then read F.28ff -- these are truly embedded systems (i.e. the routers that I 
have on my desk)

> phones can outperform most inexpensive desktop and laptop systems, and
> even some rather expensive laptops.  This leaves the only systems that
> can be assumed without further information to be representative of
> embedded boards to be the ones running Genode, and possibly the MIPS
> systems, which is a total of about 10 results out of hundreds for
> servers and desktops/workstations.


Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-22 01:16, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 15:31:07 schrieb Austin S. Hemmelgarn:
>
> Hi Austin,
>
>>> Little data, interesting statement for results on 200+ systems including
>>> all major CPU arches all showing information leading in the same
>>> directions.
>> Let me try rephrasing this to make it a bit clearer:
>> 1. You have lots of data on server systems.
>> 2. You have a significant amount of data on desktop/workstation type
>> systems.
>> 3. You have very little data on embedded systems.
>>
>> and here are your arguments:
>> A. This works well on server systems.
>> B. This works well on desktop systems.
>> C. This works well on embedded systems.
>>
>> Arguments A and B are substantiated directly by points 1 and 2.
>> Argument C is not substantiated thoroughly because of point 3.
>> My complaint is about argument C given point 3.
>
> Then let me rephrase what I try to say: my RNG rests on the intrinsic
> functionality of CPUs. When I show that such intrinsic behavior is present in
> various architectures I show that there is a common ground for the basis of
> the RNG.
You're not demonstrating it's inherently present in the architecture, 
your demonstrating that it's present for those particular 
micro-architectures you have tested.  You're dealing with effects 
resulting from such low-level details of the CPU that you can't assume 
it happens for the whole architecture.  In fact, your own results 
regarding the weak values from Pentium Celeron Mobile system reinforce 
that it's not an architectural effect at the ISA level, but results from 
low level designs.  Given the naming of that particular CPU, it's almost 
certainly a P6 or NetBurst micro-arch, neither of which had particularly 
complex branch-prediction or pipelining or similar things, and more 
significantly, probably did not have HyperThreading, which I'd be 
willing to bet is a significant contributing factor on the Xeon and Core 
processors you've got results for.
>
> I tested on all CPUs of all large scale architectures (including the
> architectures that are commonly used for embedded devices) and demonstrated
> that the fundamental phenomenon the RNG rests on is present in all
> architectures.
In all architectures you've tested.  Note that technically, from a 
low-level perspective of something like this, different revisions of an 
ISA are different architectures, and when you start talking about 
licensed IP cores like ARM and PPC (and MIPS, and SPARC), different 
manufacturer's designs almost count separately.  You're relying on 
complexities inherent in the CPU itself, which will be different between 
micro-architectures, and possibly even individual revisions of a 
specific model number.  Just because the test gives good results on an 
ARMv6 or ARMv7 does not mean it will on an ARMv4, because there are 
enough differences in typical designs of ARM CPU's that you can't 
directly draw conclusions based on such a small sample size (you've 
tested at most 4 manufacturer's designs, and even then only one from 
each, and there are about 10 different companies making ARM chips, each 
selling dozens of slightly different CPU's).
>
> I do not care about the form factor of the test system server, desktop or
> embedded systems nor do I care about the number of attached devices -- the
> form factor and number of attached devices is the differentiator of what you
> call embedded vs server vs desktop.
I don't care about form factor, I care about the CPU, and embedded 
systems almost always have simpler CPU designs (not including all the 
peripherals they love to add in on-die).  Your own analysis indicates 
that your getting entropy from the complex interaction of the different 
parts of the CPU.  Such complexities are less present in simpler CPU 
designs.
>
> Heck, I have written a test that executes the RNG on bare metal (without OS
> and with only a keyboard as device present -- i.e no interrupts are received
> apart from a keyboard), which demonstrates that the phenomenon is present.
>
> Furthermore, chapter 6 of my document analyzes the root cause of the RNG and
> here you see clearly that it has nothing to do with the size of the CPU or its
> attached devices or the size of RAM.
And yet averages are higher for systems that have more CPU cores, and 
thus more complex CPU's.  Prime examples of this are the UltraSPARC 
CPU's you've tested.  Those have more SMP cores (and threads of 
execution) than just about anything else you've listed, and they have 
significantly higher values than almost anything else you list.
>
> The massive number of x86 tests shall demonstrate the common theme I see: the
> newer the CPU the larger the phenomenon is the RNG rests on.
Except each iteration of x86 grows more complex branch-prediction and 
pipe-lining and other tricks to try and make the CPU process data 
faster.  That is the source of almost all of the increase your seeing in 
entropy for newer revisions.  The same is not inherently true of 
embedded processors, especially ones designed for hard-real-time usage 
(while I don't have the resources to do this myself, I'd love to see 
test results for this from a couple of Blackfin DSP's, I'd be willing to 
bet that you see extremely low entropy there because they're designed 
for real-time processing).
>
> I use different OSes (including microkernel systems) for testing to
> demonstrate that the OS does not materially change the test results.
>>
>> I'm not saying you have insufficient data to support argument A or B,
>> only that you have insufficient data to support argument C.
>
> And I think that this statement is not correct. But I would always welcome
> more testing.
>>
>> Android barely counts as an embedded system anymore, as many Android
>
> Then read F.28ff -- these are truly embedded systems (i.e. the routers that I
> have on my desk)
1. I'm actually rather curious what router you managed to get Android 
running on.
2. This is still an insanely small sample size compared to the rest of 
your results.
>
>> phones can outperform most inexpensive desktop and laptop systems, and
>> even some rather expensive laptops.  This leaves the only systems that
>> can be assumed without further information to be representative of
>> embedded boards to be the ones running Genode, and possibly the MIPS
>> systems, which is a total of about 10 results out of hundreds for
>> servers and desktops/workstations.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Stephan Mueller]

Am Mittwoch, 22. Juni 2016, 08:54:16 schrieb Austin S. Hemmelgarn:

Hi Austin,

> You're not demonstrating it's inherently present in the architecture,

I am not demonstrating it, interesting statement. I take different arches from 
different vendors which were developed independently from each other and I see 
the phenomenon to an equal degree in all of them.

So, this is no demonstration in your eyes? Interesting conclusion.

Yes, I do not have the statement that gate X or function Y in a CPU is the 
trigger point. Thus the absolute root cause to the unpredictable phenomenon is 
yet unknown to me. I am hunting that -- I spoke with hardware folks from 3 
different major chip vendors yet and they all have difficulties in explaining 
it. One vendor is currently helping me dissecting the issue.
> 
> > I do not care about the form factor of the test system server, desktop or
> > embedded systems nor do I care about the number of attached devices -- the
> > form factor and number of attached devices is the differentiator of what
> > you call embedded vs server vs desktop.
> 
> I don't care about form factor, I care about the CPU, and embedded
> systems almost always have simpler CPU designs (not including all the
> peripherals they love to add in on-die).  Your own analysis indicates
> that your getting entropy from the complex interaction of the different
> parts of the CPU.  Such complexities are less present in simpler CPU
> designs.

My RNG has two safety measures to detect noise source failures (again, they 
are documented): during startup and at runtime. In both cases, no data will be 
produced. But for chips where the self tests pass, we can surely harvest that 
unpredictable phenomenon.

And funnily: these health tests would scream loudly in dmesg if the noise 
source would not work. Note, in more recent kernels, the RNG is used in a lot 
of configurations and I have only received one complaint that the health test 
indicated a bad noise source. That was a very special system where a 
separation kernel did funky things.

So, as of now, it rather makes sense that you refer me to some embedded 
devices that you think will be a challenge. I do not like to theorize.

For me, embedded devices are something like a Rasperry PI or the MIPS system 
which are tested.

> >> Android barely counts as an embedded system anymore, as many Android
> > 
> > Then read F.28ff -- these are truly embedded systems (i.e. the routers
> > that I have on my desk)
> 
> 1. I'm actually rather curious what router you managed to get Android
> running on.
> 2. This is still an insanely small sample size compared to the rest of
> your results.

I think this will be the last answer for now from my side: I ask you to read 
my document as I really do not want to restate 150+ pages here!

This machine is no Android system but an AVM FritzBox router system that is 
very popular in Germany, as referenced in the document. It runs with highly 
modified Linux system -- as documented.

And instead of complaining about the test sample, you should help us by doing 
more testing, if you feel that the health tests in the RNG are insufficient.


Besides, if you really worried about the lower bound I mentioned in the 
appendix F, use the oversampling rate turning knob 
jent_entropy_collector_alloc as documented. Finally, if that is not of your 
liking, generate a bit more data with the Jitter RNG than you think you need 
entropy wise.

Ciao
Stephan

Re: [PATCH v4 0/5] /dev/random - a new approach

[Pavel Machek]

Hi!

> 6. You have a significant lack of data regarding embedded systems, which is
> one of the two biggest segments of Linux's market share.  You list no
> results for any pre-ARMv6 systems (Linux still runs on and is regularly used
> on ARMv4 CPU's, and it's worth also pointing out that the values on
> the

Feel free to contribute more test results.

I mean... you can't expect every person who wants to improve something
in linux to test on everything in the world... can you?

								Pavel

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

Re: [PATCH v4 0/5] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 09:42, Pavel Machek wrote:
> Hi!
>
>> 6. You have a significant lack of data regarding embedded systems, which is
>> one of the two biggest segments of Linux's market share.  You list no
>> results for any pre-ARMv6 systems (Linux still runs on and is regularly used
>> on ARMv4 CPU's, and it's worth also pointing out that the values on
>> the
>
> Feel free to contribute more test results.
>
> I mean... you can't expect every person who wants to improve something
> in linux to test on everything in the world... can you?
>
I was commenting less on the lack of results for such systems than on 
attempts to make statements about such systems based on a data-set that 
lacks information about such systems.

Re: [PATCH v4 0/5] /dev/random - a new approach

[David Jaša]

Hi,

On So, 2016-06-18 at 10:44 -0400, Theodore Ts'o wrote:
> On Fri, Jun 17, 2016 at 03:56:13PM +0200, David Jaša wrote:
> > I was thinking along the lines that "almost every important package
> > supports FreeBSD as well where they have to handle the condition so
> > option to switch to Rather Break Than Generate Weak Keys would be nice"
> > - but I didn't expect that systemd could be a roadblock here. :-/
> 
> It wasn't just systemd; it also broke OpenWRT and Ubuntu Quantal
> systems from booting.
> 
> > I was also thinking of little devices where OpenWRT or proprietary
> > Linux-based systems run that ended up with predictable keys way too
> > ofter (or as in OpenWRT's case, with cumbersome tutorials how to
> > generate keys elsewhere).
> 
> OpenWRT and other embedded devices (a) generally use a single master
> oscillator to drive everything, and (b) often use RISC architectures
> such as MIPS.
> 
> Which means that arguments of the form ``the Intel L1 / L2 cache
> architecture is ****soooo**** complicated that no human could possibly
> figure out how they would affect timing calculations, and besides, my
> generator passes FIPS 140-2 tests (never mind AES(NSA_KEY, CNTR++)

this

> also passes the FIPS 140-2 statistical tests)'' --- which I normally
> have trouble believing --- are even harder for me to believe.
> 
> At the end of the day, with these devices you really badly need a
> hardware RNG.  

and this.

It seems much easier to me to embed AES(NSA_KEY, CNTR++) logic directly
to HW RNG compared to tweaking of every microarchitecture to make
jitter/maxwell/havege return known numbers that are going to be mixed
with other entropy anyway (won't they?). So if I put the bits together
correctly, HW RNG helps getting more random numbers but itself is
insufficient to ensure that random numbers are truly random...

Cheers,

David Jaša

> We can't generate randomness out of thin air.  The only
> thing you really can do requires user space help, which is to generate
> keys lazily, or as late as possible, so you can gather as much entropy
> as you can --- and to feed in measurements from the WiFi (RSSI
> measurements, MAC addresses seen, etc.)  This won't help much if you
> have an FBI van parked outside your house trying to carry out a
> TEMPEST attack, but hopefully it provides some protection against a
> remote attacker who isn't try to carry out an on-premises attack.
> 
> Cheers,
> 
> 						- Ted