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 v5:
* fix treating LRNG_POOL_SIZE_BITS as entropy value in lrng_get_pool
* use CTR DRBG with AES256 as default due to its superior speed -- on X86_64
executing within a KVM I get read speeds of up to 850 MB/s now. When using a
fake NUMA system with 4 nodes on 4 CPUs, I still get up to 430 MB/s read speed
with four parallel reads. Note, this patch applies to the current
cryptodev-2.6 tree.
* simplify lrng_get_arch
* use DRBG security strengths as defined in SP800-57 section 5.6.1
* add security strength to /proc/sys/kernel/random/lrng_type
* add ChaCha20 DRNG: in case the kernel crypto API is not compiled, the ChaCha20
DRNG with the SHA-1 C implementations are used to drive the cryptographic part
of the LRNG.The ChaCha20 RNG is described in [1]. I analyzed it with a user
space version of it.
* Editorial changes requested by checkpatch.pl
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 (7):
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: isolate the chacha20_block function
crypto: LRNG - add ChaCha20 support
crypto/Kconfig | 15 +
crypto/Makefile | 8 +
crypto/chacha20_block.c | 79 ++
crypto/chacha20_generic.c | 61 --
crypto/drbg.c | 11 +-
crypto/lrng_base.c | 1942 +++++++++++++++++++++++++++++++++++++++++++++
crypto/lrng_kcapi.c | 167 ++++
crypto/lrng_standalone.c | 218 +++++
drivers/char/random.c | 9 +
drivers/hv/vmbus_drv.c | 3 +
include/crypto/chacha20.h | 1 +
include/crypto/drbg.h | 7 +
include/linux/genhd.h | 5 +
include/linux/random.h | 7 +-
14 files changed, 2465 insertions(+), 68 deletions(-)
create mode 100644 crypto/chacha20_block.c
create mode 100644 crypto/lrng_base.c
create mode 100644 crypto/lrng_kcapi.c
create mode 100644 crypto/lrng_standalone.c
--
2.5.5
Add LRNG compilation support.
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/Kconfig | 11 +++++++++++
crypto/Makefile | 2 ++
2 files changed, 13 insertions(+)
diff --git a/crypto/Kconfig b/crypto/Kconfig
index c903f18..772d430 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1589,6 +1589,17 @@ 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
+ select CRYPTO_CMAC if CRYPTO_DRBG_CTR
+ help
+ The Linux Random Number Generator (LRNG) is the replacement
+ of the legacy /dev/random provided with drivers/char/random.c.
+ It generates entropy from different noise sources and
+ delivers significant entropy during boot. 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..f013fac 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -114,6 +114,8 @@ 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
+lrng-y += lrng_base.o lrng_kcapi.o
obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
obj-$(CONFIG_CRYPTO_GHASH) += ghash-generic.o
obj-$(CONFIG_CRYPTO_USER_API) += af_alg.o
--
2.5.5
The Hyper-V Linux Integration Services use the VMBus implementation for
communication with the Hypervisor. VMBus registers its own interrupt
handler that completely bypasses the common Linux interrupt handling.
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 <[email protected]>
---
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.5.5
In case the kernel crypto API is not compiled, use ChaCha20 stream
cipher as DRNG. The LRNG ChaCha20 support provides the DRNG
implementation with the generate and update functions. Further
documentation is provided in [1].
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/Kconfig | 2 +-
crypto/Makefile | 7 +-
crypto/lrng_standalone.c | 218 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 225 insertions(+), 2 deletions(-)
create mode 100644 crypto/lrng_standalone.c
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 2822c0f..4a913c4 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1595,8 +1595,8 @@ config CRYPTO_JITTERENTROPY
config CRYPTO_LRNG
bool "Linux Random Number Generator"
- select CRYPTO_DRBG_MENU
select CRYPTO_CMAC if CRYPTO_DRBG_CTR
+ select CRYPTO_CHACHA20_BLOCK if !(CRYPTO_DRBG)
help
The Linux Random Number Generator (LRNG) is the replacement
of the legacy /dev/random provided with drivers/char/random.c.
diff --git a/crypto/Makefile b/crypto/Makefile
index 1b4cc35..f2df363 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -116,7 +116,12 @@ 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
-lrng-y += lrng_base.o lrng_kcapi.o
+lrng-y += lrng_base.o
+ifeq ($(CONFIG_CRYPTO_DRBG),y)
+lrng-y += lrng_kcapi.o
+else
+lrng-y += lrng_standalone.o
+endif
obj-$(CONFIG_CRYPTO_TEST) += tcrypt.o
obj-$(CONFIG_CRYPTO_GHASH) += ghash-generic.o
obj-$(CONFIG_CRYPTO_USER_API) += af_alg.o
diff --git a/crypto/lrng_standalone.c b/crypto/lrng_standalone.c
new file mode 100644
index 0000000..967096c
--- /dev/null
+++ b/crypto/lrng_standalone.c
@@ -0,0 +1,218 @@
+/*
+ * Backend for the LRNG providing the cryptographic primitives using
+ * standalone cipher implementations.
+ *
+ * Copyright (C) 2016, Stephan Mueller <[email protected]>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, and the entire permission notice in its entirety,
+ * including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ * products derived from this software without specific prior
+ * written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions. (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/cryptohash.h>
+#include <crypto/chacha20.h>
+#include <linux/random.h>
+
+/******************************* ChaCha20 DRNG *******************************/
+
+/* State according to RFC 7539 section 2.3 */
+struct chacha20_state {
+ u32 constants[4];
+ union {
+ u32 u[(CHACHA20_KEY_SIZE / sizeof(u32))];
+ u8 b[CHACHA20_KEY_SIZE];
+ } key;
+ u32 counter;
+ u32 nonce[3];
+};
+
+/**
+ * Update of the ChaCha20 state by generating one ChaCha20 block which is
+ * equal to the state of the ChaCha20. The generated block is XORed into
+ * the key part of the state. This shall ensure backtracking resistance as well
+ * as a proper mix of the ChaCha20 state once the key is injected.
+ */
+static void lrng_chacha20_update(struct chacha20_state *chacha20)
+{
+ u32 tmp[(CHACHA20_BLOCK_SIZE / sizeof(u32))];
+ u32 i;
+
+ BUILD_BUG_ON(sizeof(struct chacha20_state) != CHACHA20_BLOCK_SIZE);
+ BUILD_BUG_ON(CHACHA20_BLOCK_SIZE != 2 * CHACHA20_KEY_SIZE);
+
+ chacha20_block(&chacha20->constants[0], tmp);
+ for (i = 0; i < (CHACHA20_KEY_SIZE / sizeof(uint32_t)); i++)
+ chacha20->key.u[i] ^= tmp[i];
+ for (i = 0; i < (CHACHA20_KEY_SIZE / sizeof(uint32_t)); i++)
+ chacha20->key.u[i] ^=
+ tmp[i + (CHACHA20_KEY_SIZE / sizeof(uint32_t))];
+
+ /* Deterministic increment of nonce as required in RFC 7539 chapter 4 */
+ chacha20->nonce[0]++;
+ if (chacha20->nonce[0] == 0)
+ chacha20->nonce[1]++;
+ if (chacha20->nonce[1] == 0)
+ chacha20->nonce[2]++;
+
+ /* Leave counter untouched as it is start value is undefined in RFC */
+}
+
+/**
+ * Seed the ChaCha20 DRNG by injecting the input data into the key part of
+ * the ChaCha20 state. If the input data is longer than the ChaCha20 key size,
+ * perform a ChaCha20 operation after processing of key size input data.
+ * This operation shall spread out the entropy into the ChaCha20 state before
+ * new entropy is injected into the key part.
+ */
+int lrng_drng_seed_helper(void *drng, const u8 *inbuf, u32 inbuflen)
+{
+ struct chacha20_state *chacha20 = (struct chacha20_state *)drng;
+
+ while (inbuflen) {
+ u32 i, todo = min_t(u32, inbuflen, CHACHA20_KEY_SIZE);
+
+ for (i = 0; i < todo; i++)
+ chacha20->key.b[i] ^= inbuf[i];
+
+ /* Break potential dependencies between the inbuf key blocks */
+ lrng_chacha20_update(chacha20);
+ inbuf += todo;
+ inbuflen -= todo;
+ }
+
+ return 0;
+}
+
+/**
+ * Chacha20 DRNG generation of random numbers: the stream output of ChaCha20
+ * is the random number. After the completion of the generation of the
+ * stream, the entire ChaCha20 state is updated.
+ *
+ * Note, as the ChaCha20 implements a 32 bit counter, we must ensure
+ * that this function is only invoked for at most 2^32 - 1 ChaCha20 blocks
+ * before a reseed or an update happens. This is ensured by the variable
+ * outbuflen which is a 32 bit integer defining the number of bytes to be
+ * generated by the ChaCha20 DRNG. At the end of this function, an update
+ * operation is invoked which implies that the 32 bit counter will never be
+ * overflown in this implementation.
+ */
+int lrng_drng_generate_helper(void *drng, u8 *outbuf, u32 outbuflen)
+{
+ struct chacha20_state *chacha20 = (struct chacha20_state *)drng;
+ u32 ret = outbuflen;
+
+ while (outbuflen >= CHACHA20_BLOCK_SIZE) {
+ chacha20_block(&chacha20->constants[0], outbuf);
+ outbuf += CHACHA20_BLOCK_SIZE;
+ outbuflen -= CHACHA20_BLOCK_SIZE;
+ }
+
+ if (outbuflen) {
+ u8 stream[CHACHA20_BLOCK_SIZE];
+
+ chacha20_block(&chacha20->constants[0], stream);
+ memcpy(outbuf, stream, outbuflen);
+ memzero_explicit(stream, sizeof(stream));
+ }
+
+ lrng_chacha20_update(chacha20);
+
+ return ret;
+}
+
+/**
+ * Allocation of the DRBG state
+ */
+void *lrng_drng_alloc(u8 *drng_name, u32 blocklen_bytes, u32 sec_strength)
+{
+ struct chacha20_state *chacha20;
+ unsigned long v;
+
+ chacha20 = kzalloc(sizeof(struct chacha20_state), GFP_KERNEL);
+ if (!chacha20)
+ return NULL;
+
+ memcpy(&chacha20->constants[0], "expand 32-byte k", 16);
+ if (arch_get_random_long(&v))
+ chacha20->nonce[0] ^= v;
+ if (arch_get_random_long(&v))
+ chacha20->nonce[1] ^= v;
+ if (arch_get_random_long(&v))
+ chacha20->nonce[2] ^= v;
+
+ if (sec_strength > CHACHA20_KEY_SIZE)
+ goto err;
+ if (blocklen_bytes != CHACHA20_BLOCK_SIZE)
+ goto err;
+
+ pr_info("ChaCha20 core allocated\n");
+
+ return chacha20;
+
+err:
+ kfree(chacha20);
+ return NULL;
+}
+
+void lrng_drng_dealloc(void *drng)
+{
+ struct chacha20_state *chacha20 = (struct chacha20_state *)drng;
+
+ kzfree(chacha20);
+}
+
+/******************************* Hash Operation *******************************/
+
+void *lrng_hash_alloc(u8 *hashname, u8 *key, u32 keylen)
+{
+ return NULL;
+}
+
+u32 lrng_hash_digestsize(void *hash)
+{
+ return (SHA_DIGEST_WORDS * sizeof(u32));
+}
+
+int lrng_hash_buffer(void *hash, u8 *inbuf, u32 inbuflen, u8 *digest)
+{
+ u32 i;
+ u32 workspace[SHA_WORKSPACE_WORDS];
+
+ WARN_ON(inbuflen % SHA_WORKSPACE_WORDS);
+
+ for (i = 0; i < inbuflen; i += (SHA_WORKSPACE_WORDS * sizeof(u32)))
+ sha_transform((u32 *)digest, (inbuf + i), workspace);
+ memzero_explicit(workspace, sizeof(workspace));
+
+ return 0;
+}
--
2.5.5
The chacha20_block function is extracted into its separate C file to
allow it to be used by other callers.
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/Kconfig | 4 +++
crypto/Makefile | 1 +
crypto/chacha20_block.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++
crypto/chacha20_generic.c | 61 ------------------------------------
include/crypto/chacha20.h | 1 +
5 files changed, 85 insertions(+), 61 deletions(-)
create mode 100644 crypto/chacha20_block.c
diff --git a/crypto/Kconfig b/crypto/Kconfig
index 772d430..2822c0f 100644
--- a/crypto/Kconfig
+++ b/crypto/Kconfig
@@ -1224,9 +1224,13 @@ config CRYPTO_SALSA20_X86_64
The Salsa20 stream cipher algorithm is designed by Daniel J.
Bernstein <[email protected]>. See <http://cr.yp.to/snuffle.html>
+config CRYPTO_CHACHA20_BLOCK
+ bool
+
config CRYPTO_CHACHA20
tristate "ChaCha20 cipher algorithm"
select CRYPTO_BLKCIPHER
+ select CRYPTO_CHACHA20_BLOCK
help
ChaCha20 cipher algorithm, RFC7539.
diff --git a/crypto/Makefile b/crypto/Makefile
index f013fac..1b4cc35 100644
--- a/crypto/Makefile
+++ b/crypto/Makefile
@@ -97,6 +97,7 @@ obj-$(CONFIG_CRYPTO_ANUBIS) += anubis.o
obj-$(CONFIG_CRYPTO_SEED) += seed.o
obj-$(CONFIG_CRYPTO_SALSA20) += salsa20_generic.o
obj-$(CONFIG_CRYPTO_CHACHA20) += chacha20_generic.o
+obj-$(CONFIG_CRYPTO_CHACHA20_BLOCK) += chacha20_block.o
obj-$(CONFIG_CRYPTO_POLY1305) += poly1305_generic.o
obj-$(CONFIG_CRYPTO_DEFLATE) += deflate.o
obj-$(CONFIG_CRYPTO_MICHAEL_MIC) += michael_mic.o
diff --git a/crypto/chacha20_block.c b/crypto/chacha20_block.c
new file mode 100644
index 0000000..610b391
--- /dev/null
+++ b/crypto/chacha20_block.c
@@ -0,0 +1,79 @@
+/*
+ * ChaCha20 256-bit cipher algorithm, RFC7539
+ *
+ * Copyright (C) 2015 Martin Willi
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ */
+
+#include <linux/kernel.h>
+#include <linux/export.h>
+#include <linux/bitops.h>
+#include <linux/cryptohash.h>
+#include <asm/unaligned.h>
+#include <crypto/chacha20.h>
+
+static inline u32 rotl32(u32 v, u8 n)
+{
+ return (v << n) | (v >> (sizeof(v) * 8 - n));
+}
+
+void chacha20_block(u32 *state, void *stream)
+{
+ u32 x[16], *out = stream;
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(x); i++)
+ x[i] = state[i];
+
+ for (i = 0; i < 20; i += 2) {
+ x[0] += x[4]; x[12] = rotl32(x[12] ^ x[0], 16);
+ x[1] += x[5]; x[13] = rotl32(x[13] ^ x[1], 16);
+ x[2] += x[6]; x[14] = rotl32(x[14] ^ x[2], 16);
+ x[3] += x[7]; x[15] = rotl32(x[15] ^ x[3], 16);
+
+ x[8] += x[12]; x[4] = rotl32(x[4] ^ x[8], 12);
+ x[9] += x[13]; x[5] = rotl32(x[5] ^ x[9], 12);
+ x[10] += x[14]; x[6] = rotl32(x[6] ^ x[10], 12);
+ x[11] += x[15]; x[7] = rotl32(x[7] ^ x[11], 12);
+
+ x[0] += x[4]; x[12] = rotl32(x[12] ^ x[0], 8);
+ x[1] += x[5]; x[13] = rotl32(x[13] ^ x[1], 8);
+ x[2] += x[6]; x[14] = rotl32(x[14] ^ x[2], 8);
+ x[3] += x[7]; x[15] = rotl32(x[15] ^ x[3], 8);
+
+ x[8] += x[12]; x[4] = rotl32(x[4] ^ x[8], 7);
+ x[9] += x[13]; x[5] = rotl32(x[5] ^ x[9], 7);
+ x[10] += x[14]; x[6] = rotl32(x[6] ^ x[10], 7);
+ x[11] += x[15]; x[7] = rotl32(x[7] ^ x[11], 7);
+
+ x[0] += x[5]; x[15] = rotl32(x[15] ^ x[0], 16);
+ x[1] += x[6]; x[12] = rotl32(x[12] ^ x[1], 16);
+ x[2] += x[7]; x[13] = rotl32(x[13] ^ x[2], 16);
+ x[3] += x[4]; x[14] = rotl32(x[14] ^ x[3], 16);
+
+ x[10] += x[15]; x[5] = rotl32(x[5] ^ x[10], 12);
+ x[11] += x[12]; x[6] = rotl32(x[6] ^ x[11], 12);
+ x[8] += x[13]; x[7] = rotl32(x[7] ^ x[8], 12);
+ x[9] += x[14]; x[4] = rotl32(x[4] ^ x[9], 12);
+
+ x[0] += x[5]; x[15] = rotl32(x[15] ^ x[0], 8);
+ x[1] += x[6]; x[12] = rotl32(x[12] ^ x[1], 8);
+ x[2] += x[7]; x[13] = rotl32(x[13] ^ x[2], 8);
+ x[3] += x[4]; x[14] = rotl32(x[14] ^ x[3], 8);
+
+ x[10] += x[15]; x[5] = rotl32(x[5] ^ x[10], 7);
+ x[11] += x[12]; x[6] = rotl32(x[6] ^ x[11], 7);
+ x[8] += x[13]; x[7] = rotl32(x[7] ^ x[8], 7);
+ x[9] += x[14]; x[4] = rotl32(x[4] ^ x[9], 7);
+ }
+
+ for (i = 0; i < ARRAY_SIZE(x); i++)
+ out[i] = cpu_to_le32(x[i] + state[i]);
+
+ state[12]++;
+}
+EXPORT_SYMBOL(chacha20_block);
diff --git a/crypto/chacha20_generic.c b/crypto/chacha20_generic.c
index da9c899..1cab831 100644
--- a/crypto/chacha20_generic.c
+++ b/crypto/chacha20_generic.c
@@ -15,72 +15,11 @@
#include <linux/module.h>
#include <crypto/chacha20.h>
-static inline u32 rotl32(u32 v, u8 n)
-{
- return (v << n) | (v >> (sizeof(v) * 8 - n));
-}
-
static inline u32 le32_to_cpuvp(const void *p)
{
return le32_to_cpup(p);
}
-static void chacha20_block(u32 *state, void *stream)
-{
- u32 x[16], *out = stream;
- int i;
-
- for (i = 0; i < ARRAY_SIZE(x); i++)
- x[i] = state[i];
-
- for (i = 0; i < 20; i += 2) {
- x[0] += x[4]; x[12] = rotl32(x[12] ^ x[0], 16);
- x[1] += x[5]; x[13] = rotl32(x[13] ^ x[1], 16);
- x[2] += x[6]; x[14] = rotl32(x[14] ^ x[2], 16);
- x[3] += x[7]; x[15] = rotl32(x[15] ^ x[3], 16);
-
- x[8] += x[12]; x[4] = rotl32(x[4] ^ x[8], 12);
- x[9] += x[13]; x[5] = rotl32(x[5] ^ x[9], 12);
- x[10] += x[14]; x[6] = rotl32(x[6] ^ x[10], 12);
- x[11] += x[15]; x[7] = rotl32(x[7] ^ x[11], 12);
-
- x[0] += x[4]; x[12] = rotl32(x[12] ^ x[0], 8);
- x[1] += x[5]; x[13] = rotl32(x[13] ^ x[1], 8);
- x[2] += x[6]; x[14] = rotl32(x[14] ^ x[2], 8);
- x[3] += x[7]; x[15] = rotl32(x[15] ^ x[3], 8);
-
- x[8] += x[12]; x[4] = rotl32(x[4] ^ x[8], 7);
- x[9] += x[13]; x[5] = rotl32(x[5] ^ x[9], 7);
- x[10] += x[14]; x[6] = rotl32(x[6] ^ x[10], 7);
- x[11] += x[15]; x[7] = rotl32(x[7] ^ x[11], 7);
-
- x[0] += x[5]; x[15] = rotl32(x[15] ^ x[0], 16);
- x[1] += x[6]; x[12] = rotl32(x[12] ^ x[1], 16);
- x[2] += x[7]; x[13] = rotl32(x[13] ^ x[2], 16);
- x[3] += x[4]; x[14] = rotl32(x[14] ^ x[3], 16);
-
- x[10] += x[15]; x[5] = rotl32(x[5] ^ x[10], 12);
- x[11] += x[12]; x[6] = rotl32(x[6] ^ x[11], 12);
- x[8] += x[13]; x[7] = rotl32(x[7] ^ x[8], 12);
- x[9] += x[14]; x[4] = rotl32(x[4] ^ x[9], 12);
-
- x[0] += x[5]; x[15] = rotl32(x[15] ^ x[0], 8);
- x[1] += x[6]; x[12] = rotl32(x[12] ^ x[1], 8);
- x[2] += x[7]; x[13] = rotl32(x[13] ^ x[2], 8);
- x[3] += x[4]; x[14] = rotl32(x[14] ^ x[3], 8);
-
- x[10] += x[15]; x[5] = rotl32(x[5] ^ x[10], 7);
- x[11] += x[12]; x[6] = rotl32(x[6] ^ x[11], 7);
- x[8] += x[13]; x[7] = rotl32(x[7] ^ x[8], 7);
- x[9] += x[14]; x[4] = rotl32(x[4] ^ x[9], 7);
- }
-
- for (i = 0; i < ARRAY_SIZE(x); i++)
- out[i] = cpu_to_le32(x[i] + state[i]);
-
- state[12]++;
-}
-
static void chacha20_docrypt(u32 *state, u8 *dst, const u8 *src,
unsigned int bytes)
{
diff --git a/include/crypto/chacha20.h b/include/crypto/chacha20.h
index 274bbae..20d20f68 100644
--- a/include/crypto/chacha20.h
+++ b/include/crypto/chacha20.h
@@ -16,6 +16,7 @@ struct chacha20_ctx {
u32 key[8];
};
+void chacha20_block(u32 *state, void *stream);
void crypto_chacha20_init(u32 *state, struct chacha20_ctx *ctx, u8 *iv);
int crypto_chacha20_setkey(struct crypto_tfm *tfm, const u8 *key,
unsigned int keysize);
--
2.5.5
This patch allows several DRBG functions to be called by the LRNG kernel
code paths outside the drbg.c file.
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/drbg.c | 11 +++++------
include/crypto/drbg.h | 7 +++++++
2 files changed, 12 insertions(+), 6 deletions(-)
diff --git a/crypto/drbg.c b/crypto/drbg.c
index ded8638..6f968e3 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[] = {
+const 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:
@@ -1128,7 +1128,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;
@@ -1147,7 +1147,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;
@@ -1781,8 +1781,7 @@ static int drbg_kcapi_sym_ctr(struct drbg_state *drbg,
*
* 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 61580b1..1755d07 100644
--- a/include/crypto/drbg.h
+++ b/include/crypto/drbg.h
@@ -280,4 +280,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 const struct drbg_core drbg_cores[];
+extern unsigned short drbg_sec_strength(drbg_flag_t flags);
+
#endif /* _DRBG_H */
--
2.5.5
When selecting the LRNG for compilation, disable the legacy /dev/random
implementation.
The LRNG is a drop-in replacement for the legacy /dev/random which
implements the same in-kernel and user space API. Only the hooks of
/dev/random into other parts of the kernel need to be disabled.
Signed-off-by: Stephan Mueller <[email protected]>
---
drivers/char/random.c | 8 ++++++++
include/linux/genhd.h | 5 +++++
include/linux/random.h | 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.5.5
The LRNG with all its properties is documented in [1]. This
documentation covers the functional discussion as well as testing of all
aspects of entropy processing. In addition, the documentation explains
the conducted regression tests to verify that the LRNG is API and ABI
compatible with the legacy /dev/random implementation.
[1] http://www.chronox.de/lrng.html
Signed-off-by: Stephan Mueller <[email protected]>
---
crypto/lrng_base.c | 1942 +++++++++++++++++++++++++++++++++++++++++++++++++++
crypto/lrng_kcapi.c | 167 +++++
2 files changed, 2109 insertions(+)
create mode 100644 crypto/lrng_base.c
create mode 100644 crypto/lrng_kcapi.c
diff --git a/crypto/lrng_base.c b/crypto/lrng_base.c
new file mode 100644
index 0000000..10a0459
--- /dev/null
+++ b/crypto/lrng_base.c
@@ -0,0 +1,1942 @@
+/*
+ * Linux Random Number Generator (LRNG)
+ *
+ * Documentation and test code: http://www.chronox.de/lrng.html
+ *
+ * Copyright (C) 2016, Stephan Mueller <[email protected]>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, and the entire permission notice in its entirety,
+ * including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ * products derived from this software without specific prior
+ * written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions. (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#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 <linux/fips.h>
+#include <linux/slab.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.
+ *
+ * The security strengths of the DRBGs are taken from SP800-57 section 5.6.1.
+ *
+ * This definition is allowed to be changed.
+ */
+#ifdef CONFIG_CRYPTO_DRBG_CTR
+# define LRNG_HASH_NAME "cmac(aes)"
+# 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
+#elif defined CONFIG_CRYPTO_DRBG_HMAC
+# if 0
+# define LRNG_DRBG_BLOCKLEN_BYTES 32
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 16
+# define LRNG_DRBG_CORE "drbg_nopr_hmac_sha256" /* HMAC DRBG SHA-256 */
+# define LRNG_HASH_NAME "sha256"
+# else
+# 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"
+# endif
+#elif defined CONFIG_CRYPTO_DRBG_HASH
+# if 0
+# define LRNG_DRBG_BLOCKLEN_BYTES 32
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 16
+# define LRNG_DRBG_CORE "drbg_nopr_sha256" /* Hash DRBG SHA-256 */
+# define LRNG_HASH_NAME "sha256"
+# else
+# 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"
+# endif
+#else
+# define LRNG_DRBG_BLOCKLEN_BYTES 64
+# define LRNG_DRBG_SECURITY_STRENGTH_BYTES 32
+# define LRNG_DRBG_CORE "ChaCha20" /* ChaCha20 */
+# define LRNG_HASH_NAME "sha1"
+#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 {
+ void *pdrbg; /* DRNG 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 {
+ void *sdrbg; /* DRNG 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? */
+};
+
+/*
+ * 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 */
+ void *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;
+
+/************************** Crypto Implementations ***************************/
+
+/**
+ * Allocate DRNG -- the provided integers should be used for sanity checks.
+ * @return: allocated data structure or NULL on error
+ */
+void *lrng_drng_alloc(u8 *drng_name, u32 blocklen_bytes, u32 sec_strength);
+
+/* Deallocate DRNG */
+void lrng_drng_dealloc(void *drng);
+
+/**
+ * Seed the DRNG with data of arbitrary length
+ * @drng is pointer to data structure allocated with lrng_drng_alloc
+ * @return: >= 0 on success, < 0 on error
+ */
+int lrng_drng_seed_helper(void *drng, const u8 *inbuf, u32 inbuflen);
+
+/**
+ * Generate random numbers from the DRNG with arbitrary length
+ * @return: generated number of bytes, < 0 on error
+ */
+int lrng_drng_generate_helper(void *drng, u8 *outbuf, u32 outbuflen);
+
+/**
+ * Allocate the hash for reading the entropy pool
+ * @return: allocated data structure (NULL is success too) or ERR_PTR on error
+ */
+void *lrng_hash_alloc(u8 *hashname, u8 *key, u32 keylen);
+
+/**
+ * Return the digestsize for the used hash to read out entropy pool
+ * @hash is pointer to data structure allocated with lrng_hash_alloc
+ * @return size of digest of hash in bytes
+ */
+u32 lrng_hash_digestsize(void *hash);
+
+/**
+ * Generate hash
+ * @hash is pointer to data structure allocated with lrng_hash_alloc
+ * @return 0 on success, < 0 on error
+ */
+int lrng_hash_buffer(void *hash, u8 *inbuf, u32 inbuflen, u8 *digest);
+
+/********************************** 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;
+ i += sizeof(unsigned long)) {
+ if (!arch_get_random_long((unsigned long *)(outbuf + i))) {
+ archrandom = 0;
+ return 0;
+ }
+ }
+
+ /* 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(®_idx) >=
+ sizeof(struct pt_regs) / sizeof(u32))
+ atomic_set(®_idx, 0);
+ data.curr_reg = *(ptr + atomic_add_return(1, ®_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);
+ u32 digestsize = lrng_hash_digestsize(lrng_pool.lrng_hash);
+ 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 (lrng_hash_buffer(lrng_pool.lrng_hash, (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_entropy_to_data(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 *******************************/
+
+/**
+ * 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 with %u bits\n",
+ entropy_bits);
+ 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)
+{
+ 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_drng_generate_helper(lrng_pdrbg.pdrbg, 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.
+ *
+ * Note, this function seeds the primary DRBG and generates data from it
+ * in an atomic operation.
+ *
+ * @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)
+{
+ 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_drng_seed_helper(lrng_pdrbg.pdrbg, 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);
+
+ /* 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_drng_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_drng_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;
+}
+
+static int lrng_drngs_alloc(void)
+{
+ unsigned long flags;
+ struct drbg_state *pdrbg;
+ u32 node;
+ u32 num_nodes = num_possible_nodes();
+
+ pdrbg = lrng_drng_alloc(LRNG_DRBG_CORE, LRNG_DRBG_BLOCKLEN_BYTES,
+ LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+ if (!pdrbg)
+ return -ENOMEM;
+
+ spin_lock_irqsave(&lrng_pdrbg.lock, flags);
+ if (lrng_pdrbg.pdrbg) {
+ lrng_drng_dealloc(pdrbg);
+ kfree(pdrbg);
+ } else {
+ lrng_pdrbg.pdrbg = pdrbg;
+ INIT_WORK(&lrng_pdrbg.lrng_seed_work, lrng_pdrbg_seed_work);
+ pr_info("primary DRBG allocated\n");
+ }
+
+ lrng_pool.last_numa_node = num_nodes - 1;
+
+ spin_unlock_irqrestore(&lrng_pdrbg.lock, flags);
+
+ lrng_sdrbg = kmalloc_array(num_nodes, sizeof(void *),
+ 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_drng_alloc(LRNG_DRBG_CORE,
+ LRNG_DRBG_BLOCKLEN_BYTES,
+ LRNG_DRBG_SECURITY_STRENGTH_BYTES);
+ 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 for NUMA node %d allocated\n", node);
+ }
+
+ return 0;
+
+err:
+ for (node = 0; node < num_nodes; node++) {
+ struct lrng_sdrbg *sdrbg = lrng_sdrbg[node];
+
+ if (sdrbg) {
+ if (sdrbg->sdrbg)
+ lrng_drng_dealloc(sdrbg->sdrbg);
+ kfree(sdrbg);
+ }
+ }
+ kfree(lrng_sdrbg);
+
+ lrng_drng_dealloc(pdrbg);
+ kfree(pdrbg);
+
+ return -ENOMEM;
+}
+
+static int lrng_alloc(void)
+{
+ u8 key[LRNG_DRBG_SECURITY_STRENGTH_BYTES] __aligned(LRNG_KCAPI_ALIGN);
+ int ret = lrng_drngs_alloc();
+
+ if (ret)
+ return ret;
+
+ /* If the used hash is no MAC, ignore the ENOSYS return code */
+ lrng_init_rng(key, sizeof(key));
+ lrng_pool.lrng_hash = lrng_hash_alloc(LRNG_HASH_NAME, key, sizeof(key));
+ memzero_explicit(key, sizeof(key));
+ if (IS_ERR(lrng_pool.lrng_hash))
+ return -PTR_ERR(lrng_pool.lrng_hash);
+
+ 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[64] __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 > 64) {
+ 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[130];
+
+ snprintf(buf, sizeof(buf), "%s: %s\nDRNG security strength: %u bits\nentropy pool read hash: %s",
+#ifdef CONFIG_CRYPTO_DRBG_CTR
+ "CTR DRBG",
+#elif defined CONFIG_CRYPTO_DRBG_HMAC
+ "HMAC DRBG",
+#elif defined CONFIG_CRYPTO_DRBG_HASH
+ "HASH DRBG",
+#else
+ "DRNG",
+#endif
+ LRNG_DRBG_CORE, LRNG_DRBG_SECURITY_STRENGTH_BITS,
+ 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());
+
+ /*
+ * 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 <[email protected]>");
+MODULE_DESCRIPTION("Linux Random Number Generator");
diff --git a/crypto/lrng_kcapi.c b/crypto/lrng_kcapi.c
new file mode 100644
index 0000000..25c37c5
--- /dev/null
+++ b/crypto/lrng_kcapi.c
@@ -0,0 +1,167 @@
+/*
+ * Backend for the LRNG providing the cryptographic primitives using the
+ * kernel crypto API.
+ *
+ * Copyright (C) 2016, Stephan Mueller <[email protected]>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, and the entire permission notice in its entirety,
+ * including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ * products derived from this software without specific prior
+ * written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions. (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <crypto/drbg.h>
+
+struct lrng_hash_info {
+ struct shash_desc shash;
+ char ctx[];
+};
+
+int lrng_drng_seed_helper(void *drng, const u8 *inbuf, u32 inbuflen)
+{
+ struct drbg_state *drbg = (struct drbg_state *)drng;
+ LIST_HEAD(seedlist);
+ struct drbg_string data;
+ int ret;
+
+ drbg_string_fill(&data, inbuf, inbuflen);
+ list_add_tail(&data.list, &seedlist);
+ ret = drbg->d_ops->update(drbg, &seedlist, drbg->seeded);
+
+ if (ret >= 0)
+ drbg->seeded = true;
+
+ return ret;
+}
+
+int lrng_drng_generate_helper(void *drng, u8 *outbuf, u32 outbuflen)
+{
+ struct drbg_state *drbg = (struct drbg_state *)drng;
+
+ return drbg->d_ops->generate(drbg, outbuf, outbuflen, NULL);
+}
+
+void *lrng_drng_alloc(u8 *drng_name, u32 blocklen_bytes, u32 sec_strength)
+{
+ struct drbg_state *drbg = NULL;
+ int coreref = -1;
+ bool pr = false;
+ int ret;
+
+ drbg_convert_tfm_core(drng_name, &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;
+
+ if (blocklen_bytes != drbg->core->blocklen_bytes)
+ goto dealloc;
+ if (sec_strength > drbg_sec_strength(drbg->core->flags))
+ goto dealloc;
+
+ pr_info("DRBG with %s core allocated\n", drbg->core->backend_cra_name);
+
+ return drbg;
+
+dealloc:
+ if (drbg->d_ops)
+ drbg->d_ops->crypto_fini(drbg);
+ drbg_dealloc_state(drbg);
+err:
+ kfree(drbg);
+ return NULL;
+}
+
+void lrng_drng_dealloc(void *drng)
+{
+ struct drbg_state *drbg = (struct drbg_state *)drng;
+
+ drbg_dealloc_state(drbg);
+ kzfree(drbg);
+}
+
+void *lrng_hash_alloc(u8 *hashname, u8 *key, u32 keylen)
+{
+ struct lrng_hash_info *lrng_hash;
+ struct crypto_shash *tfm;
+ int size, ret;
+
+ tfm = crypto_alloc_shash(hashname, 0, 0);
+ if (IS_ERR(tfm)) {
+ pr_err("could not allocate hash %s\n", hashname);
+ return ERR_PTR(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 ERR_PTR(-ENOMEM);
+ }
+
+ lrng_hash->shash.tfm = tfm;
+ lrng_hash->shash.flags = 0x0;
+
+ ret = crypto_shash_setkey(tfm, key, keylen);
+ if (ret && ret != -ENOSYS) {
+ pr_err("could not set the key for MAC\n");
+ crypto_free_shash(tfm);
+ kfree(lrng_hash);
+ return ERR_PTR(ret);
+ }
+
+ return lrng_hash;
+}
+
+u32 lrng_hash_digestsize(void *hash)
+{
+ struct lrng_hash_info *lrng_hash = (struct lrng_hash_info *)hash;
+ struct shash_desc *shash = &lrng_hash->shash;
+
+ return crypto_shash_digestsize(shash->tfm);
+}
+
+int lrng_hash_buffer(void *hash, u8 *inbuf, u32 inbuflen, u8 *digest)
+{
+ struct lrng_hash_info *lrng_hash = (struct lrng_hash_info *)hash;
+ struct shash_desc *shash = &lrng_hash->shash;
+
+ return crypto_shash_digest(shash, inbuf, inbuflen, digest);
+}
--
2.5.5
On Sun, Jun 19, 2016 at 06:00:21PM +0200, Stephan Mueller wrote:
> 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
A web site is not a replacement for a proper commit message.
-Anid
Am Sonntag, 19. Juni 2016, 09:58:55 schrieb Andi Kleen:
Hi Andi,
> On Sun, Jun 19, 2016 at 06:00:21PM +0200, Stephan Mueller wrote:
> > 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
>
> A web site is not a replacement for a proper commit message.
I will provide a complete commit message in the next round.
Thanks.
Ciao
Stephan
On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> 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.
Dunno. It is very similar to existing rng, AFAICT. And at the very
least, constants in existing RNG could be tuned to provide "entropy at
the boot time".
So IMO this should be re-done as tweaks to existing design, not as
completely new RNG.
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
On Sun, Jun 19, 2016 at 3:36 PM, Pavel Machek <[email protected]> wrote:
>> The following patch set provides a different approach to /dev/random ...
>
> Dunno. It is very similar to existing rng, AFAICT.
I do not think so. A lot of the basic principles are the same of course,
but Stephan is suggesting some real changes. On the other hand, I'm
not sure all of them are good ideas & Ted has already incorporated
some into the driver, so it is debatable how much here is really useful.
> And at the very least, constants in existing RNG could be tuned
> to provide "entropy at the boot time".
No, this is a rather hard problem & just tweaking definitely will
not solve it. Ted's patches, Stephan's, mine, the grsecurity
stuff and the kernel hardening project all have things that
might help, but as far as I can see there is no complete
in-kernel solution yet.
Closest thing I have seen to a solution are Denker's suggestions at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
Those, though, require changes to build & installation methods
& it might be hard to get distros & device vendors to do it.
> So IMO this should be re-done as tweaks to existing design, not as
> completely new RNG.
I agree, & I think Stephan has already done some of that.
Am Sonntag, 19. Juni 2016, 21:36:14 schrieb Pavel Machek:
Hi Pavel,
> On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> > 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.
>
> Dunno. It is very similar to existing rng, AFAICT. And at the very
> least, constants in existing RNG could be tuned to provide "entropy at
> the boot time".
The key differences and thus my main concerns I have with the current design
are the following items. If we would change them, it is an intrusive change.
As of now, I have not seen that intrusive changes were accepted. This led me
to develop a competing algorithm.
- Correlation of noise sources: as outlined in [1] chapter 1, the three noise
sources of the legacy /dev/random implementation have a high correlation. Such
correlation is due to the fact that a HID/disk event at the same time produces
an IRQ event. The time stamp (which deliver the majority of entropy) of both
events are correlated. I would think that the maintenance of the fast_pools
partially breaks that correlation to some degree though, yet how much the
correlation is broken is unknown.
- Awarding IRQs only 1/64th bit of entropy compared to HID and disk noise
sources is warranted due to the correlation. As I try to show, IRQs have a
much higher entropy rate than what they are credited currently. But we cannot
set that value higher due to the correlation issue. That means, currently we
prefer desktop machines over server type systems since servers usually have no
HID. In addition, with SSDs or virtio-disks the disk noise source is
deactivated (again, common use cases for servers). Hence, server environments
are heavily penalized. (Note, awarding IRQ events one bit of entropy is the
root cause why my approach claims to be seeded very fast during boot time.
Furthermore, as outlined in [1] chapter 1 and 2, IRQ events are entropic even
in virtual machines which implies that even in VMs, my approach works well.)
- I am not sure the current way of crediting entropy has anything to do with
its entropy. It just happen to underestimate our entropy so it does not hurt.
I see no sensible reason why the calculation of an entropy estimate rests on
the first/second and third derivation of the Jiffies -- the Jiffies hardly
deliver any entropy and therefore why should they be a basis for entropy
calculation?
- There was a debate around my approach assuming one bit of entropy per
received IRQ. I am really wondering about that discussion when there is a much
bigger "forcast" problem with the legacy /dev/random: how can we credit HIDs
up to 11 bits of entropy when the user (a potential adversary) triggers these
events? I am sure I would be shot down with such an approach if I would
deliver that with a new implementation.
- The delivery of entropic data from the input_pool to the (non)blocking_pools
is not atomic (for the lack of better word), i.e. one block of data with a
given entropy content is injected into the (non)blocking_pool where the output
pool is still locked (the user cannot obtain data during that injection time).
With Ted's new patch set, two 64 bit blocks from the fast_pools are injected
into the ChaCha20 DRNG. So, it is clearly better than previously. But still,
with the blocking_pool, we face that issue. The reason for that issue is
outlined in [1] 2.1. In the pathological case with an active attack,
/dev/random could have a security strength of 2 * 128 bits of and not 2^128
bits when reading 128 bits out of it (the numbers are for illustration only,
it is a bit better as /dev/random is woken up at random_read_wakeup_bits
intervals -- but that number can be set to dangerous low levels down to 8
bits).
[1] http://www.chronox.de/lrng/doc/lrng.pdf
Ciao
Stephan
Hi!
> > On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> > > 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.
> >
> > Dunno. It is very similar to existing rng, AFAICT. And at the very
> > least, constants in existing RNG could be tuned to provide "entropy at
> > the boot time".
>
> The key differences and thus my main concerns I have with the current design
> are the following items. If we would change them, it is an intrusive change.
> As of now, I have not seen that intrusive changes were accepted. This led me
> to develop a competing algorithm.
Well, intrusive changes are hard to do, but replacing whole subsystems
is even harder -- and rightly so.
> - There was a debate around my approach assuming one bit of entropy per
> received IRQ. I am really wondering about that discussion when there is a much
> bigger "forcast" problem with the legacy /dev/random: how can we credit HIDs
> up to 11 bits of entropy when the user (a potential adversary) triggers these
> events? I am sure I would be shot down with such an approach if I would
> deliver that with a new implementation.
Well, if you can demonstrate 11 bits is too much, go ahead... I'm sure
that is rather easy to adjust.
But I believe that 1) user is not normally an adversary and 2) the
best thing for him to do would still be "pressing nothing". It will be
hard to press keys (etc) with great enough precision...
Best regards,
Pavel
--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
On Mon, Jun 20, 2016 at 07:51:59AM +0200, Stephan Mueller wrote:
>
> - Correlation of noise sources: as outlined in [1] chapter 1, the three noise
> sources of the legacy /dev/random implementation have a high correlation. Such
> correlation is due to the fact that a HID/disk event at the same time produces
> an IRQ event. The time stamp (which deliver the majority of entropy) of both
> events are correlated. I would think that the maintenance of the fast_pools
> partially breaks that correlation to some degree though, yet how much the
> correlation is broken is unknown.
We add more entropy for disk events only if they are rotational (i.e.,
not flash devices), and the justification for this is Don Davis's
"Cryptographic randomness from air turbulence in disk drives" paper.
There has also been work showing that by measuring disk completion
times, you can actually notice when someone walks by the server
(because the vibrations from footsteps affect disk head settling
times). In fact how you mount HDD's to isolate them from vibration
can make a huge difference to the overall performance of your system.
As far as HID's are concerned, I will note that in 99.99% of the
systems, if you have direct physical access to the system, you
probably are screwed from a security perspective anyway. Yes, one
could imagine systems where the user might have access to keyboard and
the mouse, and not be able to do other interesting things (such as
inserting a BadUSB device into one of the ports, rebooting the system
into single user mode, etc.). But now you have to assume the user can
actually manipulate the input devices down to jiffies 1ms or cycle
counter (nanonsecond) level of granularity...
All of this being said, I will freely admit that the hueristics of
entropy collection is by far one of the weaker aspects of the system.
Ultimately there is no way to be 100% accurate with **any** entropy
system, since ENCRYPT(NSA_KEY, COUNTER++) has zero entropy, but good
luck finding a entropy estimation system that can detect that.
> - The delivery of entropic data from the input_pool to the (non)blocking_pools
> is not atomic (for the lack of better word), i.e. one block of data with a
> given entropy content is injected into the (non)blocking_pool where the output
> pool is still locked (the user cannot obtain data during that injection time).
> With Ted's new patch set, two 64 bit blocks from the fast_pools are injected
> into the ChaCha20 DRNG. So, it is clearly better than previously. But still,
> with the blocking_pool, we face that issue. The reason for that issue is
> outlined in [1] 2.1. In the pathological case with an active attack,
> /dev/random could have a security strength of 2 * 128 bits of and not 2^128
> bits when reading 128 bits out of it (the numbers are for illustration only,
> it is a bit better as /dev/random is woken up at random_read_wakeup_bits
> intervals -- but that number can be set to dangerous low levels down to 8
> bits).
I believe what you are referring to is addressed by the avalanche
reseeding feature. Yes, that can be turned down by
random_read_wakeup_bits, but (a) this requires root (at which point
the game is up), and (b) in practice no one touches that knob. You're
right that it would probably be better to reject attempts to set that
number to too-small a number, or perhaps remove the knob entirely.
Personally, I don't really use /dev/random, nor would I recommend it
for most application programmers. At this point, getrandom(2) really
is the preferred interface unless you have some very specialized
needs.
Cheers,
- Ted
Am Montag, 20. Juni 2016, 11:28:38 schrieb Theodore Ts'o:
Hi Theodore,
> On Mon, Jun 20, 2016 at 07:51:59AM +0200, Stephan Mueller wrote:
> > - Correlation of noise sources: as outlined in [1] chapter 1, the three
> > noise sources of the legacy /dev/random implementation have a high
> > correlation. Such correlation is due to the fact that a HID/disk event at
> > the same time produces an IRQ event. The time stamp (which deliver the
> > majority of entropy) of both events are correlated. I would think that
> > the maintenance of the fast_pools partially breaks that correlation to
> > some degree though, yet how much the correlation is broken is unknown.
>
> We add more entropy for disk events only if they are rotational (i.e.,
> not flash devices), and the justification for this is Don Davis's
> "Cryptographic randomness from air turbulence in disk drives" paper.
> There has also been work showing that by measuring disk completion
> times, you can actually notice when someone walks by the server
> (because the vibrations from footsteps affect disk head settling
> times). In fact how you mount HDD's to isolate them from vibration
> can make a huge difference to the overall performance of your system.
>
> As far as HID's are concerned, I will note that in 99.99% of the
> systems, if you have direct physical access to the system, you
> probably are screwed from a security perspective anyway. Yes, one
> could imagine systems where the user might have access to keyboard and
> the mouse, and not be able to do other interesting things (such as
> inserting a BadUSB device into one of the ports, rebooting the system
> into single user mode, etc.). But now you have to assume the user can
> actually manipulate the input devices down to jiffies 1ms or cycle
> counter (nanonsecond) level of granularity...
>
> All of this being said, I will freely admit that the hueristics of
> entropy collection is by far one of the weaker aspects of the system.
With that being said, wouldn't it make sense to:
- Get rid of the entropy heuristic entirely and just assume a fixed value of
entropy for a given event?
- remove the high-res time stamp and the jiffies collection in
add_disk_randomness and add_input_randomness to not run into the correlation
issue?
- In addition, let us credit the remaining information zero bits of entropy
and just use it to stir the input_pool.
- Conversely, as we now would not have the correlation issue any more, let us
change the add_interrupt_randomness to credit each received interrupt one bit
of entropy or something in this vicinity? Only if random_get_entropy returns
0, let us drop the credited entropy rate to something like 1/10th or 1/20th
bit per event.
> Ultimately there is no way to be 100% accurate with **any** entropy
> system, since ENCRYPT(NSA_KEY, COUNTER++) has zero entropy, but good
> luck finding a entropy estimation system that can detect that.
+1 here
To me, all the entropy heuristic today is only a more elaborate test against
the failure of a noise source. And this is how I use the 1st/2nd/3rd
derivation in my code: it is just a failure test.
Hence, we cannot estimate the entropy level at runtime. All we can do is
having a good conservative estimate. And for such estimate, I feel that
throwing lots of code against that problem is not helpful.
>
> > - The delivery of entropic data from the input_pool to the
> > (non)blocking_pools is not atomic (for the lack of better word), i.e. one
> > block of data with a given entropy content is injected into the
> > (non)blocking_pool where the output pool is still locked (the user cannot
> > obtain data during that injection time). With Ted's new patch set, two 64
> > bit blocks from the fast_pools are injected into the ChaCha20 DRNG. So,
> > it is clearly better than previously. But still, with the blocking_pool,
> > we face that issue. The reason for that issue is outlined in [1] 2.1. In
> > the pathological case with an active attack, /dev/random could have a
> > security strength of 2 * 128 bits of and not 2^128 bits when reading 128
> > bits out of it (the numbers are for illustration only, it is a bit better
> > as /dev/random is woken up at random_read_wakeup_bits intervals -- but
> > that number can be set to dangerous low levels down to 8 bits).
>
> I believe what you are referring to is addressed by the avalanche
> reseeding feature. Yes, that can be turned down by
> random_read_wakeup_bits, but (a) this requires root (at which point
> the game is up), and (b) in practice no one touches that knob. You're
> right that it would probably be better to reject attempts to set that
> number to too-small a number, or perhaps remove the knob entirely.
>
> Personally, I don't really use /dev/random, nor would I recommend it
> for most application programmers. At this point, getrandom(2) really
> is the preferred interface unless you have some very specialized
> needs.
I fully agree. But there are use cases for /dev/random, notably as a seed
source for other DRNG.
>
>
> Cheers,
>
> - Ted
Ciao
Stephan
Am Montag, 20. Juni 2016, 14:44:03 schrieb George Spelvin:
Hi George,
> > With that being said, wouldn't it make sense to:
> >
> > - Get rid of the entropy heuristic entirely and just assume a fixed value
> > of entropy for a given event?
>
> What does that gain you? You can always impose an upper bound, but *some*
> evidence that it's not a metronome is nice to have.
You are right, but that is an online test -- and I suggest we have one.
However, the heuristic with its fraction of bits maintenance and the
asymptotic calculation in credit_entropy_bits is a bit over the top,
considering that we know that the input data is far from accurate.
>
> > - remove the high-res time stamp and the jiffies collection in
> > add_disk_randomness and add_input_randomness to not run into the
> > correlation issue?
>
> Again, you can argue for setting the estimate to zero, but why *remove*
> the timestamp? Maybe you lose nothing,maybe you lose something, but it's
> definitely a monotonic decrease.
The time stamp maintenance is the exact cause for the correlation: one HID
event triggers:
- add_interrupt_randomness which takes high-res time stamp, Jiffies and some
pointers
- add_input_randomness which takes high-res time stamp, Jiffies and HID event
value
The same applies to disk events. My suggestion is to get rid of the double
counting of time stamps for one event.
And I guess I do not need to stress that correlation of data that is supposed
to be entropic is not good :-)
>
> > - In addition, let us credit the remaining information zero bits of
> > entropy
> > and just use it to stir the input_pool.
>
> Unfortunately, that is of limited use. We mustn't remove more bits (of
> data, as well as entropy) from the input pool that there are bits of
> entropy coming in.
I am not saying that we take more bits out of the input pool. All I am
suggesting is to take out the correlation and in the end credit the entropy
source which definitely is available on all systems with higher entropy rates.
>
> So the extra uncounted entropy never goes anywhere and does very little
> good. So any time the input pool is "full" (by counted entropy), then the
> uncounted entropy has been squeezed out and thrown away.
>
> > - Conversely, as we now would not have the correlation issue any more, let
> > us change the add_interrupt_randomness to credit each received interrupt
> > one bit of entropy or something in this vicinity? Only if
> > random_get_entropy returns 0, let us drop the credited entropy rate to
> > something like 1/10th or 1/20th bit per event.
>
> Baically, do you have a convincing argument that *eery* interrupt has
> this? Even those coming from strongly periodic signals like audio DMA
> buffer fills?
I am sure I cannot be convincing as you like it because in the end, entropy is
relative.
But look at my measurements for my LRNG, tested with and without tickless
kernel. I see timing variations which ten times the entropy rate I suggest
here. Besides, the analysis I did for my Jitter RNG cannot be discarded
either.
>
> > Hence, we cannot estimate the entropy level at runtime. All we can do is
> > having a good conservative estimate. And for such estimate, I feel that
> > throwing lots of code against that problem is not helpful.
>
> I agree that the efficiency constraints preclude having a really
> good solution. But is it worth giving up?
>
> For example, suppose wecome up with a decent estimator, but only use it
> when we're low on entropy. When things are comfortable, underestimate.
>
> For example, a low-overhead entropy estimator can be derived from
> Maurer's universal test. There are all sort of conditions required to
I am not suggesting any test. Entropy cannot be measured. All we can measure
are statistics. And I cannot see why one statistical test is better than the
other. Thus, let us have the easiest statistical test there is: use a fixed,
but appropriate entropy value for one event and be done with it.
All that statistical tests could be used for are health tests of the noise
source.
> get an accurate measurement of entropy, but violating them produces
> a conservative *underestimate*, which is just fine for an on-line
> entropy estimator. You can hash non-binary inputs to save table space;
> collisions cause an entropy underestimate. You can use a limited-range
> age counter (e.g. 1 byte); wraps cause entropy underestimate. You need
> to initialize the history table before measurements are accurate, but
> initializing everything to zero causes an initial entropy underestimate.
Ciao
Stephan
> With that being said, wouldn't it make sense to:
>
> - Get rid of the entropy heuristic entirely and just assume a fixed value of
> entropy for a given event?
What does that gain you? You can always impose an upper bound, but *some*
evidence that it's not a metronome is nice to have.
> - remove the high-res time stamp and the jiffies collection in
> add_disk_randomness and add_input_randomness to not run into the correlation
> issue?
Again, you can argue for setting the estimate to zero, but why *remove*
the timestamp? Maybe you lose nothing,maybe you lose something, but it's definitely
a monotonic decrease.
> - In addition, let us credit the remaining information zero bits of entropy
> and just use it to stir the input_pool.
Unfortunately, that is of limited use. We mustn't remove more bits (of data,
as well as entropy) from the input pool that there are bits of entropy coming in.
So the extra uncounted entropy never goes anywhere and does very little good.
So any time the input pool is "full" (by counted entropy), then the uncounted
entropy has been squeezed out and thrown away.
> - Conversely, as we now would not have the correlation issue any more, let us
> change the add_interrupt_randomness to credit each received interrupt one bit
> of entropy or something in this vicinity? Only if random_get_entropy returns
> 0, let us drop the credited entropy rate to something like 1/10th or 1/20th
> bit per event.
Baically, do you have a convincing argument that *eery* interrupt has
this? Even those coming from strongly periodic signals like audio DMA
buffer fills?
> Hence, we cannot estimate the entropy level at runtime. All we can do is
> having a good conservative estimate. And for such estimate, I feel that
> throwing lots of code against that problem is not helpful.
I agree that the efficiency constraints preclude having a really
good solution. But is it worth giving up?
For example, suppose wecome up with a decent estimator, but only use it
when we're low on entropy. When things are comfortable, underestimate.
For example, a low-overhead entropy estimator can be derived from
Maurer's universal test. There are all sort of conditions required to
get an accurate measurement of entropy, but violating them produces
a conservative *underestimate*, which is just fine for an on-line
entropy estimator. You can hash non-binary inputs to save table space;
collisions cause an entropy underestimate. You can use a limited-range
age counter (e.g. 1 byte); wraps cause entropy underestimate. You need
to initialize the history table before measurements are accurate, but
initializing everything to zero causes an initial entropy underestimate.
On Mon, Jun 20, 2016 at 09:00:49PM +0200, Stephan Mueller wrote:
>
> The time stamp maintenance is the exact cause for the correlation: one HID
> event triggers:
>
> - add_interrupt_randomness which takes high-res time stamp, Jiffies and some
> pointers
>
> - add_input_randomness which takes high-res time stamp, Jiffies and HID event
> value
>
> The same applies to disk events. My suggestion is to get rid of the double
> counting of time stamps for one event.
>
> And I guess I do not need to stress that correlation of data that is supposed
> to be entropic is not good :-)
What is your concern, specifically? If it is in the entropy
accounting, there is more entropy in HID event interrupts, so I don't
think adding the extra 1/64th bit of entropy is going to be problematic.
If it is that there are two timestamps that are closely correleated
being added into the pool, the add_interrupt_randomness() path is
going to mix that timestamp with the interrupt timings from 63 other
interrupts before it is mixed into the input pool, while the
add_input_randomness() mixes it directly into the pool. So if you
think there is a way this could be leveraged into attack, please give
specifics --- but I think we're on pretty solid ground here.
Cheers,
- Ted
Am Dienstag, 21. Juni 2016, 01:12:55 schrieb Theodore Ts'o:
Hi Theodore,
> On Mon, Jun 20, 2016 at 09:00:49PM +0200, Stephan Mueller wrote:
> > The time stamp maintenance is the exact cause for the correlation: one HID
> > event triggers:
> >
> > - add_interrupt_randomness which takes high-res time stamp, Jiffies and
> > some pointers
> >
> > - add_input_randomness which takes high-res time stamp, Jiffies and HID
> > event value
> >
> > The same applies to disk events. My suggestion is to get rid of the double
> > counting of time stamps for one event.
> >
> > And I guess I do not need to stress that correlation of data that is
> > supposed to be entropic is not good :-)
>
> What is your concern, specifically? If it is in the entropy
> accounting, there is more entropy in HID event interrupts, so I don't
> think adding the extra 1/64th bit of entropy is going to be problematic.
My concern is that interrupts have *much* more entropy than 1/64th. With a
revaluation of the assumed entropy in interrupts, we will serve *all* systems
much better and not just systems with HID.
As said, I think we heavily penalize server type and VM environments against
desktop systems by crediting entropy in large scale to HID and conversely to a
much lesser degree to interrupts.
>
> If it is that there are two timestamps that are closely correleated
> being added into the pool, the add_interrupt_randomness() path is
> going to mix that timestamp with the interrupt timings from 63 other
> interrupts before it is mixed into the input pool, while the
> add_input_randomness() mixes it directly into the pool. So if you
> think there is a way this could be leveraged into attack, please give
> specifics --- but I think we're on pretty solid ground here.
I am not saying that there is an active attack vector. All I want is to
revalue the entropy in one interrupt which can only be done if we drop the HID
time stamp collection.
Ciao
Stephan
On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]> wrote:
>> Personally, I don't really use /dev/random, nor would I recommend it
>> for most application programmers. At this point, getrandom(2) really
>> is the preferred interface unless you have some very specialized
>> needs.
> I fully agree. But there are use cases for /dev/random, notably as a seed
> source for other DRNG.
Is that really the case? I believe all DRNG's use /dev/urandom anyway
for seeding since they cannot afford indeterminate blocking. It would
be a gain for everyone if /dev/random was the same as /dev/urandom in
Linux.
regards,
Nikos
Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
Hi Nikos,
> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]>
wrote:
> >> Personally, I don't really use /dev/random, nor would I recommend it
> >> for most application programmers. At this point, getrandom(2) really
> >> is the preferred interface unless you have some very specialized
> >> needs.
> >
> > I fully agree. But there are use cases for /dev/random, notably as a seed
> > source for other DRNG.
>
> Is that really the case? I believe all DRNG's use /dev/urandom anyway
> for seeding since they cannot afford indeterminate blocking. It would
> be a gain for everyone if /dev/random was the same as /dev/urandom in
> Linux.
For standard approaches, this is true. But there are regulations, notably in
the German realm, /dev/random shall be used, at least partially (see AIS
20/31).
Ciao
Stephan
Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:
Hi Austin,
> On 2016-06-21 03:32, Stephan Mueller wrote:
> > Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
> >
> > Hi Nikos,
> >
> >> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]>
> >
> > wrote:
> >>>> Personally, I don't really use /dev/random, nor would I recommend it
> >>>> for most application programmers. At this point, getrandom(2) really
> >>>> is the preferred interface unless you have some very specialized
> >>>> needs.
> >>>
> >>> I fully agree. But there are use cases for /dev/random, notably as a
> >>> seed
> >>> source for other DRNG.
> >>
> >> Is that really the case? I believe all DRNG's use /dev/urandom anyway
> >> for seeding since they cannot afford indeterminate blocking. It would
> >> be a gain for everyone if /dev/random was the same as /dev/urandom in
> >> Linux.
> >
> > For standard approaches, this is true. But there are regulations, notably
> > in the German realm, /dev/random shall be used, at least partially (see
> > AIS 20/31).
>
> Which just goes to show how utterly stupid some people who write laws
> and regulations are. Saying specifically that '/dev/random shall be
> used' does not enforce any improvement of entrophic value in the data at
> all, it just coincidentally improves the theoretical quality of the data
> because of how Linux and some legacy UNIX systems are designed. This
> 'regulation' already provides zero benefit other than a placebo effect
> on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
> derivatives, as /dev/random and /dev/urandom point to the same thing
> there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
> uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
> does likewise (although they use a design based on yarrow).
It is NOT utterly stupid, you should listen to the reasons. The core reason is
explained with the following analogy:
/dev/urandom, for a short period of time, operates as a DRNG. For the sake of
discussion, let us assume that it is a DRNG which is, for the sake of
discussion, seeded with 256 bits of entropy.
Now, you pull 256 bits out of it, you have 256 bits of entropy.
You pull again 256 bit out of it -- what entropy do you have? You do NOT have
*again* 256 bits of entropy. All you can say is the entire generated 512 bits
have collectively 256 bits of entropy. And so on and so forth.
Now, if you want to say that your newly spawned DRNG is seeded with X amount
of entropy, the DRNG nature of /dev/urandom makes such a statement a
challenge. The easy way out of the challenge is to use /dev/random (I am aware
of the fact that the DRNG has a computational strength, but it is not, well,
entropy).
In addition, when using /dev/urandom, you have to show that at the time you
seed the DRNG, it is fully seeded. That is a challenge at boot time - a
challenge this entire thread revolves around. Yes, getrandom(2) is the way
out, but not everybody uses it. Again, /dev/random does NOT have this
challenge.
>
> On top of that though, just because some poorly thought out standard
> requires it's usage doesn't mean we have to work based on that.
I cannot concur.
Ciao
Stephan
On 2016-06-21 03:32, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
>
> Hi Nikos,
>
>> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]>
> wrote:
>>>> Personally, I don't really use /dev/random, nor would I recommend it
>>>> for most application programmers. At this point, getrandom(2) really
>>>> is the preferred interface unless you have some very specialized
>>>> needs.
>>>
>>> I fully agree. But there are use cases for /dev/random, notably as a seed
>>> source for other DRNG.
>>
>> Is that really the case? I believe all DRNG's use /dev/urandom anyway
>> for seeding since they cannot afford indeterminate blocking. It would
>> be a gain for everyone if /dev/random was the same as /dev/urandom in
>> Linux.
>
> For standard approaches, this is true. But there are regulations, notably in
> the German realm, /dev/random shall be used, at least partially (see AIS
> 20/31).
Which just goes to show how utterly stupid some people who write laws
and regulations are. Saying specifically that '/dev/random shall be
used' does not enforce any improvement of entrophic value in the data at
all, it just coincidentally improves the theoretical quality of the data
because of how Linux and some legacy UNIX systems are designed. This
'regulation' already provides zero benefit other than a placebo effect
on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
derivatives, as /dev/random and /dev/urandom point to the same thing
there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
does likewise (although they use a design based on yarrow).
On top of that though, just because some poorly thought out standard
requires it's usage doesn't mean we have to work based on that.
On 2016-06-21 12:28, Stephan Mueller wrote:
> Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:
>
> Hi Austin,
>
>> On 2016-06-21 03:32, Stephan Mueller wrote:
>>> Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
>>>
>>> Hi Nikos,
>>>
>>>> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]>
>>>
>>> wrote:
>>>>>> Personally, I don't really use /dev/random, nor would I recommend it
>>>>>> for most application programmers. At this point, getrandom(2) really
>>>>>> is the preferred interface unless you have some very specialized
>>>>>> needs.
>>>>>
>>>>> I fully agree. But there are use cases for /dev/random, notably as a
>>>>> seed
>>>>> source for other DRNG.
>>>>
>>>> Is that really the case? I believe all DRNG's use /dev/urandom anyway
>>>> for seeding since they cannot afford indeterminate blocking. It would
>>>> be a gain for everyone if /dev/random was the same as /dev/urandom in
>>>> Linux.
>>>
>>> For standard approaches, this is true. But there are regulations, notably
>>> in the German realm, /dev/random shall be used, at least partially (see
>>> AIS 20/31).
>>
>> Which just goes to show how utterly stupid some people who write laws
>> and regulations are. Saying specifically that '/dev/random shall be
>> used' does not enforce any improvement of entrophic value in the data at
>> all, it just coincidentally improves the theoretical quality of the data
>> because of how Linux and some legacy UNIX systems are designed. This
>> 'regulation' already provides zero benefit other than a placebo effect
>> on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
>> derivatives, as /dev/random and /dev/urandom point to the same thing
>> there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
>> uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
>> does likewise (although they use a design based on yarrow).
>
> It is NOT utterly stupid, you should listen to the reasons.
I'm not commenting about them wanting cryptographically secure entropy.
My statement about the intelligence of the people who wrote the standard
was commenting on their saying '/dev/random shall be used' instead of 'a
cryptographically secure entropy source shall be used'. POSIX requires
that the first statement imply the second, but the second does not
require the first. Their choice to use the first indicates that they
assume this will be the only implementation that will ever matter, and
that POSIX systems will be the only thing anyone using the standard
cares about, both of which are inherently poor assumptions outside of a
completely closed system. Most standards proposed or mandated by
bureaucracies have similar issues making bad assumptions about the
context in which they will be used.
> The core reason is
> explained with the following analogy:
>
> /dev/urandom, for a short period of time, operates as a DRNG. For the sake of
> discussion, let us assume that it is a DRNG which is, for the sake of
> discussion, seeded with 256 bits of entropy.
>
> Now, you pull 256 bits out of it, you have 256 bits of entropy.
>
> You pull again 256 bit out of it -- what entropy do you have? You do NOT have
> *again* 256 bits of entropy. All you can say is the entire generated 512 bits
> have collectively 256 bits of entropy. And so on and so forth.
>
> Now, if you want to say that your newly spawned DRNG is seeded with X amount
> of entropy, the DRNG nature of /dev/urandom makes such a statement a
> challenge. The easy way out of the challenge is to use /dev/random (I am aware
> of the fact that the DRNG has a computational strength, but it is not, well,
> entropy).
>
> In addition, when using /dev/urandom, you have to show that at the time you
> seed the DRNG, it is fully seeded. That is a challenge at boot time - a
> challenge this entire thread revolves around. Yes, getrandom(2) is the way
> out, but not everybody uses it. Again, /dev/random does NOT have this
> challenge.
The fact that that's how /dev/urandom works is a result of the
implementation, I already listed at least 3 UNIX derivatives that do not
work this way and provide cryptographically secure entropy from the same
source stream for both /dev/random and /dev/urandom. Changing this on
Linux would not break backwards compatibility as long as we provide
sufficient entropy via /dev/random, because nobody depends on it
blocking for anything other than ensuring they get good entropy, so if
it always returns good cryptographically secure entropy, we never need
to block unless the generator hasn't yet been seeded. Now, on top of
that, there's still no absolute guarantee that what you get from
/dev/random is actually cryptographically secure, but that's a separate
issue.
Am Dienstag, 21. Juni 2016, 14:22:48 schrieb Austin S. Hemmelgarn:
Hi Austin,
> On 2016-06-21 12:28, Stephan Mueller wrote:
> > Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:
> >
> > Hi Austin,
> >
> >> On 2016-06-21 03:32, Stephan Mueller wrote:
> >>> Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
> >>>
> >>> Hi Nikos,
> >>>
> >>>> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller <[email protected]>
> >>>
> >>> wrote:
> >>>>>> Personally, I don't really use /dev/random, nor would I recommend it
> >>>>>> for most application programmers. At this point, getrandom(2) really
> >>>>>> is the preferred interface unless you have some very specialized
> >>>>>> needs.
> >>>>>
> >>>>> I fully agree. But there are use cases for /dev/random, notably as a
> >>>>> seed
> >>>>> source for other DRNG.
> >>>>
> >>>> Is that really the case? I believe all DRNG's use /dev/urandom anyway
> >>>> for seeding since they cannot afford indeterminate blocking. It would
> >>>> be a gain for everyone if /dev/random was the same as /dev/urandom in
> >>>> Linux.
> >>>
> >>> For standard approaches, this is true. But there are regulations,
> >>> notably
> >>> in the German realm, /dev/random shall be used, at least partially (see
> >>> AIS 20/31).
> >>
> >> Which just goes to show how utterly stupid some people who write laws
> >> and regulations are. Saying specifically that '/dev/random shall be
> >> used' does not enforce any improvement of entrophic value in the data at
> >> all, it just coincidentally improves the theoretical quality of the data
> >> because of how Linux and some legacy UNIX systems are designed. This
> >> 'regulation' already provides zero benefit other than a placebo effect
> >> on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
> >> derivatives, as /dev/random and /dev/urandom point to the same thing
> >> there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
> >> uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
> >> does likewise (although they use a design based on yarrow).
> >
> > It is NOT utterly stupid, you should listen to the reasons.
>
> I'm not commenting about them wanting cryptographically secure entropy.
> My statement about the intelligence of the people who wrote the standard
> was commenting on their saying '/dev/random shall be used' instead of 'a
It behooves if you read the documents before making statements! AIS 20/31 does
not require /dev/random in the documentation, but specifies a number of
requirements for a seed source (NTG.1, PTG.[1|2|3]). And /dev/random happens
to be an NTG.1 whereas /dev/urandom is not.
> cryptographically secure entropy source shall be used'. POSIX requires
> that the first statement imply the second, but the second does not
> require the first. Their choice to use the first indicates that they
> assume this will be the only implementation that will ever matter, and
> that POSIX systems will be the only thing anyone using the standard
> cares about, both of which are inherently poor assumptions outside of a
> completely closed system. Most standards proposed or mandated by
> bureaucracies have similar issues making bad assumptions about the
> context in which they will be used.
>
> > The core reason is
> > explained with the following analogy:
> >
> > /dev/urandom, for a short period of time, operates as a DRNG. For the sake
> > of discussion, let us assume that it is a DRNG which is, for the sake of
> > discussion, seeded with 256 bits of entropy.
> >
> > Now, you pull 256 bits out of it, you have 256 bits of entropy.
> >
> > You pull again 256 bit out of it -- what entropy do you have? You do NOT
> > have *again* 256 bits of entropy. All you can say is the entire generated
> > 512 bits have collectively 256 bits of entropy. And so on and so forth.
> >
> > Now, if you want to say that your newly spawned DRNG is seeded with X
> > amount of entropy, the DRNG nature of /dev/urandom makes such a statement
> > a challenge. The easy way out of the challenge is to use /dev/random (I
> > am aware of the fact that the DRNG has a computational strength, but it
> > is not, well, entropy).
> >
> > In addition, when using /dev/urandom, you have to show that at the time
> > you
> > seed the DRNG, it is fully seeded. That is a challenge at boot time - a
> > challenge this entire thread revolves around. Yes, getrandom(2) is the way
> > out, but not everybody uses it. Again, /dev/random does NOT have this
> > challenge.
>
> The fact that that's how /dev/urandom works is a result of the
> implementation, I already listed at least 3 UNIX derivatives that do not
> work this way and provide cryptographically secure entropy from the same
> source stream for both /dev/random and /dev/urandom. Changing this on
> Linux would not break backwards compatibility as long as we provide
> sufficient entropy via /dev/random, because nobody depends on it
> blocking for anything other than ensuring they get good entropy, so if
> it always returns good cryptographically secure entropy, we never need
> to block unless the generator hasn't yet been seeded. Now, on top of
> that, there's still no absolute guarantee that what you get from
> /dev/random is actually cryptographically secure, but that's a separate
> issue.
I am not sure what your point is, so let us leave it at that.
Ciao
Stephan