[PATCH] random: limit the contribution of the hw rng to at most half

[PATCH] random: limit the contribution of the hw rng to at most half

[Theodore Ts'o]

For people who don't trust a hardware RNG which can not be audited,
the changes to add support for RDSEED can be troubling since 97% or
more of the entropy will be contributed from the in-CPU hardware RNG.

We now have a in-kernel khwrngd, so for those people who do want to
implicitly trust the CPU-based system, we could create an arch-rng
hw_random driver, and allow khwrng refill the entropy pool.  This
allows system administrator whether or not they trust the CPU (I
assume the NSA will trust RDRAND/RDSEED implicitly :-), and if so,
what level of entropy derating they want to use.

The reason why this is a really good idea is that if different people
use different levels of entropy derating, it will make it much more
difficult to design a backdoor'ed hwrng that can be generally
exploited in terms of the output of /dev/random when different attack
targets are using differing levels of entropy derating.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 43 ++++---------------------------------------
 1 file changed, 4 insertions(+), 39 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 76a56f6..e7d7ac1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -911,12 +911,13 @@ void add_interrupt_randomness(int irq, int irq_flags)
 
 	/*
 	 * If we have architectural seed generator, produce a seed and
-	 * add it to the pool.  For the sake of paranoia count it as
-	 * 50% entropic.
+	 * add it to the pool.  For the sake of paranoia don't let the
+	 * architectural seed generator dominate the input from the
+	 * interrupt noise.
 	 */
 	if (arch_get_random_seed_long(&seed)) {
 		__mix_pool_bytes(r, &seed, sizeof(seed));
-		credit += sizeof(seed) * 4;
+		credit = 1;
 	}
 	spin_unlock(&r->lock);
 
@@ -1328,37 +1329,6 @@ void rand_initialize_disk(struct gendisk *disk)
 }
 #endif
 
