[RFD] Direct support for the x86 RDRAND instruction

[RFD] Direct support for the x86 RDRAND instruction

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@linux.intel.com>

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.

[PATCH 1/2] random: Add support for architectural random hooks

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@linux.intel.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c  |   26 ++++++++++++++++++++++++++
 include/linux/random.h |   18 ++++++++++++++++++
 2 files changed, 44 insertions(+), 0 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d4ddeba..ca8a86c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -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);
diff --git a/include/linux/random.h b/include/linux/random.h
index fb7ab9d..12bb392 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -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

[PATCH 2/2] x86, random: Add support for architectural random number generator

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@linux.intel.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 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

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index aa47be7..397ee05 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -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.
 
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 37357a5..a0e9bda 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
diff --git a/arch/x86/kernel/Makefile b/arch/x86/kernel/Makefile
index 90b06d4..ce5f7f3b 100644
--- a/arch/x86/kernel/Makefile
+++ b/arch/x86/kernel/Makefile
@@ -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)
diff --git a/arch/x86/kernel/rdrand.c b/arch/x86/kernel/rdrand.c
new file mode 100644
index 0000000..d89b122
--- /dev/null
+++ b/arch/x86/kernel/rdrand.c
@@ -0,0 +1,148 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#include <linux/random.h>
+#include <linux/module.h>
+#include <linux/uaccess.h>
+#include <asm/errno.h>
+
+extern int x86_rdrand_long(unsigned long *x); /* In rdrand_asm.S */
+
+/* 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)
+
+static ssize_t x86_random_bytes_krnl(void *buf, size_t size)
+{
+	unsigned long *p1 = (unsigned long *)buf;
+	unsigned long rnd;
+	ssize_t ret = 0;
+	int ok;
+
+	if (!boot_cpu_has(X86_FEATURE_RDRAND))
+		return 0;
+
+	while (size >= sizeof *p1) {
+		ok = x86_rdrand_long(p1);
+		if (unlikely(!ok))
+			goto out;
+		p1++;
+		size -= sizeof *p1;
+		ret  += sizeof *p1;
+	}
+
+	if (size) {
+		ok = x86_rdrand_long(&rnd);
+		if (unlikely(!ok))
+			goto out;
+		memcpy(p1, &rnd, size);
+		ret += size;
+	}
+
+out:
+	ZERO_VAR(rnd);
+	return ret;
+}
+
+static ssize_t x86_random_bytes_user(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;
+
+	if (!boot_cpu_has(X86_FEATURE_RDRAND))
+		return 0;
+
+	while (size >= sizeof rnd) {
+		ok = x86_rdrand_long(&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 = x86_rdrand_long(&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;
+}
+
+/*
+ * Force a reseed cycle; we are architecturally guaranteed a reseed
+ * after no more than 512 128-bit chunks of random data.  This also
+ * acts as a test of the CPU capability.
+ */
+#define RESEED_LOOP ((512*128)/sizeof(unsigned long))
+
+static bool rdrand_disabled;
+
+static __init int disable_rdrand(char *s)
+{
+	rdrand_disabled = true;
+	return 1;
+}
+__setup("nordrand", disable_rdrand);
+
+void arch_setup_random_funcs(struct get_entropy_funcs *nbp,
+			     struct get_entropy_funcs *bp)
+{
+	int i, count, ok;
+	unsigned long tmp;
+
+	(void)bp;		/* Do nothing to the blocking pool */
+
+	if (!boot_cpu_has(X86_FEATURE_RDRAND) || rdrand_disabled) {
+		/* Nothing available... */
+		return;
+	}
+
+	for (count = i = 0; i < RESEED_LOOP; i++) {
+		ok = x86_rdrand_long(&tmp);
+		if (ok)
+			count++;
+	}
+	ZERO_VAR(tmp);
+
+	if (likely(count == RESEED_LOOP)) {
+		nbp->get_entropy_krnl = x86_random_bytes_krnl;
+		nbp->get_entropy_user = x86_random_bytes_user;
+	}
+}
diff --git a/arch/x86/kernel/rdrand_asm.S b/arch/x86/kernel/rdrand_asm.S
new file mode 100644
index 0000000..5393565
--- /dev/null
+++ b/arch/x86/kernel/rdrand_asm.S
@@ -0,0 +1,57 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#include <linux/linkage.h>
+#include <asm/asm.h>
+
+#define RDRAND_RETRY_LIMIT	10
+
+#ifdef CONFIG_X86_64
+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)
+#else
+ENTRY(x86_rdrand_long)
+	mov	%eax, %ecx
+	mov	$RDRAND_RETRY_LIMIT, %eax
+1:
+	.byte 0x0f, 0xc7, 0xf2		/* rdrand %edx */
+	jnc	2f
+	mov	%edx, (%ecx)
+	ret
+2:
+	dec	%eax
+	rep;nop
+	jnz	1b
+	ret
+ENDPROC(x86_rdrand_long)
+#endif
-- 
1.7.6

