Skip to contentSkip to conversation

random: Use DRBG sources

PATCH RESEND In review Andy Lutomirski 2 participants 6 messages Apr 14, 2014

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover random: Use DRBG sources

[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(-)
Signature · 1 line
1.9.0
#1 lore raw

PATCH RESEND 1/2 random: Add add_drbg_randomness to safely seed urandom from crypto hw

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.

---
 drivers/char/random.c         | 56 +++++++++++++++++++++++++++++++++++++------
 include/linux/random.h        |  1 +
 include/trace/events/random.h | 19 +++++++++++++++
 3 files changed, 69 insertions(+), 7 deletions(-)
drivers/char/random.c +49 -7
index 6b75713..8c18722 100644
@@ -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);
 
include/linux/random.h +1 -0
index 57fbbff..2e202a0 100644
@@ -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);
include/trace/events/random.h +19 -0
index 805af6d..8a81e49 100644
@@ -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),
 
Signature · 1 line
1.9.0
#2 lore raw

PATCH RESEND 2/2 tpm,random: Call add_drbg_randomness after selftest

In reply to 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.

---
 drivers/char/tpm/tpm-interface.c | 15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)
drivers/char/tpm/tpm-interface.c +14 -1
index 62e10fd..20516e7 100644
@@ -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);
Signature · 1 line
1.9.0
#3 lore raw
In reply to Andy Lutomirski
Quoted 5 lines · 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.

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?

Quoted 1 line

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

Yes.

Quoted 3 lines

/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

#4 lore raw
Quoted 4 lines · Torsten Duwe
Quoted 3 lines · Andy Lutomirski

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

Quoted 8 lines
Quoted 2 lines

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.

Quoted 10 lines
Quoted 2 lines

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

Yes.

Quoted 3 lines

/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

#5 lore raw
In reply to Andy Lutomirski
Quoted 10 lines · 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.

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

Quoted 14 lines

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

Signature · 2 lines
Andy Lutomirski
AMA Capital Management, LLC