[PATCH 0/8] random: cleanup of code after removal of nonblocking pool

[PATCH 0/8] random: cleanup of code after removal of nonblocking pool

[Stephan Müller]

Hi Ted,

with the removal of the nonblocking_pool, several code paths are now unused
which were only applicable to the nonblocking pool. This patch set removes
these unused code paths.

Also, a code path in the add_interrupt_randomness function that is never used
is removed.

In addition, the FIPS 140-2 continuous self tests are required to process
the output data of the RNG given to a caller. A patch is added to cover this
requirement.

Ciao
Stephan

Stephan Mueller (8):
  random: remove stale maybe_reseed_primary_crng
  random: remove stale urandom_init_wait
  random: trigger random_ready callback upon crng_init == 1
  random: remove unused branch in hot code path
  random: remove variable limit
  random: fix comment for unused random_min_urandom_seed
  random: remove noop function call to xfer_secondary_pool
  random: move FIPS continuous test to output functions

 drivers/char/random.c | 118 +++++++++++++++++++++++---------------------------
 1 file changed, 53 insertions(+), 65 deletions(-)

-- 
2.9.3

[PATCH 1/8] random: remove stale maybe_reseed_primary_crng

[Stephan Müller]

>From 5e84a71d4c4b3c7f015878c0907102634603d270 Mon Sep 17 00:00:00 2001
From: Stephan Mueller <stephan.mueller@atsec.com>
Date: Thu, 15 Dec 2016 12:42:33 +0100
Subject: 

The function maybe_reseed_primary_crng is not used anywhere and thus can
be removed. Besides, it contains the check crng_init > 2 which will
never become true and thus would never trigger a reseed of the ChaCha20
primary DRNG.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 7 -------
 1 file changed, 7 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1ef2640..8e5ab20 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -855,13 +855,6 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	spin_unlock_irqrestore(&primary_crng.lock, flags);
 }
 
-static inline void maybe_reseed_primary_crng(void)
-{
-	if (crng_init > 2 &&
-	    time_after(jiffies, primary_crng.init_time + CRNG_RESEED_INTERVAL))
-		crng_reseed(&primary_crng, &input_pool);
-}
-
 static inline void crng_wait_ready(void)
 {
 	wait_event_interruptible(crng_init_wait, crng_ready());
-- 
2.9.3

[PATCH 2/8] random: remove stale urandom_init_wait

[Stephan Müller]

The urandom_init_wait wait queue is a left over from the pre-ChaCha20
times and can therefore be savely removed.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 8e5ab20..482531d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -409,7 +409,6 @@ static struct poolinfo {
  */
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
-static DECLARE_WAIT_QUEUE_HEAD(urandom_init_wait);
 static struct fasync_struct *fasync;
 
 static DEFINE_SPINLOCK(random_ready_list_lock);
-- 
2.9.3

[PATCH 3/8] random: trigger random_ready callback upon crng_init == 1

[Stephan Müller]

The random_ready callback mechanism is intended to replicate the
getrandom system call behavior to in-kernel users. As the getrandom
system call unblocks with crng_init == 1, trigger the random_ready
wakeup call at the same time.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 482531d..5c26b1c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -810,6 +810,7 @@ static int crng_fast_load(const char *cp, size_t len)
 	}
 	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
 		crng_init = 1;
+		process_random_ready_list();
 		wake_up_interruptible(&crng_init_wait);
 		pr_notice("random: fast init done\n");
 	}
-- 
2.9.3

[PATCH 4/8] random: remove unused branch in hot code path

[Stephan Müller]

The variable ip is defined to be a __u64 which is always 8 bytes on any
architecture. Thus, the check for sizeof(ip) > 4 will always be true.

As the check happens in a hot code path, remove the branch.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 5c26b1c..8d4d720 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1136,8 +1136,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	fast_pool->pool[1] ^= now ^ c_high;
 	ip = regs ? instruction_pointer(regs) : _RET_IP_;
 	fast_pool->pool[2] ^= ip;
-	fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 :
-		get_reg(fast_pool, regs);
+	fast_pool->pool[3] ^= ip >> 32;
 
 	fast_mix(fast_pool);
 	add_interrupt_bench(cycles);
-- 
2.9.3

[PATCH 5/8] random: remove variable limit

[Stephan Müller]