Re: [RFD] Direct support for the x86 RDRAND instruction

[Jeff Garzik]

On 07/29/2011 04:37 PM, H. Peter Anvin wrote:
> From: "H. Peter Anvin"<hpa@linux.intel.com>
>
> 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.

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Matt Mackall]

On Fri, 2011-07-29 at 13:37 -0700, H. Peter Anvin wrote:
> From: "H. Peter Anvin" <hpa@linux.intel.com>
> 
> 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.

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.

Re: [RFD] Direct support for the x86 RDRAND instruction

[H. Peter Anvin]

On 07/29/2011 02:05 PM, Jeff Garzik wrote:
> 
> This does not cover the one question I [predictably] have:  why not do 
> this in rngd, rather than the kernel?
> 

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.

> 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.

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

	-hpa

Re: [RFD] Direct support for the x86 RDRAND instruction

[Linus Torvalds]

On Fri, Jul 29, 2011 at 2:05 PM, Jeff Garzik <jgarzik@pobox.com> wrote:
>
> This does not cover the one question I [predictably] have:  why not do this
> in rngd, rather than the kernel?

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Fri, Jul 29, 2011 at 2:16 PM, Matt Mackall <mpm@selenic.com> wrote:
>
> I have already NAKed this approach in no uncertain terms.

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Arjan van de Ven]

On Fri, 29 Jul 2011 23:20:40 -0700
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> If you don't trust the CPU rng, don't bother with stupid arguments
> about electron microscopes.  

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Matt Mackall]

On Fri, 2011-07-29 at 23:20 -0700, Linus Torvalds wrote:
> On Fri, Jul 29, 2011 at 2:16 PM, Matt Mackall <mpm@selenic.com> wrote:
> >
> > I have already NAKed this approach in no uncertain terms.
> 
> Doesn't matter.

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

> 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.

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.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 7:45 AM, Matt Mackall <mpm@selenic.com> wrote:
>
> Did you even look at these patches?

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Matt Mackall]

On Sat, 2011-07-30 at 08:20 -1000, Linus Torvalds wrote:
> On Sat, Jul 30, 2011 at 7:45 AM, Matt Mackall <mpm@selenic.com> wrote:
> >
> > Did you even look at these patches?
> 
> 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.

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

>  But that was what you were arguing for, and that was what I
> was dismissing.

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.

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

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

> 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.

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.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 9:13 AM, Matt Mackall <mpm@selenic.com> wrote:
>
> Well then rather than saying my NAK doesn't matter, you should say you
> also NAK it.

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Ted Ts'o]

On Sat, Jul 30, 2011 at 09:29:18AM -1000, Linus Torvalds wrote:
> 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.

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

[PATCH v2 0/2] Add support for architectural random number generator

[H. Peter Anvin]

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(-)

[PATCH v2 1/2] random: Add support for architectural random hooks

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@zytor.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c  |  134 +++++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/random.h |   14 +++++
 2 files changed, 147 insertions(+), 1 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d4ddeba..f2ddc6a 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -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();
diff --git a/include/linux/random.h b/include/linux/random.h
index fb7ab9d..65a1752 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -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

[PATCH v2 2/2] x86, random: Add support for architectural random number generator

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@zytor.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Originally-by: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 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

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index aa47be7..397ee05 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -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.
 
diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 37357a5..a0e9bda 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
diff --git a/arch/x86/kernel/Makefile b/arch/x86/kernel/Makefile
index 90b06d4..d45d889 100644
--- a/arch/x86/kernel/Makefile
+++ b/arch/x86/kernel/Makefile
@@ -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)
diff --git a/arch/x86/kernel/rdrand.c b/arch/x86/kernel/rdrand.c
new file mode 100644
index 0000000..df0e46b
--- /dev/null
+++ b/arch/x86/kernel/rdrand.c
@@ -0,0 +1,65 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#include <linux/random.h>
+#include <linux/module.h>
+#include <linux/uaccess.h>
+#include <asm/errno.h>
+
+extern int x86_rdrand_long(unsigned long *x); /* In rdrand_asm.S */
+
+/*
+ * Force a reseed cycle; we are architecturally guaranteed a reseed
+ * after no more than 512 128-bit chunks of random data.  This also
+ * acts as a test of the CPU capability.
+ */
+#define RESEED_LOOP ((512*128)/sizeof(unsigned long))
+
+static bool rdrand_disabled;
+
+static __init int disable_rdrand(char *s)
+{
+	rdrand_disabled = true;
+	return 1;
+}
+__setup("nordrand", disable_rdrand);
+
+void arch_setup_random_funcs(arch_random_func_t *nonblocking_func,
+			     arch_random_func_t *blocking_func)
+{
+	int i, count, ok;
+	unsigned long tmp;
+
+	if (!boot_cpu_has(X86_FEATURE_RDRAND) || rdrand_disabled) {
+		/* Nothing available... */
+		return;
+	}
+
+	for (count = i = 0; i < RESEED_LOOP; i++) {
+		ok = x86_rdrand_long(&tmp);
+		if (ok)
+			count++;
+	}
+
+	if (likely(count == RESEED_LOOP))
+		*nonblocking_func = x86_rdrand_long;
+}
diff --git a/arch/x86/kernel/rdrand_asm.S b/arch/x86/kernel/rdrand_asm.S
new file mode 100644
index 0000000..5393565
--- /dev/null
+++ b/arch/x86/kernel/rdrand_asm.S
@@ -0,0 +1,57 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#include <linux/linkage.h>
+#include <asm/asm.h>
+
+#define RDRAND_RETRY_LIMIT	10
+
+#ifdef CONFIG_X86_64
+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)
+#else
+ENTRY(x86_rdrand_long)
+	mov	%eax, %ecx
+	mov	$RDRAND_RETRY_LIMIT, %eax
+1:
+	.byte 0x0f, 0xc7, 0xf2		/* rdrand %edx */
+	jnc	2f
+	mov	%edx, (%ecx)
+	ret
+2:
+	dec	%eax
+	rep;nop
+	jnz	1b
+	ret
+ENDPROC(x86_rdrand_long)
+#endif
-- 
1.7.6

Re: [PATCH 1/2] random: Add support for architectural random hooks

[George Spelvin]

> 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 agree with your second paragraph, but disagree violently with your
first: Intel provide no way to test their RNG, and the AES-based whitener
makes it completely private and UNtestable.

Intel go into details about the hardware's boot-up self-test, but then
provide no way to access that self-test information, much less check up
on it.

I can feed all zeros into the described whitener and get output that is
not possible to distinguish from random, without access to the secret
initial state.  That's the whole point of a cipher, and AES is a very
good cipher!

The only technically difficult thing about implementing a back door
is ensuring that the output sequence doesn't repeat each power cycle.
You need just enough entropy or nonce to get that.

As long as you can achieve that, getting caught is actually quite unlikely.

Consider a sample implementation: implement it exactly as described,
except:
- Make the hardware known answer test (or, more specifically,
  the state of the DRBG after the KAT) the backdoor secret, and
- Suppress all but the first 40 bits of entropy from the hardware
  entropy source, replacing it with a fixed pattern (e.g. all zero).

An attacker who knows the secret needs to brute-force the 40 bits plus
the number of RDRND reads to be able to predict the RDRAND outout.

Someone who doesn't can ony detect the fiddle by power-cycling the
hardware a million times and looking for duplicate outputs.  (Birthday
attack on the amount of seed entropy.)

