[PATCH] random: mix all saved registers into entropy pool

[PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

The single biggest entropy source is a high-resolution timer running
asynchronous to the triggering event.  That leaves systems without a
useful get_cycles() implementation with significantly less entropy.
Significant means orders of magnitude, not a few percent.

An alternate high-resolution timer is the register content at the time
of an interrupt.  While not monotonic, it is guaranteed to change every
few clock cycles and very unlikely to repeat the same pattern.  Not
useful for interpretation as time, but we only care about some bits
of the "clock" flipping in an unpredictable fashion.

Experimentation show this to be an excellent entropy source.  Doing 1000
boottests with kvm and dumping a hash of the registers for the first
1024 interrupts each, >40% of all hashes were unique and >80% of all
hashes occurred less than once 1% of the time.

Even assuming that only unique register hashes yield any entropy at all
and only one bit each, we would gather >400 bits of entropy early in
boot and another 40 bits/s from the timer interrupt during runtime.  I
would feel confident with this amount of entropy in the absence of any
other source.

Repeating the test on real hardware, albeit with fewer repetitions
yields roughly the same results, slightly above 40% unique hashes.

Signed-off-by: Joern Engel <joern@logfs.org>
---
 drivers/char/random.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 62 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 429b75bb60e8..b4a8968fe28d 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -553,6 +553,8 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
 
 struct fast_pool {
 	__u32		pool[4];
+	u32		last_shift;
+	u32		regs_count;
 	unsigned long	last;
 	unsigned short	count;
 	unsigned char	rotate;
@@ -835,6 +837,61 @@ EXPORT_SYMBOL_GPL(add_input_randomness);
 
 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
+/*
+ * Ratelimit to a steady state of about once per jiffy.  A naïve approach
+ * would be to return 1 every time jiffies changes.  But we want to avoid
+ * being closely coupled to the timer interrupt.  So instead we increment
+ * a counter on every call and shift it right every time jiffies changes.
+ * If the counter is a power of two, return false;
+ *
+ * Effect is that some time after a jiffies change and cutting the counter
+ * in half we reach another power of two and return false.  But the
+ * likelihood of this happening is about the same at any time within a
+ * jiffies interval.
+ */
+static inline int ratelimited(struct fast_pool *p)
+{
+	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
+
+	p->regs_count++;
+	if (p->last_shift != (u32)jiffies) {
+		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
+		p->last_shift = (u32)jiffies;
+	}
+	return ret;
+}
+
+#define BOOT_IRQS 1024
+
+/*
+ * The single biggest entropy source is a high-resolution timer running
+ * asynchronous to the triggering event.  That leaves systems without a
+ * useful get_cycles() implementation with significantly less entropy.
+ * Significant means orders of magnitude, not a few percent.
+ *
+ * An alternate high-resolution timer is the register content at the time
+ * of an interrupt.  While not monotonic, it is guaranteed to change every
+ * few clock cycles and very unlikely to repeat the same pattern.  Not
+ * useful for interpretation as time, but we only care about some bits
+ * of the "clock" flipping in an unpredictable fashion.
+ */
+static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)
+{
+	struct entropy_store	*r;
+	/* Two variables avoid decrementing by two without using atomics */
+	static int boot_count = BOOT_IRQS;
+	int in_boot = boot_count;
+
+	if (in_boot) {
+		boot_count = in_boot - 1;
+	} else if (ratelimited(fast_pool))
+		return;
+
+	/* During bootup we alternately feed both pools */
+	r = (in_boot & 1) ? &nonblocking_pool : &input_pool;
+	__mix_pool_bytes(r, regs, sizeof(*regs), NULL);
+}
+
 void add_interrupt_randomness(int irq, int irq_flags)
 {
 	struct entropy_store	*r;
@@ -845,13 +902,14 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u32			input[4], c_high, j_high;
 	__u64			ip;
 
+	mix_regs(regs, fast_pool);
 	c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
 	j_high = (sizeof(now) > 4) ? now >> 32 : 0;
-	input[0] = cycles ^ j_high ^ irq;
-	input[1] = now ^ c_high;
+	input[0] ^= cycles ^ j_high ^ irq;
+	input[1] ^= now ^ c_high;
 	ip = regs ? instruction_pointer(regs) : _RET_IP_;
-	input[2] = ip;
-	input[3] = ip >> 32;
+	input[2] ^= ip;
+	input[3] ^= ip >> 32;
 
 	fast_mix(fast_pool, input);
 
-- 
2.0.0.rc0.1.g7b2ba98

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Mon, 19 May 2014 17:17:19 -0400, Jörn Engel wrote:
> 
> Experimentation show this to be an excellent entropy source.  Doing 1000
> boottests with kvm and dumping a hash of the registers for the first
> 1024 interrupts each, >40% of all hashes were unique and >80% of all
> hashes occurred less than once 1% of the time.

And since I previously claimed the opposite, the negative result was
caused by a kvm oddity.  When starting kvm in the background, it will
run just fine.  But when starting kvm with "-nographic" in the
background, the process gets stopped.  No output is generated and the
output file is not even truncated before kvm is stopped.  Therefore
every single run will have identical kernel output - that of the
previous run.

With that embarrassment out of the way, I find this approach hugely
valuable.  Even if you disagree with some detail of this patch, we
should definitely merge something roughly related.

Jörn

--
A defeated army first battles and then seeks victory.
-- Sun Tzu

Re: [PATCH] random: mix all saved registers into entropy pool

[H. Peter Anvin]

On 05/19/2014 02:23 PM, Jörn Engel wrote:
> On Mon, 19 May 2014 17:17:19 -0400, Jörn Engel wrote:
>>
>> Experimentation show this to be an excellent entropy source.  Doing 1000
>> boottests with kvm and dumping a hash of the registers for the first
>> 1024 interrupts each, >40% of all hashes were unique and >80% of all
>> hashes occurred less than once 1% of the time.
> 
> And since I previously claimed the opposite, the negative result was
> caused by a kvm oddity.  When starting kvm in the background, it will
> run just fine.  But when starting kvm with "-nographic" in the
> background, the process gets stopped.  No output is generated and the
> output file is not even truncated before kvm is stopped.  Therefore
> every single run will have identical kernel output - that of the
> previous run.
> 
> With that embarrassment out of the way, I find this approach hugely
> valuable.  Even if you disagree with some detail of this patch, we
> should definitely merge something roughly related.
> 
> Jörn
> 

I think this is likely to be particularly valuable during boot.  I can
see it becoming substantially less valuable after that point, but during
boot is when the most critical.

What I do see as an issue is that the value is probably impossible to
quantify, and so I feel more than a bit queasy about giving it
/dev/random credit.  However, making sure the pool is well stirred
during boot is really way more important.

	-hpa

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Mon, 19 May 2014 15:18:01 -0700, H. Peter Anvin wrote:
> 
> I think this is likely to be particularly valuable during boot.  I can
> see it becoming substantially less valuable after that point, but during
> boot is when the most critical.
> 
> What I do see as an issue is that the value is probably impossible to
> quantify, and so I feel more than a bit queasy about giving it
> /dev/random credit.  However, making sure the pool is well stirred
> during boot is really way more important.

I would feel fairly confident giving this .25 bits of entropy per
event.  With 40% unique hashes and assuming at most 1 bit of entropy
for a unique hash, that is a fairly conservative underestimate.

But as you can see from the patch, I feel less confident doing any
kind of entropy-guessing in general and have skipped that step.  By
the .25 bits metric, my patch should feed 128 bits of entropy into
both the non-blocking pool and the input pool within the first 5s or
so of boot time.  In reality it is likely more.

The other problem to solve is VM clones sharing the same state for the
various pools.  Assuming HZ=100 no external interrupts and .25 bits, we
would gather 128 bits in just above 5s.  That is not great, but okish.

What worries me is that much of those 5s may be spent inside the idle
loop and have rather predictable register content and we may run
tickless.  I have no great solution for that case.

We could change the ratelimiting to, say, 4 interrupts per jiffie.
But that would still not help much in the worst case scenario above,
so the benefits don't seem convincing.

Jörn

--
When you admit that some people are too important to prosecute, it's
just a few short steps to the obvious corollary – that everybody else
is unimportant enough to jail.
-- Matt Taibbi

Re: [PATCH] random: mix all saved registers into entropy pool

[H. Peter Anvin]

On 05/19/2014 03:39 PM, Jörn Engel wrote:
> On Mon, 19 May 2014 15:18:01 -0700, H. Peter Anvin wrote:
>>
>> I think this is likely to be particularly valuable during boot.  I can
>> see it becoming substantially less valuable after that point, but during
>> boot is when the most critical.
>>
>> What I do see as an issue is that the value is probably impossible to
>> quantify, and so I feel more than a bit queasy about giving it
>> /dev/random credit.  However, making sure the pool is well stirred
>> during boot is really way more important.
> 
> I would feel fairly confident giving this .25 bits of entropy per
> event.  With 40% unique hashes and assuming at most 1 bit of entropy
> for a unique hash, that is a fairly conservative underestimate.
> 

Sure, but that is for a specific workload.

> What worries me is that much of those 5s may be spent inside the idle
> loop and have rather predictable register content and we may run
> tickless.  I have no great solution for that case.
>
> We could change the ratelimiting to, say, 4 interrupts per jiffie.
> But that would still not help much in the worst case scenario above,
> so the benefits don't seem convincing.

Exactly.

	-hpa

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Mon, 19 May 2014 16:05:06 -0700, H. Peter Anvin wrote:
> On 05/19/2014 03:39 PM, Jörn Engel wrote:
> > 
> > I would feel fairly confident giving this .25 bits of entropy per
> > event.  With 40% unique hashes and assuming at most 1 bit of entropy
> > for a unique hash, that is a fairly conservative underestimate.
> 
> Sure, but that is for a specific workload.

The workload is called boot.  That is one of the two critical ones -
the other being a cloned VM.  If we can gather enough entropy during
boot and somehow avoid the cloned VM problem, we have won.  No more
need to feed in entropy from the previous run, which on many embedded
systems won't happen anyway.

If you complained about the limited selection of hardware I tested on,
you would be right.  So far it has been x86 kvm and an x86 notebook.
It would be great to get numbers for some embedded system with arm or
mips as well.

Jörn

--
When in doubt, punt.  When somebody actually complains, go back and fix it...
The 90% solution is a good thing.
-- Rob Landley

Re: [PATCH] random: mix all saved registers into entropy pool

[Andi Kleen]

Jörn Engel <joern@logfs.org> writes:
>
> An alternate high-resolution timer is the register content at the time
> of an interrupt. 

So if you interrupt a cryptographic function you may hash in parts
of the key?

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Tue, 20 May 2014 05:12:07 -0700, Andi Kleen wrote:
> Jörn Engel <joern@logfs.org> writes:
> >
> > An alternate high-resolution timer is the register content at the time
> > of an interrupt. 
> 
> So if you interrupt a cryptographic function you may hash in parts
> of the key?

Yes.  And if there was an efficient way to deduce random generator
inputs, that would be a new side channel attack.  An efficient way to
deduce random generator inputs would allow many other attacks as well.
I don't know of such an attack nor can I conceive it being possible
under normal circumstances.

There are of course two exceptions.  If the attacker can read
arbitrary kernel memory - and therefore could read the private key
directly.  And if there is so little entropy that an attacker can
enumerate all possible states of the random generator and read enough
random numbers to exclude most of those states.

The second case also allows for many more interesting attacks and is
exactly the sort of hole I want to plug with this patch.

I think leaking of private keys or similar information is not a
concern.  But please prove me wrong.  Better you now than someone else
later.

Jörn

--
When in doubt, punt.  When somebody actually complains, go back and fix it...
The 90% solution is a good thing.
-- Rob Landley

Re: [PATCH] random: mix all saved registers into entropy pool

[Andi Kleen]

> 
> I think leaking of private keys or similar information is not a
> concern.  But please prove me wrong.  Better you now than someone else
> later.

While I don't have a concrete exploit it seems seems dangerous to me. 
The LibreSSL people just removed a similar behavior from OpenSSL.

-Andi

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Wed, 21 May 2014 21:39:05 +0200, Andi Kleen wrote:
> 
> > I think leaking of private keys or similar information is not a
> > concern.  But please prove me wrong.  Better you now than someone else
> > later.
> 
> While I don't have a concrete exploit it seems seems dangerous to me. 
> The LibreSSL people just removed a similar behavior from OpenSSL.

Similar, yes.  But there is a difference:
Unconditionally mixing your private key into the entropy pool yields
zero entropy.  While your private is hopefully unpredictable to an
attacker, it never changes.  OpenSSL mixed the private keys for no
benefit.

The reason why I want this patch in is to avoid a different
non-theoretical dangerous situation.  get_cycles() returns 0 on
several architectures and Ted's recent "improvements" are thus far
only noise.  Architectures could define random_get_entropy() to
something else, but no architecture does it.  Therefore we have
millions of embedded systems with interrupts as their sole entropy
source and jiffies as the only timestamp component.

To top it off, those same systems usually lack a read-write filesystem
and will not initialize /dev/random from state read out before the
last reboot.  Now try to estimate how much time has to pass since
reboot until those systems have accumulated 128 bits of entropy.  I
have not heard an estimate from anyone yet.

If you have an alternative approach to fix this very real problem
without potentially leaking private keys under conditions that also
allow more efficient attacks, I would love to know about it.  So far
this is my best attempt and it beats all alternatives I know about.
Which just shows you how horrible the alternatives are.

Also see:
http://blog.fefe.de/?ts=ada960dc
https://factorable.net/weakkeys12.extended.pdf

Jörn

--
The art of propaganda is not telling lies, but rather selecting
the truth you require and giving it mixed up with some truths
the audience wants to hear.
-- Richard Crossman

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Wed, 21 May 2014 21:39:05 +0200, Andi Kleen wrote:
> 
> > I think leaking of private keys or similar information is not a
> > concern.  But please prove me wrong.  Better you now than someone else
> > later.
> 
> While I don't have a concrete exploit it seems seems dangerous to me. 
> The LibreSSL people just removed a similar behavior from OpenSSL.

Btw, if your concern were justified, that would also speak volumes
about the quality of our random generator - with or without my patch.
Either you are wrong or we have a real problem on our hands already.

Jörn

--
This above all: to thine own self be true.
-- Shakespeare

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

Ping.

Jörn

--
Computer system analysis is like child-rearing; you can do grievous damage,
but you cannot ensure success."
-- Tom DeMarco

Re: [PATCH] random: mix all saved registers into entropy pool

[Theodore Ts'o]

On Mon, May 19, 2014 at 05:17:19PM -0400, Jörn Engel wrote:
> +/*
> + * Ratelimit to a steady state of about once per jiffy.  A naïve approach
> + * would be to return 1 every time jiffies changes.  But we want to avoid
> + * being closely coupled to the timer interrupt.  So instead we increment
> + * a counter on every call and shift it right every time jiffies changes.
> + * If the counter is a power of two, return false;
> + *
> + * Effect is that some time after a jiffies change and cutting the counter
> + * in half we reach another power of two and return false.  But the
> + * likelihood of this happening is about the same at any time within a
> + * jiffies interval.
> + */
> +static inline int ratelimited(struct fast_pool *p)
> +{
> +	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
> +
> +	p->regs_count++;
> +	if (p->last_shift != (u32)jiffies) {
> +		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
> +		p->last_shift = (u32)jiffies;
> +	}
> +	return ret;
> +}

I wasn't convinced this would do the right thing, so I wrote a quick
test program where the main loop was basically this:

	for (i=0; i < 1024; i++) {
		jiffies = i >> 2;
		r = ratelimited(jiffies);
		printf("%5u %5u %5u %d\n", i, jiffies, regs_count, r);
	}

... which basically simulated a very simple scheme where there were
four interrupts for each clock tick.  In the steady state ratelimited
returns true 75% of the time.  If this was as documented, we would
expect it to return true 25% of the time.  So I don't think this is
working quite right:

   20     5     3 1
   21     5     4 1
   22     5     5 0
   23     5     6 1
   24     6     3 1
   25     6     4 1
   26     6     5 0
   27     6     6 1
   28     7     3 1
   29     7     4 1
   30     7     5 0
   31     7     6 1
   32     8     3 1


> +static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)
> +{
> +	struct entropy_store	*r;
> +	/* Two variables avoid decrementing by two without using atomics */
> +	static int boot_count = BOOT_IRQS;
> +	int in_boot = boot_count;
> +
> +	if (in_boot) {
> +		boot_count = in_boot - 1;
> +	} else if (ratelimited(fast_pool))
> +		return;
> +
> +	/* During bootup we alternately feed both pools */
> +	r = (in_boot & 1) ? &nonblocking_pool : &input_pool;
> +	__mix_pool_bytes(r, regs, sizeof(*regs), NULL);
> +}

I'm also concerned about how much overhead this might eat up.  I've
already had someone who was benchmarking a high performance storage
array where the increased interrupt latency before adding something
like this was something he noticed, and kvetched to me about.  The
pt_regs structure is going to be larger than the fast_pool (which is
only 16 bytes), and we're going to be doing it once every jiffy, which
means between 100 and 1000 times per second.

If we do this only during boot up, I'd be much less concerned, but
doing it all the time is making me a bit nervous about the overhead.

If we knew which parts of the pt_regs were actually the "best" in
terms of entropy, we could xor that into the input[] array in
add_interrupt_randomness(), perhaps?  


> -	input[0] = cycles ^ j_high ^ irq;
> -	input[1] = now ^ c_high;
> +	input[0] ^= cycles ^ j_high ^ irq;
> +	input[1] ^= now ^ c_high;

This is an unrelated change, so if you want to do this, let's discuss
this on a separate commit.  We used to have something like this, but
it causes static code checkers to complain about our using stack
garbage, and people argued convincingly that it really did add as much
unpredictability, especially when correlated with the ip field.

(And yes, I know that instruction_pointer(regs) doesn't work on all
platforms, and _RET_IP_ becomes largely static --- but this is why I'd
much rather have each architecture tell me which parts of regs were
actually the best, and use that as the initialized portions of the
input[] array.)

Cheers,

					- Ted

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Tue, 10 June 2014 12:14:01 -0400, Theodore Ts'o wrote:
> On Mon, May 19, 2014 at 05:17:19PM -0400, Jörn Engel wrote:
> > +/*
> > + * Ratelimit to a steady state of about once per jiffy.  A naïve approach
> > + * would be to return 1 every time jiffies changes.  But we want to avoid
> > + * being closely coupled to the timer interrupt.  So instead we increment
> > + * a counter on every call and shift it right every time jiffies changes.
> > + * If the counter is a power of two, return false;
> > + *
> > + * Effect is that some time after a jiffies change and cutting the counter
> > + * in half we reach another power of two and return false.  But the
> > + * likelihood of this happening is about the same at any time within a
> > + * jiffies interval.
> > + */
> > +static inline int ratelimited(struct fast_pool *p)
> > +{
> > +	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
> > +
> > +	p->regs_count++;
> > +	if (p->last_shift != (u32)jiffies) {
> > +		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
> > +		p->last_shift = (u32)jiffies;
> > +	}
> > +	return ret;
> > +}
> 
> I wasn't convinced this would do the right thing, so I wrote a quick
> test program where the main loop was basically this:
> 
> 	for (i=0; i < 1024; i++) {
> 		jiffies = i >> 2;
> 		r = ratelimited(jiffies);
> 		printf("%5u %5u %5u %d\n", i, jiffies, regs_count, r);
> 	}
> 
> ... which basically simulated a very simple scheme where there were
> four interrupts for each clock tick.  In the steady state ratelimited
> returns true 75% of the time.  If this was as documented, we would
> expect it to return true 25% of the time.  So I don't think this is
> working quite right:
> 
>    20     5     3 1
>    21     5     4 1
>    22     5     5 0
>    23     5     6 1
>    24     6     3 1
>    25     6     4 1
>    26     6     5 0
>    27     6     6 1
>    28     7     3 1
>    29     7     4 1
>    30     7     5 0
>    31     7     6 1
>    32     8     3 1

Doh!  Removing the "!" from "!(p->regs_count..." will fix that.  Shows
I spent 100x more time testing the bootup entropy collection.

> > +static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)
> > +{
> > +	struct entropy_store	*r;
> > +	/* Two variables avoid decrementing by two without using atomics */
> > +	static int boot_count = BOOT_IRQS;
> > +	int in_boot = boot_count;
> > +
> > +	if (in_boot) {
> > +		boot_count = in_boot - 1;
> > +	} else if (ratelimited(fast_pool))
> > +		return;
> > +
> > +	/* During bootup we alternately feed both pools */
> > +	r = (in_boot & 1) ? &nonblocking_pool : &input_pool;
> > +	__mix_pool_bytes(r, regs, sizeof(*regs), NULL);
> > +}
> 
> I'm also concerned about how much overhead this might eat up.  I've
> already had someone who was benchmarking a high performance storage
> array where the increased interrupt latency before adding something
> like this was something he noticed, and kvetched to me about.  The
> pt_regs structure is going to be larger than the fast_pool (which is
> only 16 bytes), and we're going to be doing it once every jiffy, which
> means between 100 and 1000 times per second.

Would that someone be me? ;)

The reason I prefer doing it once every jiffy is that it doesn't
change with interrupt load.  You get 10k interrupts per second?
You pay once per jiffy.  100k interrupts per second?  Pay once per
jiffy.

I dislike the fact that HZ is anywhere between 100 and 1000.  We could
sample every time jiffies has advanced by HZ/50, which gives a stable
sample rate of 50Hz for every currently possible config.

> If we do this only during boot up, I'd be much less concerned, but
> doing it all the time is making me a bit nervous about the overhead.
> 
> If we knew which parts of the pt_regs were actually the "best" in
> terms of entropy, we could xor that into the input[] array in
> add_interrupt_randomness(), perhaps?  
> 
> 
> > -	input[0] = cycles ^ j_high ^ irq;
> > -	input[1] = now ^ c_high;
> > +	input[0] ^= cycles ^ j_high ^ irq;
> > +	input[1] ^= now ^ c_high;
> 
> This is an unrelated change, so if you want to do this, let's discuss
> this on a separate commit.  We used to have something like this, but
> it causes static code checkers to complain about our using stack
> garbage, and people argued convincingly that it really did add as much
> unpredictability, especially when correlated with the ip field.

Will remove.

> (And yes, I know that instruction_pointer(regs) doesn't work on all
> platforms, and _RET_IP_ becomes largely static --- but this is why I'd
> much rather have each architecture tell me which parts of regs were
> actually the best, and use that as the initialized portions of the
> input[] array.)

What I like about my approach is quite the opposite.  The only thing
an architecture maintainer can mess up is not saving registers on
interrupts.  And if they mess that one up, they are very likely to
notice.

Jörn

--
Victory in war is not repetitious.
-- Sun Tzu

Re: [PATCH] random: mix all saved registers into entropy pool

[Theodore Ts'o]

On Tue, Jun 10, 2014 at 08:10:09PM -0400, Jörn Engel wrote:
> > I'm also concerned about how much overhead this might eat up.  I've
> > already had someone who was benchmarking a high performance storage
> > array where the increased interrupt latency before adding something
> > like this was something he noticed, and kvetched to me about.  The
> > pt_regs structure is going to be larger than the fast_pool (which is
> > only 16 bytes), and we're going to be doing it once every jiffy, which
> > means between 100 and 1000 times per second.
> 
> Would that someone be me? ;)
> 
> The reason I prefer doing it once every jiffy is that it doesn't
> change with interrupt load.  You get 10k interrupts per second?
> You pay once per jiffy.  100k interrupts per second?  Pay once per
> jiffy.

No, actually, it was someone who was worried about tail latency.  So
even if the average overhead was small, if once a jiffy we had a much
larger time spent in the interrupt handler, that's something that
would a big concern for someone who was worried about big storage
array performance.

I'd be happier if we used fast_mix() and mixed the registers into the
fast pool.  That's much lighter weight than using mix_pool_bytes(),
which involves many more memory accesses, MUCH higher probably of
cache line bouncing between CPU's, etc.

And there has been some proposals that I've been looking at to make
fast_mix to be use even less overhead, so if we use fast_mix, any
changes we make to improve that will help here too.

> What I like about my approach is quite the opposite.  The only thing
> an architecture maintainer can mess up is not saving registers on
> interrupts.  And if they mess that one up, they are very likely to
> notice.

What probably makes sense is to make the defaults use pt_regs, but
make it be overrideable by the architecture maintainer.  For example,
if the CPU has RDRAND or RDSEED, it probably doesn't make sense to
worry about mixing in the registers.  So we could make the default be
to mix in the entire set of registers, and if someone complains about
the overhead on their system, and they have a better way of harvesting
high quality entropy, then they can use that instead of trying to rely
on the registers.

It's unlikely that someone is going to be attaching a multi-million
dollar RAID array or a PCIe attached flash device on a MIPS or m68k
platform, after all.  :-)

							- Ted

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Wed, 11 June 2014 11:27:42 -0400, Theodore Ts'o wrote:
> On Tue, Jun 10, 2014 at 08:10:09PM -0400, Jörn Engel wrote:
> > > I'm also concerned about how much overhead this might eat up.  I've
> > > already had someone who was benchmarking a high performance storage
> > > array where the increased interrupt latency before adding something
> > > like this was something he noticed, and kvetched to me about.  The
> > > pt_regs structure is going to be larger than the fast_pool (which is
> > > only 16 bytes), and we're going to be doing it once every jiffy, which
> > > means between 100 and 1000 times per second.
> > 
> > Would that someone be me? ;)
> > 
> > The reason I prefer doing it once every jiffy is that it doesn't
> > change with interrupt load.  You get 10k interrupts per second?
> > You pay once per jiffy.  100k interrupts per second?  Pay once per
> > jiffy.
> 
> No, actually, it was someone who was worried about tail latency.  So
> even if the average overhead was small, if once a jiffy we had a much
> larger time spent in the interrupt handler, that's something that
> would a big concern for someone who was worried about big storage
> array performance.
> 
> I'd be happier if we used fast_mix() and mixed the registers into the
> fast pool.  That's much lighter weight than using mix_pool_bytes(),
> which involves many more memory accesses, MUCH higher probably of
> cache line bouncing between CPU's, etc.
> 
> And there has been some proposals that I've been looking at to make
> fast_mix to be use even less overhead, so if we use fast_mix, any
> changes we make to improve that will help here too.

