Direct support for the x86 RDRAND instruction

From: "H. Peter Anvin" <[email protected]>

This is a proposed patchset to enable the new x86 RDRAND instruction, labelled "Bull Mountain Technology" by Intel. It is a different beast than any other hardware random number generator that I have personally
encountered: it is not just a random number source, but contains a high bandwidth random number generator, an AES cryptographic whitener, and integrity monitoring all in hardware.

For technical documentation see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

This proposed patchset enables RDRAND bypass for current users of the nonblocking random pool (that is, for /dev/urandom and its equvalent in-kernel users) but not for the blocking pool (/dev/random). This is because RDRAND, although reseeded way more frequently than what is practical to do in software, is technically a nonblocking source that can behave as a PRNG. It can be used as a source for randomness for /dev/random, but that is not addressed by this patchset.

From: "H. Peter Anvin" <[email protected]>

Add support for architecture-specific hooks into either the blocking or the nonblocking random pools. These hooks are defined to return the number of bytes of randomness produced (similar to a read() system call.) They could also potentialy be used to inject randomness on demand while continuing to use the pool system, by calling a suitable injection interface and returning 0.

---
 drivers/char/random.c  |   26 ++++++++++++++++++++++++++
 include/linux/random.h |   18 ++++++++++++++++++
 2 files changed, 44 insertions(+), 0 deletions(-)

index d4ddeba..ca8a86c 100644
@@ -416,6 +416,7 @@ struct entropy_store {
 	const char *name;
 	struct entropy_store *pull;
 	int limit;
+	struct get_entropy_funcs arch; /* Arch-specific shortcut */
 
 	/* read-write data: */
 	spinlock_t lock;

@@ -862,6 +863,15 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
 
+	if (r->arch.get_entropy_krnl) {
+		ret = r->arch.get_entropy_krnl(buf, nbytes);
+		buf += ret;
+		nbytes -= ret;
+	}
+
+	if (!nbytes)
+		return ret;
+
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 

@@ -894,6 +904,15 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 	ssize_t ret = 0, i;
 	__u8 tmp[EXTRACT_SIZE];
 
+	if (r->arch.get_entropy_user) {
+		ret = r->arch.get_entropy_user(buf, nbytes);
+		buf += ret;
+		nbytes -= ret;
+	}
+
+	if (!nbytes)
+		return ret;
+
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, 0, 0);
 

@@ -954,6 +973,11 @@ static void init_std_data(struct entropy_store *r)
 	r->entropy_count = 0;
 	spin_unlock_irqrestore(&r->lock, flags);
 
+	if (nonblocking_pool.arch.get_entropy_krnl) {
+		nonblocking_pool.arch.get_entropy_krnl(input_pool_data,
+						       sizeof input_pool_data);
+	}
+
 	now = ktime_get_real();
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));