Even a small amount of persistent storage makes things more difficult.
For example, an 8-bit counter that usually survives power cycles replaces
the 40-bit birthday attack with 256 32-bit birthday attacks, requiring
256 * 2^16 = 2^24 power-cycles to find a collision.  While making an
attacker's job easier after they've brute-forced 40+ bits once.


I don't think it's *likely* that Intel have done this, but given the
about of National Security bullshit the U.S. government is throwing
around these days, I'm less than 10 bits certain that they haven't.


A much more verifiable way would be to provide access to the raw hardware
generator, and enough hardware documentation to predict how its output
varies with environmental conditions (temperature, supply voltage, clock
speed, x-rays, ...) and lot-to-lot.  It would be extremely difficult
to produce a deterministic (i.e. back-door-able) generator with the
same sensitivities.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 1:46 PM, George Spelvin <linux@horizon.com> wrote:
>
> I agree with your second paragraph, but disagree violently with your
> first: Intel provide no way to test their RNG, and the AES-based whitener
> makes it completely private and UNtestable.

Umm.

Guys, if your argument is that you cannot possibly distinguish the
Intel implementation from "true" randomness, then WHAT THE HELL are
you complaining about?

We don't even care. "True randomness" and "something we cannot
possibly even test and distinguish from true randomess" are 100%
equivalent. Stop with the idiotic "we cannot test it" crap. If it
really is indistinguishable from true randomness, nobody will ever
care.

It's that simple. Really.

And if somebody ever figures out that Intel flubbed, and you actually
*can* tell it from true randomness, even then, what's the downside? It
will be practically random anyway, and we'll be mixing it up some
more.

Seriously. This whole discussion just makes me convinced that security
people are so far removed from reality that it's not even relevant any
more.

            Linus

Re: [PATCH 1/2] random: Add support for architectural random hooks

[George Spelvin]

> Guys, if your argument is that you cannot possibly distinguish the
> Intel implementation from "true" randomness, then WHAT THE HELL are
> you complaining about?
>
> We don't even care. "True randomness" and "something we cannot
> possibly even test and distinguish from true randomess" are 100%
> equivalent. Stop with the idiotic "we cannot test it" crap. If it
> really is indistinguishable from true randomness, nobody will ever
> care.

Did you READ what I wrote beyond the first paragraph?

Because the LAST paragraph included a description of a
testable and verifiable hardware RNG.  To repeat:

>> A much more verifiable way would be to provide access to the raw hardware
>> generator, and enough hardware documentation to predict how its output
>> varies with environmental conditions (temperature, supply voltage, clock
>> speed, x-rays, ...) and lot-to-lot.  It would be extremely difficult
>> to produce a deterministic (i.e. back-door-able) generator with the
>> same sensitivities.

(Apologies for the bad grammar of "much more verifiable".)


The problem is not that's it's theoretically impossible to distinguish
them, but that it's PRACTICALLY impossible to distinguish true randomness
from a good counterfeiting effort.  As long as you're limited to
black-box testing.

That's counterfeiting, not incompetence.  The Intel RNG, if implemented
as described in their documentation, is quite well engineered.
(The basic architecture is essentially the same as /dev/urandom.)


I was just saying that it would be very easy to add a deliberate back
door, and the interface they provide fails to include any way to detect
such a thing.

> Seriously. This whole discussion just makes me convinced that security
> people are so far removed from reality that it's not even relevant any
> more.

The real world matters enormously.  Because that's where security
exploits happen, not in some mathematical abstraction that can be
proved secure.

I can build an RNG that nobody else can distinguish from truly random
until I start forging your signature on kernel releases.

Isn't that a bit LATE to be noticing the problem?

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Bryan Donlan]

On Sat, Jul 30, 2011 at 19:46, George Spelvin <linux@horizon.com> wrote:
>> 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 agree with your second paragraph, but disagree violently with your
> first: Intel provide no way to test their RNG, and the AES-based whitener
> makes it completely private and UNtestable.
[snip paranoia]

That's fine, but it's also not for the kernel to judge. Certainly
there should be an option to allow the user to disable the use of
RDRAND, if they're so inclined. But those who trust Intel's HWRNG
should be able to use it as efficiently as possible.

That said, I'm not sure I like Linus's proposed API. As I understand
it, he proposes something like:

