parameterize design of adaptive refill;

clean up comments

1 files changed, 151 insertions, 75 deletions

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 5dc7ad8..66f924f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -70,13 +70,31 @@
 
  * Operation of this device is centered on four "pools".  The four
  * pools are similar in structure but serve different purposes.
+ */
 
+#ifdef OVERCOMPLICATED
+/*
+ * Here is a block diagram:
+ *
+ *  fast      fast                   devrandom
+ * events --> pool --\   input   /---> pool --> /dev/random
+ *                    --> pool --
+ * slower, larger    /           \     PRNG
+ * events ----------/             \--> pool --> /dev/urandom
+ */
+#else
+/*
  * Here is a block diagram:
  *
- *  fast events --> fast pool --\                 /--> blocking pool
- *                               --> input pool --
- *  slower, larger events ------/                 \--> nonblocking pool
+ * fast       fast
+ * events --> pool --\   input   /------------> /dev/random
+ *                    --> pool --
+ * slower, larger    /           \     PRNG
+ * events ----------/             \--> pool --> /dev/urandom
+ */
+#endif
 
+/*
  * The fast pool is similar in function to the input pool, as
  * described below.  It handles events that occur frequently but
  * contain little entropy.  It is fast enough that the overhead of
@@ -85,46 +103,46 @@
  * a modest amount of entropy, it passes the entropy on to the input
  * pool.
 
- * The input pool is serves as both a concentrator and as the main
- * storage area.  The entropy that is available as input to the input
- * pool commonly has an entropy density of much less than 8 bits per
- * byte.  This is mixed into the input pool, which is mixed using a
- * CRC-like function.  The mixing is not cryptographically strong, but
- * should be adequate if the randomness is not chosen maliciously.  As
- * bytes are mixed into this pool, the routines keep an *estimate* of
- * how many bits of entropy are contained in the pool.
+ * The input pool is serves as a concentrator, mixer, and storage
+ * area.  The entropy that is available as input to the input pool
+ * commonly has an entropy density of much less than 8 bits per byte.
+ * This is mixed into the input pool, which is mixed using a CRC-like
+ * function.  The mixing is not cryptographically strong, but should
+ * be adequate if the randomness is not chosen maliciously.  As bytes
+ * are mixed into this pool, the routines keep an *estimate* of how
+ * many bits of entropy are contained in the pool.
 
  * When randomly-distributed bytes are desired, they can be extracted
- * from the input pool by taking the SHA hash of the pool contents.
+ * from the input pool by taking the SHA1 hash of the pool contents.
  * This avoids exposing the internal state of the pool.  It is
  * believed to be computationally infeasible to derive any useful
- * information about the input of SHA from its output.  Even if it is
- * possible to analyze SHA in some clever way, as long as the amount
+ * information about the input of SHA1 from its output.  Even if it is
+ * possible to analyze SHA1 in some clever way, as long as the amount
  * of data extracted in this way is less than the entropy content of
  * the the input pool, the extracted data is totally unpredictable.
  * For this reason, the routine decreases its internal estimate of how
  * many bits of "true randomness" (aka entropy) are contained in the
  * input pool whenever data is extracted.
 
- * The blocking pool is associated with /dev/random.  It is similar in
- * structure to the input pool, but its purpose is different.  It
- * takes its input from the input pool, so the input has a high
- * entropy density (8 bits per byte) so no concentration is necessary.
- * Therefore this pool serves primarily as a fifo.  If the amount of
- * entropy stored in the blocking pool is insufficient to meet the
- * demand, and no more entropy can be pulled from the input pool, any
- * read to /dev/random will block.
-
- * The nonblocking pool is associated with the /dev/urandom device,
- * and with the get_random_bytes() function used by the kernel
- * internally.  This pool is similar in structure, but its function is
- * quite different from the other pools.  It functions primarily as a
- * PRNG i.e. pseudo ranomness generator.  Specifically, it functions
- * as hash function operated in counter mode.  The PRNG is reseeded
- * from time to time, using entropy from the input pool.  An attacker
- * may (at least in theory) be able to infer the future output of the
- * PRNG from prior outputs.  This requires successful cryptanalysis of
- * SHA, which is not believed to be feasible, but there is a remote
+ * The devrandom pool (if any) is associated with /dev/random.  It is
+ * similar in structure to the input pool, but its purpose is
+ * different.  Its input comes from the input pool, which means the
+ * the entropy density is high (8 bits per byte), so no concentration
+ * or mixing is necessary.  Therefore this pool serves primarily as a
+ * fifo.  If the amount of entropy stored in the devrandom pool is
+ * insufficient to meet the demand, and no more entropy can be pulled
+ * from the input pool, any read to /dev/random will block.
+
+ * The PRNG pool is associated with the /dev/urandom device, and with
+ * the get_random_bytes() function used by the kernel internally.
+ * This pool is similar in structure, but its function is quite
+ * different from the other pools.  It functions primarily as a PRNG
+ * i.e. pseudo ranomness generator.  Specifically, it functions as
+ * hash function operated in counter mode.  The PRNG is reseeded from
+ * time to time, using entropy from the input pool.  An attacker may
+ * (at least in theory) be able to infer the future output of the PRNG
+ * from prior outputs.  This requires successful cryptanalysis of SHA,
+ * which is not believed to be feasible, but there is a remote
  * possibility.  Nonetheless, a pseudorandom distribution of numbers
  * should be useful for a wide range of purposes.
 
@@ -196,12 +214,12 @@
 
  * .../poolsize (read only) -- reports the size of the input pool.  Since
  * 2.6.12 this is measured in bits.  Previously it was measured in
- * bytes.  Note that the blocking pool and the nonblocking pool are 4x
+ * bytes.  Note that the devrandom pool and the prng pool are 4x
  * smaller than the input pool.
 
  * .../entropy_avail (read only) -- reports the total amount of stored
  * entropy, measured in bits.  This includes entropy stored in both
- * the input pool and the blocking pool.
+ * the input pool and the devrandom pool.
 
  * .../entropy_avail_input .../entropy_avail_random
  * .../entropy_avail_urandom (r/w) -- same as above, but report the
@@ -241,28 +259,30 @@
  * start-ups.  To do this, put the following lines an appropriate
  * script which is run during the boot sequence:
 
- * The byte count of 512 is overkill at present, since we
- * only use it to reseed pools that are 4x smaller than that,
- * but we preserve it because (a) it is traditional, and (b)
- * we might put it to good use in future versions.
+ * The byte count of 512 is overkill in the OVERCOMPLICATED
+ * implementation, since we only use it to reseed pools that are 4x
+ * smaller than that.  We preserve it because (a) it is
+ * traditional, and (b) it is the right value for the non-OVERCOMPLICATED
+ * design, where the input pool is being reseeded.
 
  *	echo "Initializing random number generator..."
  *	random_seed=/var/run/random-seed
  *	# Carry a random seed from start-up to start-up
- *	# Load and then save the whole nonblocking pool
+ *	# Load the input pool:
  *	if [ -f $random_seed ]; then
  *		cat $random_seed >/dev/urandom
  *	else
  *		touch $random_seed
  *	fi
  *	chmod 600 $random_seed
+ *      # Save enough to reseed (differently!) next time:
  *	dd if=/dev/urandom of=$random_seed count=1 bs=512
  *
  * and the following lines in an appropriate script which is run as
  * the system is shutdown:
  *
  *	# Carry a random seed from shut-down to start-up
- *	# Save the whole nonblocking pool
+ *	# Save enough reseed the input pool.
  *	echo "Saving random seed..."
  *	random_seed=/var/run/random-seed
  *	touch $random_seed
@@ -273,20 +293,40 @@
  * scripts, such code fragments would be found in
  * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
  * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
+ */
 
- * Effectively, these commands cause the contents of the nonblocking
- * pool to be saved at shut-down time and then used to initialize the
- * nonblocking pool -- and the blocking pool -- at start-up.  (The
- * seed is saved by the bootup script, not only by the shutdown
- * script, to make sure that /etc/random-seed is different for every
+#ifdef OVERCOMPLICATED
+/*
+ * Effectively, these commands save a pseudorandomly-distribted seed
+ * and then use that to initialize the prng pool -- and the devrandom
+ * pool -- at the next start-up.  (The seed is saved by the bootup
+ * script, not only by the shutdown script, to make sure that
+ * /etc/random-seed is never re-used.  It must be different for every
  * start-up, even if the system crashes without executing rc.0.)  Even
  * with complete knowledge of the start-up activities, predicting the
  * state of the output pools requires knowledge of the previous
  * history of the system.
 
- * Note that writing to /dev/urandom affects only the blocking pool
- * and nonblocking pool (not the input pool or fast pool).
+ * Note that writing to /dev/urandom affects only the devrandom pool
+ * and prng pool (not the input pool or fast pool).
+ */
+#else
+/*
+ * Effectively, these commands save a pseudorandomly-distribted seed
+ * and then use that to initialize the prng pool -- and the input
+ * pool -- at the next start-up.  (The seed is saved by the bootup
+ * script, not only by the shutdown script, to make sure that
+ * /etc/random-seed is never re-used.  It must be different for every
+ * start-up, even if the system crashes without executing rc.0.)  Even
+ * with complete knowledge of the start-up activities, predicting the
+ * state of the output pools requires knowledge of the previous
+ * history of the system.
 
+ * Note that writing to /dev/urandom affects only the input pool
+ * and prng pool (not the fast pool).
+ */
+#endif
+/*
  * Writing to /dev/random is identical to writing to /dev/urandom.
 
  * Configuring the /dev/random driver under Linux
@@ -362,11 +402,34 @@
 #define OUTPUT_POOL_WORDS 32
 #define SEC_XFER_SIZE 512
 #define EXTRACT_SIZE 10
+#ifdef OVERCOMPLICATED
+/* Three fills of size BUFFILL_ZONE is more than enough
+ * to fill the output buffer */
+#  define BUFFILL_ZONE 400      /* measured in bits */
+#endif
 
 /* Choose 160 bits.  Seems reasonable.  Recommended in the Yarrow paper.  */
-#define RESEED_BATCH    160             /* bits */
+#define RESEED_BATCH 160                /* bits */
+#define FIRST_RESEED 18                 /* dimensionless log(ratio) */
+#define MIN_DILUTION 1000               /* bits, approximately */
+#define APP_MAX 20                      /* dimensionless # steps */
+/*
+ * We design for MIN_DILUTION=1000 approximately.  We get 819 exactly,
+ * because FIRST_RESEED has to be rounded to an integer.
+ *
+ * The dilution factor ranges from 819 to 1 (at appetite=0) to 819<<20
+ * i.e. 858,993,459 to 1 (at appetite=20) ... assuming APP_MAX == 20.
+ */
+#if RESEED_BATCH*MIN_DILUTION < 1<<(FIRST_RESEED-1) \
+   || RESEED_BATCH*MIN_DILUTION >= 1<<(FIRST_RESEED)
+#  error Inconsistent values of FIRST_RESEED and RESEED_BATCH*MIN_DILUTION
+#endif
+
 /* Saturation point of extraction subttl counters; large round number: */
 #define SUBTTL_SAT 1000000000000000000LL
+#if SUBTTL_SAT <= RESEED_BATCH<<(FIRST_RESEED + APP_MAX)
+#  error Bogus value for SUBTTL_SAT
+#endif
 
 typedef unsigned long long int ulonglong;
 #if defined __SIZEOF_LONG_LONG__ && __SIZEOF_LONG_LONG__ == 8
@@ -760,7 +823,7 @@ struct timer_rand_state {
  * pools to help initialize them to unique values.
  *
  * None of this adds any entropy, it is meant to avoid the
- * problem of the nonblocking pool having similar initial state
+ * problem of the prng pool having similar initial state
  * across largely identical devices.
  */
 void add_device_randomness(const void *buf, unsigned int size)
@@ -928,7 +991,7 @@ void add_disk_randomness(struct gendisk *disk)
  * Since the latter is not guaranteed, please do not call them
  * "entropy" extraction routines.
 
- * Specifically, in the case of the PRNG, i.e. the nonblocking pool,
+ * Specifically, in the case of the PRNG, i.e. the prng pool,
  * the extracted bytes may have an entropy density that is vastly less
  * than 8 bits per byte, orders of magnitude less.
 
@@ -959,45 +1022,58 @@ static void fill_pool(
         size_t want_level               /* measured in BYTES */
 ){
 	__u32 tmp[OUTPUT_POOL_WORDS];
-        int rsvd;                       /* measured in bits */
+        int rsvd = 0;                   /* measured in bits */
+        int mybatch = 0;
         int txbits;
-        int mybatch;
         int actual;                     /* measured in BYTES */
-        int headspace = r->poolinfo->POOLBITS - r->entropy_count;
 	if (!r->pull) return;           /* no upstream pool to pull from */
         if (r->blockable) {
+#ifndef OVERCOMPLICATED
+/* should never get here; devrandom pool has nowhere to pull from */
+#else
 /* Here if we are blockable i.e. /dev/random i.e. TRNG. */
-                int pullhead = r->pull->poolinfo->POOLBITS - r->pull->entropy_count;
-/* Only the top 500 bits are free for extraloading: */
-                int extraload = 500 - pullhead;
-/* Don't extraload more than needed to fill the headspace: */
-                extraload = min_t(int, extraload, headspace);
+/* How much _unfilled_ headspace is our buffer: */
+                int ourhead = r->poolinfo->POOLBITS
+                            - r->entropy_count;
+/* Ditto for the upstream source: */
+                int pullhead = r->pull->poolinfo->POOLBITS
+                             - r->pull->entropy_count;
+/* The more the source is unfilled, the less we can buffill */
+                int buffill = BUFFILL_ZONE - pullhead;
+/* Don't buffill more than needed to fill our headspace: */
+                buffill = min_t(int, buffill, headspace);
+/* Number of bits to transfer: */
                 txbits = BYTE2BIT(want_level) - r->entropy_count;
-/* Load what is actually requested, or extraload whatever is freely available: */
-                txbits =  max_t(int, txbits, extraload);
+/*
+ * Transfer enough to meet the requested level,
+ * or buffill with whatever is freely available,
+ * whichever is more:
+ */
+                txbits =  max_t(int, txbits, buffill);
                 if (txbits <= 0) return;        /* already have all we want */
                 mybatch = rsvd = 0;
+#endif
         } else {
 /*
- * Here if we are non-blocking i.e. urandom i.e. PRNG.
- * Reserve a suitable amount of entropy in the input pool, on a
- * sliding scale based on how desperately we need to be reseeded.
+ * Here if we are non-blocking i.e. urandom i.e. PRNG.  Reserve a
+ * suitable amount of entropy in the upstream source, on a sliding
+ * scale based on how desperately we need to be reseeded.
  *
  * Ignore the caller's want_level.  Entropy level doesn't mean much
- * for a PRNG.  The only thing the PRNG ever requests is RESEED_BATCH.
+ * for a PRNG.  The only amount the PRNG ever requests is RESEED_BATCH.
  *
- * The dilution factor ranges from 819 to 1 (at appetite=0)
- * to 858,993,459 to 1 (at appetite=20)
  */
-          int appetite = fls64(r->extracted_subttl) - 18;
+         int appetite = fls64(r->extracted_subttl) - FIRST_RESEED;
           if (appetite < 0) return;      /* 128k bits maps to appetite 0 */
-/* The largest rsvd that makes any sense: */
+/* The largest rsvd that makes any sense;
+ * applies when appetite=0:
+ */
           rsvd = W2BIT(r->pull->poolinfo->poolwords) - RESEED_BATCH;
 /* When the appetite gets to 20, rsvd goes to zero: */
-          rsvd = rsvd - appetite*rsvd/20;
+          rsvd = rsvd - appetite*rsvd / APP_MAX;
           if (rsvd < 0) rsvd = 0;
 /*
- * For the PRNG, make the request big enough to be
+ * For the PRNG, make the requested batch big enough to be
  * "significant" to any attacker:
  */
           mybatch = txbits = RESEED_BATCH;
@@ -1007,12 +1083,12 @@ static void fill_pool(
         txbits = min_t(int, txbits, 8*sizeof(tmp));
 
         DEBUG_ENT("About to reseed %s adding %d bits;"
-                  "  caller want_level: %zu  prev level: %d"
-                  "  batch: %d  rsvd: %d\n",
+                  "  caller want_level: %zu  prev level: %d bits\n",
                   r->name, txbits,
-                  want_level * 8, r->entropy_count,
+                  want_level * 8, r->entropy_count);
+        DEBUG_ENT("Reseed batch: %d  rsvd: %d bytes\n",
                   BIT2BYTE(mybatch), BIT2BYTE(rsvd));
-        if (txbits < 0) return;         /* already full enough */
+        if (txbits <= 0) return;         /* already full enough */
 
         actual = extract_rnd(r->pull, tmp, BIT2BYTE(txbits),
                 BIT2BYTE(mybatch), BIT2BYTE(rsvd));