make the comments slightly less wrong

1 files changed, 165 insertions, 109 deletions

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 7a06c59..13d5164 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -62,39 +62,72 @@
  * must be hard for outside attackers to observe, and use that to
  * generate random numbers.  In a Unix environment, this is best done
  * from inside the kernel.
- *
- * Sources of randomness from the environment include inter-keyboard
- * timings, inter-interrupt timings from some interrupts, and other
- * events which are both (a) non-deterministic and (b) hard for an
- * outside observer to measure.  Randomness from these sources are
- * added to an "entropy pool", which is mixed using a CRC-like function.
- * This is not cryptographically strong, but it is adequate assuming
- * the randomness is not chosen maliciously, and it is fast enough that
- * the overhead of doing it on every interrupt is very reasonable.
- * As random bytes are mixed into the entropy pool, the routines keep
- * an *estimate* of how many bits of randomness have been stored into
- * the random number generator's internal state.
- *
- * When random bytes are desired, they are obtained by taking the SHA
- * hash of the contents of the "entropy pool".  The SHA hash avoids
- * exposing the internal state of the entropy 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
+
+ * Sources of true randomness from the environment include
+ * inter-keyboard timings, inter-interrupt timings from some
+ * interrupts, and other events which are both (a) non-deterministic
+ * and (b) hard for an outside observer to measure.
+
+ * Operation of this device is centered on four "pools".  The four
+ * pools are similar in structure but serve different purposes.
+
+ * Here is a block diagram:
+ *
+ *  fast data --> fast pool --\                 /--> blocking pool
+ *                             --> input pool --
+ *  slower, larger data ------/                 \--> nonblocking pool
+
+ * 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
+ * doing it on every interrupt is very reasonable.  It is similar in
+ * structure to the input pool, but much smaller.  After accumulating
+ * 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
+ * it is adequate assuming the randomness is not chosen maliciously.
+ * As random bytes are mixed into this pool, the routines keep an
+ * *estimate* of how many bits of entropy are contained in the pool.
+
+ * When random bytes are desired, they can be extracted from the input
+ * pool by taking the SHA 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 of data
- * returned from the generator is less than the inherent entropy in
- * the pool, the output data is totally unpredictable.  For this
+ * 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" are contained in the entropy pool as it
- * outputs random numbers.
- *
- * If this estimate goes to zero, the routine can still generate
- * random numbers; however, an attacker may (at least in theory) be
- * able to infer the future output of the generator from prior
- * outputs.  This requires successful cryptanalysis of SHA, which is
- * not believed to be feasible, but there is a remote possibility.
- * Nonetheless, these numbers should be useful for the vast majority
- * of purposes.
- *
+ * 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
+ * possibility.  Nonetheless, a pseudorandom distribution of numbers
+ * should be useful for a wide range of purposes.
+
  * Exported interfaces ---- output
  * ===============================
  *
@@ -105,20 +138,20 @@
  *
  * This interface will return the requested number of random bytes,
  * and place it in the requested buffer.
- *
+
  * The two other interfaces are two character devices /dev/random and
  * /dev/urandom.  /dev/random is suitable for use when very high
  * quality randomness is desired (for example, for key generation or
  * one-time pads), as it will only return a maximum of the number of
- * bits of randomness (as estimated by the random number generator)
- * contained in the entropy pool.
- *
- * 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.
- *
+ * bits of randomness on hand (as estimated by the random number
+ * generator).
+
+ * The /dev/urandom device will never block, and will return as many
+ * bytes as are requested.  It is a PRNG.  It is reseeded from time to
+ * time.  The resulting distribution of numbers is cryptographically
+ * strong, but not in principle unbreakable.  For many applications,
+ * however, this is acceptable.
+
  * Exported interfaces ---- input
  * ==============================
  *
@@ -143,69 +176,89 @@
  * the event type information from the hardware.
  *
  * add_interrupt_randomness() uses the interrupt timing as random
- * inputs to the entropy pool. Using the cycle counters and the irq source
+ * inputs to the fast pool. Using the cycle counters and the irq source
  * as inputs, it feeds the randomness roughly once a second.
  *
  * add_disk_randomness() uses what amounts to the seek time of block
  * layer request events, on a per-disk_devt basis, as input to the
- * entropy pool. Note that high-speed solid state drives with very low
+ * fast pool. Note that high-speed solid state drives with very low
  * seek times do not make for good sources of entropy, as their seek
  * times are usually fairly consistent.
  *
  * 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.