int arch_get_random_word(unsigned long *pRandom);

Where arch_get_random_word returns 0 if not supported.

If we have that interface, then the urandom code implementing it might
look something _vaguely_ like this (ignoring the possibility of nbytes
% sizeof(unsigned long) != 0):

void __user *bufend = buf + nbytes;
while (buf < bufend) {
  unsigned long tmp;
  if (arch_get_random_word(&tmp)) {
    if (copy_to_user(buf, &tmp, sizeof(tmp))) {
      ret = -EFAULT;
      break;
    }
  } else {
    return urandom_fallback(buf, bufend-buf);
  }
  buf += sizeof(tmp);
}

The problem, as you can see here, is we need to test for the existence
of an architecture-specific HWRNG once for _every word processed_. And
since we don't know the return value of arch_get_random_word until we
probe the CPU's capability set at runtime, this isn't going to be
eliminated statically.

The alternative is to simply have a single hook-based API, passing in
a buffer and length, as in the HWRNG API, as well as this patch
series. You can then test whether there is a hook once, and then go
straight into a tight loop to generate your random data. This does add
a _tiny_ amount of overhead to the case where the user wants a single
word of random data, due to the indirect function call. However, in
that case the overhead is nothing compared to the system call entry
overhead. For larger buffers, the savings from avoiding a branch every
loop is likely to be far larger than your function pointer invocation.

Now, of course, you could do something like this:

if (arch_has_get_random_word) {
  while (buf < bufend) {
    unsigned long tmp = arch_get_random_word();
    copy_to_user(buf, &tmp, sizeof(tmp));
    buf += sizeof(tmp);
  }
}

I think it should be obvious that this a pretty terrible API, but as
far as I can see if you're steadfast on avoiding the overhead of a
hook then it's the best you can do.

In short, I have to agree with George Spelvin's suggestion of using
the hwrng API - just add a hook to allow urandom to be directed to a
hwrng device, and appropriate initialization code to do this at
startup if RDRAND is available. Heck, you might not even have to do
that - just configure udev to point /dev/urandom at the hwrng device
node, and now the kernel doesn't have to make any policy decisions on
what RNG to use at all.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

