(6/7) core accounting

diff -ur a/drivers/char/random.c b/drivers/char/random.c
@@ -1,7 +1,8 @@
 /*
  * random.c -- A strong random number generator
  *
- * Version 1.89, last modified 19-Sep-99
+ * Version 2.0, last modified 8-Aug-2002 
+ * by Oliver Xymoron <[email protected]>
  * 
  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
  * rights reserved.

@@ -116,8 +117,9 @@
  * The /dev/urandom device does not have this limit, and will return
  * as many bytes as are requested.  As more and more random bytes are
  * requested without giving time for the entropy pool to recharge,
- * this will result in random numbers that are merely cryptographically
- * strong.  For many applications, however, this is acceptable.
+ * this will result in random numbers that are merely
+ * cryptographically strong.  For almost all applications other than
+ * generation of large public/private key pairs, this is acceptable.
  *
  * Exported interfaces ---- input
  * ==============================

@@ -125,30 +127,24 @@
  * The current exported interfaces for gathering environmental noise
  * from the devices are:
  * 
- * 	void add_keyboard_randomness(unsigned char scancode);
- * 	void add_mouse_randomness(__u32 mouse_data);
- * 	void add_interrupt_randomness(int irq);
- * 	void add_blkdev_randomness(int irq);
- * 
- * add_keyboard_randomness() uses the inter-keypress timing, as well as the
- * scancode as random inputs into the "entropy pool".
- * 
- * add_mouse_randomness() uses the mouse interrupt timing, as well as
- * the reported position of the mouse from the hardware.
- *
- * add_interrupt_randomness() uses the inter-interrupt timing as random
- * inputs to the entropy pool.  Note that not all interrupts are good
- * sources of randomness!  For example, the timer interrupts is not a
- * good choice, because the periodicity of the interrupts is too
- * regular, and hence predictable to an attacker.  Disk interrupts are
- * a better measure, since the timing of the disk interrupts are more
- * unpredictable.
- * 
- * add_blkdev_randomness() times the finishing time of block requests.
- * 
- * All of these routines try to estimate how many bits of randomness a
- * particular randomness source.  They do this by keeping track of the
- * first and second order deltas of the event timings.
+ *	void *create_entropy_source(int granularity_khz);
+ *	void free_entropy_source(void *src);
+ *	void add_timer_randomness(void *src, unsigned datum);
+ *
+ * create_entropy_source() returns a handle for future calls to
+ * add_timer_randomness. The granularity_khz parameter is used to
+ * describe the intrinsic timing granularity of the source, eg 33000
+ * for a fast PCI device or 9 for a 9600bps serial device. 
+ *
+ * Untrusted sources can simply call add_timer_randomness with a null
+ * handle. Note that network timings cannot be trusted, nor can disk
+ * timings if they're immediately fed to the network! We'll assume the
+ * user has a modern ssh implementation that doesn't leak local
+ * keyboard and mouse timings.
+ *
+ * add_timing_entropy() mixes timing information and the given datum
+ * into the pool after making initial checks for randomness and
+ * estimating the number of usable entropy bits. 
  *
  * Ensuring unpredictability at system startup
  * ============================================

@@ -682,40 +678,71 @@
  *
  *********************************************************************/
 
-/* There is one of these per entropy source */
-struct timer_rand_state {
-	__u32		last_time;
-	__s32		last_delta,last_delta2;
+#if defined (__i386__) || defined (__x86_64__)
+#define CLOCK_KHZ cpu_khz
+#else
+#define CLOCK_KHZ HZ/1000
+#endif
+
+struct entropy_source
+{
+	int shift;
+	__u32 time, delta, delta2;
 };
 
-static struct timer_rand_state keyboard_timer_state;
-static struct timer_rand_state mouse_timer_state;
-static struct timer_rand_state extract_timer_state;
-static int trust_break=50, trust_pct=0, trust_min=0, trust_max=100;
+void *create_entropy_source(int granularity_khz)
+{
+	int factor;
+	struct entropy_source *es;
+
+	es = kmalloc(sizeof(struct entropy_source), GFP_KERNEL);
+
+	if(!es) return 0; /* untrusted */
+
+	/* figure out how many bits of clock resolution we
+	 * have to throw out given the source granularity */
+
+	factor=CLOCK_KHZ/granularity_khz;
+	
+	/* count bits in factor */
+	es->shift=0;
+	while(factor>>=1) es->shift++;
+			
+	DEBUG_ENT("new entropy source granularity %d kHZ, shift %d\n",
+		  granularity_khz, es->shift);
+
+	return (void *)es;
+}
+
+void free_entropy_source(void *src)
+{
+	kfree(src);
+}
+
+static void *generic_kbd, *generic_mouse;
 
 /*
- * This function adds entropy to the entropy "pool" by using timing
- * delays.  It uses the timer_rand_state structure to make an estimate
- * of how many bits of entropy this call has added to the pool.
- *
- * The number "num" is also added to the pool - it should somehow describe
- * the type of event which just happened.  This is currently 0-255 for
- * keyboard scan codes, and 256 upwards for interrupts.
- * On the i386, this is assumed to be at most 16 bits, and the high bits
- * are used for a high-resolution timer.
- *
- */
-static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
-{
-	__u32		time;
-	__s32		delta, delta2, delta3;
-	int		entropy = 0;
+ * estimation of entropy contained in a n-bit delta from an exponential
+ * distribution, derived from Benford's Law (rounded down)
+ */
+
+static int benford[16]={0,0,0,1,2,3,4,5,5,6,7,7,8,9,9,10};
+static int last_ctxt=0;
+static int trust_break=50, trust_pct=0, trust_min=0, trust_max=100;
+
+void add_timer_randomness(void *src, unsigned datum)
+{
+	struct entropy_source *es=(struct entropy_source *)src;
+	unsigned long ctxt;
+	__u32 time, delta;
+	__s32 delta2, delta3;
+	int bits = 0;
 
 #if defined (__i386__) || defined (__x86_64__)
 	if (cpu_has_tsc) {
 		__u32 high;
 		rdtsc(time, high);
-		num ^= high;
+		datum ^= high;
 	} else {
 		time = jiffies;
 	}

@@ -723,41 +750,28 @@
 	time = jiffies;
 #endif
 
-	/*
-	 * 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.
-	 */
-	if (state) {
-		delta = time - state->last_time;
-		state->last_time = time;
-
-		delta2 = delta - state->last_delta;
-		state->last_delta = delta;
-
-		delta3 = delta2 - state->last_delta2;
-		state->last_delta2 = delta2;
-
-		if (delta < 0)
-			delta = -delta;
-		if (delta2 < 0)
-			delta2 = -delta2;
-		if (delta3 < 0)
-			delta3 = -delta3;
-		if (delta > delta2)
-			delta = delta2;
-		if (delta > delta3)
-			delta = delta3;
-
-		/*
-		 * delta is now minimum absolute delta.
-		 * Round down by 1 bit on general principles,
-		 * and limit entropy entimate to 12 bits.
-		 */
-		delta >>= 1;
-		delta &= (1 << 12) - 1;
-
-		entropy = int_log2_16bits(delta);
+	if(es) /* trusted */
+	{
+		/* Check for obvious periodicity in sources */
+		delta = time - es->time;
+		delta2 = delta - es->delta;
+		if (delta2 < 0)	delta2 = -delta2;
+		delta3 = delta2 - es->delta2;
+		if (delta3 < 0)	delta3 = -delta3;
+		es->time = time;
+		es->delta = delta;
+		es->delta2 = delta2;
+		if (delta2 < delta) delta=delta2;
+		if (delta3 < delta) delta=delta3;
+
+		/* Check for possible busy waiting or irq flooding */
+		ctxt=nr_context_switches();
+		if (ctxt == last_ctxt) delta=0;
+		last_ctxt=ctxt;
+
+		/* Calculate entropy distribution */
+		delta>>=es->shift;
+		bits=benford[int_log2_16bits(delta & 0xffff)];
 	}
 	else if(trust_pct)
 	{

@@ -765,27 +779,23 @@
 		trust_break+=trust_pct;
 		if(trust_break >= 100)
 		{
-			entropy=1;
+			bits=1;
 			trust_break-=100;
 		}
 	}
 
-	batch_entropy_store(num^time, entropy);
+	batch_entropy_store(datum^time, bits);
 }
 
 void add_keyboard_randomness(unsigned char scancode)
 {
-	static unsigned char last_scancode;
-	/* ignore autorepeat (multiple key down w/o key up) */
-	if (scancode != last_scancode) {
-		last_scancode = scancode;
-		add_timer_randomness(&keyboard_timer_state, scancode);
-	}
+	/* autorepeat ignored based on coarse timing */
+	add_timer_randomness(generic_kbd, scancode);
 }
 
 void add_mouse_randomness(__u32 mouse_data)
 {
-	add_timer_randomness(&mouse_timer_state, mouse_data);
+	add_timer_randomness(generic_mouse, mouse_data);
 }
 
 void add_interrupt_randomness(int irq)

@@ -1389,8 +1399,6 @@
 
 void __init rand_initialize(void)
 {
-	int i;
-
 	if (create_entropy_store(DEFAULT_POOL_SIZE, &random_state))
 		return;		/* Error, return */
 	if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))

@@ -1403,8 +1411,8 @@
 #ifdef CONFIG_SYSCTL
 	sysctl_init_random(random_state);
 #endif
-	memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state));
-	memset(&mouse_timer_state, 0, sizeof(struct timer_rand_state));
+	generic_kbd = create_entropy_source(1);
+	generic_mouse = create_entropy_source(1);
 }
 
 static ssize_t

@@ -2203,6 +2211,9 @@
 
 
 
+EXPORT_SYMBOL(create_entropy_source);
+EXPORT_SYMBOL(free_entropy_source);
+EXPORT_SYMBOL(add_timer_randomness);
 EXPORT_SYMBOL(add_keyboard_randomness);
 EXPORT_SYMBOL(add_mouse_randomness);
 EXPORT_SYMBOL(add_interrupt_randomness);

diff -ur a/include/linux/random.h b/include/linux/random.h
@@ -46,6 +46,9 @@
 
 extern void batch_entropy_store(u32 val, int bits);
 
+extern void *create_entropy_source(int granularity_khz);
+extern void free_entropy_source(void *src);
+extern void add_timer_randomness(void *src, unsigned datum);
 extern void add_keyboard_randomness(unsigned char scancode);
 extern void add_mouse_randomness(__u32 mouse_data);
 extern void add_interrupt_randomness(int irq);