That makes sense to me.  It would require replacing current fast_mix()
with somethat doesn't doesn't assume __u32 input[4] as the only
possible parameter.  In a previous incarnation of my patch I was using
a single round of siphash to condense the registers and added that to
our fast_pool.

While siphash is fairly fast, doing that for every interrupt seemed
too much for me, hence the current ratelimit approach.  But if people
care more about maximum latency than amortized cost, we can combine
siphash (or something similar) with the ratelimit.

At any rate, here is a slightly updated patch that is independent of
CONFIG_HZ.

Jörn

--
"Error protection by error detection and correction."
-- from a university class

>From 867d62e0165723f9d8dc568d0cb9d8898948ddaa Mon Sep 17 00:00:00 2001
From: Joern Engel <joern@logfs.org>
Date: Sat, 15 Feb 2014 16:29:28 -0800
Subject: [PATCH] random: mix all saved registers into entropy pool

The single biggest entropy source is a high-resolution timer running
asynchronous to the triggering event.  That leaves systems without a
useful get_cycles() implementation with significantly less entropy.
Significant means orders of magnitude, not a few percent.

An alternate high-resolution timer is the register content at the time
of an interrupt.  While not monotonic, it is guaranteed to change every
few clock cycles and very unlikely to repeat the same pattern.  Not
useful for interpretation as time, but we only care about some bits
of the "clock" flipping in an unpredictable fashion.

Experimentation show this to be an excellent entropy source.  Doing 1000
boottests with kvm and dumping a hash of the registers for the first
1024 interrupts each, >40% of all hashes were unique and >80% of all
hashes occurred less than once 1% of the time.

Even assuming that only unique register hashes yield any entropy at all
and only one bit each, we would gather >400 bits of entropy early in
boot and another 40 bits/s from the timer interrupt during runtime.  I
would feel confident with this amount of entropy in the absence of any
other source.

Repeating the test on real hardware, albeit with fewer repetitions
yields roughly the same results, slightly above 40% unique hashes.

Signed-off-by: Joern Engel <joern@logfs.org>
---
 drivers/char/random.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 65 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 429b75bb60e8..8e9f6274cf76 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -553,6 +553,8 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
 
 struct fast_pool {
 	__u32		pool[4];
+	u32		last_shift;
+	u32		regs_count;
 	unsigned long	last;
 	unsigned short	count;
 	unsigned char	rotate;
@@ -835,6 +837,64 @@ EXPORT_SYMBOL_GPL(add_input_randomness);
 
 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
+/*
+ * Ratelimit to a steady state of about 50Hz.  A naïve approach would be
+ * to return 1 every time jiffies changes.  But we want to avoid being
+ * closely coupled to the timer interrupt.  So instead we increment a
+ * counter on every call and shift it right every time jiffies increments
+ * by 20ms.
+ * 20ms or 50Hz is chosen to work well for all options of CONFIG_HZ.
+ * If the counter is a power of two, return false.
+ *
+ * Effect is that some time after a jiffies change and cutting the counter
+ * in half we reach another power of two and return false.  But the
+ * likelihood of this happening is about the same at any time within a
+ * jiffies interval.
+ */
+static inline int ratelimited(struct fast_pool *p)
+{
+	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
+	u32 jiffies_low = (u32)jiffies;
+
+	p->regs_count++;
+	if (p->last_shift > jiffies_low || p->last_shift + HZ/50 <= jiffies_low) {
+		p->regs_count >>= 1;
+		p->last_shift = jiffies_low;
+	}
+	return ret;
+}
+
+#define BOOT_IRQS 1024
+
+/*
+ * The single biggest entropy source is a high-resolution timer running
+ * asynchronous to the triggering event.  That leaves systems without a
+ * useful get_cycles() implementation with significantly less entropy.
+ * Significant means orders of magnitude, not a few percent.
+ *
+ * An alternate high-resolution timer is the register content at the time
+ * of an interrupt.  While not monotonic, it is guaranteed to change every
+ * few clock cycles and very unlikely to repeat the same pattern.  Not
+ * useful for interpretation as time, but we only care about some bits
+ * of the "clock" flipping in an unpredictable fashion.
+ */
+static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)
+{
+	struct entropy_store	*r;
+	/* Two variables avoid decrementing by two without using atomics */
+	static int boot_count = BOOT_IRQS;
+	int in_boot = boot_count;
+
+	if (in_boot) {
+		boot_count = in_boot - 1;
+	} else if (ratelimited(fast_pool))
+		return;
+
+	/* During bootup we alternately feed both pools */
+	r = (in_boot & 1) ? &nonblocking_pool : &input_pool;
+	__mix_pool_bytes(r, regs, sizeof(*regs), NULL);
+}
+
 void add_interrupt_randomness(int irq, int irq_flags)
 {
 	struct entropy_store	*r;
@@ -845,13 +905,14 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u32			input[4], c_high, j_high;
 	__u64			ip;
 
+	mix_regs(regs, fast_pool);
 	c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
 	j_high = (sizeof(now) > 4) ? now >> 32 : 0;
-	input[0] = cycles ^ j_high ^ irq;
-	input[1] = now ^ c_high;
+	input[0] ^= cycles ^ j_high ^ irq;
+	input[1] ^= now ^ c_high;
 	ip = regs ? instruction_pointer(regs) : _RET_IP_;
-	input[2] = ip;
-	input[3] = ip >> 32;
+	input[2] ^= ip;
+	input[3] ^= ip >> 32;
 
 	fast_mix(fast_pool, input);
 
-- 
2.0.0.rc0.1.g7b2ba98

Re: [PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Tue, 10 June 2014 20:10:09 -0400, Jörn Engel wrote:
> On Tue, 10 June 2014 12:14:01 -0400, Theodore Ts'o wrote:
> > On Mon, May 19, 2014 at 05:17:19PM -0400, Jörn Engel wrote:
> > > +/*
> > > + * Ratelimit to a steady state of about once per jiffy.  A naïve approach
> > > + * would be to return 1 every time jiffies changes.  But we want to avoid
> > > + * being closely coupled to the timer interrupt.  So instead we increment
> > > + * a counter on every call and shift it right every time jiffies changes.
> > > + * If the counter is a power of two, return false;
> > > + *
> > > + * Effect is that some time after a jiffies change and cutting the counter
> > > + * in half we reach another power of two and return false.  But the
> > > + * likelihood of this happening is about the same at any time within a
> > > + * jiffies interval.
> > > + */
> > > +static inline int ratelimited(struct fast_pool *p)
> > > +{
> > > +	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
> > > +
> > > +	p->regs_count++;
> > > +	if (p->last_shift != (u32)jiffies) {
> > > +		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
> > > +		p->last_shift = (u32)jiffies;
> > > +	}
> > > +	return ret;
> > > +}
> > 
> > I wasn't convinced this would do the right thing, so I wrote a quick
> > test program where the main loop was basically this:
> > 
> > 	for (i=0; i < 1024; i++) {
> > 		jiffies = i >> 2;
> > 		r = ratelimited(jiffies);
> > 		printf("%5u %5u %5u %d\n", i, jiffies, regs_count, r);
> > 	}
> > 
> > ... which basically simulated a very simple scheme where there were
> > four interrupts for each clock tick.  In the steady state ratelimited
> > returns true 75% of the time.  If this was as documented, we would
> > expect it to return true 25% of the time.  So I don't think this is
> > working quite right:
> > 
> >    20     5     3 1
> >    21     5     4 1
> >    22     5     5 0
> >    23     5     6 1
> >    24     6     3 1
> >    25     6     4 1
> >    26     6     5 0
> >    27     6     6 1
> >    28     7     3 1
> >    29     7     4 1
> >    30     7     5 0
> >    31     7     6 1
> >    32     8     3 1
> 
> Doh!  Removing the "!" from "!(p->regs_count..." will fix that.  Shows
> I spent 100x more time testing the bootup entropy collection.

On second look, the function was correct.  If ratelimited() returns
true, the interrupt is ratelimited, i.e. ignored.  So correct
behaviour is to return false 25% of the time, just like it does.

You confused me for a moment!

Jörn

--
There are two ways of constructing a software design: one way is to make
it so simple that there are obviously no deficiencies, and the other is
to make it so complicated that there are no obvious deficiencies.
-- C. A. R. Hoare

[PATCH,RFC] random: collect cpu randomness

[Jörn Engel]

Collects entropy from random behaviour all modern cpus exhibit.  The
scheduler and slab allocator are instrumented for this purpose.  How
much randomness can be gathered is clearly hardware-dependent and hard
to estimate.  Therefore the entropy estimate is zero, but random bits
still get mixed into the pools.

Performance overhead seems low.  I did 20 kernel compiles with
allnoconfig, everything precompiled and warm caches.  Difference was in
the noise and on average performance was actually better when collecting
randomness.

To judge the benefits I ran this in kvm with instrumentation to print
out the various input values.  Entropy was estimated by booting ten
times, collecting the output for each boot, doing a diff between any two
and counting the diff hunks.  Numbers like "46 .. 215" means the two
most similar runs had 46 hunks, the two most dissimilar ones had 215.

Running kvm with -smp 4 gave the following results:
                 slab+sched     slab            sched
input[0]         46 .. 215      202 .. 342        0 ..   0
input[1]         76 .. 180        0 ..   4        0 ..   0
input[2]        147 .. 388        4 ..  44      286 .. 464
input[3]         56 .. 185        0 ..   2        9 ..  40
jiffies           8 ..  67       10 ..  28       19 ..  50
caller          114 .. 306       25 .. 178      219 .. 422
val              54 .. 254       15 .. 106      175 .. 321
&input           50 .. 246        0 ..  59      178 .. 387

First column collected entropy from both the slab allocator and the
scheduler, second and third only collected from one source.  I only used
the first 512 values per cpu.  Therefore the combined numbers can be
lower than the individual ones - there was more entropy collected, it
was just swamped by non-entropy.

Lots of entropy gets collected and about half of it stems from the
uninitialized valued of input[] on the stack.

Rerunning only the first column with -smp 1 was more sobering:
                slab+sched
input[0]          0 ..  13
input[1]          0 ..  13
input[2]          0 ..  14
input[3]          0 ..  11
jiffies           2 ..  22
caller            0 ..  19
val               0 ..  16
&input            0 ..   4

Every single input value contains entropy in some runs, but the only one
that was an entropy guarantee was jiffies.  In other words, a
low-precision clock.  This clearly shows how important it is to have a
high-precision clock, which would gather significantly more entropy.

Measuring the randomness from random_get_entropy() with above approach
failed because there was so much randomness.  All numbers in all runs
were different.  Taking the delta between the numbers, again almost all
numbers were different with at most 1 identical delta per 1000.
Compared to a high-precision clock, no other input comes within two
orders of magnitude.

An interesting aside is that the cpu actually functions as a
high-precision clock.  This partially explains why the -smp 4 number are
so much better - any drift between the four cpu-clocks gets turned into
randomness.  The other explanation is that kvm is actually collecting
randomness from the host system.  I tried to minimize that effect by not
touching my notebook while running these tests, but a hardware test box
would clearly yield more meaningful results.

I invite others to also test whether the patch collects useful
randomness or causes a measureable performance loss on any hardware or
workload.  Preferrably not using my methods, in order to avoid
systematic errors.

Signed-off-by: Joern Engel <joern@logfs.org>
---
 drivers/char/random.c  | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/random.h |  2 ++
 kernel/sched/core.c    |  1 +
 mm/slab.c              |  1 +
 4 files changed, 65 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 429b75bb60e8..693dea730a3e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -587,6 +587,30 @@ static void fast_mix(struct fast_pool *f, __u32 input[4])
 }
 
 /*
+ * An even faster variant of fast_mix, albeit with worse mixing.
+ */
+static void weak_mix(struct fast_pool *f, __u32 input[4])
+{
+	__u32 acc, carry = f->pool[3] >> 25;
+
+	acc = (f->pool[0] << 7) ^ input[0] ^ carry;
+	carry = f->pool[0] >> 25;
+	f->pool[0] = acc;
+
+	acc = (f->pool[1] << 7) ^ input[1] ^ carry;
+	carry = f->pool[1] >> 25;
+	f->pool[1] = acc;
+
+	acc = (f->pool[2] << 7) ^ input[2] ^ carry;
+	carry = f->pool[2] >> 25;
+	f->pool[2] = acc;
+
+	acc = (f->pool[3] << 7) ^ input[3] ^ carry;
+	//carry = f->pool[3] >> 25;
+	f->pool[3] = acc;
+}
+
+/*
  * Credit (or debit) the entropy store with n bits of entropy.
  * Use credit_entropy_bits_safe() if the value comes from userspace
  * or otherwise should be checked for extreme values.
@@ -833,6 +857,43 @@ void add_input_randomness(unsigned int type, unsigned int code,
 }
 EXPORT_SYMBOL_GPL(add_input_randomness);
 
+static DEFINE_PER_CPU(struct fast_pool, cpu_randomness);
+
+void __add_cpu_randomness(void *caller, void *val)
+{
+	struct entropy_store	*r;
+	struct fast_pool	*fast_pool = &__get_cpu_var(cpu_randomness);
+	unsigned long		now = jiffies;
+	__u32			input[4], cycles = random_get_entropy();
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wuninitialized"
+	input[0] ^= cycles ^ jiffies;
+	input[1] ^= (unsigned long)caller;
+	input[2] ^= (unsigned long)val;
+	input[3] ^= (unsigned long)&input;
+#pragma GCC diagnostic pop
+
+	weak_mix(fast_pool, input);
+
+	if ((fast_pool->count++ & 1023) &&
+	    !time_after(now, fast_pool->last + HZ))
+		return;
+
+	fast_pool->last = now;
+	fast_pool->count = 1;
+
+	r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
+	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL);
+}
+
+void add_cpu_randomness(void *caller, void *val)
+{
+	preempt_disable();
+	__add_cpu_randomness(caller, val);
+	preempt_enable();
+}
+
 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
 void add_interrupt_randomness(int irq, int irq_flags)
diff --git a/include/linux/random.h b/include/linux/random.h
index 4002b3df4c85..ce0ccdcd1d63 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -12,6 +12,8 @@
 extern void add_device_randomness(const void *, unsigned int);
 extern void add_input_randomness(unsigned int type, unsigned int code,
 				 unsigned int value);
+extern void __add_cpu_randomness(void *caller, void *val);
+extern void add_cpu_randomness(void *caller, void *val);
 extern void add_interrupt_randomness(int irq, int irq_flags);
 
 extern void get_random_bytes(void *buf, int nbytes);
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index a88f4a485c5e..7af6389f9b9e 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2511,6 +2511,7 @@ need_resched:
 	rq = cpu_rq(cpu);
 	rcu_note_context_switch(cpu);
 	prev = rq->curr;
+	__add_cpu_randomness(__builtin_return_address(1), prev);
 
 	schedule_debug(prev);
 
diff --git a/mm/slab.c b/mm/slab.c
index eb043bf05f4c..ea5a30d44ad1 100644
--- a/mm/slab.c
+++ b/mm/slab.c
@@ -3587,6 +3587,7 @@ static __always_inline void *__do_kmalloc(size_t size, gfp_t flags,
 	trace_kmalloc(caller, ret,
 		      size, cachep->size, flags);
 
+	add_cpu_randomness(__builtin_return_address(2), ret);
 	return ret;
 }
 
-- 
1.8.5.2

Re: [PATCH,RFC] random: collect cpu randomness

[Jörn Engel]

On Sun, 2 February 2014 15:36:17 -0500, Jörn Engel wrote:
> 
> Measuring the randomness from random_get_entropy() with above approach
> failed because there was so much randomness.  All numbers in all runs
> were different.  Taking the delta between the numbers, again almost all
> numbers were different with at most 1 identical delta per 1000.
> Compared to a high-precision clock, no other input comes within two
> orders of magnitude.

I think this is a key result from my tests.  The best source is a
timer (counter) that is both
a) high-resolution and
b) asynchronous to the measurement event.

If the measurement event is an interrupt and the CPU has a
cycle-counter, you are set.  On interesting systems lacking a
cycle-counter, we still have a high-resolution counter or sorts that
is the CPU itself.

Instruction pointer and stack pointer for both kernel and userland are
one way to read out the "counter".  Main problem here are tight loops
where your "counter" is not high-resolution at all.  But something
within the CPU is constantly changing.  And that something tends to be
contained in the registers.

How about taking the saved registers from the interrupted CPU, xor'ing
them all and calling the result random_get_entropy() on systems
lacking a good cycles-counter?

Jörn

--
I can say that I spend most of my time fixing bugs even if I have lots
of new features to implement in mind, but I give bugs more priority.
-- Andrea Arcangeli, 2000

Re: [PATCH,RFC] random: collect cpu randomness

[Theodore Ts'o]

On Mon, Feb 03, 2014 at 10:50:42AM -0500, Jörn Engel wrote:
> If the measurement event is an interrupt and the CPU has a
> cycle-counter, you are set.  On interesting systems lacking a
> cycle-counter, we still have a high-resolution counter or sorts that
> is the CPU itself.
> 
> Instruction pointer and stack pointer for both kernel and userland are
> one way to read out the "counter".  Main problem here are tight loops
> where your "counter" is not high-resolution at all.  But something
> within the CPU is constantly changing.  And that something tends to be
> contained in the registers.
> 
> How about taking the saved registers from the interrupted CPU, xor'ing
> them all and calling the result random_get_entropy() on systems
> lacking a good cycles-counter?

So we could take the struct pt_regs which we get from get_irq_regs(),
XOR them together and use them to feed into input[2] amd input[3] in
add_interrupt_randomness().  Or some other way of distributing the
values of all of the irq registers into the __u32 input[4] array.

That would probably be a good and useful thing to do.  Was that
basically what you were suggesting?

						- Ted

Re: [PATCH,RFC] random: collect cpu randomness

[Jörn Engel]

On Mon, 3 February 2014 11:37:29 -0500, Theodore Ts'o wrote:
> 
> So we could take the struct pt_regs which we get from get_irq_regs(),
> XOR them together and use them to feed into input[2] amd input[3] in
> add_interrupt_randomness().  Or some other way of distributing the
> values of all of the irq registers into the __u32 input[4] array.
> 
> That would probably be a good and useful thing to do.  Was that
> basically what you were suggesting?

Yes.

Jörn

--
When you copy some code, you are supposed to read it.  If nothing else,
there's a chance to spot and fix an obvious bug instead of sharing it...
-- Al Viro

[PATCH] random: mix all saved registers into entropy pool

[Jörn Engel]

On Mon, 3 February 2014 13:48:57 -0500, Jörn Engel wrote:
> On Mon, 3 February 2014 11:37:29 -0500, Theodore Ts'o wrote:
> > 
> > So we could take the struct pt_regs which we get from get_irq_regs(),
> > XOR them together and use them to feed into input[2] amd input[3] in
> > add_interrupt_randomness().  Or some other way of distributing the
> > values of all of the irq registers into the __u32 input[4] array.
> > 
> > That would probably be a good and useful thing to do.  Was that
> > basically what you were suggesting?
> 
> Yes.

And here is a patch to do just that.  I am extremely unhappy with it
because it plain Does Not Help(tm).  At least it does not when using
kvm without VGA output.  Booting kvm 1000 times gave me the exact same
values for every single boot.  Quite sobering.

This patch didn't collect a single bit of entropy!

Surprisingly I find this failure quite valuable.  I managed to prove
the futility of my method - at least on automated virtual machines
without network interactions.  Afaiu none of the other entropy sources
have proven to be of any value under these circumstances either.  It
is entirely possible that zero bits of entropy is the final verdict
for such virtual machines.  Not sure about everyone else, but that is
quite a surprise to me.

Next step will be to test this patch on some entropy-challenged
hardware.

Jörn

--
The object-oriented version of 'Spaghetti code' is, of course, 'Lasagna code'.
(Too many layers).
-- Roberto Waltman.


The single biggest entropy source is a high-resolution timer running
asynchronous to the triggering event.  That leaves systems without a
useful get_cycles() implementation with significantly less entropy.
Significant means orders of magnitude, not a few percent.

An alternate high-resolution timer is the register content at the time
of an interrupt.  While not monotonic, it is guaranteed to change every
few clock cycles and very unlikely to repeat the same pattern.  Not
useful for interpretation as time, but we only care about some bits
of the "clock" to flip in an unpredictable fashion.

Signed-off-by: Joern Engel <joern@logfs.org>
---
 drivers/char/random.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 81 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 693dea730a3e..4a0633973aa7 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -257,6 +257,7 @@
 #include <linux/kmemcheck.h>
 #include <linux/workqueue.h>
 #include <linux/irq.h>
+#include <linux/crc32.h>
 
 #include <asm/processor.h>
 #include <asm/uaccess.h>
@@ -553,6 +554,8 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
 
 struct fast_pool {
 	__u32		pool[4];
+	u32		last_shift;
+	u32		regs_count;
 	unsigned long	last;
 	unsigned short	count;
 	unsigned char	rotate;
@@ -896,6 +899,79 @@ void add_cpu_randomness(void *caller, void *val)
 
 static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
+/*
+ * Ratelimit to a steady state of about once per jiffy.  A naïve approach
+ * would be to return 1 every time jiffies changes.  But we want to avoid
+ * being closely coupled to the timer interrupt.  So instead we increment
+ * a counter on every call and shift it right every time jiffies changes.
+ * If the counter is a power of two, return false;
+ *
+ * Effect is that some time after a jiffies change and cutting the counter
+ * in half we reach another power of two and return false.  But the
+ * likelihood of this happening is about the same at any time within a
+ * jiffies interval.
+ */
+static inline int ratelimited(struct fast_pool *p)
+{
+	int ret = !(p->regs_count == 0 || is_power_of_2(p->regs_count));
+
+	p->regs_count++;
+	if (p->last_shift != (u32)jiffies) {
+		p->regs_count >>= min(31u, (u32)jiffies - p->last_shift);
+		p->last_shift = (u32)jiffies;
+	}
+	return ret;
+}
+
+#define BOOT_IRQS 1024
+
+#if 1 /* XXX: create config option, as it is a bit spammy */
+/*
+ * We have a few conflicting requirements.  In order to judge the quality
+ * of randomness we want to print out inputs on the console.  Clearly we
+ * also want to keep the inputs secret.  Tradeoff is to print a hash of
+ * the inputs a couple of times during boot.
+ */
+static void trace_boot_regs(struct pt_regs *regs, int boot_count)
+{
+	static u32 log[BOOT_IRQS];
+	int i;
+	log[BOOT_IRQS - boot_count] = crc32(0, regs, sizeof(*regs));
+	if (boot_count == 1) {
+		for (i = 0; i < BOOT_IRQS; i++)
+			pr_info("irq regs(%d): %x\n", i, log[i]);
+	}
+}
+#endif
+
+/*
+ * The single biggest entropy source is a high-resolution timer running
+ * asynchronous to the triggering event.  That leaves systems without a
+ * useful get_cycles() implementation with significantly less entropy.
+ * Significant means orders of magnitude, not a few percent.
+ *
+ * An alternate high-resolution timer is the register content at the time
+ * of an interrupt.  While not monotonic, it is guaranteed to change every
+ * few clock cycles and very unlikely to repeat the same pattern.  Not
+ * useful for interpretation as time, but we only care about some bits
+ * of the "clock" to flip in an unpredictable fashion.
+ */
+static void mix_regs(struct pt_regs *regs, struct fast_pool *fast_pool)
+{
+	/* Two variables avoid decrementing by two without using atomics */
+	static int boot_count = BOOT_IRQS;
+	int in_boot = boot_count;
+
+	if (in_boot) {
+		trace_boot_regs(regs, boot_count);
+		boot_count = in_boot - 1;
+	} else if (ratelimited(fast_pool))
+		return;
+
+	mix_pool_bytes(&input_pool, regs, sizeof(*regs), NULL);
+	mix_pool_bytes(&nonblocking_pool, regs, sizeof(*regs), NULL);
+}
+
 void add_interrupt_randomness(int irq, int irq_flags)
 {
 	struct entropy_store	*r;
@@ -906,13 +982,14 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u32			input[4], c_high, j_high;
 	__u64			ip;
 
+	mix_regs(regs, fast_pool);
 	c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0;
 	j_high = (sizeof(now) > 4) ? now >> 32 : 0;
-	input[0] = cycles ^ j_high ^ irq;
-	input[1] = now ^ c_high;
+	input[0] ^= cycles ^ j_high ^ irq;
+	input[1] ^= now ^ c_high;
 	ip = regs ? instruction_pointer(regs) : _RET_IP_;
-	input[2] = ip;
-	input[3] = ip >> 32;
+	input[2] ^= ip;
+	input[3] ^= ip >> 32;
 
 	fast_mix(fast_pool, input);
 
-- 
1.8.5.3