[-- Attachment #1: Type: text/plain, Size: 1161 bytes --]

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

[-- Attachment #2: patch.diff --]
[-- Type: text/x-patch, Size: 2402 bytes --]

commit 218603412aad073a04ea815858b98f6c33ab30d2
Author: Linus Torvalds <torvalds@linux-foundation.org>
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(-)

diff --git a/arch/x86/include/asm/random.h b/arch/x86/include/asm/random.h
new file mode 100644
index 000000000000..f6fbd3340608
--- /dev/null
+++ b/arch/x86/include/asm/random.h
@@ -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
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 729281961f22..e335ec96bf88 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -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);
 
diff --git a/include/asm-generic/random.h b/include/asm-generic/random.h
new file mode 100644
index 000000000000..e9be12ba86fa
--- /dev/null
+++ b/include/asm-generic/random.h
@@ -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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[H. Peter Anvin]

On 07/30/2011 06:13 PM, Linus Torvalds wrote:
> 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".
> 

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.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 3:02 PM, Bryan Donlan <bdonlan@gmail.com> wrote:
>
> The problem, as you can see here, is we need to test for the existence
> of an architecture-specific HWRNG once for _every word processed_.

See the patch I sent out. Not only doesn't it check an
architecture-specific flag on x86, IT COSTS NOTHING AT ALL on other
architectures. Not per byte, not per call, not at all.

On x86, it does have the cost of:

 - basically one conditional for the whole loop (branching out if
there is no rdrand support at all). You cannot do much better than
that, except of course if you statically say "compile for an x86 that
doesn't have rdrand")

 - a per-word cost of checking CF - which you are supposed to do
anyway (ie the rdrand hardware will return with CF clear if the data
isn't reliable).

So at least on x86, I think you can get pretty close to "optimal
behavior" with my approach.

              Linus

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 3:32 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>
> 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.

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.

> 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().

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

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Bryan Donlan]

On Sat, Jul 30, 2011 at 21:35, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> On Sat, Jul 30, 2011 at 3:02 PM, Bryan Donlan <bdonlan@gmail.com> wrote:
>>
>> The problem, as you can see here, is we need to test for the existence
>> of an architecture-specific HWRNG once for _every word processed_.
>
> See the patch I sent out. Not only doesn't it check an
> architecture-specific flag on x86, IT COSTS NOTHING AT ALL on other
> architectures. Not per byte, not per call, not at all.

Certainly, on architectures which never support fast hwrngs, you can
avoid the overhead. I'm concerned about whether you're actually coming
out ahead in the case where there _is_ an arch hwrng.

> On x86, it does have the cost of:
>
>  - basically one conditional for the whole loop (branching out if
> there is no rdrand support at all). You cannot do much better than
> that, except of course if you statically say "compile for an x86 that
> doesn't have rdrand")
>
>  - a per-word cost of checking CF - which you are supposed to do
> anyway (ie the rdrand hardware will return with CF clear if the data
> isn't reliable).
>
> So at least on x86, I think you can get pretty close to "optimal
> behavior" with my approach.

Ah, I see - I wasn't aware RDRAND could fail. In that case, it's not
so bad, although it would be nicer to directly branch on the carry
flag, rather than emitting code that will, eventually, do a setcc ->
and -> test -> branch.

In any case though, what about my suggestion - don't mess with urandom
at all, and let udev replace the /dev/urandom device node with one
directed to a fast hwrng device if one is detected? This has zero
extra overhead - you have to pass through the character device layer
no matter what, and you can go straight from there to either the
standard hwrng wrapper code, or to your own special extra-fast
implementation of dev_read. It should also satisfy Mr. Spelvin's
paranoia - he can just instruct his udev to not replace /dev/urandom.
And so we don't need to introduce any new APIs to the kernel at all,
nor do we need to touch any core code.

The downside, of course, is that in-kernel users of entropy won't have
this fast API - do we have the kind of high-volume non-blocking
entropy consumers in the kernel that might care about this?

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Henrique de Moraes Holschuh]

On Sat, 30 Jul 2011, Bryan Donlan wrote:
> In any case though, what about my suggestion - don't mess with urandom
> at all, and let udev replace the /dev/urandom device node with one
> directed to a fast hwrng device if one is detected? This has zero

Now, THAT would be unsafe, and a nasty way to go about it.

If you really don't want to touch /dev/.random, make it simple: either
export the embedded RNG as high-bandwidth /dev/hwrandom and let
userspace postprocess it and reroute it back to /dev/random as needed,
or do the same with a kernel thread.

-- 
  "One disk to rule them all, One disk to find them. One disk to bring
  them all and in the darkness grind them. In the Land of Redmond
  where the shadows lie." -- The Silicon Valley Tarot
  Henrique Holschuh

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Bryan Donlan]

On Sat, Jul 30, 2011 at 22:42, Henrique de Moraes Holschuh
<hmh@hmh.eng.br> wrote:
> On Sat, 30 Jul 2011, Bryan Donlan wrote:
>> In any case though, what about my suggestion - don't mess with urandom
>> at all, and let udev replace the /dev/urandom device node with one
>> directed to a fast hwrng device if one is detected? This has zero
>
> Now, THAT would be unsafe, and a nasty way to go about it.

I don't see why it's unsafe. It's leaving the policy decision of what
RNG to use up to userspace, without needing to introduce any new API
or parameter to do so. As long as the replacement device exposes the
same interface as /dev/urandom, no problem, right? Userspace programs
shouldn't notice the difference unless they stat() /dev/urandom and
look at the device numbers.

I do realize it's a bit unorthodox to replace what has, traditionally,
been a fixed device node with a configurable symlink, but there's no
technical reason (as far as I can see) why it shouldn't work.

> If you really don't want to touch /dev/.random, make it simple: either
> export the embedded RNG as high-bandwidth /dev/hwrandom and let
> userspace postprocess it and reroute it back to /dev/random as needed,
> or do the same with a kernel thread.

This approach is identical to mine as far as the kernel is concerned :)
You'd set up a daemon to pump entropy into /dev/random. Users who want
/dev/urandom to be even faster/more secure(?) can further symlink
/dev/urandom to /dev/hwrandom. But there's no need to change
/dev/urandom's implementation in the kernel to redirect it to the
hwrng when userspace can do that just as well on its own, is my point.

