[PATCH resend 0/2] random: Use DRBG sources

[PATCH resend 0/2] random: Use DRBG sources

[Andy Lutomirski]

[Resent because I forgot to email lkml.  This also surreptitiously
 fixes a silly typo on a patch description.]

This is my attempt to come up with a workable way to use so-called
entropy sources like a TPM to feed /dev/urandom.

Arguably we should be feeding the input pool as well, but if the
/dev/random algorithm is correct, this shouldn't matter.  I don't want
sensible use of TPMs for /dev/urandom to block on a long debate about
/dev/random, so these patches have no effect on /dev/random.

Andy Lutomirski (2):
  random: Add add_drbg_randomness to safely seed urandom from crypto hw
  tpm,random: Call add_drbg_randomness after selftest

 drivers/char/random.c            | 56 +++++++++++++++++++++++++++++++++++-----
 drivers/char/tpm/tpm-interface.c | 15 ++++++++++-
 include/linux/random.h           |  1 +
 include/trace/events/random.h    | 19 ++++++++++++++
 4 files changed, 83 insertions(+), 8 deletions(-)

-- 
1.9.0

[PATCH resend 1/2] random: Add add_drbg_randomness to safely seed urandom from crypto hw

[Andy Lutomirski]

There has been a longstanding debate as to how devices such as TPMs
should be used to seed the kernel's RNG.  Arguments in this debate
include:

 - The TPM is untrustworthy and possibly malicious, so we shouldn't use
   it.

 - The TPM almost certainly supplies no real entropy, so we shouldn't
   credit any entropy from it.

The upshot is that we don't use TPM-like devices at all as entropy
sources, unless CONFIG_HW_RANDOM_TPM is set, in which case we use it in
a way that looks rather wrong to me.

Let's resolve this problem by calling these devices what they are:
DRBGs, aka deterministic random bit generators.  They may be broken,
they may be backdoored, they're probably deterministic, they arguably
shouldn't supply any entropy credits, but they're still valuable sources
of cryptographic data to mix into at least the urandom pool.

This adds add_drbg_randomness to allow these devices to safely seed
urandom.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 drivers/char/random.c         | 56 +++++++++++++++++++++++++++++++++++++------
 include/linux/random.h        |  1 +
 include/trace/events/random.h | 19 +++++++++++++++
 3 files changed, 69 insertions(+), 7 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 6b75713..8c18722 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -125,12 +125,24 @@
  * The current exported interfaces for gathering environmental noise
  * from the devices are:
  *
+ *	void add_drbg_randomness(const void *buf, unsigned int size);
  *	void add_device_randomness(const void *buf, unsigned int size);
  * 	void add_input_randomness(unsigned int type, unsigned int code,
  *                                unsigned int value);
  *	void add_interrupt_randomness(int irq, int irq_flags);
  * 	void add_disk_randomness(struct gendisk *disk);
  *
+ * add_drbg_randomness() adds data from a so-called hardware rng.  These
+ * devices can include TPMs, hypervisors, and similar sources of
+ * hopefully cryptographically secure bits of uncertain quality.
+ * add_drbg_randomness() should not be called for
+ * arch_get_random_long-style RNGs, as the core random code does that
+ * automatically.  There is no requirement that add_drbg_randomness be
+ * provided with any actual entropy.  In cases where the number of bits
+ * provided is easy to adjust and where security could realistically
+ * depend on the number of bits provided, 256 bits or more should be
+ * used.
+ *
  * add_device_randomness() is for adding data to the random pool that
  * is likely to differ between two devices (or possibly even per boot).
  * This would be things like MAC addresses or serial numbers, or the
@@ -466,6 +478,12 @@ static struct entropy_store nonblocking_pool = {
 					push_to_pool),
 };
 
+/*
+ * Tracks total bits supplied to add_drbg_randomness.  Protected by
+ * nonblocking_pool.lock.
+ */
+static __u64 total_drbg_input;
+
 static __u32 const twist_table[8] = {
 	0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 	0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
@@ -654,11 +672,12 @@ retry:
 	r->entropy_total += nbits;
 	if (!r->initialized && r->entropy_total > 128) {
 		r->initialized = 1;
-		r->entropy_total = 0;
 		if (r == &nonblocking_pool) {
 			prandom_reseed_late();
-			pr_notice("random: %s pool is initialized\n", r->name);
+			pr_notice("random: %s pool is initialized with %d bits of entropy and %llu bits of DRBG data\n",
+				  r->name, r->entropy_total, total_drbg_input);
 		}
+		r->entropy_total = 0;
 	}
 
 	trace_credit_entropy_bits(r->name, nbits,
@@ -725,6 +744,23 @@ struct timer_rand_state {
 #define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, };
 
 /*
+ * Add DRBG randomness.  This type of input is not trusted enough to go
+ * to the blocking pool, and no entropy is credited, but it can substantially
+ * strengthen the nonblocking pool, especially during and shortly after
+ * boot.
+ */
+void add_drbg_randomness(const void *buf, unsigned int size)
+{
+	unsigned long flags;
+	trace_add_drbg_randomness(size, _RET_IP_);
+	spin_lock_irqsave(&nonblocking_pool.lock, flags);
+	_mix_pool_bytes(&nonblocking_pool, buf, size, NULL);
+	total_drbg_input += size * 8;
+	spin_unlock_irqrestore(&nonblocking_pool.lock, flags);
+}
+EXPORT_SYMBOL(add_drbg_randomness);
+
+/*
  * Add device- or boot-specific data to the input and nonblocking
  * pools to help initialize them to unique values.
  *
@@ -1246,16 +1282,22 @@ static void init_std_data(struct entropy_store *r)
 	int i;
 	ktime_t now = ktime_get_real();
 	unsigned long rv;
+	__u64 drbg_bits = 0;
 
 	r->last_pulled = jiffies;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
-		if (!arch_get_random_seed_long(&rv) &&
-		    !arch_get_random_long(&rv))
+		if (arch_get_random_seed_long(&rv) ||
+		    arch_get_random_long(&rv))
+			drbg_bits += sizeof(unsigned long) * 8;
+		else
 			rv = random_get_entropy();
 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
 	}
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
+
+	if (r == &nonblocking_pool && drbg_bits)
+		total_drbg_input += drbg_bits;
 }
 
 /*
@@ -1367,9 +1409,9 @@ urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 	int ret;
 
 	if (unlikely(nonblocking_pool.initialized == 0))
-		printk_once(KERN_NOTICE "random: %s urandom read "
-			    "with %d bits of entropy available\n",
-			    current->comm, nonblocking_pool.entropy_total);
+		printk_once(KERN_NOTICE "random: %s urandom read with %d bits of entropy available and %llu bits of DRBG data\n",
+			    current->comm, nonblocking_pool.entropy_total,
+			    total_drbg_input);
 
 	ret = extract_entropy_user(&nonblocking_pool, buf, nbytes);
 
diff --git a/include/linux/random.h b/include/linux/random.h
index 57fbbff..2e202a0 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -8,6 +8,7 @@
 
 #include <uapi/linux/random.h>
 
+extern void add_drbg_randomness(const void *, unsigned int);
 extern void add_device_randomness(const void *, unsigned int);
 extern void add_input_randomness(unsigned int type, unsigned int code,
 				 unsigned int value);
diff --git a/include/trace/events/random.h b/include/trace/events/random.h
index 805af6d..8a81e49 100644
--- a/include/trace/events/random.h
+++ b/include/trace/events/random.h
@@ -7,6 +7,25 @@
 #include <linux/writeback.h>
 #include <linux/tracepoint.h>
 
+TRACE_EVENT(add_drbg_randomness,
+	TP_PROTO(int bytes, unsigned long IP),
+
+	TP_ARGS(bytes, IP),
+
+	TP_STRUCT__entry(
+		__field(	  int,	bytes			)
+		__field(unsigned long,	IP			)
+	),
+
+	TP_fast_assign(
+		__entry->bytes		= bytes;
+		__entry->IP		= IP;
+	),
+
+	TP_printk("bytes %d caller %pF",
+		__entry->bytes, (void *)__entry->IP)
+);
+
 TRACE_EVENT(add_device_randomness,
 	TP_PROTO(int bytes, unsigned long IP),
 
-- 
1.9.0

[PATCH resend 2/2] tpm,random: Call add_drbg_randomness after selftest

[Andy Lutomirski]

TPMs contain a DRBG.  Use it.

On some but not all TPMs, this will also call add_drbg_randomness on
resume.  As a future improvement, this could be tweaked to cover all
of them, but I'll leave that to someone more familiar with the
individual drivers.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 drivers/char/tpm/tpm-interface.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

diff --git a/drivers/char/tpm/tpm-interface.c b/drivers/char/tpm/tpm-interface.c
index 62e10fd..20516e7 100644
--- a/drivers/char/tpm/tpm-interface.c
+++ b/drivers/char/tpm/tpm-interface.c
@@ -28,6 +28,7 @@
 #include <linux/mutex.h>
 #include <linux/spinlock.h>
 #include <linux/freezer.h>
+#include <linux/random.h>
 
 #include "tpm.h"
 #include "tpm_eventlog.h"
@@ -780,10 +781,22 @@ int tpm_do_selftest(struct tpm_chip *chip)
 			return 0;
 		}
 		if (rc != TPM_WARN_DOING_SELFTEST)
-			return rc;
+			break;
 		msleep(delay_msec);
 	} while (--loops > 0);
 
+	if (rc == 0) {
+		/* We're functional and/or we just resumed. */
+		u8 randomness[32];
+		int bytes = tpm_get_random(chip->dev_num,
+					   randomness, sizeof(randomness));
+		if (bytes > 0) {
+			dev_info(chip->dev, "adding %d bits of DRBG data\n",
+				 bytes * 8);
+			add_drbg_randomness(randomness, bytes);
+		}
+	}
+
 	return rc;
 }
 EXPORT_SYMBOL_GPL(tpm_do_selftest);
-- 
1.9.0

Re: [PATCH resend 0/2] random: Use DRBG sources

[Torsten Duwe]

On Mon, Apr 14, 2014 at 08:49:58AM -0700, Andy Lutomirski wrote:
> [Resent because I forgot to email lkml.  This also surreptitiously
>  fixes a silly typo on a patch description.]
> 
> This is my attempt to come up with a workable way to use so-called
> entropy sources like a TPM to feed /dev/urandom.

Ahem, The TPM RNGs are true HWRNGs, but they are very limited.
Their main purpose is to generate enough bits so that the TPM
can generate a genuine key pair after a few seconds.

Why do you want to put those valuable true random bits into urandom?

> Arguably we should be feeding the input pool as well, but if the

Yes.

> /dev/random algorithm is correct, this shouldn't matter.  I don't want
> sensible use of TPMs for /dev/urandom to block on a long debate about
> /dev/random, so these patches have no effect on /dev/random.

That confuses me a bit.

	Torsten

Re: [PATCH resend 0/2] random: Use DRBG sources

[Andy Lutomirski]

On Mon, Apr 14, 2014 at 9:13 AM, Torsten Duwe <duwe@lst.de> wrote:
> On Mon, Apr 14, 2014 at 08:49:58AM -0700, Andy Lutomirski wrote:
>> [Resent because I forgot to email lkml.  This also surreptitiously
>>  fixes a silly typo on a patch description.]
>>
>> This is my attempt to come up with a workable way to use so-called
>> entropy sources like a TPM to feed /dev/urandom.
>
> Ahem, The TPM RNGs are true HWRNGs, but they are very limited.
> Their main purpose is to generate enough bits so that the TPM
> can generate a genuine key pair after a few seconds.
>
> Why do you want to put those valuable true random bits into urandom?

I don't consider 256 bits, once per TPM initialization, to be valuable
in the sense that we should try to conserve them.  I consider them
valuable in the sense that we should put them where that matter most,
ASAP.  That place is IMO urandom, since readers of /dev/random will
happily block until /dev/random is adequately seeded.

If urandom is working correctly, seeding it with 256 cryptographically
secure bits, once, is enough.  Seeding it more is nice, but doing that
is IMO much lower priority.

Because urandom can be weak shortly after bootup, the TPM is there,
and putting these bits into urandom will either make urandom quite
secure, if the TPM is trustworthy, or will at least be harmless, if
the TPM is untrustworthy.

As an added benefit, this code is very simple and can easily coexist
with your code.

>
>> Arguably we should be feeding the input pool as well, but if the
>
> Yes.
>
>> /dev/random algorithm is correct, this shouldn't matter.  I don't want
>> sensible use of TPMs for /dev/urandom to block on a long debate about
>> /dev/random, so these patches have no effect on /dev/random.
>
> That confuses me a bit.

Currently there is no quick algorithm to seed urandom from sources
like a TPM.  IMO we should have one.  There are also people who are
nervous about devices like the TPM, and they may object to crediting
any entropy from the TPM.  The amount of entropy credited affects
urandom reseeding, and setting it to zero and/or turning the whole
hwrng/khwrngd thing off should not prevent urandom from getting the
benefit of a TPM.

--Andy

Re: [PATCH resend 0/2] random: Use DRBG sources

[Andy Lutomirski]

On Mon, Apr 14, 2014 at 8:49 AM, Andy Lutomirski <luto@amacapital.net> wrote:
> [Resent because I forgot to email lkml.  This also surreptitiously
>  fixes a silly typo on a patch description.]
>
> This is my attempt to come up with a workable way to use so-called
> entropy sources like a TPM to feed /dev/urandom.
>
> Arguably we should be feeding the input pool as well, but if the
> /dev/random algorithm is correct, this shouldn't matter.  I don't want
> sensible use of TPMs for /dev/urandom to block on a long debate about
> /dev/random, so these patches have no effect on /dev/random.

Please consider these patches withdrawn.  I'll redo them on top of the
hwrng stuff.

Reasons:

 - add_drbg_randomness can probably be replaced with
add_device_randomness.  I'm not convinced that I like
add_device_randomness as a way to add small amounts of entropy: if an
attacker knows the initial state of the nonblocking pool, they can use
it to back out small amounts of entropy added via
add_device_randomness, which allows them to track all input_pool
entropy added by add_device_randomness.  This type of attack is
impractical for large amounts of device randomness added at once, so
this is orthogonal to the purpose of my patches.

 - The hwrng code itself is already a sensible place to do this kind
of initial seeding of the nonblocking pool, so I think that it would
be better to improve the hwrng code a bit instead.

My current thought is to split CONFIG_HW_RANDOM into
CONFIG_HW_RANDOM_DEVICES and CONFIG_HW_RANDOM.
CONFIG_HW_RANDOM_DEVICES will default to m and will expose
hwrng_register but not the /dev/hwrng code.  hwrng_register will call
add_device_randomness, but I'll add logging so that we can tell that
it's working.

I'll also rewrite the tpm hwrng driver.  There should be a hwrng
instance per TPM, and it shouldn't show up until there's actually a
TPM there.

--Andy

>
> Andy Lutomirski (2):
>   random: Add add_drbg_randomness to safely seed urandom from crypto hw
>   tpm,random: Call add_drbg_randomness after selftest
>
>  drivers/char/random.c            | 56 +++++++++++++++++++++++++++++++++++-----
>  drivers/char/tpm/tpm-interface.c | 15 ++++++++++-
>  include/linux/random.h           |  1 +
>  include/trace/events/random.h    | 19 ++++++++++++++
>  4 files changed, 83 insertions(+), 8 deletions(-)
>
> --
> 1.9.0
>



-- 
Andy Lutomirski
AMA Capital Management, LLC