[PATCH v4 0/5] random,x86,kvm: Rework arch RNG seeds and get some from kvm

[PATCH v4 0/5] random,x86,kvm: Rework arch RNG seeds and get some from kvm

[Andy Lutomirski]

This introduces and uses a very simple synchronous mechanism to get
/dev/urandom-style bits appropriate for initial KVM PV guest RNG
seeding.

It also re-works the way that architectural random data is fed into
random.c's pools.  I added a new arch hook called arch_get_rng_seed.
The default implementation uses arch_get_random_seed_long and
arch_get_random_long, but not quite the same way as before.

x86 gets a custom arch_get_rng_seed, which is significantly enhanced
over the generic implementation.  It uses RDSEED less aggressively (the
old implementation requested 4x or 8x as many bits as would fit in the
pool, depending on kernel bitness), but, if using RDRAND, it requests
enough bits to comply with Intel's recommendations.

x86's arch_get_rng_seed will also use KVM_GET_RNG_SEED if available.
If more paravirt seed sources show up, it will be a natural place
to add them.

I sent the corresponding kvm-unit-tests and qemu changes separately.

Changes from v3:
 - Other than KASLR, the guest pieces are completely rewritten.
   Patches 2-4 have essentially nothing in common with v2.

Changes from v2:
 - Bisection fix (patch 2 had a misplaced brace).  The final states is
   identical to that of v2.
 - Improve the 0/5 description a little bit.

Changes from v1:
 - Split patches 2 and 3
 - Log all arch sources in init_std_data
 - Fix the 32-bit kaslr build

Andy Lutomirski (5):
  x86,kvm: Add MSR_KVM_GET_RNG_SEED and a matching feature bit
  random: Add and use arch_get_rng_seed
  x86,random: Add an x86 implementation of arch_get_rng_seed
  x86,random,kvm: Use KVM_GET_RNG_SEED in arch_get_rng_seed
  x86,kaslr: Use MSR_KVM_GET_RNG_SEED for KASLR if available

 Documentation/virtual/kvm/cpuid.txt  |  3 ++
 arch/x86/Kconfig                     |  4 ++
 arch/x86/boot/compressed/aslr.c      | 27 ++++++++++
 arch/x86/include/asm/archrandom.h    |  6 +++
 arch/x86/include/asm/kvm_guest.h     |  9 ++++
 arch/x86/include/asm/processor.h     | 21 ++++++--
 arch/x86/include/uapi/asm/kvm_para.h |  2 +
 arch/x86/kernel/Makefile             |  2 +
 arch/x86/kernel/archrandom.c         | 99 ++++++++++++++++++++++++++++++++++++
 arch/x86/kernel/kvm.c                | 10 ++++
 arch/x86/kvm/cpuid.c                 |  3 +-
 arch/x86/kvm/x86.c                   |  4 ++
 drivers/char/random.c                | 14 +++--
 include/linux/random.h               | 40 +++++++++++++++
 14 files changed, 237 insertions(+), 7 deletions(-)
 create mode 100644 arch/x86/kernel/archrandom.c

-- 
1.9.3

[PATCH v4 1/5] x86,kvm: Add MSR_KVM_GET_RNG_SEED and a matching feature bit

[Andy Lutomirski]

This adds a simple interface to allow a guest to request 64 bits of
host nonblocking entropy.  This is independent of virtio-rng for a
couple of reasons:

 - It's intended to be usable during early boot, when a trivial
   synchronous interface is needed.

 - virtio-rng gives blocking entropy, and making guest boot wait for
   the host's /dev/random will cause problems.

MSR_KVM_GET_RNG_SEED is intended to provide 64 bits of best-effort
cryptographically secure data for use as a seed.  It provides no
guarantee that the result contains any actual entropy.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 Documentation/virtual/kvm/cpuid.txt  | 3 +++
 arch/x86/include/uapi/asm/kvm_para.h | 2 ++
 arch/x86/kvm/cpuid.c                 | 3 ++-
 arch/x86/kvm/x86.c                   | 4 ++++
 4 files changed, 11 insertions(+), 1 deletion(-)

diff --git a/Documentation/virtual/kvm/cpuid.txt b/Documentation/virtual/kvm/cpuid.txt
index 3c65feb..0ab043b 100644
--- a/Documentation/virtual/kvm/cpuid.txt
+++ b/Documentation/virtual/kvm/cpuid.txt
@@ -54,6 +54,9 @@ KVM_FEATURE_PV_UNHALT              ||     7 || guest checks this feature bit
                                    ||       || before enabling paravirtualized
                                    ||       || spinlock support.
 ------------------------------------------------------------------------------