Re: [PATCH 1/2] random: Add support for architectural random hooks

[Linus Torvalds]

On Sat, Jul 30, 2011 at 4:02 PM, Bryan Donlan <bdonlan@gmail.com> wrote:
>
> In any case though, what about my suggestion - don't mess with urandom
> at all, and let udev replace the /dev/urandom device node with one
> directed to a fast hwrng device if one is detected?

Umm, user space is encouraged to do exactly that.

However, at no point does that mean "the kernel shouldn't do the best
it can". So it's a totally independent issue.

The kernel will want to use rdrand regardless of what user space does.
Both for legacy applications that don't know about rdrand, and for
scripts that don't want to bother. And for just its own use.

             Linus

[PATCH v3 0/3] Add support for architectural random number generator

[H. Peter Anvin]

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(-)

[PATCH v3 1/3] random: Add support for architectural random hooks

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@zytor.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 drivers/char/random.c  |   25 ++++++++++++++++++++++---
 include/linux/random.h |   13 +++++++++++++
 2 files changed, 35 insertions(+), 3 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d4ddeba..bb58712 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -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();
diff --git a/include/linux/random.h b/include/linux/random.h
index fb7ab9d..079cbba 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -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

[PATCH v3 2/3] x86, random: Architectural inlines to get random integers with RDRAND

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@zytor.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Originally-by: Fenghua Yu <fenghua.yu@intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 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

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index 37357a5..a0e9bda 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
diff --git a/arch/x86/include/asm/archrandom.h b/arch/x86/include/asm/archrandom.h
new file mode 100644
index 0000000..b7b5bc0
--- /dev/null
+++ b/arch/x86/include/asm/archrandom.h
@@ -0,0 +1,73 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#ifndef ASM_X86_ARCHRANDOM_H
+#define ASM_X86_ARCHRANDOM_H
+
+#include <asm/processor.h>
+#include <asm/cpufeature.h>
+#include <asm/alternative.h>
+#include <asm/nops.h>
+
+#define RDRAND_RETRY_LOOPS	10
+
+#define RDRAND_INT	".byte 0x0f,0xc7,0xf0"
+#ifdef CONFIG_X86_64
+# define RDRAND_LONG	".byte 0x48,0x0f,0xc7,0xf0"
+#else
+# define RDRAND_LONG	RDRAND_INT
+#endif
+
+#ifdef CONFIG_ARCH_RANDOM
+
+#define GET_RANDOM(name, type, rdrand, nop)			\
+static inline int name(type *v)					\
+{								\
+	int ok;							\
+	alternative_io("movl $0, %0\n\t"			\
+		       nop,					\
+		       "\n1: " rdrand "\n\t"			\
+		       "jc 2f\n\t"				\
+		       "decl %0\n\t"                            \
+		       "jnz 1b\n\t"                             \
+		       "2:",                                    \
+		       X86_FEATURE_RDRAND,                      \
+		       ASM_OUTPUT2("=r" (ok), "=a" (*v)),       \
+		       "0" (RDRAND_RETRY_LOOPS));		\
+	return ok;						\
+}
+
+#ifdef CONFIG_X86_64
+
+GET_RANDOM(arch_get_random_long, unsigned long, RDRAND_LONG, ASM_NOP5);
+GET_RANDOM(arch_get_random_int, unsigned int, RDRAND_INT, ASM_NOP4);
+
+#else
+
+GET_RANDOM(arch_get_random_long, unsigned long, RDRAND_LONG, ASM_NOP3);
+GET_RANDOM(arch_get_random_int, unsigned int, RDRAND_INT, ASM_NOP3);
+
+#endif /* CONFIG_X86_64 */
+
+#endif  /* CONFIG_ARCH_RANDOM */
+
+#endif /* ASM_X86_ARCHRANDOM_H */
-- 
1.7.6

[PATCH v3 3/3] x86, random: Verify RDRAND functionality and allow it to be disabled

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@zytor.com>

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.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: "Theodore Ts'o" <tytso@mit.edu>
---
 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

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index aa47be7..397ee05 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -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.
 