The variable limit was used to identify the nonblocking pool's unlimited
random number generation. As the nonblocking pool is a thing of the
past, remove the limit variable and any conditions around it (i.e.
preserve the branches for limit == 1).

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 30 +++++++-----------------------
 1 file changed, 7 insertions(+), 23 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 8d4d720..d19108c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -466,7 +466,6 @@ struct entropy_store {
 	int entropy_count;
 	int entropy_total;
 	unsigned int initialized:1;
-	unsigned int limit:1;
 	unsigned int last_data_init:1;
 	__u8 last_data[EXTRACT_SIZE];
 };
@@ -484,7 +483,6 @@ static __u32 blocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy;
 static struct entropy_store input_pool = {
 	.poolinfo = &poolinfo_table[0],
 	.name = "input",
-	.limit = 1,
 	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
 	.pool = input_pool_data
 };
@@ -492,7 +490,6 @@ static struct entropy_store input_pool = {
 static struct entropy_store blocking_pool = {
 	.poolinfo = &poolinfo_table[1],
 	.name = "blocking",
-	.limit = 1,
 	.pull = &input_pool,
 	.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
 	.pool = blocking_pool_data,
@@ -1212,15 +1209,6 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 	    r->entropy_count > r->poolinfo->poolfracbits)
 		return;
 
-	if (r->limit == 0 && random_min_urandom_seed) {
-		unsigned long now = jiffies;
-
-		if (time_before(now,
-				r->last_pulled + random_min_urandom_seed * HZ))
-			return;
-		r->last_pulled = now;
-	}
-
 	_xfer_secondary_pool(r, nbytes);
 }
 
@@ -1228,8 +1216,6 @@ static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 {
 	__u32	tmp[OUTPUT_POOL_WORDS];
 
-	/* For /dev/random's pool, always leave two wakeups' worth */
-	int rsvd_bytes = r->limit ? 0 : random_read_wakeup_bits / 4;
 	int bytes = nbytes;
 
 	/* pull at least as much as a wakeup */
@@ -1240,7 +1226,7 @@ static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 	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, rsvd_bytes);
+				random_read_wakeup_bits / 8, 0);
 	mix_pool_bytes(r, tmp, bytes);
 	credit_entropy_bits(r, bytes*8);
 }
@@ -1268,7 +1254,7 @@ static void push_to_pool(struct work_struct *work)
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
 		      int reserved)
 {
-	int entropy_count, orig;
+	int entropy_count, orig, have_bytes;
 	size_t ibytes, nfrac;
 
 	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
@@ -1277,14 +1263,12 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 retry:
 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
 	ibytes = nbytes;
-	/* If limited, never pull more than available */
-	if (r->limit) {
-		int have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
+	/* never pull more than available */
+	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
 
-		if ((have_bytes -= reserved) < 0)
-			have_bytes = 0;
-		ibytes = min_t(size_t, ibytes, have_bytes);
-	}
+	if ((have_bytes -= reserved) < 0)
+		have_bytes = 0;
+	ibytes = min_t(size_t, ibytes, have_bytes);
 	if (ibytes < min)
 		ibytes = 0;
 
-- 
2.9.3

[PATCH 6/8] random: fix comment for unused random_min_urandom_seed

[Stephan Müller]

The variable random_min_urandom_seed is not needed any more as it
defined the reseeding behavior of the nonblocking pool. Though it is not
needed any more, it is left in the code for user space interface
compatibility.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d19108c..89d67c0 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -313,9 +313,7 @@ static int random_read_wakeup_bits = 64;
 static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS;
 
 /*
- * The minimum number of seconds between urandom pool reseeding.  We
- * do this to limit the amount of entropy that can be drained from the
- * input pool even if there are heavy demands on /dev/urandom.
+ * Variable is currently unused by left for user space compatibility.
  */
 static int random_min_urandom_seed = 60;
 
-- 
2.9.3

[PATCH 7/8] random: remove noop function call to xfer_secondary_pool

[Stephan Müller]

Since the introduction of the ChaCha20 DRNG, extract_entropy is only
invoked with the input_pool. For this entropy pool, xfer_secondary_pool
is a no-op and can therefore be safely removed.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 89d67c0..7b72a01 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1417,7 +1417,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);
-- 
2.9.3

[PATCH 8/8] random: move FIPS continuous test to output functions

[Stephan Müller]

The current lockation of the FIPS continuous self test covers the
input_pool only. However, the FIPS continuous self test shall cover the
output of the random number generator, i.e. the blocking pool and the
ChaCha20 DRNG.

This patch therefore moves the continuous test to the output function
used for /dev/random. In addition, it adds the continuous test to the
ChaCha20 output function.