+KVM_FEATURE_GET_RNG_SEED           ||     8 || host provides rng seed data via
+                                   ||       || MSR_KVM_GET_RNG_SEED.
+------------------------------------------------------------------------------
 KVM_FEATURE_CLOCKSOURCE_STABLE_BIT ||    24 || host will warn if no guest-side
                                    ||       || per-cpu warps are expected in
                                    ||       || kvmclock.
diff --git a/arch/x86/include/uapi/asm/kvm_para.h b/arch/x86/include/uapi/asm/kvm_para.h
index 94dc8ca..e2eaf93 100644
--- a/arch/x86/include/uapi/asm/kvm_para.h
+++ b/arch/x86/include/uapi/asm/kvm_para.h
@@ -24,6 +24,7 @@
 #define KVM_FEATURE_STEAL_TIME		5
 #define KVM_FEATURE_PV_EOI		6
 #define KVM_FEATURE_PV_UNHALT		7
+#define KVM_FEATURE_GET_RNG_SEED	8
 
 /* The last 8 bits are used to indicate how to interpret the flags field
  * in pvclock structure. If no bits are set, all flags are ignored.
@@ -40,6 +41,7 @@
 #define MSR_KVM_ASYNC_PF_EN 0x4b564d02
 #define MSR_KVM_STEAL_TIME  0x4b564d03
 #define MSR_KVM_PV_EOI_EN      0x4b564d04
+#define MSR_KVM_GET_RNG_SEED 0x4b564d05
 
 struct kvm_steal_time {
 	__u64 steal;
diff --git a/arch/x86/kvm/cpuid.c b/arch/x86/kvm/cpuid.c
index 38a0afe..40d6763 100644
--- a/arch/x86/kvm/cpuid.c
+++ b/arch/x86/kvm/cpuid.c
@@ -479,7 +479,8 @@ static inline int __do_cpuid_ent(struct kvm_cpuid_entry2 *entry, u32 function,
 			     (1 << KVM_FEATURE_ASYNC_PF) |
 			     (1 << KVM_FEATURE_PV_EOI) |
 			     (1 << KVM_FEATURE_CLOCKSOURCE_STABLE_BIT) |
-			     (1 << KVM_FEATURE_PV_UNHALT);
+			     (1 << KVM_FEATURE_PV_UNHALT) |
+			     (1 << KVM_FEATURE_GET_RNG_SEED);
 
 		if (sched_info_on())
 			entry->eax |= (1 << KVM_FEATURE_STEAL_TIME);
diff --git a/arch/x86/kvm/x86.c b/arch/x86/kvm/x86.c
index f644933..4e81853 100644
--- a/arch/x86/kvm/x86.c
+++ b/arch/x86/kvm/x86.c
@@ -48,6 +48,7 @@
 #include <linux/pci.h>
 #include <linux/timekeeper_internal.h>
 #include <linux/pvclock_gtod.h>
+#include <linux/random.h>
 #include <trace/events/kvm.h>
 
 #define CREATE_TRACE_POINTS
@@ -2480,6 +2481,9 @@ int kvm_get_msr_common(struct kvm_vcpu *vcpu, u32 msr, u64 *pdata)
 	case MSR_KVM_PV_EOI_EN:
 		data = vcpu->arch.pv_eoi.msr_val;
 		break;
+	case MSR_KVM_GET_RNG_SEED:
+		get_random_bytes(&data, sizeof(data));
+		break;
 	case MSR_IA32_P5_MC_ADDR:
 	case MSR_IA32_P5_MC_TYPE:
 	case MSR_IA32_MCG_CAP:
-- 
1.9.3

[PATCH v4 2/5] random: Add and use arch_get_rng_seed

[Andy Lutomirski]

Currently, init_std_data contains its own logic for using arch
random sources.  This logic is a bit strange: it reads one long of
arch random data per byte of internal state.

This replaces that logic with a generic function arch_get_rng_seed
that allows arch code to supply its own logic.  The default
implementation tries arch_get_random_seed_long and
arch_get_random_long individually, requesting one bit per bit of
internal state being seeded.

Assuming the arch sources are perfect, this is the right thing to
do.  They're not, though, so the followup patch attempts to
implement the correct logic on x86.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 drivers/char/random.c  | 14 +++++++++++---
 include/linux/random.h | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 51 insertions(+), 3 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0a7ac0a..be7a94e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1236,6 +1236,10 @@ void get_random_bytes_arch(void *buf, int nbytes)
 }
 EXPORT_SYMBOL(get_random_bytes_arch);
 
+static void seed_entropy_store(void *ctx, u32 data)
+{
+	mix_pool_bytes((struct entropy_store *)ctx, &data, sizeof(data), NULL);
+}
 
 /*
  * init_std_data - initialize pool with system data
@@ -1251,15 +1255,19 @@ static void init_std_data(struct entropy_store *r)
 	int i;
 	ktime_t now = ktime_get_real();
 	unsigned long rv;
+	char log_prefix[128];
 
 	r->last_pulled = jiffies;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
 	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
-		if (!arch_get_random_seed_long(&rv) &&
-		    !arch_get_random_long(&rv))
-			rv = random_get_entropy();
+		rv = random_get_entropy();
 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
 	}
+
+	sprintf(log_prefix, "random: seeded %s pool", r->name);
+	arch_get_rng_seed(r, seed_entropy_store, 8 * r->poolinfo->poolbytes,
+			  log_prefix);
+
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL);
 }
 
diff --git a/include/linux/random.h b/include/linux/random.h
index 57fbbff..a17065e 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -106,6 +106,46 @@ static inline int arch_has_random_seed(void)
 }
 #endif
 
+#ifndef __HAVE_ARCH_GET_RNG_SEED
+
+/**
+ * arch_get_rng_seed() - get architectural rng seed data
+ * @ctx: context for the seed function
+ * @seed: function to call for each u32 obtained
+ * @bits_per_source: number of bits from each source to try to use
+ * @log_prefix: beginning of log output (may be NULL)
+ *
+ * Synchronously load some architectural entropy or other best-effort
+ * random seed data.  An arch-specific implementation should be no worse
+ * than this generic implementation.  If the arch code does something
+ * interesting, it may log something of the form "log_prefix with
+ * 8 bits of stuff".
+ *
+ * No arch-specific implementation should be any worse than the generic
+ * implementation.
+ */
+static inline void arch_get_rng_seed(void *ctx,
+				     void (*seed)(void *ctx, u32 data),
+				     int bits_per_source,
+				     const char *log_prefix)
+{
+	int i, longs = (bits_per_source + BITS_PER_LONG - 1) / BITS_PER_LONG;
+
+	for (i = 0; i < longs; i++) {
+		unsigned long rv;
+
+		if (arch_get_random_seed_long(&rv) ||
+		    arch_get_random_long(&rv)) {
+			seed(ctx, (u32)rv);
+#if BITS_PER_LONG > 32
+			seed(ctx, (u32)(rv >> 32));
+#endif
+		}
+	}
+}
+
+#endif /* __HAVE_ARCH_GET_RNG_SEED */
+
 /* Pseudo random number generator from numerical recipes. */
 static inline u32 next_pseudo_random32(u32 seed)
 {
-- 
1.9.3

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[Theodore Ts'o]

On Thu, Jul 17, 2014 at 11:22:17AM -0700, Andy Lutomirski wrote:
> Currently, init_std_data contains its own logic for using arch
> random sources.  This logic is a bit strange: it reads one long of
> arch random data per byte of internal state.

This isn't true.  Check out the init_std_data() a bit more closely.

	unsigned long rv;

	...

	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
	    ...

In particular, note the "i -= sizeof(rv)".  We are reading one bit per
bit of internal state beeing seeded.

> Assuming the arch sources are perfect, this is the right thing to
> do.  They're not, though, so the followup patch attempts to
> implement the correct logic on x86.

... and that's not a problem because we aren't giving any entropy
credit --- and this is deliberate, because we don't want to trust
un-auditable hardware.  We are deliberately trying to be conservative
here.

So I don't think either this patch or the next one is needed.  It adds
far more complexity than is warranted.

Regards,

						- Ted

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[Andy Lutomirski]

On Tue, Jul 22, 2014 at 6:59 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> On Thu, Jul 17, 2014 at 11:22:17AM -0700, Andy Lutomirski wrote:
>> Currently, init_std_data contains its own logic for using arch
>> random sources.  This logic is a bit strange: it reads one long of
>> arch random data per byte of internal state.
>
> This isn't true.  Check out the init_std_data() a bit more closely.
>
>         unsigned long rv;
>
>         ...
>
>         for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
>             ...
>
> In particular, note the "i -= sizeof(rv)".  We are reading one bit per
> bit of internal state beeing seeded.

Whoops, my bad.

>
>> Assuming the arch sources are perfect, this is the right thing to
>> do.  They're not, though, so the followup patch attempts to
>> implement the correct logic on x86.
>
> ... and that's not a problem because we aren't giving any entropy
> credit --- and this is deliberate, because we don't want to trust
> un-auditable hardware.  We are deliberately trying to be conservative
> here.

True.

But, if you Intel's hardware does, in fact, work as documented, then
the current code will collect very little entropy on RDSEED-less
hardware.  I see no great reason that we should do something weaker
than following Intel's explicit recommendation for how to seed a PRNG
from RDRAND.

>
> So I don't think either this patch or the next one is needed.  It adds
> far more complexity than is warranted.

The real reason I did this is because I didn't want to pollute the
kernel with yet more arch_get_random_xyz functions.  In the previous
iteration of this patchset, init_std_data had to deal with no less
than three arch random sources.  If Xen adds something (which, IMO,
they should), then either it'll be up to four, or one of them will
have to multiplex.

Another benefit of this split is that it will potentially allow
arch_get_rng_seed to be made to work before alternatives are run.
There's no fundamental reason that it couldn't work *extremely* early
in boot.  (The KASLR code is an example of how this might work.)  On
the other hand, making arch_get_random_long work very early in boot
would either slow down all the other callers or add a considerable
amount of extra complexity.

So I think that this patch is a slight improvement in RNG
initialization and will actually result in simpler code.  (And yes, if
I submit a new version of it, I'll fix the changelog.)

--Andy

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[H. Peter Anvin]

On 07/22/2014 01:44 PM, Andy Lutomirski wrote:
> 
> But, if you Intel's hardware does, in fact, work as documented, then
> the current code will collect very little entropy on RDSEED-less
> hardware.  I see no great reason that we should do something weaker
> than following Intel's explicit recommendation for how to seed a PRNG
> from RDRAND.
> 

Very little entropy in the architectural worst case.  However, since we
are running single-threaded at this point, actual hardware performs
orders of magnitude better.  Since we run the mixing function (for no
particularly good reason -- it is a linear function and doesn't add
security) there will be enough delay that RDRAND will in practice catch
up and the output will be quite high quality.  Since the pool is quite
large, the likely outcome is that there will be enough randomness that
in practice we would probably be okay if *no* further entropy was ever
collected.

> Another benefit of this split is that it will potentially allow
> arch_get_rng_seed to be made to work before alternatives are run.
> There's no fundamental reason that it couldn't work *extremely* early
> in boot.  (The KASLR code is an example of how this might work.)  On
> the other hand, making arch_get_random_long work very early in boot
> would either slow down all the other callers or add a considerable
> amount of extra complexity.
> 
> So I think that this patch is a slight improvement in RNG
> initialization and will actually result in simpler code.  (And yes, if
> I submit a new version of it, I'll fix the changelog.)

There really isn't any significant reason why we could not permit
randomness initialization very early in the boot, indeed.  It has
largely been useless in the past because until the I/O system gets
initialized there is no randomness of any kind available on traditional
hardware.

	-hpa

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[Andy Lutomirski]

On Tue, Jul 22, 2014 at 1:57 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> On 07/22/2014 01:44 PM, Andy Lutomirski wrote:
>>
>> But, if you Intel's hardware does, in fact, work as documented, then
>> the current code will collect very little entropy on RDSEED-less
>> hardware.  I see no great reason that we should do something weaker
>> than following Intel's explicit recommendation for how to seed a PRNG
>> from RDRAND.
>>
>
> Very little entropy in the architectural worst case.  However, since we
> are running single-threaded at this point, actual hardware performs
> orders of magnitude better.  Since we run the mixing function (for no
> particularly good reason -- it is a linear function and doesn't add
> security) there will be enough delay that RDRAND will in practice catch
> up and the output will be quite high quality.  Since the pool is quite
> large, the likely outcome is that there will be enough randomness that
> in practice we would probably be okay if *no* further entropy was ever
> collected.

Just to check: do you mean the RDRAND is very likely to work (i.e.
arch_get_random_long will return true) or that RDRAND will actually
reseed several times during initialization?

I have no RDRAND-capable hardware, so I can't benchmark it, but I
imagine that we're talking about adding 1-2 ms per boot to ensure that
the pool is filled to capacity with *NRBG* data according to the the
architectural specification.

Anyway, the current code is IMO very much encoding some form of
knowledge of how arch_get_random_* work into init_std_data, and I
don't think that's the place for it.

>
>> Another benefit of this split is that it will potentially allow
>> arch_get_rng_seed to be made to work before alternatives are run.
>> There's no fundamental reason that it couldn't work *extremely* early
>> in boot.  (The KASLR code is an example of how this might work.)  On
>> the other hand, making arch_get_random_long work very early in boot
>> would either slow down all the other callers or add a considerable
>> amount of extra complexity.
>>
>> So I think that this patch is a slight improvement in RNG
>> initialization and will actually result in simpler code.  (And yes, if
>> I submit a new version of it, I'll fix the changelog.)
>
> There really isn't any significant reason why we could not permit
> randomness initialization very early in the boot, indeed.  It has
> largely been useless in the past because until the I/O system gets
> initialized there is no randomness of any kind available on traditional
> hardware.

To me, the question is whether this is a sufficient reason to add
arch_get_rng_data.  If it is, then great.  If not, then I'd like to
know what other way of doing this would be acceptable.  You disliked
arch_get_slow_rng_u64 or whatever I called it, and I agree -- I think
it sucked.

--Andy

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[H. Peter Anvin]

On 07/22/2014 02:04 PM, Andy Lutomirski wrote:
> 
> Just to check: do you mean the RDRAND is very likely to work (i.e.
> arch_get_random_long will return true) or that RDRAND will actually
> reseed several times during initialization?
> 

I mean that RDRAND will actually reseed several times during
initialization.  The documented architectural limit is actually
extremely conservative.

Either way, it isn't really different from seeding from a VM hosts
/dev/urandom...

	-hpa

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[Andy Lutomirski]

On Tue, Jul 22, 2014 at 2:08 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> On 07/22/2014 02:04 PM, Andy Lutomirski wrote:
>>
>> Just to check: do you mean the RDRAND is very likely to work (i.e.
>> arch_get_random_long will return true) or that RDRAND will actually
>> reseed several times during initialization?
>>
>
> I mean that RDRAND will actually reseed several times during
> initialization.  The documented architectural limit is actually
> extremely conservative.
>
> Either way, it isn't really different from seeding from a VM hosts
> /dev/urandom...
>

Sure it is.  The VM host's /dev/urandom makes no guarantee (or AFAIK
even any particular effort) to reseed such that the output has some
minimum entropy per bit, so there would be no point to reading extra
data from it.

Anyway, I'd be willing to drop the conservative RDRAND logic, but I
*still* think that arch_get_rng_seed is a much better interface than
arch_get_slow_rng_u64.

--Andy

Re: [PATCH v4 2/5] random: Add and use arch_get_rng_seed

[H. Peter Anvin]

On 07/22/2014 02:10 PM, Andy Lutomirski wrote:
> On Tue, Jul 22, 2014 at 2:08 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>> On 07/22/2014 02:04 PM, Andy Lutomirski wrote:
>>>
>>> Just to check: do you mean the RDRAND is very likely to work (i.e.
>>> arch_get_random_long will return true) or that RDRAND will actually
>>> reseed several times during initialization?
>>>
>>
>> I mean that RDRAND will actually reseed several times during
>> initialization.  The documented architectural limit is actually
>> extremely conservative.
>>
>> Either way, it isn't really different from seeding from a VM hosts
>> /dev/urandom...
> 
> Sure it is.  The VM host's /dev/urandom makes no guarantee (or AFAIK
> even any particular effort) to reseed such that the output has some
> minimum entropy per bit, so there would be no point to reading extra
> data from it.

Depends on what you define as "extra data".  If the data pulled is less
than the size of the output pool, it *may* be fully entropic.

(Fun fact: it may even have been fully entropic at the time you pull it,
but then turn out not to be later because *another* process consumed
data from /dev/urandom without adequate reseeding.)

> Anyway, I'd be willing to drop the conservative RDRAND logic, but I
> *still* think that arch_get_rng_seed is a much better interface than
> arch_get_slow_rng_u64.

That I will leave up to you and Ted.

	-hpa

[PATCH v4 3/5] x86,random: Add an x86 implementation of arch_get_rng_seed

[Andy Lutomirski]

This is closer to Intel's recommended logic for using RDRAND and
RDSEED.  It will attempt to seed the entire internal state of the
RNG pool using RDSEED (with one bit of RDSEED output per bit of
state).  For any bits that can't be obtained using RDSEED (e.g. if
RDSEED is unavailable), it calculates the number of RDRAND reseeds
needed to obtain the missing bits from the internal NRBG and then
requests enough bits from RDRAND to obtain the full output from at
least that many reseeds.

Arguably, arch_get_random_seed could be removed now: I'm having some
trouble imagining a sensible non-architecture-specific use of it
that wouldn't be better served by arch_get_rng_seed.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 arch/x86/include/asm/archrandom.h |  6 +++
 arch/x86/kernel/Makefile          |  2 +
 arch/x86/kernel/archrandom.c      | 79 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 87 insertions(+)
 create mode 100644 arch/x86/kernel/archrandom.c

diff --git a/arch/x86/include/asm/archrandom.h b/arch/x86/include/asm/archrandom.h
index 69f1366..88f9c5a 100644
--- a/arch/x86/include/asm/archrandom.h
+++ b/arch/x86/include/asm/archrandom.h
@@ -117,6 +117,12 @@ GET_SEED(arch_get_random_seed_int, unsigned int, RDSEED_INT, ASM_NOP4);
 #define arch_has_random()	static_cpu_has(X86_FEATURE_RDRAND)
 #define arch_has_random_seed()	static_cpu_has(X86_FEATURE_RDSEED)
 
+#define __HAVE_ARCH_GET_RNG_SEED
+extern void arch_get_rng_seed(void *ctx,
+			      void (*seed)(void *ctx, u32 data),
+			      int bits_per_source,
+			      const char *log_prefix);
+
 #else
 
 static inline int rdrand_long(unsigned long *v)
diff --git a/arch/x86/kernel/Makefile b/arch/x86/kernel/Makefile
index 047f9ff..0718bae 100644
--- a/arch/x86/kernel/Makefile
+++ b/arch/x86/kernel/Makefile
@@ -92,6 +92,8 @@ obj-$(CONFIG_PARAVIRT)		+= paravirt.o paravirt_patch_$(BITS).o
 obj-$(CONFIG_PARAVIRT_SPINLOCKS)+= paravirt-spinlocks.o
 obj-$(CONFIG_PARAVIRT_CLOCK)	+= pvclock.o
 
+obj-$(CONFIG_ARCH_RANDOM)	+= archrandom.o
+
 obj-$(CONFIG_PCSPKR_PLATFORM)	+= pcspeaker.o
 
 obj-$(CONFIG_X86_CHECK_BIOS_CORRUPTION) += check.o
diff --git a/arch/x86/kernel/archrandom.c b/arch/x86/kernel/archrandom.c
new file mode 100644
index 0000000..5515fc8
--- /dev/null
+++ b/arch/x86/kernel/archrandom.c
@@ -0,0 +1,79 @@
+/*
+ * This file is part of the Linux kernel.
+ *
+ * Copyright (c) 2014 Andy Lutomirski
+ * Authors: Andy Lutomirski <luto@amacapital.net>
+ *
+ * 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.
+ */
+
+#include <asm/archrandom.h>
+
+void arch_get_rng_seed(void *ctx,
+		       void (*seed)(void *ctx, u32 data),
+		       int bits_per_source,
+		       const char *log_prefix)
+{
+	int i, longs = (bits_per_source + BITS_PER_LONG - 1) / BITS_PER_LONG;
+	int rdseed_bits = 0, rdrand_bits = 0;
+	int rdrand_longs_wanted = 0;
+	char buf[128] = "";
+	char *msgptr = buf;
+
+	for (i = 0; i < longs; i++) {
+		unsigned long rv;
+
+		if (arch_get_random_seed_long(&rv)) {
+			seed(ctx, (u32)rv);
+#if BITS_PER_LONG > 32
+			seed(ctx, (u32)(rv >> 32));
+#endif
+			rdseed_bits += 8 * sizeof(rv);
+		}
+	}
+	if (rdseed_bits)
+		msgptr += sprintf(msgptr, ", %d bits from RDSEED", rdseed_bits);
+
+	/*
+	 * According to the Intel DRNG Software Implementation Guide 2.0,
+	 * the RDRAND hardware is guaranteed to provide at least 128 bits
+	 * of non-deterministic entropy per 511*128 bits of RDRAND output.
+	 * Nonetheless, the guide suggests using a 512:1 reduction for
+	 * generating seeds.
+	 *
+	 * We use one extra reseed, because we might not own the first
+	 * or last few samples.
+	 *
+	 * We skip using RDRAND for any bits already provided by RDSEED,
+	 * as they use the same underlying entropy source.
+	 */
+	if (rdseed_bits < bits_per_source && arch_has_random()) {
+		int nrbg_bits = bits_per_source - rdseed_bits;
+		int reseeds = (nrbg_bits + 127) / 128 + 1;
+
+		rdrand_longs_wanted = reseeds * 512 * 128 / BITS_PER_LONG;
+	}
+	for (i = 0; i < rdrand_longs_wanted; i++) {
+		unsigned long rv;
+
+		if (arch_get_random_long(&rv)) {
+			seed(ctx, (u32)rv);
+#if BITS_PER_LONG > 32
+			seed(ctx, (u32)(rv >> 32));
+#endif
+			rdrand_bits += 8 * sizeof(rv);
+		}
+	}
+	if (rdrand_bits)
+		msgptr += sprintf(msgptr, ", %d bits from RDRAND", rdrand_bits);
+
+	if (buf[0])
+		pr_info("%s with %s\n", log_prefix, buf + 2);
+}
-- 
1.9.3

[PATCH v4 4/5] x86,random,kvm: Use KVM_GET_RNG_SEED in arch_get_rng_seed

[Andy Lutomirski]

This is a straightforward implementation: for each bit of internal
RNG state, request one bit from KVM_GET_RNG_SEED.  This is done even
if RDSEED/RDRAND worked, since KVM_GET_RNG_SEED is likely to provide
cryptographically secure output even if the CPU's RNG is weak or
compromised.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 arch/x86/Kconfig                 |  4 ++++
 arch/x86/include/asm/kvm_guest.h |  9 +++++++++
 arch/x86/kernel/archrandom.c     | 22 +++++++++++++++++++++-
 arch/x86/kernel/kvm.c            | 10 ++++++++++
 4 files changed, 44 insertions(+), 1 deletion(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index a8f749e..adfa09c 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -593,6 +593,7 @@ config KVM_GUEST
 	bool "KVM Guest support (including kvmclock)"
 	depends on PARAVIRT
 	select PARAVIRT_CLOCK
+	select ARCH_RANDOM
 	default y
 	---help---
 	  This option enables various optimizations for running under the KVM
@@ -1507,6 +1508,9 @@ config ARCH_RANDOM
 	  If supported, this is a high bandwidth, cryptographically
 	  secure hardware random number generator.
 
+	  This also enables paravirt RNGs such as KVM's if the relevant
+	  PV guest support is enabled.
+
 config X86_SMAP
 	def_bool y
 	prompt "Supervisor Mode Access Prevention" if EXPERT
diff --git a/arch/x86/include/asm/kvm_guest.h b/arch/x86/include/asm/kvm_guest.h
index a92b176..8c4dbd5 100644
--- a/arch/x86/include/asm/kvm_guest.h
+++ b/arch/x86/include/asm/kvm_guest.h
@@ -3,4 +3,13 @@
 
 int kvm_setup_vsyscall_timeinfo(void);
 
+#if defined(CONFIG_KVM_GUEST) && defined(CONFIG_ARCH_RANDOM)
+extern bool kvm_get_rng_seed(u64 *rv);
+#else
+static inline bool kvm_get_rng_seed(u64 *rv)
+{
+	return false;
+}
+#endif
+
 #endif /* _ASM_X86_KVM_GUEST_H */
diff --git a/arch/x86/kernel/archrandom.c b/arch/x86/kernel/archrandom.c
index 5515fc8..3bcfa58 100644
--- a/arch/x86/kernel/archrandom.c
+++ b/arch/x86/kernel/archrandom.c
@@ -15,6 +15,7 @@
  */
 
 #include <asm/archrandom.h>
+#include <asm/kvm_guest.h>
 
 void arch_get_rng_seed(void *ctx,
 		       void (*seed)(void *ctx, u32 data),
@@ -22,7 +23,7 @@ void arch_get_rng_seed(void *ctx,
 		       const char *log_prefix)
 {
 	int i, longs = (bits_per_source + BITS_PER_LONG - 1) / BITS_PER_LONG;
-	int rdseed_bits = 0, rdrand_bits = 0;
+	int rdseed_bits = 0, rdrand_bits = 0, kvm_bits = 0;
 	int rdrand_longs_wanted = 0;
 	char buf[128] = "";
 	char *msgptr = buf;
@@ -74,6 +75,25 @@ void arch_get_rng_seed(void *ctx,
 	if (rdrand_bits)
 		msgptr += sprintf(msgptr, ", %d bits from RDRAND", rdrand_bits);
 
+	/*
+	 * Use KVM_GET_RNG_SEED regardless of whether the CPU RNG worked,
+	 * since it incorporates entropy unavailable to the CPU.  We
+	 * request enough bits for the entire internal RNG state, because
+	 * there's no good reason not to.
+	 */
+	for (i = 0; i < (bits_per_source + 63) / 64; i++) {
+		u64 rv;
+
+		if (kvm_get_rng_seed(&rv)) {
+			seed(ctx, (u32)rv);
+			seed(ctx, (u32)(rv >> 32));
+			kvm_bits += 8 * sizeof(rv);
+		}
+	}
+	if (kvm_bits)
+		msgptr += sprintf(msgptr, ", %d bits from KVM_GET_RNG_BITS",
+				  kvm_bits);
+
 	if (buf[0])
 		pr_info("%s with %s\n", log_prefix, buf + 2);
 }
diff --git a/arch/x86/kernel/kvm.c b/arch/x86/kernel/kvm.c
index 3dd8e2c..bd8783a 100644
--- a/arch/x86/kernel/kvm.c
+++ b/arch/x86/kernel/kvm.c
@@ -416,6 +416,16 @@ void kvm_disable_steal_time(void)
 	wrmsr(MSR_KVM_STEAL_TIME, 0, 0);
 }
 
+bool kvm_get_rng_seed(u64 *v)
+{
+	/*
+	 * Allow migration from a hypervisor with the GET_RNG_SEED
+	 * feature to a hypervisor without it.
+	 */
+	return (kvm_para_has_feature(KVM_FEATURE_GET_RNG_SEED) &&
+		rdmsrl_safe(MSR_KVM_GET_RNG_SEED, v) == 0);
+}
+
 #ifdef CONFIG_SMP
 static void __init kvm_smp_prepare_boot_cpu(void)
 {
-- 
1.9.3

[PATCH v4 5/5] x86,kaslr: Use MSR_KVM_GET_RNG_SEED for KASLR if available

[Andy Lutomirski]

It's considerably better than any of the alternatives on KVM.

Rather than reinventing all of the cpu feature query code, this fixes
native_cpuid to work in PIC objects.

I haven't combined it with boot/cpuflags.c's cpuid implementation:
including asm/processor.h from boot/cpuflags.c results in a flood of
unrelated errors, and fixing it might be messy.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
---
 arch/x86/boot/compressed/aslr.c  | 27 +++++++++++++++++++++++++++
 arch/x86/include/asm/processor.h | 21 ++++++++++++++++++---
 2 files changed, 45 insertions(+), 3 deletions(-)

diff --git a/arch/x86/boot/compressed/aslr.c b/arch/x86/boot/compressed/aslr.c
index fc6091a..8583f0e 100644
--- a/arch/x86/boot/compressed/aslr.c
+++ b/arch/x86/boot/compressed/aslr.c
@@ -5,6 +5,8 @@
 #include <asm/archrandom.h>
 #include <asm/e820.h>
 
+#include <uapi/asm/kvm_para.h>
+
 #include <generated/compile.h>
 #include <linux/module.h>
 #include <linux/uts.h>
@@ -15,6 +17,22 @@
 static const char build_str[] = UTS_RELEASE " (" LINUX_COMPILE_BY "@"
 		LINUX_COMPILE_HOST ") (" LINUX_COMPILER ") " UTS_VERSION;
 
+static bool kvm_para_has_feature(unsigned int feature)
+{
+	u32 kvm_base;
+	u32 features;
+
+	if (!has_cpuflag(X86_FEATURE_HYPERVISOR))
+		return false;
+
+	kvm_base = hypervisor_cpuid_base("KVMKVMKVM\0\0\0", KVM_CPUID_FEATURES);
+	if (!kvm_base)
+		return false;
+
+	features = cpuid_eax(kvm_base | KVM_CPUID_FEATURES);
+	return features & (1UL << feature);
+}
+
 #define I8254_PORT_CONTROL	0x43
 #define I8254_PORT_COUNTER0	0x40
 #define I8254_CMD_READBACK	0xC0
@@ -81,6 +99,15 @@ static unsigned long get_random_long(void)
 		}
 	}
 
+	if (kvm_para_has_feature(KVM_FEATURE_GET_RNG_SEED)) {
+		u64 seed;
+
+		debug_putstr(" MSR_KVM_GET_RNG_SEED");
+		rdmsrl(MSR_KVM_GET_RNG_SEED, seed);
+		random ^= (unsigned long)seed;
+		use_i8254 = false;
+	}
+
 	if (has_cpuflag(X86_FEATURE_TSC)) {
 		debug_putstr(" RDTSC");
 		rdtscll(raw);
diff --git a/arch/x86/include/asm/processor.h b/arch/x86/include/asm/processor.h
index a4ea023..6096f3c 100644
--- a/arch/x86/include/asm/processor.h
+++ b/arch/x86/include/asm/processor.h
@@ -189,10 +189,25 @@ static inline int have_cpuid_p(void)
 static inline void native_cpuid(unsigned int *eax, unsigned int *ebx,
 				unsigned int *ecx, unsigned int *edx)
 {
-	/* ecx is often an input as well as an output. */
-	asm volatile("cpuid"
+	/*
+	 * This function can be used from the boot code, so it needs
+	 * to avoid using EBX in constraints in PIC mode.
+	 *
+	 * ecx is often an input as well as an output.
+	 */
+	asm volatile(".ifnc %%ebx,%1 ; .ifnc %%rbx,%1           \n\t"
+		     "movl  %%ebx,%1                            \n\t"
+		     ".endif ; .endif                           \n\t"
+		     "cpuid					\n\t"
+		     ".ifnc %%ebx,%1 ; .ifnc %%rbx,%1           \n\t"
+		     "xchgl %%ebx,%1                            \n\t"
+		     ".endif ; .endif"
 	    : "=a" (*eax),
-	      "=b" (*ebx),
+#if defined(__i386__) && defined(__PIC__)
+	      "=r" (*ebx),	/* gcc won't let us use ebx */
+#else
+	      "=b" (*ebx),	/* ebx is okay */
+#endif
 	      "=c" (*ecx),
 	      "=d" (*edx)
 	    : "0" (*eax), "2" (*ecx)
-- 
1.9.3

Re: [PATCH v4 5/5] x86,kaslr: Use MSR_KVM_GET_RNG_SEED for KASLR if available

[Kees Cook]

On Thu, Jul 17, 2014 at 11:22 AM, Andy Lutomirski <luto@amacapital.net> wrote:
> It's considerably better than any of the alternatives on KVM.
>
> Rather than reinventing all of the cpu feature query code, this fixes
> native_cpuid to work in PIC objects.
>
> I haven't combined it with boot/cpuflags.c's cpuid implementation:
> including asm/processor.h from boot/cpuflags.c results in a flood of
> unrelated errors, and fixing it might be messy.
>
> Signed-off-by: Andy Lutomirski <luto@amacapital.net>

This will be very nice to have under kvm!

Reviewed-by: Kees Cook <keescook@chromium.org>

Thanks,

-Kees

-- 
Kees Cook
Chrome OS Security