- *
+
+ * Exported interfaces ---- sysctl
+ * ===============================
+
+ * /proc/sys/kernel/random/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 smaller than the input pool.
+
+ * /proc/sys/kernel/random/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.
+
  * Ensuring unpredictability at system startup
  * ============================================
  *
  * When any operating system starts up, it will go through a sequence
  * of actions that are fairly predictable by an adversary, especially
  * if the start-up does not involve interaction with a human operator.
- * This reduces the actual number of bits of unpredictability in the
- * entropy pool below the value in entropy_count.  In order to
- * counteract this effect, it helps to carry information in the
- * entropy pool across shut-downs and start-ups.  To do this, put the
- * following lines an appropriate script which is run during the boot
- * sequence:
- *
+ * There is likely to be virtually zero real entropy available.
+
+ * However, we still need the /dev/urandom and get_random_bytes()
+ * interfaces to be usable at startup, and to have some semblance of
+ * security.  Therefore, it helps to store a seed that can be used to
+ * re-seed the PRNG, and to carry this seed across shut-downs and
+ * start-ups.  To do this, put the following lines an appropriate
+ * script which is run during the boot sequence:
+
  *	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 entropy pool
+ *	# Load and then save the whole nonblocking pool
  *	if [ -f $random_seed ]; then
  *		cat $random_seed >/dev/urandom
  *	else
  *		touch $random_seed
  *	fi
  *	chmod 600 $random_seed
- *	dd if=/dev/urandom of=$random_seed count=1 bs=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=128
  *
  * 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 entropy pool
+ *	# Save the whole nonblocking pool
  *	echo "Saving random seed..."
  *	random_seed=/var/run/random-seed
  *	touch $random_seed
  *	chmod 600 $random_seed
- *	dd if=/dev/urandom of=$random_seed count=1 bs=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=128
  *
  * For example, on most modern systems using the System V init
  * 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 entropy pool
- * to be saved at shut-down time and reloaded into the entropy pool at
- * start-up.  (The 'dd' in the addition to the bootup script is to
- * make sure that /etc/random-seed is 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 entropy pool requires knowledge of the previous history of
- * the system.
- *
+
+ * 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
+ * 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).
+
+ * Writing to /dev/random is identical to writing to /dev/urandom.
+
  * Configuring the /dev/random driver under Linux
  * ==============================================
  *
@@ -441,18 +494,18 @@ module_param(debug, bool, 0644);
 
 /**********************************************************************
  *
- * OS independent entropy store.   Here are the functions which handle
- * storing entropy in an entropy pool.
+ * OS independent pool.   Here are the functions which handle
+ * entropy storage, mixing, concentration, and PRNG counter mode.
  *
  **********************************************************************/
 
-struct entropy_store;
-struct entropy_store {
+struct Pool;
+struct Pool {
 	/* read-only data: */
 	struct poolinfo *poolinfo;
-	__u32 *pool;
+	__u32 *pooldata;
 	const char *name;
-	struct entropy_store *pull;
+	struct Pool *pull;
 	int limit;
 
 	/* read-write data: */
@@ -472,29 +525,29 @@ static __u32 input_pool_data[INPUT_POOL_WORDS];
 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
 
-static struct entropy_store input_pool = {
+static struct Pool input_pool = {
 	.poolinfo = &poolinfo_table[0],
 	.name = "input",
 	.limit = 1,
 	.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
-	.pool = input_pool_data
+	.pooldata = input_pool_data
 };
 
-static struct entropy_store blocking_pool = {
+static struct Pool blocking_pool = {
 	.poolinfo = &poolinfo_table[1],
 	.name = "blocking",
 	.limit = 1,
 	.pull = &input_pool,
 	.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
-	.pool = blocking_pool_data
+	.pooldata = blocking_pool_data
 };
 
-static struct entropy_store nonblocking_pool = {
+static struct Pool nonblocking_pool = {
 	.poolinfo = &poolinfo_table[1],
 	.name = "nonblocking",
 	.pull = &input_pool,
 	.lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock),
-	.pool = nonblocking_pool_data
+	.pooldata = nonblocking_pool_data
 };
 
 static __u32 const twist_table[8] = {
@@ -511,7 +564,7 @@ static __u32 const twist_table[8] = {
  * it's cheap to do so and helps slightly in the expected case where
  * the entropy is concentrated in the low-order bits.
  */
-static void _mix_pool_bytes(struct entropy_store *r, const void *in,
+static void _mix_pool_bytes(struct Pool *r, const void *in,
 			    int nbytes, __u8 out[64])
 {
 	unsigned long i, j, tap1, tap2, tap3, tap4, tap5;
@@ -536,15 +589,15 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
 		i = (i - 1) & wordmask;
 
 		/* XOR in the various taps */
-		w ^= r->pool[i];
-		w ^= r->pool[(i + tap1) & wordmask];
-		w ^= r->pool[(i + tap2) & wordmask];
-		w ^= r->pool[(i + tap3) & wordmask];
-		w ^= r->pool[(i + tap4) & wordmask];
-		w ^= r->pool[(i + tap5) & wordmask];
+		w ^= r->pooldata[i];
+		w ^= r->pooldata[(i + tap1) & wordmask];
+		w ^= r->pooldata[(i + tap2) & wordmask];
+		w ^= r->pooldata[(i + tap3) & wordmask];
+		w ^= r->pooldata[(i + tap4) & wordmask];
+		w ^= r->pooldata[(i + tap5) & wordmask];
 
 		/* Mix the result back in with a twist */
-		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
+		r->pooldata[i] = (w >> 3) ^ twist_table[w & 7];
 
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
@@ -561,17 +614,17 @@ static void _mix_pool_bytes(struct entropy_store *r, const void *in,
 
 	if (out)
 		for (j = 0; j < 16; j++)
-			((__u32 *)out)[j] = r->pool[(i - j) & wordmask];
+			((__u32 *)out)[j] = r->pooldata[(i - j) & wordmask];
 }
 
-static void __mix_pool_bytes(struct entropy_store *r, const void *in,
+static void __mix_pool_bytes(struct Pool *r, const void *in,
 			     int nbytes, __u8 out[64])
 {
 	trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_);
 	_mix_pool_bytes(r, in, nbytes, out);
 }
 
-static void mix_pool_bytes(struct entropy_store *r, const void *in,
+static void mix_pool_bytes(struct Pool *r, const void *in,
 			   int nbytes, __u8 out[64])
 {
 	unsigned long flags;
@@ -583,7 +636,7 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
 }
 
 struct fast_pool {
-	__u32		pool[4];
+	__u32		pooldata[4];
 	unsigned long	last;
 	unsigned short	count;
 	unsigned char	rotate;
@@ -603,9 +656,9 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
 	unsigned	input_rotate = f->rotate;
 
 	while (nbytes--) {
-		w = rol32(*bytes++, input_rotate & 31) ^ f->pool[i & 3] ^
-			f->pool[(i + 1) & 3];
-		f->pool[i & 3] = (w >> 3) ^ twist_table[w & 7];
+		w = rol32(*bytes++, input_rotate & 31) ^ f->pooldata[i & 3] ^
+			f->pooldata[(i + 1) & 3];
+		f->pooldata[i & 3] = (w >> 3) ^ twist_table[w & 7];
 		input_rotate += (i++ & 3) ? 7 : 14;
 	}
 	f->count = i;
@@ -619,7 +672,7 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
  * Negative n values are allowed, but the resulting behavior
  * might not be what you wanted.
  */
-static void credit_entropy_bits(struct entropy_store *r, int nbits)
+static void credit_entropy_bits(struct Pool *r, int nbits)
 {
 	int entropy_count, orig;
 
@@ -778,7 +831,7 @@ static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
 
 void add_interrupt_randomness(int irq, int irq_flags)
 {
-	struct entropy_store	*r;
+	struct Pool	*r;
 	struct fast_pool	*fast_pool = &__get_cpu_var(irq_randomness);
 	struct pt_regs		*regs = get_irq_regs();
 	unsigned long		now = jiffies;
@@ -801,7 +854,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	fast_pool->last = now;
 
 	r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
-	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool), NULL);
+	__mix_pool_bytes(r, &fast_pool->pooldata, sizeof(fast_pool->pooldata), NULL);
 	/*
 	 * If we don't have a valid cycle counter, and we see
 	 * back-to-back timer interrupts, then skip giving credit for
@@ -847,7 +900,7 @@ void add_disk_randomness(struct gendisk *disk)
  * ********************************************************************/
 
 /* Forward reference */
-static ssize_t extract_rnd(struct entropy_store *r, void *buf,
+static ssize_t extract_rnd(struct Pool *r, void *buf,
 			       size_t nbytes, int min, int rsvd);
 
 /*
@@ -867,7 +920,7 @@ static ssize_t extract_rnd(struct entropy_store *r, void *buf,
  * Mild fixme:  Handling of this case needs more thought.
  */
 static void fill_pool(
-        struct entropy_store *r,
+        struct Pool *r,
         size_t want_level               /* measured in BYTES */
 ){
 	__u32 tmp[OUTPUT_POOL_WORDS];
@@ -954,7 +1007,7 @@ static void fill_pool(
  * Usually done right before an extract_buf().
  * The return value is the amount to extract.
  */
-static size_t debit(struct entropy_store *r, size_t nbytes, int min,
+static size_t debit(struct Pool *r, size_t nbytes, int min,
 		      int reserved)
 {
 	unsigned long flags;
@@ -1009,7 +1062,7 @@ retry:
  * Extract randomness from the specified pool (r) and return it in a buffer.
  * Probably should always be preceded by debit(...).
  */
-static void extract_buf(struct entropy_store *r, __u8 *out)
+static void extract_buf(struct Pool *r, __u8 *out)
 {
 	int i;
 	union {
@@ -1024,7 +1077,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 	sha_init(hash.w);
 	spin_lock_irqsave(&r->lock, flags);
 	for (i = 0; i < r->poolinfo->poolwords; i += 16)
-		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
+		sha_transform(hash.w, (__u8 *)(r->pooldata + i), workspace);
 
 	/*
 	 * We mix the hash back into the pool to prevent backtracking
@@ -1075,7 +1128,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
  *
  * We return the actual number of bytes extracted.
  */
-static ssize_t extract_rnd(struct entropy_store *r, void *buf,
+static ssize_t extract_rnd(struct Pool *r, void *buf,
 				 size_t txbytes, int min, int reserved)
 {
 	ssize_t ret = 0, i;
@@ -1139,7 +1192,7 @@ static ssize_t extract_rnd(struct entropy_store *r, void *buf,
 	return ret;
 }
 
-static ssize_t extract_rnd_user(struct entropy_store *r, void __user *buf,
+static ssize_t extract_rnd_user(struct Pool *r, void __user *buf,
 				    size_t nbytes)
 {
 	ssize_t ret = 0, i;
@@ -1237,7 +1290,7 @@ EXPORT_SYMBOL(get_random_bytes_arch);
  * data into the pool to prepare it for use. The pool is not cleared
  * as that can only decrease the entropy in the pool.
  */
-static void init_std_data(struct entropy_store *r)
+static void init_std_data(struct Pool *r)
 {
 	int i;
 	ktime_t now = ktime_get_real();
@@ -1381,7 +1434,7 @@ random_poll(struct file *file, poll_table * wait)
 }
 
 static int
-write_pool(struct entropy_store *r, const char __user *buffer, size_t count)
+write_pool(struct Pool *r, const char __user *buffer, size_t count)
 {
 	size_t bytes;
 	__u32 buf[16];
@@ -1409,10 +1462,10 @@ static ssize_t random_write(struct file *file, const char __user *buffer,
 
 	ret = write_pool(&blocking_pool, buffer, count);
 	if (ret)
-		return ret;
+		return ret;     /* some error */
 	ret = write_pool(&nonblocking_pool, buffer, count);
 	if (ret)
-		return ret;
+		return ret;     /* some error */
 
 	return (ssize_t)count;
 }
@@ -1455,7 +1508,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 		return 0;
 	case RNDZAPENTCNT:
 	case RNDCLEARPOOL:
-		/* Clear the entropy pool counters. */
+		/* Clear the entropy estimates. */
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
 		rand_initialize();
@@ -1694,9 +1747,12 @@ late_initcall(random_int_secret_init);
 
 /*
  * Get a random word for internal kernel use only. Similar to urandom but
- * with the goal of minimal entropy pool depletion. As a result, the random
+ * with the goal of minimal consumption of entropy.  As a result, the random
  * value is not cryptographically secure but for several uses the cost of
- * depleting entropy is too high
+ * depleting entropy is too high.
+ *
+ * Presumably no longer needed, now that /dev/urandom
+ * no longer consumes entropy so rapaciously.
  */
 static DEFINE_PER_CPU(__u32 [MD5_DIGEST_WORDS], get_random_int_hash);
 unsigned int get_random_int(void)