random: mix all saved registers into entropy pool

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.

Quoted 5 lines · Jörn Engel

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.

Quoted 5 lines · H. Peter Anvin

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.

Quoted 4 lines

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.

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.

Quoted 4 lines · Jörn Engel

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.

An alternate high-resolution timer is the register content at the time of an interrupt.

Quoted 3 lines · Jörn Engel

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?

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.

Quoted 4 lines

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.

Quoted 4 lines

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.

drivers/char/random.c +13 -0

+/*
+ * 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)

drivers/char/random.c +6 -0

+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;

Quoted 13 lines · Jörn Engel

drivers/char/random.c +13 -0

+/*
+ * 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)

drivers/char/random.c EXPORT_SYMBOL_GPL(add_input_randomness); · line 862

Quoted 10 lines

drivers/char/random.c +10 -0

+{
+	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

Quoted 6 lines

drivers/char/random.c +6 -0

+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;

drivers/char/random.c EXPORT_SYMBOL_GPL(add_input_randomness); · line 893

Quoted 10 lines

drivers/char/random.c +10 -0

+
+	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?

drivers/char/random.c void add_interrupt_randomness(int irq, int irq_flags) · line 909

Quoted 4 lines

drivers/char/random.c +2 -2

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

Quoted 7 lines

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.

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.

Quoted 8 lines · Jörn Engel

Quoted 7 lines

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.

Quoted 6 lines

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.

From 867d62e0165723f9d8dc568d0cb9d8898948ddaa Mon Sep 17 00:00:00 2001

Quoted 40 lines · Theodore Ts'o

Quoted 13 lines · Jörn Engel

drivers/char/random.c +13 -0

+/*
+ * 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)

drivers/char/random.c EXPORT_SYMBOL_GPL(add_input_randomness); · line 862

Quoted 10 lines

drivers/char/random.c +10 -0

+{
+	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:

Quoted 13 lines

   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.