@@ -961,6 +985,8 @@ static void init_std_data(struct entropy_store *r)
 
 static int rand_initialize(void)
 {
+	arch_setup_random_funcs(&nonblocking_pool.arch,
+				&blocking_pool.arch);
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	init_std_data(&nonblocking_pool);

index fb7ab9d..12bb392 100644
@@ -10,6 +10,7 @@
 #include <linux/types.h>
 #include <linux/ioctl.h>
 #include <linux/irqnr.h>
+#include <linux/errno.h>
 
 /* ioctl()'s for the random number generator */
 

@@ -75,7 +76,24 @@ extern const struct file_operations random_fops, urandom_fops;
 unsigned int get_random_int(void);
 unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
 
+struct get_entropy_funcs {
+	ssize_t (*get_entropy_krnl)(void *buf, size_t nbytes);
+	ssize_t (*get_entropy_user)(void __user *buf, size_t nbytes);
+};
+
+#ifdef CONFIG_ARCH_RANDOM
+void arch_setup_random_funcs(struct get_entropy_funcs *nbp,
+			     struct get_entropy_funcs *bp);
+#else
+static inline void arch_setup_random_funcs(struct get_entropy_funcs *nbp,
+					   struct get_entropy_funcs *bp)
+{
+	/* Nothing to do */
+}
+#endif
+
 u32 random32(void);
+
 void srandom32(u32 seed);
 
 u32 prandom32(struct rnd_state *);

1.7.6

I have already NAKed this approach in no uncertain terms.

What if the next fancy hardware RNG with its own crypto hardening[1] that shows up is not a special CPU instruction or indeed not even arch-specific? It could just as easily be a USB or i2c or PCI device. There's no reason to think the two notions are connected AT ALL. Your whole notion of an 'architectural random source' is just plain wrong. The right way to do this is to add a generic extension to the existing hardware RNG design.

If you want to make forward progress, spend the half a day to implement a standard HWRNG driver so people with your hardware have basic functionality, then come back and we'll discuss implementing a trusted fast path API to HWRNG drivers. If you had done this weeks ago when I first asked you to do that, you would have had no problem getting basic support into the current merge window.

[1] hopefully auditable without an electron microscope!

Mathematics is the supreme nostalgia of our time.

Doesn't matter.

Talking about "standard hardware random number drivers" is just crazy talk, when the instruction is a single instruction that takes tens of nanoseconds to run. Any driver overhead would be just crazy, and no user would ever want that anyway.

User space would never use it, because they just want to use the instruction directly.

And kernel space doesn't want it either, for the exact same reason. There's no point in making it anything but a simple direct function call, because the whole functionality is so cheap.

This is not like some stupid "behind PCI" crap. It's high bandwidth and low latency.

If anything, I think Peter's approach perhaps doesn't tie it in close enough. Instead of making it some indirect function you register, just make it an inline function per architecture that just returns how many bits of randomness it gives (default to just an inline function that returns 0 for the case of no on-CPU rng).

On x86, choice between the different possible random number generators (if somebody cares enough about the cyrix and whatever ones) could be a an asm_alternate() thing.

If you don't trust the CPU rng, don't bother with stupid arguments about electron microscopes. Test it - or more reasonably - make it just one small part of the entropy pool. But don't make it something heavy-weight, when the whole *point* of having the hardware is to make it light-weight.

Linus

also, if you don't trust the CPU and want an electron microscope, make sure to also audit the "mov" instruction that you use the cycle after getting the random number, maybe THAT is booby trapped to muck with the result ;-)

Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Good to know, feel free to drop me from MAINTAINERS.

Did you even look at these patches?

Here's Peter's interface:

+ ssize_t (*get_entropy_krnl)(void *buf, size_t nbytes);

Here's the hwrng interface:

	int (*read)(struct hwrng *rng, void *data, size_t max, bool wait);

The overhead on the kernel side for an "architectural random hook" and a bog-standard HWRNG is basically the same. Here's a buffer, put N bytes in it.

But then, the bulk of this patch is actually putting in a fast path to pass this off to user space through /dev/urandom.

So here you are yammering on about "any driver overhead would be just crazy" when the whole point of these patches is in fact CHARACTER DRIVERS. We could already have a HWRNG interface that's just as fast in the time we've spent debating this.

If you want to add a function get_fast_random_bytes() that turns into inline assembly on Intel (and Via Padlock and whatever else shows up) and falls back to get_random_bytes, great. That has nothing to do with these patches.

Mathematics is the supreme nostalgia of our time.

Umm. My exact point about the email was that we should if anything change Peter's patch *away* from some kind of abstracted driver interface. But that was what you were arguing for, and that was what I was dismissing.

So when you argue for not taking the patches because you want a generic interface, I tell you that the argument is bogus.

Now, if you now argue that we should make it closer, and not take Peter's patches for *that* reason, then I'd be in whole-hearted agreement with you.

Which way is it?

Linus

Well then rather than saying my NAK doesn't matter, you should say you also NAK it.

Is there a reason you think making RDRAND available to userspace as a HWRNG is a bad idea? Is there a reason it's not the most obviously correct, least controversial first step to supporting this hardware?

No, there's not. Which is why I asked Peter to do this weeks ago.

It will only be bogus when Peter shows up with a patch that doesn't touch /dev/urandom, which IS a generic interface.

There are two sets of possible consumers here, in-kernel and userspace. Peter's patches are aimed squarely at the latter but you seem to be talking exclusively about in-kernel users.

This is a lot like RDTSC. Sure, it makes sense to have an in-kernel inline for this. I've even suggested a name. But when it comes to gettimeofday(), we're going to insist on using a clocksource and we're going to insist that it meets all the guarantees that gettimeofday() normally makes.

Mathematics is the supreme nostalgia of our time.

No, I don't think your NAK matters because your arguments were so insane.

Talking about electron microscopes and *expanding* on the patch just makes me go "that NAK is not worth worrying about".

You comparing the rdrand to 'rdtsc' is more realistic, but it still dismisses how powerful rdrand is.

The fact is, even if you worry about some back door for the NSA, or some theoretical lack of perfect 32-bit randomness, we can pretty much depend on it. We still do our own hashing on top of whatever entropy we get out of rdrand, and we would still have all our other stuff. Plus the instruction is public and testable - if Intel did something wrong, they'll be *very* embarrassed.

In other words, there's absolutely no reason not to use it, and allow us to get away from /dev/random running out of entropy. We absolutely should use it for bootup randomness (where we currently are somewhat weak), and I absolutely disagree that it should be made into more of a driver abstraction.

I'd be willing to take Peter's patch *without* the abstraction, and then just expect to cut it down.

But I'd be even more willing to just take something that just introduces a per-arch interface to get a "unsigned long *" that is random, and returning the number of bits of expected entropy in that thing. And for x86 CPU's with the RDRAND capability bit, I'd give Intel the benefit of the doubt and just make it do a single "rdrand" and return the full 64 bit (or is it a 32-bit interface? I should know, but I didn't look it up).

Of course, if there are other known random interfaces that might give more random bits, maybe "void *"+size is actually the right thing. Probably a single word is the most reasonable and simple interface in the absence of examples to the contrary, though.

Linus

Technically speaking, if Intel and the NSA were colluding together in a competent way, we'd never know; it's not something that could be tested. Intel could have implemented a incrementing counter which was initialized to some randomness, which was then encrypted by some NSA secret algorithm with a secret key known only to the NSA. We'd never know, but it would be enough of a backdoor for the NSA to do what they need to know. The only way it could leak out is via the human channel; if someone was upset enough about it that they send the algorithm and secret key to wikileaks.

But yeah, we can definitely depend on it if it is hashed into the pool and it's on top of everything else that we do. And it's all a matter of how paranoid you want to be. If you are working for government, where the NSA is by definition one of the good guys, then using rdrand directly is completely not a problem. If you are working for any other government agency, you'd probably want to mix it into the a random pool just to feel better about implicitly trusting Intel.

So I agree with Linus here.

- Ted

So here is my counter-suggestion

NOTE NOTE NOTE! This is completely and utterly untested. I didn't actually check how big the "rdrand" and "setc" instructions are, so the ASM_NOP4 there is just a random "I guess two 'xor' instructions are four bytes shorter than the rdrand/setc instructions are".

So please don't take this as a serious patch that should be applied, but instead take it as a serious alternative *approach*.

Note that with the default inline function in <asm-generic/random.h> is designed so that architectures that use it (this patch does *not* contain the architecture glue to enable it) will compile the loop in random.c entirely away. No test, no nothing.

Comments?

(Btw, even on x86, assuming the concept works and the ASM_NOP4 is corrected to the right length, we'd need to support older assemblers that don't understand the "rdrand" instruction, so it would need to be done as a explicit byte sequence).

Again, TOTALLY UNTESTED. Concept patch only!! There may be seriously stupid bugs here, but the point is that it should make it easy for an architecture to have a "get a word of random data quickly".

Linus

commit 218603412aad073a04ea815858b98f6c33ab30d2

Author: Linus Torvalds <[email protected]>
Date:   Sat Jul 30 15:06:16 2011 -1000

EXAMPLE 'RDRAND' PATCH

NOT FOR REAL CONSUMPTION!

---
 arch/x86/include/asm/random.h |   23 +++++++++++++++++++++++
 drivers/char/random.c         |   15 +++++++++++++++
 include/asm-generic/random.h  |   13 +++++++++++++
 3 files changed, 51 insertions(+), 0 deletions(-)

new file mode 100644
index 000000000000..f6fbd3340608
@@ -0,0 +1,23 @@
+#ifndef _X86_RANDOM_H
+#define _X86_RANDOM_H
+
+#include <asm/alternative.h>
+
+static inline int arch_get_random_word(unsigned long *word)
+{
+	int ret;
+
+	alternative_io("xor %0,%0; xor %1,%1" ASM_NOP4,
+		"rdrand %1; setcc %0",
+		X86_FEATURE_PERFCTR_CORE,
+		ASM_OUTPUT2("=a" (ret), "=d" (*word)),
+		"i" (0) /* fake input */);
+	/*
+	 * We return 0 if CF is clear of if the CPU
+	 * doesn't support RDRAND, otherwise we return
+	 * 8 (for 8 bytes of data).
+	 */
+	return ret & 8;
+}
+
+#endif

index 729281961f22..e335ec96bf88 100644
@@ -257,6 +257,7 @@
 #include <asm/uaccess.h>
 #include <asm/irq.h>
 #include <asm/io.h>
+#include <asm/random.h>
 
 /*
  * Configuration information

@@ -865,6 +866,20 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 
+	/* Use fast CPU random words if available */
+	while (nbytes) {
+		unsigned long word;
+		int bytes = arch_get_random_word(&word);
+		if (!bytes)
+			break;
+		if (bytes > nbytes)
+			bytes = nbytes;
+		memcpy(buf, &word, bytes);
+		nbytes -= bytes;
+		buf += bytes;
+		ret += bytes;
+	}
+
 	while (nbytes) {
 		extract_buf(r, tmp);
 

new file mode 100644
index 000000000000..e9be12ba86fa
@@ -0,0 +1,13 @@
+#ifndef _ASM_RANDOM_H
+#define _ASM_RANDOM_H
+
+/*
+ * Architecture random data in low bytes of "word", return how
+ * many bytes were filled in. Default implementation: none.
+ */
+static inline int arch_get_random_word(unsigned long *word)
+{
+	return 0;
+}
+
+#endif

The only minor issue with this is that RDRAND can, at least in theory, return a failure condition transiently ("the entropy buffer is empty") or permanently ("the random number generator is broken.") Although we have never actually observed the former under anything approaching realistic conditions, the recommendation is to loop for 10 iterations.

The end result is a small loop, just over 20 bytes long; as a result I left the implementation as a subroutine instead of inlining it in my v2 patch:

ENTRY(x86_rdrand_long)
mov $RDRAND_RETRY_LIMIT, %eax
1:
.byte 0x48, 0x0f, 0xc7, 0xf2 /* rdrand %rdx */
jnc 2f
mov %rdx, (%rdi)
ret
2:
dec %eax
rep;nop
jnz 1b
ret
ENDPROC(x86_rdrand_long)

We can of course inline this loop with alternatives if you would prefer.
I'll do a v3 patchset with that implementation later today and we can
check out how it looks.

What makes that more than a bit ugly is that extract_entropy() and extract_entropy_user() take their randomness type ("perfect/blocking" versus "PRNG degrade OK/nonblocking") from a pointer to the pool, which means that some kind of indirection or policy information is going to be necessary there anyway, in order to enable get_random_bytes() and its friends -- as opposed to get_random_int().

As such, it seems cleaner to me to take the hit of going through a function pointer.

-hpa

H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

So I don't care too deeply, we could easily make the "alternative_io()" thing just do a "call" to an out-of-line thing instead.

That said, I seriously suggest that we shouldn't even care.

Why?

Because the high-level code needs to handle the failure case *anyway*, so if there is some "in theory, CF might be clear and we don't get any data" under certain odd an unusual circumstances, I think we might as well just opt out for braking out early. So I don't think we really should necessarily at all do the intel-recommended "loop at least ten times", because quite frankly, we're probably better off just falling back to our old sw fallback anyway.

So at this point, I'd much rather go for "really simple, straightforward and small" than anything else.

Why?

WHY SHOULD WE CARE?

Nobody is ever going to complain about being better than necessary, and the whole point of rdrand should be that it's (a) fast enough and
(b) good enough that the whole "blocking/degraded" thing is a total nonissue.

In other words, we should consider rdrand to be "perfect + nonblocking", which is acceptable to everybody. Those nonblocking users aren't going to complain about good randomness, even if they might *accept* less than perfect randomness.

IOW, I really want to aim for simple and straightforward. Don't make it more complicated than it is.

Aim to make my patch *smaller* rather than trying to find ways to make it bigger.

Linus

This version of the patchset uses inlines with alternatives as proposed by Linus. In order to avoid the issue of "random" vs "urandom", this hooks into *only* the kernel consumer interfaces get_random_bytes() and get_random_int(); this means that legacy users of /dev/urandom in userspace will not get direct use RDRAND, but those can be eventually converted to using RDRAND directly in userspace.

We can, of course, still both pools randomness via rngd or a future in-kernel mechanism as proposed by Matt.

Since there was a minor amount of confusion I want to clarify: RDRAND architecturally has weaker security guarantees than the documented interface for /dev/random, so we can't just replace all users of extract_entropy() with RDRAND.

Git tree also available:

git://git.kernel.org/pub/scm/linux/kernel/git/hpa/linux-rdrand.git rdrand-3

Again, for technical documentation see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

Changes in version 3:
- Use inline hooks.
- Enable get_random_int() and get_random_bytes() only, in other words only enable the in-kernel users.
- Drop the preinitialization of the random pools; since they are only used for userspace consumers when RDRAND is available, they can be fed entropy via the input mechanism.

Total changes:

 Documentation/kernel-parameters.txt |    5 ++
 arch/x86/Kconfig                    |    9 ++++
 arch/x86/include/asm/archrandom.h   |   75 +++++++++++++++++++++++++++++++++++
 arch/x86/kernel/cpu/Makefile        |    1 +
 arch/x86/kernel/cpu/common.c        |    2 +
 arch/x86/kernel/cpu/rdrand.c        |   73 ++++++++++++++++++++++++++++++++++
 drivers/char/random.c               |   25 ++++++++++-
 include/linux/random.h              |   13 ++++++
 8 files changed, 200 insertions(+), 3 deletions(-)

From: "H. Peter Anvin" <[email protected]>

Add support for architecture-specific hooks into the kernel-directed random number generator interfaces. This patchset does not use the architecture random number generator interfaces for the userspace-directed interfaces (/dev/random and /dev/urandom), thus eliminating the need to distinguish between them based on a pool pointer.

Changes in version 3:
- Moved the hooks from extract_entropy() to get_random_bytes().
- Changes the hooks to inlines.

---
 drivers/char/random.c  |   25 ++++++++++++++++++++++---
 include/linux/random.h |   13 +++++++++++++
 2 files changed, 35 insertions(+), 3 deletions(-)

index d4ddeba..bb58712 100644
@@ -932,7 +932,21 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
  */
 void get_random_bytes(void *buf, int nbytes)
 {
-	extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0);
+	char *p = buf;
+
+	while (nbytes) {
+		unsigned long v;
+		int chunk = min(nbytes, (int)sizeof(unsigned long));
+		
+		if (!arch_get_random_long(&v))
+			break;
+		
+		memcpy(buf, &v, chunk);
+		p += chunk;
+		nbytes -= chunk;
+	}
+
+	extract_entropy(&nonblocking_pool, p, nbytes, 0, 0);
 }
 EXPORT_SYMBOL(get_random_bytes);
 

@@ -1635,8 +1649,13 @@ DEFINE_PER_CPU(__u32 [4], get_random_int_hash);
 unsigned int get_random_int(void)
 {
 	struct keydata *keyptr;
-	__u32 *hash = get_cpu_var(get_random_int_hash);
-	int ret;
+	__u32 *hash;
+	unsigned int ret;
+
+	if (arch_get_random_int(&ret))
+		return ret;
+
+	hash = get_cpu_var(get_random_int_hash);
 
 	keyptr = get_keyptr();
 	hash[0] += current->pid + jiffies + get_cycles();

index fb7ab9d..079cbba 100644
@@ -102,6 +102,19 @@ static inline void prandom32_seed(struct rnd_state *state, u64 seed)
 	state->s3 = __seed(i, 15);
 }
 
+#ifdef CONFIG_ARCH_RANDOM
+# include <asm/archrandom.h>
+#else
+static inline int arch_get_random_long(unsigned long *v)
+{
+	return 0;
+}
+static inline int arch_get_random_int(unsigned int *v)
+{
+	return 0;
+}
+#endif
+
 #endif /* __KERNEL___ */
 
 #endif /* _LINUX_RANDOM_H */

1.7.6

From: "H. Peter Anvin" <[email protected]>

Architectural inlines to get random ints and longs using the RDRAND instruction.

Intel has introduced a new RDRAND instruction, a Digital Random Number Generator (DRNG), which is functionally an high bandwidth entropy source, cryptographic whitener, and integrity monitor all built into hardware. This enables RDRAND to be used directly, bypassing the kernel random number pool.

For technical documentation, see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

In this patch, this is *only* used for the nonblocking random number pool. RDRAND is a nonblocking source, similar to our /dev/urandom, and is therefore not a direct replacement for /dev/random. The architectural hooks presented in the previous patch only feed the kernel internal users, which only use the nonblocking pool, and so this is not a problem.

Since this instruction is available in userspace, there is no reason to have a /dev/hw_rng device driver for the purpose of feeding rngd. This is especially so since RDRAND is a nonblocking source, and needs additional whitening and reduction (see the above technical documentation for details) in order to be of "pure entropy source" quality.

The CONFIG_EXPERT compile-time option can be used to disable this use of RDRAND.

---
 arch/x86/Kconfig                  |    9 +++++
 arch/x86/include/asm/archrandom.h |   73 +++++++++++++++++++++++++++++++++++++
 2 files changed, 82 insertions(+), 0 deletions(-)
 create mode 100644 arch/x86/include/asm/archrandom.h

index 37357a5..a0e9bda 100644
@@ -1451,6 +1451,15 @@ config ARCH_USES_PG_UNCACHED
 	def_bool y
 	depends on X86_PAT
 
+config ARCH_RANDOM
+	def_bool y
+	prompt "x86 architectural random number generator" if EXPERT
+	---help---
+	  Enable the x86 architectural RDRAND instruction
+	  (Intel Bull Mountain technology) to generate random numbers.
+	  If supported, this is a high bandwidth, cryptographically
+	  secure hardware random number generator.
+
 config EFI
 	bool "EFI runtime service support"
 	depends on ACPI

1.7.6

From: "H. Peter Anvin" <[email protected]>

If the CPU declares that RDRAND is available, go through a guranteed reseed sequence, and make sure that it is actually working (producing
data.) If it does not, disable the CPU feature flag.

Allow RDRAND to be disabled on the command line (as opposed to at compile time) for a user who has special requirements with regards to random numbers.

---
 Documentation/kernel-parameters.txt |    5 ++
 arch/x86/include/asm/archrandom.h   |    2 +
 arch/x86/kernel/cpu/Makefile        |    1 +
 arch/x86/kernel/cpu/common.c        |    2 +
 arch/x86/kernel/cpu/rdrand.c        |   73 +++++++++++++++++++++++++++++++++++
 5 files changed, 83 insertions(+), 0 deletions(-)
 create mode 100644 arch/x86/kernel/cpu/rdrand.c

index aa47be7..397ee05 100644
@@ -1764,6 +1764,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
 
 	noresidual	[PPC] Don't use residual data on PReP machines.
 
+	nordrand	[X86] Disable the direct use of the RDRAND
+			instruction even if it is supported by the
+			processor.  RDRAND is still available to user
+			space applications.
+
 	noresume	[SWSUSP] Disables resume and restores original swap
 			space.
 

index b7b5bc0..0d9ec77 100644
@@ -70,4 +70,6 @@ GET_RANDOM(arch_get_random_int, unsigned int, RDRAND_INT, ASM_NOP3);
 
 #endif  /* CONFIG_ARCH_RANDOM */
 
+extern void x86_init_rdrand(struct cpuinfo_x86 *c);
+
 #endif /* ASM_X86_ARCHRANDOM_H */

index 6042981..0e3a82a 100644
@@ -15,6 +15,7 @@ CFLAGS_common.o		:= $(nostackp)
 obj-y			:= intel_cacheinfo.o scattered.o topology.o
 obj-y			+= proc.o capflags.o powerflags.o common.o
 obj-y			+= vmware.o hypervisor.o sched.o mshyperv.o
+obj-y			+= rdrand.o
 
 obj-$(CONFIG_X86_32)	+= bugs.o
 obj-$(CONFIG_X86_64)	+= bugs_64.o

index 22a073d..8dbd929 100644
@@ -15,6 +15,7 @@
 #include <asm/stackprotector.h>
 #include <asm/perf_event.h>
 #include <asm/mmu_context.h>
+#include <asm/archrandom.h>
 #include <asm/hypervisor.h>
 #include <asm/processor.h>
 #include <asm/sections.h>

@@ -857,6 +858,7 @@ static void __cpuinit identify_cpu(struct cpuinfo_x86 *c)
 #endif
 
 	init_hypervisor(c);
+	x86_init_rdrand(c);
 
 	/*
 	 * Clear/Set all flags overriden by options, need do it

1.7.6

FWIW these patches look good to me and I'm happy to take them if Linus doesn't merge them directly.

Thanks,

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Thanks. I have put them in -tip as well:

git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-tip.git x86/rdrand

... but if you think there is a more appropriate workflow that would be good too.

-hpa

H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

That works for me.

Thanks!

Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

From: "H. Peter Anvin" <[email protected]>

Intel has introduced a new RDRAND instruction, a Digital Random Number Generator (DRNG), which is functionally an high bandwidth entropy source, cryptographic whitener, and integrity monitor all built into hardware. This enables RDRAND to be used directly, bypassing the kernel random number pool.

For technical documentation, see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

In this patch, this is *only* used for the nonblocking random number pool. RDRAND is a nonblocking source, similar to our /dev/urandom, and is therefore not a direct replacement for /dev/random. It can, and presumably should, be used to feed the blocking entropy pool as well, but that is not implemented in this patch and may be better done in rngd.

The nordrand kernel parameter or a CONFIG_EXPERT compile-time option can be used to disable this use of RDRAND.

---
 Documentation/kernel-parameters.txt |    5 +
 arch/x86/Kconfig                    |    9 ++
 arch/x86/kernel/Makefile            |    6 +-
 arch/x86/kernel/rdrand.c            |  148 +++++++++++++++++++++++++++++++++++
 arch/x86/kernel/rdrand_asm.S        |   57 +++++++++++++
 5 files changed, 223 insertions(+), 2 deletions(-)
 create mode 100644 arch/x86/kernel/rdrand.c
 create mode 100644 arch/x86/kernel/rdrand_asm.S

index aa47be7..397ee05 100644
@@ -1764,6 +1764,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
 
 	noresidual	[PPC] Don't use residual data on PReP machines.
 
+	nordrand	[X86] Disable the direct use of the RDRAND
+			instruction even if it is supported by the
+			processor.  RDRAND is still available to user
+			space applications.
+
 	noresume	[SWSUSP] Disables resume and restores original swap
 			space.
 

index 37357a5..a0e9bda 100644
@@ -1451,6 +1451,15 @@ config ARCH_USES_PG_UNCACHED
 	def_bool y
 	depends on X86_PAT
 
+config ARCH_RANDOM
+	def_bool y
+	prompt "x86 architectural random number generator" if EXPERT
+	---help---
+	  Enable the x86 architectural RDRAND instruction
+	  (Intel Bull Mountain technology) to generate random numbers.
+	  If supported, this is a high bandwidth, cryptographically
+	  secure hardware random number generator.
+
 config EFI
 	bool "EFI runtime service support"
 	depends on ACPI

index 90b06d4..ce5f7f3b 100644
@@ -86,12 +86,12 @@ obj-$(CONFIG_KEXEC)		+= relocate_kernel_$(BITS).o crash.o
 obj-$(CONFIG_CRASH_DUMP)	+= crash_dump_$(BITS).o
 obj-$(CONFIG_KPROBES)		+= kprobes.o
 obj-$(CONFIG_MODULES)		+= module.o
-obj-$(CONFIG_DOUBLEFAULT) 	+= doublefault_32.o
+obj-$(CONFIG_DOUBLEFAULT)	+= doublefault_32.o
 obj-$(CONFIG_KGDB)		+= kgdb.o
 obj-$(CONFIG_VM86)		+= vm86_32.o
 obj-$(CONFIG_EARLY_PRINTK)	+= early_printk.o
 
-obj-$(CONFIG_HPET_TIMER) 	+= hpet.o
+obj-$(CONFIG_HPET_TIMER)	+= hpet.o
 obj-$(CONFIG_APB_TIMER)		+= apb_timer.o
 
 obj-$(CONFIG_AMD_NB)		+= amd_nb.o

@@ -116,6 +116,8 @@ obj-$(CONFIG_X86_CHECK_BIOS_CORRUPTION) += check.o
 obj-$(CONFIG_SWIOTLB)			+= pci-swiotlb.o
 obj-$(CONFIG_OF)			+= devicetree.o
 
+obj-$(CONFIG_ARCH_RANDOM)		+= rdrand.o rdrand_asm.o
+
 ###
 # 64 bit specific files
 ifeq ($(CONFIG_X86_64),y)

1.7.6

This does not cover the one question I [predictably] have: why not do this in rngd, rather than the kernel?

Since many (all?) TPM chips include a random number generator, Dell has made sure that most distros have a useful copy of the rng-tools userspace pkg I've been maintaining.

It would seem straightforward to add this to rngd, and enable RDRAND on older distros and kernels, as well as current distros / kernels. This also gets useful entropy to /dev/random as part of normal operation, rather than only merely speeding up /dev/urandom.

Though for the record, I do agree that this is a nice, small and clean kernel implementation.

Jeff

That is actually why I didn't do the /dev/random aspect of this. I have an rngd enabling patch in the works as well.

The reason for not using RDRAND *only* in rngd is that it is a poor match -- RDRAND is designed as a /dev/urandom-type replacement, but it is *way* faster than the in-kernel system (since it is all in hardware)... plus it is reseeded far more frequently than what is possible in software (the architectural spec guarantees a reseed every 512 reads; I am told by the hardware people that in reality it is way more frequent than that.)

For /dev/random, we do want to be hyper-conservative, though. rngd in its current form doesn't deal with fractional entropy, which means boiling it down to guaranteed pure entropy; this is an enormous data reduction and about three orders of magnitude reduction in bandwidth. For /dev/random, I think that is just fine; after all, if you're asking for /dev/random, you're asking for security at every cost.

As previously stated, I have that patch in the works as well.

-hpa

So that's a silly question. It's a dichotomy that just doesn't exist. Go ahead and use rdrand in rngd too.

But that is entirely independent of the kernel. Why should any potential rngd use suddenly mean that the kernel shouldn't try to improve *its* random number code?

No reason what-so-ever. rngd can do whatever the hell it wants. The kernel doesn't care, and the kernel isn't impacted. There really is no reason to do "either or", and they have nothing to do with each other.

The kernel also uses the "mov" instruction too to move data between registers. Should that mean that user programs shouldn't use that instruction? Obviously not.

Linus

Updated version of the previous patchset, implementing the "single long" interface, adding get_random_int() enabling, and fixing a few bugs.

Git tree also available:

git://git.kernel.org/pub/scm/linux/kernel/git/hpa/linux-rdrand.git rdrand-2

This is a proposed patchset to enable the new x86 RDRAND instruction, labelled "Bull Mountain Technology" by Intel. It is a different beast than any other hardware random number generator that I have personally
encountered: it is not just a random number source, but contains a high bandwidth random number generator, an AES cryptographic whitener, and integrity monitoring all in hardware.

For technical documentation see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

This proposed patchset enables RDRAND bypass for current users of the nonblocking random pool (that is, for /dev/urandom and its equvalent in-kernel users) but not for the blocking pool (/dev/random). This is because RDRAND, although reseeded way more frequently than what is practical to do in software, is technically a nonblocking source that can behave as a PRNG. It can be used as a source for randomness for /dev/random, but that is not addressed by this patchset.

Changes in version 2:
- Have a single hook per pool (blocking, nonblocking) that returns an unsigned long. The loops to fill an arbitrary buffer has moved to generic code.
- Invoke the nonblocking hook to service get_random_int() if it is available. (Note: we could in theory do this for random32() as well, however, I have made the assumption that random32() is used when speed is the only thing that matters, and the current random32() implementation is extremely fast.)
- Correct the use of the nonblocking hook to preinitialize the pool data buffers. Version 1 would incorrectly initialize the input pool three times.

This version still retains the indirect function call. In the particular case of x86 RDRAND, there is some machinery that we need around the instruction which makes it slighly awkward to inline, and the function call doesn't seem to add enough overhead that it is worth making the interface uglier.

Total changes:

 Documentation/kernel-parameters.txt |    5 ++
 arch/x86/Kconfig                    |    9 +++
 arch/x86/kernel/Makefile            |    2 +
 arch/x86/kernel/rdrand.c            |   65 +++++++++++++++++
 arch/x86/kernel/rdrand_asm.S        |   57 +++++++++++++++
 drivers/char/random.c               |  134 ++++++++++++++++++++++++++++++++++-
 include/linux/random.h              |   14 ++++
 7 files changed, 285 insertions(+), 1 deletions(-)

From: "H. Peter Anvin" <[email protected]>

Add support for architecture-specific hooks into either the blocking or the nonblocking random pools. These hooks are defined to produce a single random "unsigned long" and return true (nonzero) on success.

They could also potentialy be used to inject randomness on demand while continuing to use the pool system, by calling a suitable injection interface and returning 0.

Note: the "blocking" hook is not actually allowed to block; the semantic difference is that it is required to produce /dev/random-quality entropy if available.

Changes in version 2:
- Have a single hook per pool (blocking, nonblocking) that returns an unsigned long. The loops to fill an arbitrary buffer has moved to generic code.
- Invoke the nonblocking hook to service get_random_int() if it is available. (Note: we could in theory do this for random32() as well, however, the assumption is that random32() is used when speed is the only thing that matters, and the current random32() implementation is extremely fast.)
- Correct the use of the nonblocking hook to preinitialize the pool data buffers. Version 1 would incorrectly initialize the input pool three times.

---
 drivers/char/random.c  |  134 +++++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/random.h |   14 +++++
 2 files changed, 147 insertions(+), 1 deletions(-)

index d4ddeba..f2ddc6a 100644
@@ -416,6 +416,7 @@ struct entropy_store {
 	const char *name;
 	struct entropy_store *pull;
 	int limit;
+	arch_random_func_t arch_func; /* Arch-specific shortcut */
 
 	/* read-write data: */
 	spinlock_t lock;

@@ -724,6 +725,104 @@ void add_disk_randomness(struct gendisk *disk)
 
 /*********************************************************************
  *
+ * Helper functions to fill a block from an arch-specific function
+ *
+ *********************************************************************/
+
+/* Clear a variable and make sure it is actually zeroed in memory */
+#define ZERO_VAR(x) do {			\
+	(x) = 0;				\
+	asm volatile("" : : "m" (x));		\
+} while (0)
+
+#ifdef CONFIG_ARCH_RANDOM
+
+static ssize_t func_to_kern(arch_random_func_t func,
+			    void *buf, size_t size)
+{
+	unsigned long *p1 = (unsigned long *)buf;
+	unsigned long rnd;
+	ssize_t ret = 0;
+	int ok;
+
+	while (size >= sizeof *p1) {
+		ok = func(p1);
+		if (unlikely(!ok))
+			goto out;
+		p1++;
+		size -= sizeof *p1;
+		ret  += sizeof *p1;
+	}
+
+	if (size) {
+		ok = func(&rnd);
+		if (unlikely(!ok))
+			goto out;
+		memcpy(p1, &rnd, size);
+		ret += size;
+	}
+
+out:
+	ZERO_VAR(rnd);
+	return ret;
+}
+
+static ssize_t func_to_user(arch_random_func_t func,
+			    void __user *buf, size_t size)
+{
+	char __user *p1 = (char __user *)buf;
+	unsigned long rnd;
+	size_t chunk;
+	ssize_t ret = 0;
+	int ok, err;
+
+	while (size >= sizeof rnd) {
+		ok = func(&rnd);
+		if (unlikely(!ok))
+			goto out;
+		err = copy_to_user(p1, &rnd, sizeof rnd);
+		chunk  = sizeof rnd - err;
+		p1    += chunk;
+		ret   += chunk;
+		size  -= chunk;
+		if (err)
+			goto out;
+	}
+
+	if (size) {
+		ok = func(&rnd);
+		if (unlikely(!ok))
+			goto out;
+		err = copy_to_user(p1, &rnd, size);
+		chunk  = size - err;
+		p1    += chunk;
+		ret   += chunk;
+		size  -= chunk;
+	}
+
+out:
+	ZERO_VAR(rnd);
+	return ret;
+}
+
+#else
+
+static inline ssize_t func_to_kern(arch_random_func_t func,
+				   void *buf, size_t size)
+{
+	return 0;
+}
+
+static inline ssize_t func_to_user(arch_random_func_t func,
+				   void __user *buf, size_t size)
+{
+	return 0;
+}
+
+#endif
+
+/*********************************************************************
+ *
  * Entropy extraction routines
  *
  *********************************************************************/

@@ -862,6 +961,15 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
 
+	if (r->arch_func) {
+		ret = func_to_kern(r->arch_func, buf, nbytes);
+		buf += ret;
+		nbytes -= ret;
+	}
+
+	if (!nbytes)
+		return ret;
+
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, min, reserved);
 

@@ -894,6 +1002,15 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 	ssize_t ret = 0, i;
 	__u8 tmp[EXTRACT_SIZE];
 
+	if (r->arch_func) {
+		ret = func_to_user(r->arch_func, buf, nbytes);
+		buf += ret;
+		nbytes -= ret;
+	}
+
+	if (!nbytes)
+		return ret;
+
 	xfer_secondary_pool(r, nbytes);
 	nbytes = account(r, nbytes, 0, 0);
 

@@ -954,6 +1071,11 @@ static void init_std_data(struct entropy_store *r)
 	r->entropy_count = 0;
 	spin_unlock_irqrestore(&r->lock, flags);
 
+	if (nonblocking_pool.arch_func) {
+		func_to_kern(nonblocking_pool.arch_func,
+			     r->pool, r->poolinfo->POOLBYTES);
+	}
+
 	now = ktime_get_real();
 	mix_pool_bytes(r, &now, sizeof(now));
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));

@@ -961,6 +1083,8 @@ static void init_std_data(struct entropy_store *r)
 
 static int rand_initialize(void)
 {
+	arch_setup_random_funcs(&nonblocking_pool.arch_func,
+				&blocking_pool.arch_func);
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	init_std_data(&nonblocking_pool);

@@ -1635,8 +1759,16 @@ DEFINE_PER_CPU(__u32 [4], get_random_int_hash);
 unsigned int get_random_int(void)
 {
 	struct keydata *keyptr;
-	__u32 *hash = get_cpu_var(get_random_int_hash);
+	__u32 *hash;
 	int ret;
+	unsigned long tmp;
+
+	if (nonblocking_pool.arch_func) {
+		if (nonblocking_pool.arch_func(&tmp))
+			return tmp;
+	}
+
+	hash = get_cpu_var(get_random_int_hash);
 
 	keyptr = get_keyptr();
 	hash[0] += current->pid + jiffies + get_cycles();

index fb7ab9d..65a1752 100644
@@ -10,6 +10,7 @@
 #include <linux/types.h>
 #include <linux/ioctl.h>
 #include <linux/irqnr.h>
+#include <linux/errno.h>
 
 /* ioctl()'s for the random number generator */
 

@@ -75,7 +76,20 @@ extern const struct file_operations random_fops, urandom_fops;
 unsigned int get_random_int(void);
 unsigned long randomize_range(unsigned long start, unsigned long end, unsigned long len);
 
+typedef int (*arch_random_func_t)(unsigned long *);
+#ifdef CONFIG_ARCH_RANDOM
+void arch_setup_random_funcs(arch_random_func_t *nonblocking,
+			     arch_random_func_t *blocking);
+#else
+static inline void arch_setup_random_funcs(arch_random_func_t *nonblocking,
+					   arch_random_func_t *blocking)
+{
+	/* Nothing to do */
+}
+#endif
+
 u32 random32(void);
+
 void srandom32(u32 seed);
 
 u32 prandom32(struct rnd_state *);

1.7.6

From: "H. Peter Anvin" <[email protected]>

Intel has introduced a new RDRAND instruction, a Digital Random Number Generator (DRNG), which is functionally an high bandwidth entropy source, cryptographic whitener, and integrity monitor all built into hardware. This enables RDRAND to be used directly, bypassing the kernel random number pool.

For technical documentation, see:

http://software.intel.com/en-us/articles/download-the-latest-bull-mountain-software-implementation-guide/

In this patch, this is *only* used for the nonblocking random number pool. RDRAND is a nonblocking source, similar to our /dev/urandom, and is therefore not a direct replacement for /dev/random. It can, and presumably should, be used to feed the blocking entropy pool as well, but that is not implemented in this patch and may be better done in rngd.

Since this instruction is available in userspace, there is no reason to have a /dev/hw_rng device driver for the purpose of feeding rngd. This is especially so since RDRAND is a nonblocking source, and needs additional whitening and reduction (see the above technical documentation for details) in order to be of "pure entropy source" quality.

The nordrand kernel parameter or a CONFIG_EXPERT compile-time option can be used to disable this use of RDRAND.

---
 Documentation/kernel-parameters.txt |    5 +++
 arch/x86/Kconfig                    |    9 +++++
 arch/x86/kernel/Makefile            |    2 +
 arch/x86/kernel/rdrand.c            |   65 +++++++++++++++++++++++++++++++++++
 arch/x86/kernel/rdrand_asm.S        |   57 ++++++++++++++++++++++++++++++
 5 files changed, 138 insertions(+), 0 deletions(-)
 create mode 100644 arch/x86/kernel/rdrand.c
 create mode 100644 arch/x86/kernel/rdrand_asm.S

index aa47be7..397ee05 100644
@@ -1764,6 +1764,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
 
 	noresidual	[PPC] Don't use residual data on PReP machines.
 
+	nordrand	[X86] Disable the direct use of the RDRAND
+			instruction even if it is supported by the
+			processor.  RDRAND is still available to user
+			space applications.
+
 	noresume	[SWSUSP] Disables resume and restores original swap
 			space.
 

index 37357a5..a0e9bda 100644
@@ -1451,6 +1451,15 @@ config ARCH_USES_PG_UNCACHED
 	def_bool y
 	depends on X86_PAT
 
+config ARCH_RANDOM
+	def_bool y
+	prompt "x86 architectural random number generator" if EXPERT
+	---help---
+	  Enable the x86 architectural RDRAND instruction
+	  (Intel Bull Mountain technology) to generate random numbers.
+	  If supported, this is a high bandwidth, cryptographically
+	  secure hardware random number generator.
+
 config EFI
 	bool "EFI runtime service support"
 	depends on ACPI

index 90b06d4..d45d889 100644
@@ -116,6 +116,8 @@ obj-$(CONFIG_X86_CHECK_BIOS_CORRUPTION) += check.o
 obj-$(CONFIG_SWIOTLB)			+= pci-swiotlb.o
 obj-$(CONFIG_OF)			+= devicetree.o
 
+obj-$(CONFIG_ARCH_RANDOM)		+= rdrand.o rdrand_asm.o
+
 ###
 # 64 bit specific files
 ifeq ($(CONFIG_X86_64),y)

1.7.6