Signed-off-by: Stephan Mueller <smueller@chronox.de>
---
 drivers/char/random.c | 71 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 43 insertions(+), 28 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 7b72a01..d185d1f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -416,6 +416,8 @@ struct crng_state {
 	__u32		state[16];
 	unsigned long	init_time;
 	spinlock_t	lock;
+	unsigned int last_data_init:1;
+	__u8 last_data[CHACHA20_BLOCK_SIZE];
 };
 
 struct crng_state primary_crng = {
@@ -471,7 +473,7 @@ struct entropy_store {
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 			       size_t nbytes, int min, int rsvd);
 static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
-				size_t nbytes, int fips);
+				size_t nbytes);
 
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r);
 static void push_to_pool(struct work_struct *work);
@@ -775,7 +777,7 @@ static void crng_initialize(struct crng_state *crng)
 	memcpy(&crng->state[0], "expand 32-byte k", 16);
 	if (crng == &primary_crng)
 		_extract_entropy(&input_pool, &crng->state[4],
-				 sizeof(__u32) * 12, 0);
+				 sizeof(__u32) * 12);
 	else
 		get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
 	for (i = 4; i < 16; i++) {
@@ -864,11 +866,25 @@ static void _extract_crng(struct crng_state *crng,
 	    time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))
 		crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL);
 	spin_lock_irqsave(&crng->lock, flags);
+
+	if (fips_enabled && !crng->last_data_init) {
+		crng->last_data_init = 1;
+		chacha20_block(&crng->state[0], out);
+		memcpy(crng->last_data, out, CHACHA20_BLOCK_SIZE);
+	}
+
 	if (arch_get_random_long(&v))
 		crng->state[14] ^= v;
 	chacha20_block(&crng->state[0], out);
 	if (crng->state[12] == 0)
 		crng->state[13]++;
+
+	if (fips_enabled) {
+		if (!memcmp(out, crng->last_data, CHACHA20_BLOCK_SIZE))
+			panic("ChaCha20 RNG duplicated output!\n");
+		memcpy(crng->last_data, out, CHACHA20_BLOCK_SIZE);
+	}
+
 	spin_unlock_irqrestore(&crng->lock, flags);
 }
 
@@ -1356,22 +1372,14 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 }
 
 static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