-/*
- * Attempt an emergency refill using arch_get_random_seed_long().
- *
- * As with add_interrupt_randomness() be paranoid and only
- * credit the output as 50% entropic.
- */
-static int arch_random_refill(void)
-{
-	const unsigned int nlongs = 64;	/* Arbitrary number */
-	unsigned int n = 0;
-	unsigned int i;
-	unsigned long buf[nlongs];
-
-	if (!arch_has_random_seed())
-		return 0;
-
-	for (i = 0; i < nlongs; i++) {
-		if (arch_get_random_seed_long(&buf[n]))
-			n++;
-	}
-
-	if (n) {
-		unsigned int rand_bytes = n * sizeof(unsigned long);
-
-		mix_pool_bytes(&input_pool, buf, rand_bytes);
-		credit_entropy_bits(&input_pool, rand_bytes*4);
-	}
-
-	return n;
-}
-
 static ssize_t
 _random_read(int nonblock, char __user *buf, size_t nbytes)
 {
@@ -1379,11 +1349,6 @@ _random_read(int nonblock, char __user *buf, size_t nbytes)
 			return n;
 
 		/* Pool is (near) empty.  Maybe wait and retry. */
-
-		/* First try an emergency refill */
-		if (arch_random_refill())
-			continue;
-
 		if (nonblock)
 			return -EAGAIN;
 
-- 
2.0.0

Re: [PATCH] random: limit the contribution of the hw rng to at most half

[H. Peter Anvin]

On 07/17/2014 03:03 AM, Theodore Ts'o wrote:
> For people who don't trust a hardware RNG which can not be audited,
> the changes to add support for RDSEED can be troubling since 97% or
> more of the entropy will be contributed from the in-CPU hardware RNG.
> 
> We now have a in-kernel khwrngd, so for those people who do want to
> implicitly trust the CPU-based system, we could create an arch-rng
> hw_random driver, and allow khwrng refill the entropy pool.  This
> allows system administrator whether or not they trust the CPU (I
> assume the NSA will trust RDRAND/RDSEED implicitly :-), and if so,
> what level of entropy derating they want to use.
> 
> The reason why this is a really good idea is that if different people
> use different levels of entropy derating, it will make it much more
> difficult to design a backdoor'ed hwrng that can be generally
> exploited in terms of the output of /dev/random when different attack
> targets are using differing levels of entropy derating.
> 
> Signed-off-by: Theodore Ts'o <tytso@mit.edu>

I saw exactly one complaint to that nature, but that was from someone
who really wanted the "nordrand" option (at which point I observed that
it had inadvertently left RDSEED enabled which quickly got rectified.)
The implication was that this was a request from a specific customer who
presumably have their own "audited" hardware RNG.

There may have been other complaints (justified or not) but if so I
haven't seen them.  I'm wondering if we are overgeneralizing here and if
so if it wouldn't be better to defer this until the hwrng supplier for
this is ready, which probably won't happen in time for 3.17 just given
the current timeline.

	-hpa

Re: [PATCH] random: limit the contribution of the hw rng to at most half

[Theodore Ts'o]

On Thu, Jul 17, 2014 at 10:39:57AM -0700, H. Peter Anvin wrote:
> 
> I saw exactly one complaint to that nature, but that was from someone
> who really wanted the "nordrand" option (at which point I observed that
> it had inadvertently left RDSEED enabled which quickly got rectified.)
> The implication was that this was a request from a specific customer who
> presumably have their own "audited" hardware RNG.

There was another complaint more recently, that wasn't related to
nordrand.  And I was rather disturbed that in
add_interrupt_randomness() 97% of the entropy was coming from RDSEED.
I'm willing to have some of the entropy come from RDSEED by default,
but 97% seems to really way too much.

And the emergency refill code in random_read() was extremely
problematic.  First of all, we're dropping 512 bytes on the stack,
which is kind of bad, but hopefully all of the code paths which call
random_read() won't have a terribly deep stack.  Secondly, even after
the emergency refill, we block anyway.  Which is kind of OK, but what
it means is that we are pulling 512 bytes from RDSEED, and giving
credit for 2048 bits of entropy; but since we block until the next
contribution from interrupt randomness, that means we get 1 bit from
the entropy randomness, and 2048 bits of entropy from RDSEED --- which
means that from the standpoint of entropy accounting, 99.95%
(2048/2049) of the entropy is coming from RDSEED when reading from
/dev/random when its entropy pool is empty.

Remember, regardless of whether or not you believe (as a former head
of NSA's technology directorate recently claimed) that the DUAL-EC p
and q were generated using NSA's standard high-quality HW RNG system
which they use to generate all of their crypto variables, or (as the
NIST advisory panel has recently concluded) that it was highly likely
that DUAL-EC was backdoored, it's the optics that matter, because
those of us without top-drawer SI security clearances can't prove
things one way or another.

And when 99.95% of the entropy when reading large quantities of keying
material from /dev/random is coming from RDSEED, that just has
terrible, terrible optics....

						- Ted

Re: [PATCH] random: limit the contribution of the hw rng to at most half

[H. Peter Anvin]

On 07/17/2014 03:08 PM, Theodore Ts'o wrote:
> 
> There was another complaint more recently, that wasn't related to
> nordrand.  And I was rather disturbed that in
> add_interrupt_randomness() 97% of the entropy was coming from RDSEED.
> I'm willing to have some of the entropy come from RDSEED by default,
> but 97% seems to really way too much.
> 

OK, the that formula was Linus' suggestion.

> And the emergency refill code in random_read() was extremely
> problematic.  First of all, we're dropping 512 bytes on the stack,
> which is kind of bad, but hopefully all of the code paths which call
> random_read() won't have a terribly deep stack.

512 bytes is fine here (1K would possibly not have been.)

> Secondly, even after the emergency refill, we block anyway.

Not unless we don't get any data back.  For a nonzero return we loop
back to extract_entropy_user().

> Remember, regardless of whether or not you believe (as a former head
> of NSA's technology directorate recently claimed) that the DUAL-EC p
> and q were generated using NSA's standard high-quality HW RNG system
> which they use to generate all of their crypto variables, or (as the
> NIST advisory panel has recently concluded) that it was highly likely
> that DUAL-EC was backdoored, it's the optics that matter, because
> those of us without top-drawer SI security clearances can't prove
> things one way or another.

Dual-EC was also heavily criticized by the civilian cryptographic
community since at least 2006.

> And when 99.95% of the entropy when reading large quantities of keying
> material from /dev/random is coming from RDSEED, that just has
> terrible, terrible optics....

I just want to make sure we don't negatively impact the real security of
users because of "optics".  We already have a lot of problems with
people extracting long-living keys from /dev/urandom because /dev/random
is too slow.

I have no objection to the khwrngd route -- in fact, as you know, I have
been heavily encouraging the development of khwrngd with exactly this in
mind -- but it is just an issue of timing.

	-hpa

Re: [PATCH] random: limit the contribution of the hw rng to at most half

[Theodore Ts'o]

On Thu, Jul 17, 2014 at 04:33:36PM -0700, H. Peter Anvin wrote:
> 
> I just want to make sure we don't negatively impact the real security of
> users because of "optics".  We already have a lot of problems with
> people extracting long-living keys from /dev/urandom because /dev/random
> is too slow.

With a system with RDRAND, we're mixing arch_get_rand_long() as part
of the extraction process (as the seed for the SHA's IV).  So if you
trust RDRAND, then using /dev/urandom even when the entropy count is
zero is going to be secure.  If you don't trust RDRAND, then the
RDSEED entropy accounting is going to be extremely disturbing.

So the only way that we could be impacting the "real security" of
users, would be if RDRAND was back-doored, but RDSEED wasn't.  And
that doesn't seem like a terribly likely scenario to me, but what do I
know?  :-)

						- Ted