[PATCH 4/5] random periodicity detection fix

[PATCH 4/5] random periodicity detection fix

[Matt Mackall]

The input layer is now sending us a bunch of events in a row for each
actual event. This shows up weaknesses in the periodicity detector and
using the high clock rate from get_clock: each keystroke is getting
accounted as 10 different tmaximal-entropy events.

A brief touch on a trackpad will generate as much as 2000 maximal
entropy events which is more than 2k of /dev/random output. IOW, we're
WAY overestimating input entropy. Here's one keystroke:

random 0024 0000 0000: mouse event
random 0035 0000 0000: added 11 entropy credits to input
random 0035 0000 0000: mouse event
random 0046 0000 0000: added 11 entropy credits to input
random 0046 0000 0000: mouse event
random 0056 0000 0000: added 10 entropy credits to input
random 0056 0000 0000: keyboard event
random 0067 0000 0000: added 11 entropy credits to input
random 0067 0000 0000: mouse event
random 0078 0000 0000: added 11 entropy credits to input
random 0078 0000 0000: awake
random 0078 0000 0000: reading 128 bits
random 0078 0000 0000: going to reseed blocking with 128 bits (128 of 0 requested)
random 0078 0000 0000: trying to extract 128 bits from input
random 0006 0000 0000: debiting 72 entropy credits from input
random 0006 0072 0000: added 72 entropy credits to blocking
random 0006 0072 0000: trying to extract 128 bits from blocking
random 0006 0000 0000: debiting 72 entropy credits from blocking
random 0006 0000 0000: read got 72 bits (56 still needed)
random 0006 0000 0000: reading 56 bits
random 0006 0000 0000: going to reseed blocking with 64 bits (56 of 0 requested
random 0006 0000 0000: trying to extract 64 bits from input
random 0006 0000 0000: debiting 0 entropy credits from input
random 0006 0000 0000: trying to extract 56 bits from blocking
random 0006 0000 0000: debiting 0 entropy credits from blocking
random 0006 0000 0000: read got 0 bits (56 still needed)
random 0006 0000 0000: sleeping
random 0006 0000 0000: mouse event
random 0017 0000 0000: added 11 entropy credits to input
random 0017 0000 0000: mouse event
random 0028 0000 0000: added 11 entropy credits to input
random 0028 0000 0000: mouse event
random 0038 0000 0000: added 10 entropy credits to input
random 0038 0000 0000: keyboard event
random 0049 0000 0000: added 11 entropy credits to input
random 0049 0000 0000: mouse event
random 0060 0000 0000: added 11 entropy credits to input

The first step to fixing this is to check periodicity and estimate
entropy against a slow clock like jiffies. We continue to mix in
get_clock() rather than jiffies where available.

This throws away most of the duplicate events and gives us more
sensible entropy estimates, but we still duplicates from input.c and
keyboard.c.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:27:56.027022454 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:27:57.406846542 -0800
@@ -805,8 +805,8 @@
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	cycles_t time;
-	long delta, delta2, delta3;
+	cycles_t data;
+	long delta, delta2, delta3, time;
 	int entropy = 0;
 
 	preempt_disable();
@@ -816,20 +816,12 @@
 		goto out;
 
 	/*
-	 * Use get_cycles() if implemented, otherwise fall back to
-	 * jiffies.
-	 */
-	time = get_cycles();
-	if (time)
-		num ^= (u32)((time >> 31) >> 1);
-	else
-		time = jiffies;
-
-	/*
 	 * Calculate number of bits of randomness we probably added.
 	 * We take into account the first, second and third-order deltas
 	 * in order to make our estimate.
 	 */
+	time = jiffies;
+
 	if (!state->dont_count_entropy) {
 		delta = time - state->last_time;
 		state->last_time = time;
@@ -861,7 +853,18 @@
 
 		entropy = int_ln_12bits(delta);
 	}
-	batch_entropy_store(num, time, entropy);
+
+	/*
+	 * Use get_cycles() if implemented, otherwise fall back to
+	 * jiffies.
+	 */
+	data = get_cycles();
+	if (data)
+		num ^= (u32)((data >> 31) >> 1);
+	else
+		data = time;
+
+	batch_entropy_store(num, data, entropy);
 out:
 	preempt_enable();
 }


-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 4/5] random periodicity detection fix

[Andries Brouwer]

On Wed, Jan 12, 2005 at 10:46:29PM -0800, Matt Mackall wrote:

> The input layer is now sending us a bunch of events in a row for each
> actual event. This shows up weaknesses in the periodicity detector and
> using the high clock rate from get_clock: each keystroke is getting
> accounted as 10 different tmaximal-entropy events.
> 
> A brief touch on a trackpad will generate as much as 2000 maximal
> entropy events which is more than 2k of /dev/random output. IOW, we're
> WAY overestimating input entropy.

Yes, indeed. I muttered about this long ago - let me see, yes,
http://marc.theaimsgroup.com/?l=linux-kernel&m=106271659930542&w=3

My patch did the opposite of your patch: I removed the
add entropy call in input.c.

I don't recall the details, but I think my reason was that some events
are synthetic, and I wanted all entropy calls to be derived from
actual outside sources.

Also, when there are several sources, all constant or almost constant,
then merging the streams might cause one to see variation where
there isn't really any.
Also that is a reason not to do the adding so far away from the source.

Andries

Re: [PATCH 4/5] random periodicity detection fix

[Matt Mackall]

On Thu, Jan 13, 2005 at 11:34:37PM +0100, Andries Brouwer wrote:
> On Wed, Jan 12, 2005 at 10:46:29PM -0800, Matt Mackall wrote:
> 
> > The input layer is now sending us a bunch of events in a row for each
> > actual event. This shows up weaknesses in the periodicity detector and
> > using the high clock rate from get_clock: each keystroke is getting
> > accounted as 10 different tmaximal-entropy events.
> > 
> > A brief touch on a trackpad will generate as much as 2000 maximal
> > entropy events which is more than 2k of /dev/random output. IOW, we're
> > WAY overestimating input entropy.
> 
> Yes, indeed. I muttered about this long ago - let me see, yes,
> http://marc.theaimsgroup.com/?l=linux-kernel&m=106271659930542&w=3
> 
> My patch did the opposite of your patch: I removed the
> add entropy call in input.c.

Unfortunately almost all the original call sites have been dropped, so
it's now easier to do it this way.

Further, the input folks can't be relied upon to do the right thing,
so it's better to grab _all_ the relevant data in one place and do our
own filtering. 5/5 is a step in that direction, but the filtering is
currently primitive.

Eventually we can do as gendisk does and embed a pointer to an
entropy_state in the input objects and get back to all devices being
monitored independently. 

I've got a few dozen more /dev/random cleanup patches to push before
that happens though.

> Also, when there are several sources, all constant or almost constant,
> then merging the streams might cause one to see variation where
> there isn't really any.

Agreed. Not a huge problem for input as the sources are all really a
single console user (or so), but I'd like to check periodicity
per-device and globally eventually.

-- 
Mathematics is the supreme nostalgia of our time.