-				size_t nbytes, int fips)
+				size_t nbytes)
 {
 	ssize_t ret = 0, i;
 	__u8 tmp[EXTRACT_SIZE];
-	unsigned long flags;
 
 	while (nbytes) {
 		extract_buf(r, tmp);
 
-		if (fips) {
-			spin_lock_irqsave(&r->lock, flags);
-			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
-				panic("Hardware RNG duplicated output!\n");
-			memcpy(r->last_data, tmp, EXTRACT_SIZE);
-			spin_unlock_irqrestore(&r->lock, flags);
-		}
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		memcpy(buf, tmp, i);
 		nbytes -= i;
@@ -1397,7 +1405,22 @@ static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 				 size_t nbytes, int min, int reserved)
 {
+	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
+	nbytes = account(r, nbytes, min, reserved);
+
+	return _extract_entropy(r, buf, nbytes);
+}
+
+/*
+ * 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);
 	unsigned long flags;
 
 	/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
@@ -1416,23 +1439,6 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 		spin_unlock_irqrestore(&r->lock, flags);
 	}
 
-	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
-	nbytes = account(r, nbytes, min, reserved);
-
-	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_);
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, 0, 0);
@@ -1448,6 +1454,15 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 		}
 
 		extract_buf(r, tmp);
+
+		if (fips_enabled) {
+			spin_lock_irqsave(&r->lock, flags);
+			if (!memcmp(tmp, r->last_data, EXTRACT_SIZE))
+				panic("Hardware RNG duplicated output!\n");
+			memcpy(r->last_data, tmp, EXTRACT_SIZE);
+			spin_unlock_irqrestore(&r->lock, flags);
+		}
+
 		i = min_t(int, nbytes, EXTRACT_SIZE);
 		if (copy_to_user(buf, tmp, i)) {
 			ret = -EFAULT;
-- 
2.9.3

Re: [PATCH 3/8] random: trigger random_ready callback upon crng_init == 1

[Theodore Ts'o]

On Tue, Dec 27, 2016 at 11:39:57PM +0100, Stephan Müller wrote:
> The random_ready callback mechanism is intended to replicate the
> getrandom system call behavior to in-kernel users. As the getrandom
> system call unblocks with crng_init == 1, trigger the random_ready
> wakeup call at the same time.

It was deliberate that random_ready would only get triggered with
crng_init==2.

In general I'm assuming kernel callers really want real randomness (as
opposed to using prandom), where as there's a lot of b.s. userspace
users of kernel randomness (for things that really don't require
cryptographic randomness, e.g., for salting Python dictionaries,
systemd/udev using /dev/urandom for non-cryptographic, non-security
applications etc.)

						- Ted

Re: [PATCH 4/8] random: remove unused branch in hot code path

[Theodore Ts'o]

On Tue, Dec 27, 2016 at 11:40:23PM +0100, Stephan Müller wrote:
> The variable ip is defined to be a __u64 which is always 8 bytes on any
> architecture. Thus, the check for sizeof(ip) > 4 will always be true.
> 
> As the check happens in a hot code path, remove the branch.

The fact that it's a hot code path means the compiler will optimize it
out, so the fact that it's on the hot code path is irrelevant.  The
main issue is that on platforms with a 32-bit IP's, ip >> 32 will
always be zero.  It might be that we can just do this via

#if BITS_PER_LONG == 32
  ...
#else
  ...  
#endif

I'm not sure that works for all platforms, though.  More research is
needed...

					- Ted

Re: [PATCH 7/8] random: remove noop function call to xfer_secondary_pool

[Theodore Ts'o]

On Tue, Dec 27, 2016 at 11:41:46PM +0100, Stephan Müller wrote:
> Since the introduction of the ChaCha20 DRNG, extract_entropy is only
> invoked with the input_pool. For this entropy pool, xfer_secondary_pool
> is a no-op and can therefore be safely removed.
> 
> Signed-off-by: Stephan Mueller <smueller@chronox.de>

Instead of doing some minor deletions of single lines, what I want to
do is to look at a more comprehensive refactoring of the code.  The
fact that we have extract_entropy() only being used for the input
pool, and extract_entropy_user() ony being used for the non-blocking
pool, is not obvious from the function name and the arguments that
these functions take.

Either the functions should be kept general (so someone else using
them in the future won't get confused about how they work), or they
should be made more speceific.  But doing light modifications like
have the danger of causing confusion and bugs in the future.

     	 	   	   	     	 - Ted

Re: [PATCH 3/8] random: trigger random_ready callback upon crng_init == 1

[Stephan Müller]

Am Dienstag, 17. Januar 2017, 23:12:50 CET schrieb Theodore Ts'o:

Hi Theodore,

> On Tue, Dec 27, 2016 at 11:39:57PM +0100, Stephan Müller wrote:
> > The random_ready callback mechanism is intended to replicate the
> > getrandom system call behavior to in-kernel users. As the getrandom
> > system call unblocks with crng_init == 1, trigger the random_ready
> > wakeup call at the same time.
> 
> It was deliberate that random_ready would only get triggered with
> crng_init==2.
> 
> In general I'm assuming kernel callers really want real randomness (as
> opposed to using prandom), where as there's a lot of b.s. userspace
> users of kernel randomness (for things that really don't require
> cryptographic randomness, e.g., for salting Python dictionaries,
> systemd/udev using /dev/urandom for non-cryptographic, non-security
> applications etc.)

Users of getrandom want to ensure that they get random data from a DRNG that 
is seeded, just like in-kernel users may want if they choose the callback-
approach.

I do not understand why there should be different treatment of in-kernel vs 
user space callers in that respect.

(And yes, I do not want to open a discussion whether crng_init==1 can 
considered as a sufficiently seeded DRNG as such discussion will lead 
nowhere.)

Ciao
Stephan

Re: [PATCH 4/8] random: remove unused branch in hot code path

[Geert Uytterhoeven]

Hi Ted,

(replying to an old thread)

On Wed, Jan 18, 2017 at 5:35 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> On Tue, Dec 27, 2016 at 11:40:23PM +0100, Stephan Müller wrote:
>> The variable ip is defined to be a __u64 which is always 8 bytes on any
>> architecture. Thus, the check for sizeof(ip) > 4 will always be true.
>>
>> As the check happens in a hot code path, remove the branch.
>
> The fact that it's a hot code path means the compiler will optimize it
> out, so the fact that it's on the hot code path is irrelevant.  The
> main issue is that on platforms with a 32-bit IP's, ip >> 32 will
> always be zero.  It might be that we can just do this via
>
> #if BITS_PER_LONG == 32
>   ...
> #else
>   ...
> #endif
>
> I'm not sure that works for all platforms, though.  More research is
> needed...

Is the intention for the test "sizeof(ip) > 4" to distinguish between
32-bit and 64-bit platforms?
As ip is __u64, while regs is a pointer, shouldn't the test be
"sizeof(regs) > 4"?

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds