[PATCH v3 0/8] Rework random blocking

[PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

This makes two major semantic changes to Linux's random APIs:

It adds getentropy(..., GRND_INSECURE).  This causes getentropy to
always return *something*.  There is no guarantee whatsoever that
the result will be cryptographically random or even unique, but the
kernel will give the best quality random output it can.  The name is
a big hint: the resulting output is INSECURE.

The purpose of this is to allow programs that genuinely want
best-effort entropy to get it without resorting to /dev/urandom.
Plenty of programs do this because they need to do *something*
during boot and they can't afford to wait.  Calling it "INSECURE" is
probably the best we can do to discourage using this API for things
that need security.

This series also removes the blocking pool and makes /dev/random
work just like getentropy(..., 0) and makes GRND_RANDOM a no-op.  I
believe that Linux's blocking pool has outlived its usefulness.
Linux's CRNG generates output that is good enough to use even for
key generation.  The blocking pool is not stronger in any material
way, and keeping it around requires a lot of infrastructure of
dubious value.

This series should not break any existing programs.  /dev/urandom is
unchanged.  /dev/random will still block just after booting, but it
will block less than it used to.  getentropy() with existing flags
will return output that is, for practical purposes, just as strong
as before.

There are some open questions and future work here:

Should the kernel provide an interface to get software-generated
"true random" numbers?  I can think of only one legitimate reason to
use such an interface: compliance with government standards.  If the
kernel provides such an interface going forward, I think it should
be a brand new character device, and it should have a default mode
0440 or similar.  Software-generated "true random numbers" are a
very limited resource, and resource exhaustion is a big deal.  Ask
anyone who has twiddled their thumbs while waiting for gnupg to
generate a key.  If we think the kernel might do such a thing, then
patches 5-8 could be tabled for now.

Alternatively, perhaps the kernel should instead provide a
privileged interface to read out raw samples from the various
entropy sources, and users who care could have a user daemon that
does something intelligent with them.  This would push the mess of
trying to comply with whatever standards are involved to userspace.
Userspace could then export "true randomness" via CUSE if it is so
inclined, or could have a socket with a well-known name, or whatever
else seems appropriate.

I think that each available hwrng device should have its own
character device, which will make it much easier to use sensibly
from user mode.  But I don't think this series needs to block on
this.

Changes from v2:
 - Fix some bugs in the conditions that cause warnings.  Patch 2 is new.
 - Rebase to Linus' tree today.  This didn't change anything.

Changes from v1:
 - Rebased to v5.3.  No other changes.

Andy Lutomirski (8):
  random: Don't wake crng_init_wait when crng_init == 1
  random: Add a urandom_read_nowait() for random APIs that don't warn
  random: Add GRND_INSECURE to return best-effort non-cryptographic
    bytes
  random: Ignore GRND_RANDOM in getentropy(2)
  random: Make /dev/random be almost like /dev/urandom
  random: Remove the blocking pool
  random: Delete code to pull data into pools
  random: Remove kernel.random.read_wakeup_threshold

 drivers/char/random.c       | 245 +++++-------------------------------
 include/uapi/linux/random.h |   4 +-
 2 files changed, 37 insertions(+), 212 deletions(-)

-- 
2.23.0

[PATCH v3 1/8] random: Don't wake crng_init_wait when crng_init == 1

[Andy Lutomirski]

crng_init_wait is only used to wayt for crng_init to be set to 2, so
there's no point to waking it when crng_init is set to 1.  Remove the
unnecessary wake_up_interruptible() call.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index cda12933a17d..c6252a3a4aec 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -946,7 +946,6 @@ static int crng_fast_load(const char *cp, size_t len)
 	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
 		invalidate_batched_entropy();
 		crng_init = 1;
-		wake_up_interruptible(&crng_init_wait);
 		pr_notice("random: fast init done\n");
 	}
 	return 1;
-- 
2.23.0

[PATCH v3 2/8] random: Add a urandom_read_nowait() for random APIs that don't warn

[Andy Lutomirski]

/dev/random and getrandom() never warn.  Split the meat of
urandom_read() into urandom_read_nowarn() and leave the warning code
in urandom_read().

This has no effect on kernel behavior, but it makes subsequent
patches more straightforward.  It also makes the fact that
getrandom() never warns more obvious.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index c6252a3a4aec..7b46751772e5 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2018,12 +2018,23 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 	return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes);
 }
 
+static ssize_t
+urandom_read_nowarn(struct file *file, char __user *buf, size_t nbytes,
+		    loff_t *ppos)
+{
+	int ret;
+
+	nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3));
+	ret = extract_crng_user(buf, nbytes);
+	trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool));
+	return ret;
+}
+
 static ssize_t
 urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 {
 	unsigned long flags;
 	static int maxwarn = 10;
-	int ret;
 
 	if (!crng_ready() && maxwarn > 0) {
 		maxwarn--;
@@ -2035,10 +2046,8 @@ urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 		crng_init_cnt = 0;
 		spin_unlock_irqrestore(&primary_crng.lock, flags);
 	}
-	nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3));
-	ret = extract_crng_user(buf, nbytes);
-	trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool));
-	return ret;
+
+	return urandom_read_nowarn(file, buf, nbytes, ppos);
 }
 
 static __poll_t
@@ -2200,7 +2209,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 		if (unlikely(ret))
 			return ret;
 	}
-	return urandom_read(NULL, buf, count, NULL);
+	return urandom_read_nowarn(NULL, buf, count, NULL);
 }
 
 /********************************************************************
-- 
2.23.0

[PATCH v3 3/8] random: Add GRND_INSECURE to return best-effort non-cryptographic bytes

[Andy Lutomirski]

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c       | 11 +++++++++--
 include/uapi/linux/random.h |  2 ++
 2 files changed, 11 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 7b46751772e5..675b8a48e18a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2193,7 +2193,14 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 {
 	int ret;
 
-	if (flags & ~(GRND_NONBLOCK|GRND_RANDOM))
+	if (flags & ~(GRND_NONBLOCK|GRND_RANDOM|GRND_INSECURE))
+		return -EINVAL;
+
+	/*
+	 * Requesting insecure and blocking randomness at the same time makes
+	 * no sense.
+	 */
+	if ((flags & (GRND_INSECURE|GRND_RANDOM)) == (GRND_INSECURE|GRND_RANDOM))
 		return -EINVAL;
 
 	if (count > INT_MAX)
@@ -2202,7 +2209,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 	if (flags & GRND_RANDOM)
 		return _random_read(flags & GRND_NONBLOCK, buf, count);
 
-	if (!crng_ready()) {
+	if (!(flags & GRND_INSECURE) && !crng_ready()) {
 		if (flags & GRND_NONBLOCK)
 			return -EAGAIN;
 		ret = wait_for_random_bytes();
diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h
index 26ee91300e3e..c092d20088d3 100644
--- a/include/uapi/linux/random.h
+++ b/include/uapi/linux/random.h
@@ -49,8 +49,10 @@ struct rand_pool_info {
  *
  * GRND_NONBLOCK	Don't block and return EAGAIN instead
  * GRND_RANDOM		Use the /dev/random pool instead of /dev/urandom
+ * GRND_INSECURE	Return non-cryptographic random bytes
  */
 #define GRND_NONBLOCK	0x0001
 #define GRND_RANDOM	0x0002
+#define GRND_INSECURE	0x0004
 
 #endif /* _UAPI_LINUX_RANDOM_H */
-- 
2.23.0

[PATCH v3 4/8] random: Ignore GRND_RANDOM in getentropy(2)

[Andy Lutomirski]

The separate blocking pool is going away.  Start by ignoring
GRND_RANDOM in getentropy(2).

This should not materially break any API.  Any code that worked
without this change should work at least as well with this change.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c       | 3 ---
 include/uapi/linux/random.h | 2 +-
 2 files changed, 1 insertion(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 675b8a48e18a..c0a3032b30ca 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -2206,9 +2206,6 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 	if (count > INT_MAX)
 		count = INT_MAX;
 
-	if (flags & GRND_RANDOM)
-		return _random_read(flags & GRND_NONBLOCK, buf, count);
-
 	if (!(flags & GRND_INSECURE) && !crng_ready()) {
 		if (flags & GRND_NONBLOCK)
 			return -EAGAIN;
diff --git a/include/uapi/linux/random.h b/include/uapi/linux/random.h
index c092d20088d3..dcc1b3e6106f 100644
--- a/include/uapi/linux/random.h
+++ b/include/uapi/linux/random.h
@@ -48,7 +48,7 @@ struct rand_pool_info {
  * Flags for getrandom(2)
  *
  * GRND_NONBLOCK	Don't block and return EAGAIN instead
- * GRND_RANDOM		Use the /dev/random pool instead of /dev/urandom
+ * GRND_RANDOM		No effect
  * GRND_INSECURE	Return non-cryptographic random bytes
  */
 #define GRND_NONBLOCK	0x0001
-- 
2.23.0

[PATCH v3 5/8] random: Make /dev/random be almost like /dev/urandom

[Andy Lutomirski]

This patch changes the read semantics of /dev/random to be the same
as /dev/urandom except that reads will block until the CRNG is
ready.

None of the cleanups that this enables have been done yet.  As a
result, this gives a warning about an unused function.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 55 +++++++++++--------------------------------
 1 file changed, 14 insertions(+), 41 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index c0a3032b30ca..cf131f5989a1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -354,7 +354,6 @@
 #define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
 #define OUTPUT_POOL_SHIFT	10
 #define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
-#define SEC_XFER_SIZE		512
 #define EXTRACT_SIZE		10
 
 
@@ -803,7 +802,6 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 		if (entropy_bits >= random_read_wakeup_bits &&
 		    wq_has_sleeper(&random_read_wait)) {
 			wake_up_interruptible(&random_read_wait);
-			kill_fasync(&fasync, SIGIO, POLL_IN);
 		}
 		/* If the input pool is getting full, and the blocking
 		 * pool has room, send some entropy to the blocking
@@ -1031,6 +1029,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 		crng_init = 2;
 		process_random_ready_list();
 		wake_up_interruptible(&crng_init_wait);
+		kill_fasync(&fasync, SIGIO, POLL_IN);
 		pr_notice("random: crng init done\n");
 		if (unseeded_warning.missed) {
 			pr_notice("random: %d get_random_xx warning(s) missed "
@@ -1981,43 +1980,6 @@ void rand_initialize_disk(struct gendisk *disk)
 }
 #endif
 
-static ssize_t
-_random_read(int nonblock, char __user *buf, size_t nbytes)
-{
-	ssize_t n;
-
-	if (nbytes == 0)
-		return 0;
-
-	nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
-	while (1) {
-		n = extract_entropy_user(&blocking_pool, buf, nbytes);
-		if (n < 0)
-			return n;
-		trace_random_read(n*8, (nbytes-n)*8,
-				  ENTROPY_BITS(&blocking_pool),
-				  ENTROPY_BITS(&input_pool));
-		if (n > 0)
-			return n;
-
-		/* Pool is (near) empty.  Maybe wait and retry. */
-		if (nonblock)
-			return -EAGAIN;
-
-		wait_event_interruptible(random_read_wait,
-		    blocking_pool.initialized &&
-		    (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits));
-		if (signal_pending(current))
-			return -ERESTARTSYS;
-	}
-}
-
-static ssize_t
-random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
-{
-	return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes);
-}
-
 static ssize_t
 urandom_read_nowarn(struct file *file, char __user *buf, size_t nbytes,
 		    loff_t *ppos)
@@ -2050,15 +2012,26 @@ urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 	return urandom_read_nowarn(file, buf, nbytes, ppos);
 }
 
+static ssize_t
+random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
+{
+	int ret;
+
+	ret = wait_for_random_bytes();
+	if (ret != 0)
+		return ret;
+	return urandom_read_nowarn(file, buf, nbytes, ppos);
+}
+
 static __poll_t
 random_poll(struct file *file, poll_table * wait)
 {
 	__poll_t mask;
 
-	poll_wait(file, &random_read_wait, wait);
+	poll_wait(file, &crng_init_wait, wait);
 	poll_wait(file, &random_write_wait, wait);
 	mask = 0;
-	if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits)
+	if (crng_ready())
 		mask |= EPOLLIN | EPOLLRDNORM;
 	if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits)
 		mask |= EPOLLOUT | EPOLLWRNORM;
-- 
2.23.0

[PATCH v3 6/8] random: Remove the blocking pool

[Andy Lutomirski]

There is no longer any interface to read data from the blocking
pool, so remove it.

This enables quite a bit of code deletion, much of which will be
done in subsequent patches.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 106 ------------------------------------------
 1 file changed, 106 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index cf131f5989a1..b4f834893d9d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -470,7 +470,6 @@ static const struct poolinfo {
 /*
  * Static global variables
  */
-static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
 static struct fasync_struct *fasync;
 
@@ -530,7 +529,6 @@ struct entropy_store {
 	__u32 *pool;
 	const char *name;
 	struct entropy_store *pull;
-	struct work_struct push_work;
 
 	/* read-write data: */
 	unsigned long last_pulled;
@@ -549,9 +547,7 @@ static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
 				size_t nbytes, int fips);
 
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r);
-static void push_to_pool(struct work_struct *work);
 static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy;
-static __u32 blocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy;
 
 static struct entropy_store input_pool = {
 	.poolinfo = &poolinfo_table[0],
@@ -560,16 +556,6 @@ static struct entropy_store input_pool = {
 	.pool = input_pool_data
 };
 
-static struct entropy_store blocking_pool = {
-	.poolinfo = &poolinfo_table[1],
-	.name = "blocking",
-	.pull = &input_pool,
-	.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
-	.pool = blocking_pool_data,
-	.push_work = __WORK_INITIALIZER(blocking_pool.push_work,
-					push_to_pool),
-};
-
 static __u32 const twist_table[8] = {
 	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
@@ -765,15 +751,11 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 		entropy_count = 0;
 	} else if (entropy_count > pool_size)
 		entropy_count = pool_size;
-	if ((r == &blocking_pool) && !r->initialized &&
-	    (entropy_count >> ENTROPY_SHIFT) > 128)
-		has_initialized = 1;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
 	if (has_initialized) {
 		r->initialized = 1;
-		wake_up_interruptible(&random_read_wait);
 		kill_fasync(&fasync, SIGIO, POLL_IN);
 	}
 
@@ -782,7 +764,6 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 
 	if (r == &input_pool) {
 		int entropy_bits = entropy_count >> ENTROPY_SHIFT;
-		struct entropy_store *other = &blocking_pool;
 
 		if (crng_init < 2) {
 			if (entropy_bits < 128)
@@ -790,27 +771,6 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 			crng_reseed(&primary_crng, r);
 			entropy_bits = r->entropy_count >> ENTROPY_SHIFT;
 		}
-
-		/* initialize the blocking pool if necessary */
-		if (entropy_bits >= random_read_wakeup_bits &&
-		    !other->initialized) {
-			schedule_work(&other->push_work);
-			return;
-		}
-
-		/* should we wake readers? */
-		if (entropy_bits >= random_read_wakeup_bits &&
-		    wq_has_sleeper(&random_read_wait)) {
-			wake_up_interruptible(&random_read_wait);
-		}
-		/* If the input pool is getting full, and the blocking
-		 * pool has room, send some entropy to the blocking
-		 * pool.
-		 */
-		if (!work_pending(&other->push_work) &&
-		    (ENTROPY_BITS(r) > 6 * r->poolinfo->poolbytes) &&
-		    (ENTROPY_BITS(other) <= 6 * other->poolinfo->poolbytes))
-			schedule_work(&other->push_work);
 	}
 }
 
@@ -1422,22 +1382,6 @@ static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 	credit_entropy_bits(r, bytes*8);
 }
 
-/*
- * Used as a workqueue function so that when the input pool is getting
- * full, we can "spill over" some entropy to the output pools.  That
- * way the output pools can store some of the excess entropy instead
- * of letting it go to waste.
- */
-static void push_to_pool(struct work_struct *work)
-{
-	struct entropy_store *r = container_of(work, struct entropy_store,
-					      push_work);
-	BUG_ON(!r);
-	_xfer_secondary_pool(r, random_read_wakeup_bits/8);
-	trace_push_to_pool(r->name, r->entropy_count >> ENTROPY_SHIFT,
-			   r->pull->entropy_count >> ENTROPY_SHIFT);
-}
-
 /*
  * This function decides how many bytes to actually take from the
  * given pool, and also debits the entropy count accordingly.
@@ -1616,54 +1560,6 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	return _extract_entropy(r, buf, nbytes, fips_enabled);
 }
 
-/*
- * This function extracts randomness from the "entropy pool", and
- * returns it in a userspace buffer.
- */
-static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
-				    size_t nbytes)
-{
-	ssize_t ret = 0, i;
-	__u8 tmp[EXTRACT_SIZE];
-	int large_request = (nbytes > 256);
-
-	trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
-	if (!r->initialized && r->pull) {
-		xfer_secondary_pool(r, ENTROPY_BITS(r->pull)/8);
-		if (!r->initialized)
-			return 0;
-	}
-	xfer_secondary_pool(r, nbytes);
-	nbytes = account(r, nbytes, 0, 0);
-
-	while (nbytes) {
-		if (large_request && need_resched()) {
-			if (signal_pending(current)) {
-				if (ret == 0)
-					ret = -ERESTARTSYS;
-				break;
-			}
-			schedule();
-		}
-
-		extract_buf(r, tmp);
-		i = min_t(int, nbytes, EXTRACT_SIZE);
-		if (copy_to_user(buf, tmp, i)) {
-			ret = -EFAULT;
-			break;
-		}
-
-		nbytes -= i;
-		buf += i;
-		ret += i;
-	}
-
-	/* Wipe data just returned from memory */
-	memzero_explicit(tmp, sizeof(tmp));
-
-	return ret;
-}
-
 #define warn_unseeded_randomness(previous) \
 	_warn_unseeded_randomness(__func__, (void *) _RET_IP_, (previous))
 
@@ -1953,7 +1849,6 @@ static void __init init_std_data(struct entropy_store *r)
 int __init rand_initialize(void)
 {
 	init_std_data(&input_pool);
-	init_std_data(&blocking_pool);
 	crng_initialize(&primary_crng);
 	crng_global_init_time = jiffies;
 	if (ratelimit_disable) {
@@ -2122,7 +2017,6 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
 		input_pool.entropy_count = 0;
-		blocking_pool.entropy_count = 0;
 		return 0;
 	case RNDRESEEDCRNG:
 		if (!capable(CAP_SYS_ADMIN))
-- 
2.23.0

[PATCH v3 7/8] random: Delete code to pull data into pools

[Andy Lutomirski]

There is no pool that pulls, so it was just dead code.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 40 ----------------------------------------
 1 file changed, 40 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index b4f834893d9d..920bf771e3e1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -528,10 +528,8 @@ struct entropy_store {
 	const struct poolinfo *poolinfo;
 	__u32 *pool;
 	const char *name;
-	struct entropy_store *pull;
 
 	/* read-write data: */
-	unsigned long last_pulled;
 	spinlock_t lock;
 	unsigned short add_ptr;
 	unsigned short input_rotate;
@@ -1347,41 +1345,6 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
  *
  *********************************************************************/
 
-/*
- * This utility inline function is responsible for transferring entropy
- * from the primary pool to the secondary extraction pool. We make
- * sure we pull enough for a 'catastrophic reseed'.
- */
-static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes);
-static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
-{
-	if (!r->pull ||
-	    r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) ||
-	    r->entropy_count > r->poolinfo->poolfracbits)
-		return;
-
-	_xfer_secondary_pool(r, nbytes);
-}
-
-static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
-{
-	__u32	tmp[OUTPUT_POOL_WORDS];
-
-	int bytes = nbytes;
-
-	/* pull at least as much as a wakeup */
-	bytes = max_t(int, bytes, random_read_wakeup_bits / 8);
-	/* but never more than the buffer size */
-	bytes = min_t(int, bytes, sizeof(tmp));
-
-	trace_xfer_secondary_pool(r->name, bytes * 8, nbytes * 8,
-				  ENTROPY_BITS(r), ENTROPY_BITS(r->pull));
-	bytes = extract_entropy(r->pull, tmp, bytes,
-				random_read_wakeup_bits / 8, 0);
-	mix_pool_bytes(r, tmp, bytes);
-	credit_entropy_bits(r, bytes*8);
-}
-
 /*
  * This function decides how many bytes to actually take from the
  * given pool, and also debits the entropy count accordingly.
@@ -1545,7 +1508,6 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 			spin_unlock_irqrestore(&r->lock, flags);
 			trace_extract_entropy(r->name, EXTRACT_SIZE,
 					      ENTROPY_BITS(r), _RET_IP_);
-			xfer_secondary_pool(r, EXTRACT_SIZE);
 			extract_buf(r, tmp);
 			spin_lock_irqsave(&r->lock, flags);
 			memcpy(r->last_data, tmp, EXTRACT_SIZE);
@@ -1554,7 +1516,6 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	}
 
 	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
-	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
 	return _extract_entropy(r, buf, nbytes, fips_enabled);
@@ -1825,7 +1786,6 @@ static void __init init_std_data(struct entropy_store *r)
 	ktime_t now = ktime_get_real();
 	unsigned long rv;
 
-	r->last_pulled = jiffies;
 	mix_pool_bytes(r, &now, sizeof(now));
 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
 		if (!arch_get_random_seed_long(&rv) &&
-- 
2.23.0

[PATCH v3 8/8] random: Remove kernel.random.read_wakeup_threshold

[Andy Lutomirski]

It has no effect any more, so remove it.  We can revert this if
there is some user code that expects to be able to set this sysctl.

Signed-off-by: Andy Lutomirski <luto@kernel.org>
---
 drivers/char/random.c | 18 +-----------------
 1 file changed, 1 insertion(+), 17 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 920bf771e3e1..2a6818cae2d6 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -369,12 +369,6 @@
 #define ENTROPY_SHIFT 3
 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
 
-/*
- * The minimum number of bits of entropy before we wake up a read on
- * /dev/random.  Should be enough to do a significant reseed.
- */
-static int random_read_wakeup_bits = 64;
-
 /*
  * If the entropy count falls under this number of bits, then we
  * should wake up processes which are selecting or polling on write
@@ -2053,8 +2047,7 @@ SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
 
 #include <linux/sysctl.h>
 
-static int min_read_thresh = 8, min_write_thresh;
-static int max_read_thresh = OUTPUT_POOL_WORDS * 32;
+static int min_write_thresh;
 static int max_write_thresh = INPUT_POOL_WORDS * 32;
 static int random_min_urandom_seed = 60;
 static char sysctl_bootid[16];
@@ -2129,15 +2122,6 @@ struct ctl_table random_table[] = {
 		.proc_handler	= proc_do_entropy,
 		.data		= &input_pool.entropy_count,
 	},
-	{
-		.procname	= "read_wakeup_threshold",
-		.data		= &random_read_wakeup_bits,
-		.maxlen		= sizeof(int),
-		.mode		= 0644,
-		.proc_handler	= proc_dointvec_minmax,
-		.extra1		= &min_read_thresh,
-		.extra2		= &max_read_thresh,
-	},
 	{
 		.procname	= "write_wakeup_threshold",
 		.data		= &random_write_wakeup_bits,
-- 
2.23.0

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Müller]

Am Montag, 23. Dezember 2019, 09:20:43 CET schrieb Andy Lutomirski:

Hi Andy,
> 
> There are some open questions and future work here:
> 
> Should the kernel provide an interface to get software-generated
> "true random" numbers?  I can think of only one legitimate reason to
> use such an interface: compliance with government standards.  If the
> kernel provides such an interface going forward, I think it should
> be a brand new character device, and it should have a default mode
> 0440 or similar.  Software-generated "true random numbers" are a
> very limited resource, and resource exhaustion is a big deal.  Ask
> anyone who has twiddled their thumbs while waiting for gnupg to
> generate a key.  If we think the kernel might do such a thing, then
> patches 5-8 could be tabled for now.

What about offering a compile-time option to enable or disable such code? 
Note, with the existing random.c code base, there is no need to have a 
separate blocking_pool. The ChaCha20 DRNG could be used for that very same 
purpose, provided that in case these true random numbers are generated when 
the Chacha20 DRNG received an equal amount of "unused" entropy.
> 
> Alternatively, perhaps the kernel should instead provide a
> privileged interface to read out raw samples from the various
> entropy sources, and users who care could have a user daemon that
> does something intelligent with them.  This would push the mess of
> trying to comply with whatever standards are involved to userspace.
> Userspace could then export "true randomness" via CUSE if it is so
> inclined, or could have a socket with a well-known name, or whatever
> else seems appropriate.

With the patch set v26 of my LRNG I offer another possible alternative 
avoiding any additional character device file and preventing the starvation of 
legitimate use cases: the LRNG has an entropy pool that leaves different 
levels of entropy in the pool depending on the use cases of this data.

If an unprivileged caller requests true random data, at least 1024 bits of 
entropy is left in the pool. I.e. all entropy above that point is available 
for this request type. Note, even namespaces fall into this category 
considering that unprivileged users can create a user name space in which they 
can become root.

If a non-blocking DRNG serving /dev/urandom or getrandom(2) needs reseeding, 
at least 512 bits of entropy is left in the pool. Each DRNG seeding operation 
requires at least 128 bits and at most 256 bits of entropy. This means that at 
least 2 reseed operations worth of entropy is found in the entropy pool even 
though massive amount of true random numbers are requested by unprivileged 
users.

If a privileged caller requests true random numbers, the entropy pool is 
allowed to be exhausted.

Access to the true random number generator is provided with getrandom(2) and 
the GRND_TRUERANDOM flag. If the true random number generator (TRNG) is not 
compiled or not present, -EOPNOTSUPP is returned.

Entire patch set:

Reviewed-by: Stephan Müller <smueller@chronox.de>

Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Matthew Garrett]

On Thu, Dec 26, 2019 at 10:29:00AM +0100, Stephan Müller wrote:
> 
> What about offering a compile-time option to enable or disable such code? 
> Note, with the existing random.c code base, there is no need to have a 
> separate blocking_pool. The ChaCha20 DRNG could be used for that very same 
> purpose, provided that in case these true random numbers are generated when 
> the Chacha20 DRNG received an equal amount of "unused" entropy.

I think it's reasonable to offer such an option as long as it's made 
clear that it'll break userland and should only be enabled under very 
weird circumstances. We don't want to end up in a situation where 
userland developers feel that they need to code to handle such 
situations - the only people who care about this distinction should be 
in control of their userland stack and able to cope with the 
consequences.

> If an unprivileged caller requests true random data, at least 1024 bits of 
> entropy is left in the pool. I.e. all entropy above that point is available 
> for this request type. Note, even namespaces fall into this category 
> considering that unprivileged users can create a user name space in which they 
> can become root.

I also feel like describing any of this as "true random data" is 
misleading. Most of our entropy sources are devices that could, given 
sufficient information, be modelled accurately. We're not sampling 
quantum events here.
 
-- 
Matthew Garrett | mjg59@srcf.ucam.org

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

> On Dec 26, 2019, at 5:29 PM, Stephan Müller <smueller@chronox.de> wrote:
> 
> Am Montag, 23. Dezember 2019, 09:20:43 CET schrieb Andy Lutomirski:
> 
> Hi Andy,
>> 
>> There are some open questions and future work here:
>> 
>> Should the kernel provide an interface to get software-generated
>> "true random" numbers?  I can think of only one legitimate reason to
>> use such an interface: compliance with government standards.  If the
>> kernel provides such an interface going forward, I think it should
>> be a brand new character device, and it should have a default mode
>> 0440 or similar.  Software-generated "true random numbers" are a
>> very limited resource, and resource exhaustion is a big deal.  Ask
>> anyone who has twiddled their thumbs while waiting for gnupg to
>> generate a key.  If we think the kernel might do such a thing, then
>> patches 5-8 could be tabled for now.
> 
> What about offering a compile-time option to enable or disable such code?
> Note, with the existing random.c code base, there is no need to have a 
> separate blocking_pool. The ChaCha20 DRNG could be used for that very same 
> purpose, provided that in case these true random numbers are generated when 
> the Chacha20 DRNG received an equal amount of "unused" entropy.

This scares me. The DRNG should be simple and easy to understand. If we’re tapping extra numbers in some weird way, then I would be more comfortable with some clear assurance that this doesn’t break the security. If we’re tapping numbers in the same way as normal urandom, then I don’t really see the point.

>> 
>> Alternatively, perhaps the kernel should instead provide a
>> privileged interface to read out raw samples from the various
>> entropy sources, and users who care could have a user daemon that
>> does something intelligent with them.  This would push the mess of
>> trying to comply with whatever standards are involved to userspace.
>> Userspace could then export "true randomness" via CUSE if it is so
>> inclined, or could have a socket with a well-known name, or whatever
>> else seems appropriate.
> 
> With the patch set v26 of my LRNG I offer another possible alternative 
> avoiding any additional character device file and preventing the starvation of 
> legitimate use cases: the LRNG has an entropy pool that leaves different 
> levels of entropy in the pool depending on the use cases of this data.
> 
> If an unprivileged caller requests true random data, at least 1024 bits of 
> entropy is left in the pool. I.e. all entropy above that point is available 
> for this request type. Note, even namespaces fall into this category 
> considering that unprivileged users can create a user name space in which they 
> can become root.

This doesn’t solve the problem. If two different users run stupid programs like gnupg, they will starve each other.

As I see it, there are two major problems with /dev/random right now: it’s prone to DoS (i.e. starvation, malicious or otherwise), and, because no privilege is required, it’s prone to misuse. Gnupg is misuse, full stop. If we add a new unprivileged interface, gnupg and similar programs will use it, and we lose all over again.

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Donnerstag, 26. Dezember 2019, 11:03:34 CET schrieb Matthew Garrett:

Hi Matthew,

> On Thu, Dec 26, 2019 at 10:29:00AM +0100, Stephan Müller wrote:
> > What about offering a compile-time option to enable or disable such code?
> > Note, with the existing random.c code base, there is no need to have a
> > separate blocking_pool. The ChaCha20 DRNG could be used for that very same
> > purpose, provided that in case these true random numbers are generated
> > when
> > the Chacha20 DRNG received an equal amount of "unused" entropy.
> 
> I think it's reasonable to offer such an option as long as it's made
> clear that it'll break userland and should only be enabled under very
> weird circumstances. We don't want to end up in a situation where
> userland developers feel that they need to code to handle such
> situations - the only people who care about this distinction should be
> in control of their userland stack and able to cope with the
> consequences.

Ok.
> 
> > If an unprivileged caller requests true random data, at least 1024 bits of
> > entropy is left in the pool. I.e. all entropy above that point is
> > available
> > for this request type. Note, even namespaces fall into this category
> > considering that unprivileged users can create a user name space in which
> > they can become root.
> 
> I also feel like describing any of this as "true random data" is
> misleading. Most of our entropy sources are devices that could, given
> sufficient information, be modelled accurately. We're not sampling
> quantum events here.

I am fine using any terminology that fits.

The terminology I used comes from the German AIS 31:

"""
True RNG: A device or mechanism for which the output values depend on some 
unpredictable source (noise source, entropy source) that produces entropy.

Note: The class of TRNGs splits into two subclasses (PTRNGs and NPTRNGs).
"""

Bottom line, a TRNG produces random numbers at an equal rate as the underlying 
noise source produces entropy. E.g. if the noise source produces 10 bits of 
entropy, the RNG shall only generate 10 bits of random data.

A physical TRNG (PTRNG) uses a physical phenomenon like shot noise of a diode 
in a ring oscillator. Commonly, stochastical models can be created for those 
noise sources.

A non-physical TRNG (NPTRNG) uses non-physical phenomenons like timing of 
events as noise source. The random.c or my LRNG are NPTRNGs. For NPTRNGs it is 
unlikely that there is a stochastical model.


Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Donnerstag, 26. Dezember 2019, 12:12:29 CET schrieb Andy Lutomirski:

Hi Andy,

> > On Dec 26, 2019, at 5:29 PM, Stephan Müller <smueller@chronox.de> wrote:
> > 
> > Am Montag, 23. Dezember 2019, 09:20:43 CET schrieb Andy Lutomirski:
> > 
> > Hi Andy,
> > 
> >> There are some open questions and future work here:
> >> 
> >> Should the kernel provide an interface to get software-generated
> >> "true random" numbers?  I can think of only one legitimate reason to
> >> use such an interface: compliance with government standards.  If the
> >> kernel provides such an interface going forward, I think it should
> >> be a brand new character device, and it should have a default mode
> >> 0440 or similar.  Software-generated "true random numbers" are a
> >> very limited resource, and resource exhaustion is a big deal.  Ask
> >> anyone who has twiddled their thumbs while waiting for gnupg to
> >> generate a key.  If we think the kernel might do such a thing, then
> >> patches 5-8 could be tabled for now.
> > 
> > What about offering a compile-time option to enable or disable such code?
> > Note, with the existing random.c code base, there is no need to have a
> > separate blocking_pool. The ChaCha20 DRNG could be used for that very same
> > purpose, provided that in case these true random numbers are generated
> > when
> > the Chacha20 DRNG received an equal amount of "unused" entropy.
> 
> This scares me. The DRNG should be simple and easy to understand. If we’re
> tapping extra numbers in some weird way, then I would be more comfortable
> with some clear assurance that this doesn’t break the security. If we’re
> tapping numbers in the same way as normal urandom, then I don’t really see
> the point.

Agreed. I was just trying to outline that the removal of the blocking_pool is 
a good thing. Even when we decide that random.c should receive a TRNG, we do 
not need to re-add a blocking pool, but can easily use the existing ChaCha20 
DRNG (most likely with its own instance).

> >> Alternatively, perhaps the kernel should instead provide a
> >> privileged interface to read out raw samples from the various
> >> entropy sources, and users who care could have a user daemon that
> >> does something intelligent with them.  This would push the mess of
> >> trying to comply with whatever standards are involved to userspace.
> >> Userspace could then export "true randomness" via CUSE if it is so
> >> inclined, or could have a socket with a well-known name, or whatever
> >> else seems appropriate.
> > 
> > With the patch set v26 of my LRNG I offer another possible alternative
> > avoiding any additional character device file and preventing the
> > starvation of legitimate use cases: the LRNG has an entropy pool that
> > leaves different levels of entropy in the pool depending on the use cases
> > of this data.
> > 
> > If an unprivileged caller requests true random data, at least 1024 bits of
> > entropy is left in the pool. I.e. all entropy above that point is
> > available
> > for this request type. Note, even namespaces fall into this category
> > considering that unprivileged users can create a user name space in which
> > they can become root.
> 
> This doesn’t solve the problem. If two different users run stupid programs
> like gnupg, they will starve each other.

But such scenario will always occur, will it not? If there are two callers for 
a limited resource, they will content if one "over-uses" the resource. My idea 
was to provide an interface where its use does not starve other more relevant 
use cases (e.g. seeding of the DRNGs). I.e. a user of a TRNG has the right to 
be DoSed - that is the price to pay when using this concept.
> 
> As I see it, there are two major problems with /dev/random right now: it’s
> prone to DoS (i.e. starvation, malicious or otherwise), and, because no
> privilege is required, it’s prone to misuse. Gnupg is misuse, full stop. If
> we add a new unprivileged interface, gnupg and similar programs will use
> it, and we lose all over again.

I am under the impression that the over-using of /dev/random is that other use 
cases like re-seeding of /dev/urandom are DoSed. But if there is a hog on the 
TRNG that only causes a problem for itself for other equally specialized 
applications, so be it.

When using a char device with rights of 440, then at least all applications 
part of that special group will still content for TRNG data. The only 
additional benefit I would currently see for a char device with permissions of 
440 is that an admin can control which applications have access to the TRNG to 
begin with. But when an attacker can fool those applications to use more 
random data, we again have a DoS. So, we just pushed the issue down the road 
without solving it (and I think there is no solution for the issue that TRNG 
users can DoS each other). 

Speaking of GnuPG and after having some discussions with Werner Koch, I think 
the reason for using /dev/random was that this (used to be) the only 
randomness source that has a guarantee of being seeded (Werner is not 
participating in this thread, so I hope I am not misrepresenting his words). 
With the presence of getrandom(2), this is now solved. IIRC libgcrypt has 
received support for getrandom(2) and the issue of blocking on /dev/random 
should now be a thing of the past with recent libgcrypt (and thus GnuPG) 
versions. 

Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

> On Dec 26, 2019, at 8:04 PM, Stephan Mueller <smueller@chronox.de> wrote:
> 
> Am Donnerstag, 26. Dezember 2019, 12:12:29 CET schrieb Andy Lutomirski:
> 
> Hi Andy,
> 
>>>> On Dec 26, 2019, at 5:29 PM, Stephan Müller <smueller@chronox.de> wrote:
>>> 
>>> Am Montag, 23. Dezember 2019, 09:20:43 CET schrieb Andy Lutomirski:
>>> 
>>> Hi Andy,
>>> 
>>>> There are some open questions and future work here:
>>>> 
>>>> Should the kernel provide an interface to get software-generated
>>>> "true random" numbers?  I can think of only one legitimate reason to
>>>> use such an interface: compliance with government standards.  If the
>>>> kernel provides such an interface going forward, I think it should
>>>> be a brand new character device, and it should have a default mode
>>>> 0440 or similar.  Software-generated "true random numbers" are a
>>>> very limited resource, and resource exhaustion is a big deal.  Ask
>>>> anyone who has twiddled their thumbs while waiting for gnupg to
>>>> generate a key.  If we think the kernel might do such a thing, then
>>>> patches 5-8 could be tabled for now.
>>> 
>>> What about offering a compile-time option to enable or disable such code?
>>> Note, with the existing random.c code base, there is no need to have a
>>> separate blocking_pool. The ChaCha20 DRNG could be used for that very same
>>> purpose, provided that in case these true random numbers are generated
>>> when
>>> the Chacha20 DRNG received an equal amount of "unused" entropy.
>> 
>> This scares me. The DRNG should be simple and easy to understand. If we’re
>> tapping extra numbers in some weird way, then I would be more comfortable
>> with some clear assurance that this doesn’t break the security. If we’re
>> tapping numbers in the same way as normal urandom, then I don’t really see
>> the point.
> 
> Agreed. I was just trying to outline that the removal of the blocking_pool is 
> a good thing. Even when we decide that random.c should receive a TRNG, we do 
> not need to re-add a blocking pool, but can easily use the existing ChaCha20 
> DRNG (most likely with its own instance).

Fair enough.

> 
>>>> Alternatively, perhaps the kernel should instead provide a
>>>> privileged interface to read out raw samples from the various
>>>> entropy sources, and users who care could have a user daemon that
>>>> does something intelligent with them.  This would push the mess of
>>>> trying to comply with whatever standards are involved to userspace.
>>>> Userspace could then export "true randomness" via CUSE if it is so
>>>> inclined, or could have a socket with a well-known name, or whatever
>>>> else seems appropriate.
>>> 
>>> With the patch set v26 of my LRNG I offer another possible alternative
>>> avoiding any additional character device file and preventing the
>>> starvation of legitimate use cases: the LRNG has an entropy pool that
>>> leaves different levels of entropy in the pool depending on the use cases
>>> of this data.
>>> 
>>> If an unprivileged caller requests true random data, at least 1024 bits of
>>> entropy is left in the pool. I.e. all entropy above that point is
>>> available
>>> for this request type. Note, even namespaces fall into this category
>>> considering that unprivileged users can create a user name space in which
>>> they can become root.
>> 
>> This doesn’t solve the problem. If two different users run stupid programs
>> like gnupg, they will starve each other.
> 
> But such scenario will always occur, will it not? If there are two callers for 
> a limited resource, they will content if one "over-uses" the resource. My idea 
> was to provide an interface where its use does not starve other more relevant 
> use cases (e.g. seeding of the DRNGs). I.e. a user of a TRNG has the right to 
> be DoSed - that is the price to pay when using this concept.

Maybe I’m just cynical, but I expect that, if the feature is available to everyone, then lots of user programmers will use it even though they don’t need to.  If, on the other hand, there is a barrier to entry, then people will be more likely to stop and think.

Even gnupg could have been more clever — when generating a 4096-bit RSA key, there is no actual need for 4096 bits of entropy, however entropy is defined. 256 bits would have been more than adequate.

(FWIW, my personal view is that 512 bits, in the sense of “the distribution being sampled produces no output with probability greater than about 2^-512”, is a good upper limit for even the most paranoid.  This is because it’s reasonable to assume that an attacker can’t do more than 2^128 operations. As djb has noted, multi-target attacks mean that you can amplify success probability in some cases by a factor that won’t exceed 2^128.  Some day, quantum computers might square-root everything, giving 512 bits. Actually, quantum computers won’t square root everything, but much more complicated analysis is needed to get a believable bound.)

—Andy

Re: [PATCH v3 0/8] Rework random blocking

[Theodore Y. Ts'o]

On Thu, Dec 26, 2019 at 01:03:34PM +0100, Stephan Mueller wrote:
> Agreed. I was just trying to outline that the removal of the blocking_pool is 
> a good thing. Even when we decide that random.c should receive a TRNG, we do 
> not need to re-add a blocking pool, but can easily use the existing ChaCha20 
> DRNG (most likely with its own instance).

Well, it depends on what you mean by "TRNG" --- the ChaCha20 DRNG only
has a state of 256 bits.  So if you want to only depend on "true
entropy" you can't extract more than 256 bits without violating that
assumption, at least if you're using a very strict definition of TRNG.

By getting rid of the blocking pool, and making /dev/random work like
getrandom with flags set to 0, we're effectively abandoning any kind
of assertion that /dev/random is some kind of TRNG.  This is not
insane; this is what the *BSD's have always done.

But once we do this, and /dev/random takes on the semantics of "block
until the CRNG has been initialized, and then it won't block after
that", if we change it so that it now has some different semantics,
such as "one you extract a 256-bit key, the read from /dev/random will
block until we can refill it, which might take seconds, minutes or
hours", will be considered a regression, and we can't do that.

Of course, we can hope that people will be using getrandom() and there
will be very few new users of the /dev/random pathname.  But nothing
is ever guaranteed..

						- Ted

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

>> On Dec 26, 2019, at 10:04 PM, Theodore Y. Ts'o <tytso@mit.edu> wrote:
>> 
>> On Thu, Dec 26, 2019 at 01:03:34PM +0100, Stephan Mueller wrote:
>> Agreed. I was just trying to outline that the removal of the blocking_pool is
>> a good thing. Even when we decide that random.c should receive a TRNG, we do
>> not need to re-add a blocking pool, but can easily use the existing ChaCha20
>> DRNG (most likely with its own instance).
> 
> Well, it depends on what you mean by "TRNG" --- the ChaCha20 DRNG only
> has a state of 256 bits.  So if you want to only depend on "true
> entropy" you can't extract more than 256 bits without violating that
> assumption, at least if you're using a very strict definition of TRNG.
> 
> By getting rid of the blocking pool, and making /dev/random work like
> getrandom with flags set to 0, we're effectively abandoning any kind
> of assertion that /dev/random is some kind of TRNG.  This is not
> insane; this is what the *BSD's have always done.
> 
> But once we do this, and /dev/random takes on the semantics of "block
> until the CRNG has been initialized, and then it won't block after
> that", if we change it so that it now has some different semantics,
> such as "one you extract a 256-bit key, the read from /dev/random will
> block until we can refill it, which might take seconds, minutes or
> hours", will be considered a regression, and we can't do that.

I don’t think Stephan was proposing that. He was proposing a way to implement a new interface that blocks.

> 
> Of course, we can hope that people will be using getrandom() and there
> will be very few new users of the /dev/random pathname.  But nothing
> is ever guaranteed..
> 
>                       - Ted

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Donnerstag, 26. Dezember 2019, 13:46:52 CET schrieb Andy Lutomirski:

Hi Andy,

> > On Dec 26, 2019, at 8:04 PM, Stephan Mueller <smueller@chronox.de> wrote:
> > 
> > Am Donnerstag, 26. Dezember 2019, 12:12:29 CET schrieb Andy Lutomirski:
> > 
> > Hi Andy,
> > 
> >>>> On Dec 26, 2019, at 5:29 PM, Stephan Müller <smueller@chronox.de> 
wrote:
> >>> Am Montag, 23. Dezember 2019, 09:20:43 CET schrieb Andy Lutomirski:
> >>> 
> >>> Hi Andy,
> >>> 
> >>>> There are some open questions and future work here:
> >>>> 
> >>>> Should the kernel provide an interface to get software-generated
> >>>> "true random" numbers?  I can think of only one legitimate reason to
> >>>> use such an interface: compliance with government standards.  If the
> >>>> kernel provides such an interface going forward, I think it should
> >>>> be a brand new character device, and it should have a default mode
> >>>> 0440 or similar.  Software-generated "true random numbers" are a
> >>>> very limited resource, and resource exhaustion is a big deal.  Ask
> >>>> anyone who has twiddled their thumbs while waiting for gnupg to
> >>>> generate a key.  If we think the kernel might do such a thing, then
> >>>> patches 5-8 could be tabled for now.
> >>> 
> >>> What about offering a compile-time option to enable or disable such
> >>> code?
> >>> Note, with the existing random.c code base, there is no need to have a
> >>> separate blocking_pool. The ChaCha20 DRNG could be used for that very
> >>> same
> >>> purpose, provided that in case these true random numbers are generated
> >>> when
> >>> the Chacha20 DRNG received an equal amount of "unused" entropy.
> >> 
> >> This scares me. The DRNG should be simple and easy to understand. If
> >> we’re
> >> tapping extra numbers in some weird way, then I would be more comfortable
> >> with some clear assurance that this doesn’t break the security. If we’re
> >> tapping numbers in the same way as normal urandom, then I don’t really
> >> see
> >> the point.
> > 
> > Agreed. I was just trying to outline that the removal of the blocking_pool
> > is a good thing. Even when we decide that random.c should receive a TRNG,
> > we do not need to re-add a blocking pool, but can easily use the existing
> > ChaCha20 DRNG (most likely with its own instance).
> 
> Fair enough.
> 
> >>>> Alternatively, perhaps the kernel should instead provide a
> >>>> privileged interface to read out raw samples from the various
> >>>> entropy sources, and users who care could have a user daemon that
> >>>> does something intelligent with them.  This would push the mess of
> >>>> trying to comply with whatever standards are involved to userspace.
> >>>> Userspace could then export "true randomness" via CUSE if it is so
> >>>> inclined, or could have a socket with a well-known name, or whatever
> >>>> else seems appropriate.
> >>> 
> >>> With the patch set v26 of my LRNG I offer another possible alternative
> >>> avoiding any additional character device file and preventing the
> >>> starvation of legitimate use cases: the LRNG has an entropy pool that
> >>> leaves different levels of entropy in the pool depending on the use
> >>> cases
> >>> of this data.
> >>> 
> >>> If an unprivileged caller requests true random data, at least 1024 bits
> >>> of
> >>> entropy is left in the pool. I.e. all entropy above that point is
> >>> available
> >>> for this request type. Note, even namespaces fall into this category
> >>> considering that unprivileged users can create a user name space in
> >>> which
> >>> they can become root.
> >> 
> >> This doesn’t solve the problem. If two different users run stupid
> >> programs
> >> like gnupg, they will starve each other.
> > 
> > But such scenario will always occur, will it not? If there are two callers
> > for a limited resource, they will content if one "over-uses" the
> > resource. My idea was to provide an interface where its use does not
> > starve other more relevant use cases (e.g. seeding of the DRNGs). I.e. a
> > user of a TRNG has the right to be DoSed - that is the price to pay when
> > using this concept.
> 
> Maybe I’m just cynical, but I expect that, if the feature is available to
> everyone, then lots of user programmers will use it even though they don’t
> need to.  If, on the other hand, there is a barrier to entry, then people
> will be more likely to stop and think.

I would tend to agree with you. But if the man page provides an appropriate 
warning that such DoS is the price to pay, wouldn't you say it is sufficient? 
I guess you will say no :-)

Thus, if you can convince Greg to allow us creating another device node, I am 
definitely not in the way of creating and using it. All my suggestions simply 
try to bridge the gap between Greg's rather reluctant agreement and our needs.

The good thing is IMHO that we are only talking about the actual kernel/user 
interface. The plumbing behind it will be identical - at least in my LRNG 
implementation, I can use the very same handler function for accessing the 
TRNG with either the device file or the getrandom syscall. I guess the same 
would be applicable to any possible random.c TRNG implementation.

> 
> Even gnupg could have been more clever — when generating a 4096-bit RSA key,
> there is no actual need for 4096 bits of entropy, however entropy is
> defined. 256 bits would have been more than adequate.

I am in violent agreement.
> 
> (FWIW, my personal view is that 512 bits, in the sense of “the distribution
> being sampled produces no output with probability greater than about
> 2^-512”, is a good upper limit for even the most paranoid.  This is because
> it’s reasonable to assume that an attacker can’t do more than 2^128
> operations. As djb has noted, multi-target attacks mean that you can
> amplify success probability in some cases by a factor that won’t exceed
> 2^128.  Some day, quantum computers might square-root everything, giving
> 512 bits. Actually, quantum computers won’t square root everything, but
> much more complicated analysis is needed to get a believable bound.)
> 
> —Andy



Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Freitag, 27. Dezember 2019, 00:29:20 CET schrieb Andy Lutomirski:

Hi Ted, Andy,

> >> On Dec 26, 2019, at 10:04 PM, Theodore Y. Ts'o <tytso@mit.edu> wrote:
> >> 
> >> On Thu, Dec 26, 2019 at 01:03:34PM +0100, Stephan Mueller wrote:
> >> Agreed. I was just trying to outline that the removal of the
> >> blocking_pool is a good thing. Even when we decide that random.c should
> >> receive a TRNG, we do not need to re-add a blocking pool, but can easily
> >> use the existing ChaCha20 DRNG (most likely with its own instance).
> > 
> > Well, it depends on what you mean by "TRNG" --- the ChaCha20 DRNG only
> > has a state of 256 bits.  So if you want to only depend on "true
> > entropy" you can't extract more than 256 bits without violating that
> > assumption, at least if you're using a very strict definition of TRNG.


My definition of TRNG is identical to the German AIS 31 and I guess identical 
to your definition of a TRNG.

A TRNG will produce an amount of random data that is equal to the amount of 
"fresh" entropy that was provided by the noise source. I.e. it should be 
identical to the blocking_pool behavior.

This definition is slightly stricter than the SP800-90A definition of "a DRBG 
with prediction resistance" which requires a reseed with entropy equal to the 
security strength of the DRBG, but allows one generate operation which at most 
generates 2^19 random bits.

Such TRNG has two components

1. the noise source / the entropy pool

2. the random number generator

All I try to say is that the random number generator does not need to be a 
special implementation of, say, a blocking_pool, but it can be any type of 
DRNG (ChaCha20, SP800-90A DRBG, ...).

To manage that DRNG, the logic needs to ensure that the maximum entropy 
content assumed to be present in the DRNG is min(entropy_from_noise_source, 
security_strength_DRNG). For the case of the blocking_pool, the security 
strength is 1024 bits which means that at most the blocking_pool can hold up 
to 1024 bits. With a ChaCha20 DRNG, the security strength is 256 bits. 
SP800-90A defines the security strengths of the DRBGs.

That said, for a TRNG, the DRNG part must be seeded with the amount of entropy 
equaling the requested numbers of random bits, but at most with entropy 
equaling the security strength of the DRNG. If the caller wants more random 
data, the request must be chunked to ensure that the DRNG is always reseeded 
before satisfying the chunk of the request.

> > 
> > By getting rid of the blocking pool, and making /dev/random work like
> > getrandom with flags set to 0, we're effectively abandoning any kind
> > of assertion that /dev/random is some kind of TRNG.  This is not
> > insane; this is what the *BSD's have always done.

Correct, and I am not disputing it. And I think that making Linux to behave 
like the BSD's and guaranteeing that the DRNG is fully seeded based on Andy's 
patch set is a good thing.

All I try to say is that there are use cases where a TRNG with the initially 
defined operation is required. This most prominent use case is the German AIS 
31 and the (re)seeding requirements of deterministic RNGs.
> > 
> > But once we do this, and /dev/random takes on the semantics of "block
> > until the CRNG has been initialized, and then it won't block after
> > that", if we change it so that it now has some different semantics,
> > such as "one you extract a 256-bit key, the read from /dev/random will
> > block until we can refill it, which might take seconds, minutes or
> > hours", will be considered a regression, and we can't do that.
> 
> I don’t think Stephan was proposing that. He was proposing a way to
> implement a new interface that blocks.

Thank you, Andy. Yes. I am trying to propose a separate interface.

Our discussion currently produced the following suggestions:

- add a new GRND_TRUERANDOM flag to getrandom(2) which allows access to the 
TRNG. Andy did not like it because he mentioned that it may be misused since 
the syscall is unprivileged. I had some suggestions to overcome this problem, 
but not all of Andy's considerations could be addressed with this suggestion. 
As an idea, my current LRNG system call implementation looks like:

SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count,
                unsigned int, flags)
{
        if (flags & ~(GRND_NONBLOCK|GRND_RANDOM|GRND_INSECURE|
GRND_TRUERANDOM))
                return -EINVAL;

        /*
         * Requesting insecure and blocking randomness at the same time makes
         * no sense.
         */
        if ((flags &
             (GRND_INSECURE|GRND_RANDOM)) == (GRND_INSECURE|GRND_RANDOM))
                return -EINVAL;

        /* Only allow GRND_TRUERANDOM by itself or with NONBLOCK */
        if ((flags & GRND_TRUERANDOM) &&
            ((flags &~ GRND_TRUERANDOM) != 0) &&
            ((flags &~ (GRND_TRUERANDOM | GRND_NONBLOCK)) != 0))
                return -EINVAL;

        if (count > INT_MAX)
                count = INT_MAX;

        if (flags & GRND_TRUERANDOM)
                return lrng_read_common_block(flags & GRND_NONBLOCK, buf,
                                              count, lrng_trng_get);
        if (flags & GRND_INSECURE)
                return lrng_sdrng_read(NULL, buf, count, NULL);

        return lrng_read_common_block(flags & GRND_NONBLOCK, buf, count,
                                      lrng_sdrng_get_sleep);

}


- Andy mentioned that he likes the approach with having another new char 
device with permissions 440 to provide an interface to the TRNG as more 
appropriate. However, Greg was reluctant to add a new device file.

I personally am indifferent. All I am suggesting is to have a TRNG offered to 
user space.

> > Of course, we can hope that people will be using getrandom() and there
> > will be very few new users of the /dev/random pathname.  But nothing
> > is ever guaranteed..
> > 
> >                       - Ted



Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Theodore Y. Ts'o]

On Fri, Dec 27, 2019 at 11:29:22AM +0100, Stephan Mueller wrote:
> 
> My definition of TRNG is identical to the German AIS 31 and I guess identical 
> to your definition of a TRNG.
> 
> A TRNG will produce an amount of random data that is equal to the amount of 
> "fresh" entropy that was provided by the noise source. I.e. it should be 
> identical to the blocking_pool behavior.

This begs the question of determining: (a) how much "fresh entropy"
you can actually get from a noise source, (b) at what rate the "fresh
entropy" is arriving, and (c) what assurance(s) you have that the
noise source is actually working correctly.

You can't make those assurances from software alone; it needs to be an
aspect of holistic design of the hardware's design; the supply chain,
and the software.  So if we are going to claime that we have something
like GRND_TRUERANDOM or /dev/trandom, or whatever, it needs to work on
IOT devices running ARM, RISC-V, MIPS, PowerPC, x86.  Some of these
architectures have no instruction reordering and are stupid simple;
some of these hardware platforms may have no high-resolution clock or
cryptographic instructions.

In addition, if you use a hardware device which is USB attached, how
does the kernel know that it really is the device that you think it
is?  The only way you know that a ChaosKey is a ChaosKey is by its USB
vendor and product id --- which can be easily forged by an attacker,
either in the supply chain or delivery path, or who walks up to the
laptop, yanks out the ChaosKey and replaces it with a "PutinKey" or a
"NSAKey".

So creating somethinig which shows up as "true random number
generator" as a generic Linux concept seems to me to be fraught
endeavor, and I'm not at all convince people need it.

> - add a new GRND_TRUERANDOM flag to getrandom(2) which allows access to the 
> TRNG. Andy did not like it because he mentioned that it may be misused since 
> the syscall is unprivileged.

Even if we could solve the "how the hell can the kernel guarantee that
the noise source is legitimate" problem in a general way that works
across all of the architectures, we still have the problem that
everyone thinks they need "the good stuff".

Suppose the system call was privileged and "true randomness" could
only be accessed as root.  What would happen?  Application programmers
would give instructions requiring that their application be installed
as root to be more secure, "because that way you can get access the
_really_ good random numbers".

So let's take a step back and ask the question: "Exactly what _value_
do you want to provide by creating some kind of true random
interface?"  What does this enable?  What applications does this
really help?

As I thought while watching the latest Star Wars movie: Why?  Why?
Whywhywhy?

					- Ted

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Freitag, 27. Dezember 2019, 14:04:36 CET schrieb Theodore Y. Ts'o:

Hi Theodore,

> On Fri, Dec 27, 2019 at 11:29:22AM +0100, Stephan Mueller wrote:
> > My definition of TRNG is identical to the German AIS 31 and I guess
> > identical to your definition of a TRNG.
> > 
> > A TRNG will produce an amount of random data that is equal to the amount
> > of
> > "fresh" entropy that was provided by the noise source. I.e. it should be
> > identical to the blocking_pool behavior.
> 
> This begs the question of determining: (a) how much "fresh entropy"
> you can actually get from a noise source, (b) at what rate the "fresh
> entropy" is arriving, and (c) what assurance(s) you have that the
> noise source is actually working correctly.
> 
> You can't make those assurances from software alone; it needs to be an
> aspect of holistic design of the hardware's design; the supply chain,
> and the software.  So if we are going to claime that we have something
> like GRND_TRUERANDOM or /dev/trandom, or whatever, it needs to work on
> IOT devices running ARM, RISC-V, MIPS, PowerPC, x86.  Some of these
> architectures have no instruction reordering and are stupid simple;
> some of these hardware platforms may have no high-resolution clock or
> cryptographic instructions.
> 
> In addition, if you use a hardware device which is USB attached, how
> does the kernel know that it really is the device that you think it
> is?  The only way you know that a ChaosKey is a ChaosKey is by its USB
> vendor and product id --- which can be easily forged by an attacker,
> either in the supply chain or delivery path, or who walks up to the
> laptop, yanks out the ChaosKey and replaces it with a "PutinKey" or a
> "NSAKey".
> 
> So creating somethinig which shows up as "true random number
> generator" as a generic Linux concept seems to me to be fraught
> endeavor, and I'm not at all convince people need it.

I am unsure but it sounds like you are refuting your blocking_pool 
implementation. Nothing more and nothing less than the blocking_pool, just 
with a more modern and further analyzed DRNG is what was referenced as a TRNG.

Or maybe the terminology of TRNG (i.e. "true") is offending. I have no concern 
to have it replaced with some other terminology. Yet, I was just taking one 
well-defined term.

Yet, I fully agree that a noise source always must be vetted. This is what I 
tried with random.c in [1], specifically section 6.1 for x86 systems.

For my LRNG, I tried that in [2] section 3.2 compliant to SP800-90B. In order 
to provide a means to everybody to perform such entropy analysis, the entire 
tool set required for it is provided:

- with CONFIG_LRNG_TESTING providing an interface to the raw unconditioned 
noise

- with [3] providing a tool set to gather all data needed for an SP800-90B 
compliant quantitative analysis

Unfortunately due to license restrictions, I cannot make the same tool set 
available used for the quantiative study provided with [1] section 6.1.

Finally, to support the conclusions drawn from a noise source analysis, the 
health tests provided with LRNG compliant to SP800-90B are available with 
CONFIG_LRNG_HEALTH_TESTS. These tests help in identifying weak or broken noise 
sources.

It is fully clear that such studies of non-physical noise sources do not have 
a stochastical model which implies that we cannot make global statements. That 
is the limitation when using such noise sources. Though, the implementation 
should have sufficient "leeway" (i.e. underestmation) when crediting entropy 
to some events.
> 
> > - add a new GRND_TRUERANDOM flag to getrandom(2) which allows access to
> > the
> > TRNG. Andy did not like it because he mentioned that it may be misused
> > since the syscall is unprivileged.
> 
> Even if we could solve the "how the hell can the kernel guarantee that
> the noise source is legitimate" problem in a general way that works
> across all of the architectures, we still have the problem that
> everyone thinks they need "the good stuff".
> 
> Suppose the system call was privileged and "true randomness" could
> only be accessed as root.  What would happen?  Application programmers
> would give instructions requiring that their application be installed
> as root to be more secure, "because that way you can get access the
> _really_ good random numbers".

That is why I think that it is no bug when this interface can DoS other users 
wanting to access the very same resource. This is the price to pay for getting 
access to this type of data.
> 
> So let's take a step back and ask the question: "Exactly what _value_
> do you want to provide by creating some kind of true random
> interface?"  What does this enable?  What applications does this
> really help?

There are simply cryptographers who have use cases for such random numbers. 
The core use case is to seed other DRNGs and avoiding the chaining of free-
running DRNGs.

This is a common approach that you can see in action with the RDSEED 
instruction, for example.
> 
> As I thought while watching the latest Star Wars movie: Why?  Why?
> Whywhywhy?
> 
> 					- Ted

[1] https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Studies/
LinuxRNG/LinuxRNG_EN.pdf?__blob=publicationFile&v=11

[2] https://chronox.de/lrng/doc/lrng.pdf

[3] https://chronox.de/lrng/lrng-tests-20191123.tar.xz

Ciao
Stephan

Re: [PATCH v3 0/8] Rework random blocking

[Theodore Y. Ts'o]

On Fri, Dec 27, 2019 at 10:22:23PM +0100, Stephan Mueller wrote:
> 
> I am unsure but it sounds like you are refuting your blocking_pool 
> implementation. Nothing more and nothing less than the blocking_pool, just 
> with a more modern and further analyzed DRNG is what was referenced as a TRNG.

Yes, and that's why I am planning on taking Andy's patches to drop the
blocking pool.  Trying to make the claim that you can read one byte
from /dev/random if and only if one byte of entropy has flowed into
it.... is a mug's game, for the reasons I gave above.

> Or maybe the terminology of TRNG (i.e. "true") is offending. I have no concern 
> to have it replaced with some other terminology. Yet, I was just taking one 
> well-defined term.

But my point is that it *isn't* a well defined term, precisely because
it's completely unclear what application programmer can expect when
they try to use some hypothetical GRANDOM_TRUERANDOM flag.  What does
that *mean*?  The kernel can't offer up any guarantees about whether
or not the noise source has been appropriately characterized.  All
say, a GPG or OpenSSL developer can do is get the vague sense that
TRUERANDOM is "better" and of course, they want the best security, so
of *course* they are going to try to use it.  At which point it will
block, and when some other clever user (maybe a distro release
engineer) puts it into an init script, then systems will stop working
and users will complain to Linus.

And then we'll have companies like Intel claiming that RDSEED has been
very carefully characterized --- by them --- and we should *obviously*
trust it, and wire up RDSEED so that TRUERANDOM will have a near
infinite supply of really good entropy.  And they might even be
correct.  But this way lies a huge mess which is fundamentally social,
not technical.

The claim we can make for getrandom(2) is that we do the best job that
we can, and we feed in as many sources as possible and hope that at
least one or more sources is not known to the attacker.  One of the
sources could very well be AES(NSA_KEY, SEQ++).  But that still will
protect us from the Chinese and Russian crypto teams.  And we can hope
that the NSA doesn't have access to the inter-packet arrival times on
the local area network, or the radio strength as recorded from the
WiFi radio, etc. etc.  But note that we didn't make any claims of how
many bits of entropy that we have; it helps that we are implicitly
making a claim that we trust the crypto algorithms.   

> > So let's take a step back and ask the question: "Exactly what _value_
> > do you want to provide by creating some kind of true random
> > interface?"  What does this enable?  What applications does this
> > really help?
> 
> There are simply cryptographers who have use cases for such random numbers. 
> The core use case is to seed other DRNGs and avoiding the chaining of free-
> running DRNGs.

For this very specialized use case, what I think the kernel should
provide is maximal transparency; that is, given the DRBG direct access
to the TPM's random number generator, or direct access to the
ChaosKey, and the userspace DRBG should be able to get a list of the
various hardware RNG's, and select one, with the characterization
being done userspace, not in the kernel.

The kernel shouldn't be mixing various noise sources together, and it
certainly shouldn't be trying to claim that it knows how many bits of
entropy that it gets when is trying to play some jitter entropy game
on a stupid-simple CPU architecture for IOT/Embedded user cases where
everything is synchronized off of a single master oscillator, and
there is no CPU instruction reordering or register renaming, etc.,
etc.

You can talk about providing tools that try to make these estimations
--- but these sorts of things would have to be done on each user's
hardware, and for most distro users, it's just not practical.

So if it's just for cryptographers, then let it all be done in
userspace, and let's not make it easy for GPG, OpenSSL, etc., to all
say, "We want TrueRandom(tm); we won't settle for less".  We can talk
about how do we provide the interfaces so that those cryptographers
can get the information they need so they can get access to the raw
noise sources, separated out and named, and with possibly some way
that the noise source can authenticate itself to the Cryptographer's
userspace library/application.

But all of this should probably not be in drivers/char/random.c, and
we probably need to figure out a better kernel to userspace interface
than what we have with /dev/hwrng.

					- Ted

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

On Fri, Dec 27, 2019 at 2:09 PM Theodore Y. Ts'o <tytso@mit.edu> wrote:

> So if it's just for cryptographers, then let it all be done in
> userspace, and let's not make it easy for GPG, OpenSSL, etc., to all
> say, "We want TrueRandom(tm); we won't settle for less".  We can talk
> about how do we provide the interfaces so that those cryptographers
> can get the information they need so they can get access to the raw
> noise sources, separated out and named, and with possibly some way
> that the noise source can authenticate itself to the Cryptographer's
> userspace library/application.
>
> But all of this should probably not be in drivers/char/random.c, and
> we probably need to figure out a better kernel to userspace interface
> than what we have with /dev/hwrng.

I'm thinking of having a real class device and chardev for each hwrng
device.  Authentication is entirely in userspace: whatever user code
is involved can look at the sysfs hierarchy and decide to what extent
it trusts a given source.  This could be done based on bus topology or
based on anything else.

The kernel could also separately expose various noise sources, and the
user code can do whatever it wants with them.  But these should be
explicitly unconditioned, un-entropy-extracted sources -- user code
can run its favorite algorithm to extract something it believes to be
useful.  The only conceptually tricky bit is keeping user code like
this from interfering with the in-kernel RNG.

--Andy

Re: [PATCH v3 0/8] Rework random blocking

[Willy Tarreau]

On Fri, Dec 27, 2019 at 05:08:57PM -0500, Theodore Y. Ts'o wrote:
> > Or maybe the terminology of TRNG (i.e. "true") is offending. I have no concern 
> > to have it replaced with some other terminology. Yet, I was just taking one 
> > well-defined term.
> 
> But my point is that it *isn't* a well defined term, precisely because
> it's completely unclear what application programmer can expect when
> they try to use some hypothetical GRANDOM_TRUERANDOM flag.  What does
> that *mean*?

I've also seen this term used and abused too many times and this bothers
me because the expectations around it are the cause of the current
situation.

Randomness doesn't exist by itself. It's what characterizes the
unpredictable nature of something. I.e. our inability to model it and
guess what will happen based on what we know. 200 years ago we'd have
considered the weather as a true random source. Now we have super
computers making this moot. In the current state of art we consider
that cesium decay or tunnel noise are unpredictable and excellent
random sources, until one day we figure that magnetic fields,
temperature or gamma rays strongly affect them.

So in practice we should only talk about the complexity of the model we
rely on. The more complex it is (i.e. the most independent variables it
relies on), the less predictable it is and the more random it is. Jitter
entropy and RAM contents are good examples of this: they may be highly
unpredictable on some platforms and almost constant on others. And for
sure, software cannot fix this, it can at best make the output *look*
like it's unpredictable. Once someone can model all variables of the
environment this is not true random anymore.

That's why the best we can do is to combine as many sources as possible
hoping that nobody can model enough of them, and produce an output which
never ever reveals these sources' internal states. *This* is what software
can and must do. And once the initial entropy is hidden enough and there
is enough of it, there's no reason for it to ever get depleted if these
initial bits cannot be guessed nor brute-forced.

And quite frankly I'd rather just speak about the diversity of sources
than "true" randomness. Just asking a user to press 10 random keys and
to enter a random word for some operations can break many assumptions
an attacker could have about the environment, by just adding one extra,
less controllable, source.

Just my two cents,
Willy

Re: [PATCH v3 0/8] Rework random blocking

[Theodore Y. Ts'o]

On Fri, Dec 27, 2019 at 06:06:56PM -0800, Andy Lutomirski wrote:
> 
> I'm thinking of having a real class device and chardev for each hwrng
> device.  Authentication is entirely in userspace: whatever user code
> is involved can look at the sysfs hierarchy and decide to what extent
> it trusts a given source.  This could be done based on bus topology or
> based on anything else.

Yes, that's what I was thinking.  Another project on my "when I can
get a round tuit" list is to change how drivers/char/random.c taps
into the hwrng devices, mixing in a bit from each of these devies in a
round-robin fashion, instead of just feeding from a single hwrng.

> The kernel could also separately expose various noise sources, and the
> user code can do whatever it wants with them.  But these should be
> explicitly unconditioned, un-entropy-extracted sources -- user code
> can run its favorite algorithm to extract something it believes to be
> useful.  The only conceptually tricky bit is keeping user code like
> this from interfering with the in-kernel RNG.

The other problem is the unconditioned values of the noise sources may
leak unacceptable amounts of information about system operation.  The
most obvious example of this would be keyboard and mouse sources,
where today we mix in not only the timing information, but the actual
input values (e.g., the keyboard scancodes) into the entropy pool.
Exposing this to userspace, even if it is via a privileged system
call, would be... unwise.

						- Ted

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

> On Dec 29, 2019, at 10:49 PM, Theodore Y. Ts'o <tytso@mit.edu> wrote:
> 
> On Fri, Dec 27, 2019 at 06:06:56PM -0800, Andy Lutomirski wrote:
>> 
>> I'm thinking of having a real class device and chardev for each hwrng
>> device.  Authentication is entirely in userspace: whatever user code
>> is involved can look at the sysfs hierarchy and decide to what extent
>> it trusts a given source.  This could be done based on bus topology or
>> based on anything else.
> 
> Yes, that's what I was thinking.  Another project on my "when I can
> get a round tuit" list is to change how drivers/char/random.c taps
> into the hwrng devices, mixing in a bit from each of these devies in a
> round-robin fashion, instead of just feeding from a single hwrng.
> 
>> The kernel could also separately expose various noise sources, and the
>> user code can do whatever it wants with them.  But these should be
>> explicitly unconditioned, un-entropy-extracted sources -- user code
>> can run its favorite algorithm to extract something it believes to be
>> useful.  The only conceptually tricky bit is keeping user code like
>> this from interfering with the in-kernel RNG.
> 
> The other problem is the unconditioned values of the noise sources may
> leak unacceptable amounts of information about system operation.  The
> most obvious example of this would be keyboard and mouse sources,
> where today we mix in not only the timing information, but the actual
> input values (e.g., the keyboard scancodes) into the entropy pool.
> Exposing this to userspace, even if it is via a privileged system
> call, would be... unwise.
> 
>          

Hmm. We could give only the timing.

We could also say that the official interface for this is to use tracepoints and punt everything into userspace.

Re: [PATCH v3 1/8] random: Don't wake crng_init_wait when crng_init == 1

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:44AM -0800, Andy Lutomirski wrote:
> crng_init_wait is only used to wayt for crng_init to be set to 2, so
> there's no point to waking it when crng_init is set to 1.  Remove the
> unnecessary wake_up_interruptible() call.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied with a spelling fix ("wayt->wait").

					- Ted

Re: [PATCH v3 2/8] random: Add a urandom_read_nowait() for random APIs that don't warn

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:45AM -0800, Andy Lutomirski wrote:
> /dev/random and getrandom() never warn.  Split the meat of
> urandom_read() into urandom_read_nowarn() and leave the warning code
> in urandom_read().
> 
> This has no effect on kernel behavior, but it makes subsequent
> patches more straightforward.  It also makes the fact that
> getrandom() never warns more obvious.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 3/8] random: Add GRND_INSECURE to return best-effort non-cryptographic bytes

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:46AM -0800, Andy Lutomirski wrote:
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 4/8] random: Ignore GRND_RANDOM in getentropy(2)

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:47AM -0800, Andy Lutomirski wrote:
> The separate blocking pool is going away.  Start by ignoring
> GRND_RANDOM in getentropy(2).
> 
> This should not materially break any API.  Any code that worked
> without this change should work at least as well with this change.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 5/8] random: Make /dev/random be almost like /dev/urandom

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:48AM -0800, Andy Lutomirski wrote:
> This patch changes the read semantics of /dev/random to be the same
> as /dev/urandom except that reads will block until the CRNG is
> ready.
> 
> None of the cleanups that this enables have been done yet.  As a
> result, this gives a warning about an unused function.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

						- Ted

Re: [PATCH v3 6/8] random: Remove the blocking pool

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:49AM -0800, Andy Lutomirski wrote:
> There is no longer any interface to read data from the blocking
> pool, so remove it.
> 
> This enables quite a bit of code deletion, much of which will be
> done in subsequent patches.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 7/8] random: Delete code to pull data into pools

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:50AM -0800, Andy Lutomirski wrote:
> There is no pool that pulls, so it was just dead code.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 8/8] random: Remove kernel.random.read_wakeup_threshold

[Theodore Y. Ts'o]

On Mon, Dec 23, 2019 at 12:20:51AM -0800, Andy Lutomirski wrote:
> It has no effect any more, so remove it.  We can revert this if
> there is some user code that expects to be able to set this sysctl.
> 
> Signed-off-by: Andy Lutomirski <luto@kernel.org>

Applied, thanks.

					- Ted

Re: [PATCH v3 0/8] Rework random blocking

[Kurt Roeckx]

On Fri, Dec 27, 2019 at 05:08:57PM -0500, Theodore Y. Ts'o wrote:
> On Fri, Dec 27, 2019 at 10:22:23PM +0100, Stephan Mueller wrote:
> > > So let's take a step back and ask the question: "Exactly what _value_
> > > do you want to provide by creating some kind of true random
> > > interface?"  What does this enable?  What applications does this
> > > really help?
> > 
> > There are simply cryptographers who have use cases for such random numbers. 
> > The core use case is to seed other DRNGs and avoiding the chaining of free-
> > running DRNGs.
> 
> For this very specialized use case, what I think the kernel should
> provide is maximal transparency; that is, given the DRBG direct access
> to the TPM's random number generator, or direct access to the
> ChaosKey, and the userspace DRBG should be able to get a list of the
> various hardware RNG's, and select one, with the characterization
> being done userspace, not in the kernel.

One thing the NIST DRBGs have is prediction resistance, which is
done by reseeding. If you chain DRBGs, you tell your parent DRBG
that you want prediction resistance, so your parent will also
reseed. There currently is no way to tell the kernel to reseed.

This reseed option might be something that some people would like
to see. If such an option is added, I expect that the kernel might
block until it has gotten enough new entropy from it's entropy
sources. But I don't actually see a need to add such an option.

If the kernel provides a good RNG, the only reason I can see why
you would like to have direct access to a hwrng is to verify that
it's working correctly. That might mean that you put it in some
special mode where it returns raw unprocessed values. If the device
is in such a mode, it's output will not provide the same entropy
per bit, and so I would expect the kernel to stop using it directly.

I guess there might be people who would like to use it directly,
but I think we should instead encourage them kernel RNG.

> You can talk about providing tools that try to make these estimations
> --- but these sorts of things would have to be done on each user's
> hardware, and for most distro users, it's just not practical.

I would check my own hardware if such an option was available. I
think it can be useful to see if the current estimates in the
kernel are conservative enough or not. But it would require that
you can know what the entropy source is, like the keyboard or
harddisk.

> So if it's just for cryptographers, then let it all be done in
> userspace, and let's not make it easy for GPG, OpenSSL, etc., to all
> say, "We want TrueRandom(tm); we won't settle for less".

I don't think we want that. As far as I know, the only reason for
using /dev/random is that /dev/urandom returns data before it
has sufficient entropy.


Kurt

Re: [PATCH v3 0/8] Rework random blocking

[Theodore Y. Ts'o]

On Thu, Jan 09, 2020 at 11:02:30PM +0100, Kurt Roeckx wrote:
> 
> One thing the NIST DRBGs have is prediction resistance, which is
> done by reseeding. If you chain DRBGs, you tell your parent DRBG
> that you want prediction resistance, so your parent will also
> reseed. There currently is no way to tell the kernel to reseed.

It would be simple enough to add a new flag, perhaps GRND_RESEED, to
getrandom() which requests that the kernel reseed first.  This would
require sufficient amounts of entropy in the input pool to do the
reseed; if there is not enough, the getrandom() call would block until
there was enough.  If GRND_NONBLOCK is supplied, then getrandom()
would return EAGAIN if there wasn't sufficient entropy.

Is this what you want?

What should happen if two racing processes simultaneously call
getrandom(2) with GRND_RESEED?  Do they need to be serialized with a
separate reseed for each one?  Does it matter whether, after the
reseed, some other process calling getrandom(2) manages to get output
from the CRNG before the process requesting the RESEED gets a chance
to use the reseeded CRNG?

This can all be fixed by adding more locking, of course, but then the
crazy people who think that:

      dd if=/dev/random of=/dev/sdb

needs to be able to work at HDD, SSD, or networking line speeds, will
complain that all of this locking has slowed down /dev/[u]random, and
they can't get their hundreds of megabytes/second out of the CRNG....

> I would check my own hardware if such an option was available. I
> think it can be useful to see if the current estimates in the
> kernel are conservative enough or not. But it would require that
> you can know what the entropy source is, like the keyboard or
> harddisk.

Creating such an interface is not high on my priority list.  If
someone wants to send a proposal for such an interface, followed by a
patch, I'm happy to take a look at it.  I am worried about the
potential information leakage that such an interface might provide,
though.  So at the very least, it should be something that can be
disabled via build-time config, and perhaps hidden behind
CONFIG_EXPERIMENTAL.  I really would want to make it clear that it's
only for use by experts who are interesting in tinkering, and not
something which is enabled in a distro kernel.

> I don't think we want that. As far as I know, the only reason for
> using /dev/random is that /dev/urandom returns data before it
> has sufficient entropy.

Is there any objections to just using getrandom(2)?

   	     		   	      - Ted

Re: [PATCH v3 0/8] Rework random blocking

[Kurt Roeckx]

On Thu, Jan 09, 2020 at 05:40:11PM -0500, Theodore Y. Ts'o wrote:
> On Thu, Jan 09, 2020 at 11:02:30PM +0100, Kurt Roeckx wrote:
> > 
> > One thing the NIST DRBGs have is prediction resistance, which is
> > done by reseeding. If you chain DRBGs, you tell your parent DRBG
> > that you want prediction resistance, so your parent will also
> > reseed. There currently is no way to tell the kernel to reseed.
> 
> It would be simple enough to add a new flag, perhaps GRND_RESEED, to
> getrandom() which requests that the kernel reseed first.  This would
> require sufficient amounts of entropy in the input pool to do the
> reseed; if there is not enough, the getrandom() call would block until
> there was enough.  If GRND_NONBLOCK is supplied, then getrandom()
> would return EAGAIN if there wasn't sufficient entropy.
> 
> Is this what you want?

I think some people might want to see it, but I think you
shouldn't add it.

> > I don't think we want that. As far as I know, the only reason for
> > using /dev/random is that /dev/urandom returns data before it
> > has sufficient entropy.
> 
> Is there any objections to just using getrandom(2)?

It provides the interface we want, so no. But there are still
people who don't have it for various reasons. OpenSSL actually
does the system call itself if libc doesn't provider a wrapper for
it.


Kurt

Re: [PATCH v3 0/8] Rework random blocking

[Andy Lutomirski]

> On Jan 9, 2020, at 12:02 PM, Kurt Roeckx <kurt@roeckx.be> wrote:
> 

> 
> If the kernel provides a good RNG, the only reason I can see why
> you would like to have direct access to a hwrng is to verify that
> it's working correctly. That might mean that you put it in some
> special mode where it returns raw unprocessed values. If the device
> is in such a mode, it's output will not provide the same entropy
> per bit, and so I would expect the kernel to stop using it directly.

I disagree.

If I buy a ChaosKey or a fancy EAL4FIPSOMG key, I presumably have it for a reason and I want to actually use the thing for real. Maybe it’s for some certification reason and maybe it’s just because it’s really cool.

As for “direct” access,  I think AMD provides an interface to read raw output from the on-die entropy source. Exposing this to user space is potentially quite useful for anyone who wants to try to characterize it.  I don’t really think people should use a raw sample interface as a source of production random numbers, though.

Re: [PATCH v3 0/8] Rework random blocking

[Stephan Mueller]

Am Freitag, 10. Januar 2020, 00:02:37 CET schrieb Kurt Roeckx:

Hi Kurt,

> On Thu, Jan 09, 2020 at 05:40:11PM -0500, Theodore Y. Ts'o wrote:
> > On Thu, Jan 09, 2020 at 11:02:30PM +0100, Kurt Roeckx wrote:
> > > One thing the NIST DRBGs have is prediction resistance, which is
> > > done by reseeding. If you chain DRBGs, you tell your parent DRBG
> > > that you want prediction resistance, so your parent will also
> > > reseed. There currently is no way to tell the kernel to reseed.
> > 
> > It would be simple enough to add a new flag, perhaps GRND_RESEED, to
> > getrandom() which requests that the kernel reseed first.  This would
> > require sufficient amounts of entropy in the input pool to do the
> > reseed; if there is not enough, the getrandom() call would block until
> > there was enough.  If GRND_NONBLOCK is supplied, then getrandom()
> > would return EAGAIN if there wasn't sufficient entropy.
> > 
> > Is this what you want?
> 
> I think some people might want to see it, but I think you
> shouldn't add it.

Just for your information: I played with that already as seen in [1] which 
does not require any kernel change.

The only issue that is currently there are the two races noted in [1]. These 
races seem to be only addressable when the reseeding and the gathering of 
random numbers are atomic. I was toying with the idea that the RNDRESEEDCRNG 
allows the user to specify an output buffer which would be filled in an atomic 
operation when the reseed is invoked. That buffer should only be at most in 
size of the security strength of the DRNG.

[1] https://github.com/smuellerDD/lrng/blob/master/test/syscall_test.c#L101
> 
> > > I don't think we want that. As far as I know, the only reason for
> > > using /dev/random is that /dev/urandom returns data before it
> > > has sufficient entropy.
> > 
> > Is there any objections to just using getrandom(2)?
> 
> It provides the interface we want, so no. But there are still
> people who don't have it for various reasons. OpenSSL actually
> does the system call itself if libc doesn't provider a wrapper for
> it.
> 
> 
> Kurt



Ciao
Stephan