diff --git a/arch/x86/include/asm/archrandom.h b/arch/x86/include/asm/archrandom.h
index b7b5bc0..0d9ec77 100644
--- a/arch/x86/include/asm/archrandom.h
+++ b/arch/x86/include/asm/archrandom.h
@@ -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 */
diff --git a/arch/x86/kernel/cpu/Makefile b/arch/x86/kernel/cpu/Makefile
index 6042981..0e3a82a 100644
--- a/arch/x86/kernel/cpu/Makefile
+++ b/arch/x86/kernel/cpu/Makefile
@@ -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
diff --git a/arch/x86/kernel/cpu/common.c b/arch/x86/kernel/cpu/common.c
index 22a073d..8dbd929 100644
--- a/arch/x86/kernel/cpu/common.c
+++ b/arch/x86/kernel/cpu/common.c
@@ -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
diff --git a/arch/x86/kernel/cpu/rdrand.c b/arch/x86/kernel/cpu/rdrand.c
new file mode 100644
index 0000000..feca286
--- /dev/null
+++ b/arch/x86/kernel/cpu/rdrand.c
@@ -0,0 +1,73 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2011, Intel Corporation
+ * Authors: Fenghua Yu <fenghua.yu@intel.com>,
+ *          H. Peter Anvin <hpa@linux.intel.com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ */
+
+#include <asm/processor.h>
+#include <asm/archrandom.h>
+#include <asm/sections.h>
+
+static int __init x86_rdrand_setup(char *s)
+{
+	setup_clear_cpu_cap(X86_FEATURE_RDRAND);
+	return 1;
+}
+__setup("nordrand", x86_rdrand_setup);
+
+/* We can't use arch_get_random_long() here since alternatives haven't run */
+static inline int rdrand_long(unsigned long *v)
+{
+	int ok;
+	asm volatile("1: " RDRAND_LONG "\n\t"
+		     "jc 2f\n\t"
+		     "decl %0\n\t"
+		     "jnz 1b\n\t"
+		     "2:"
+		     : "=r" (ok), "=a" (*v)
+		     : "0" (RDRAND_RETRY_LOOPS));
+	return ok;
+}
+
+/*
+ * Force a reseed cycle; we are architecturally guaranteed a reseed
+ * after no more than 512 128-bit chunks of random data.  This also
+ * acts as a test of the CPU capability.
+ */
+#define RESEED_LOOP ((512*128)/sizeof(unsigned long))
+
+void __cpuinit x86_init_rdrand(struct cpuinfo_x86 *c)
+{
+#ifdef CONFIG_ARCH_RANDOM
+	unsigned long tmp;
+	int i, count, ok;
+
+	if (!cpu_has(c, X86_FEATURE_RDRAND))
+		return;		/* Nothing to do */
+
+	for (count = i = 0; i < RESEED_LOOP; i++) {
+		ok = rdrand_long(&tmp);
+		if (ok)
+			count++;
+	}
+
+	if (count != RESEED_LOOP)
+		clear_cpu_cap(c, X86_FEATURE_RDRAND);
+#endif
+}
-- 
1.7.6

Re: [PATCH v3 0/3] Add support for architectural random number generator

[Herbert Xu]

On Sun, Jul 31, 2011 at 02:26:53PM -0700, H. Peter Anvin wrote:
> 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/

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 <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH v3 0/3] Add support for architectural random number generator

[H. Peter Anvin]

On 08/05/2011 05:00 AM, Herbert Xu wrote:
>>
>> 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/
> 
> FWIW these patches look good to me and I'm happy to take them
> if Linus doesn't merge them directly.
> 

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.

Re: [PATCH v3 0/3] Add support for architectural random number generator

[Herbert Xu]

On Fri, Aug 05, 2011 at 09:28:17AM -0700, H. Peter Anvin wrote:
> On 08/05/2011 05:00 AM, Herbert Xu wrote:
> >>
> >> 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/
> > 
> > FWIW these patches look good to me and I'm happy to take them
> > if Linus doesn't merge them directly.
> > 
> 
> Thanks.  I have put them in -tip as well:
> 
> git://git.kernel.org/pub/scm/linux/kernel/git/tip/linux-tip.git x86/rdrand

That works for me.

Thanks!
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt