summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohn Denker <jsd@av8n.com>2013-10-18 12:13:46 (GMT)
committerJohn Denker <jsd@av8n.com>2013-10-18 12:33:22 (GMT)
commit49af75a02eb35c6842e60625a25d92c34d4b4c75 (patch)
tree32928b0a43539d4f9725e9ba77af96a3d1f321a2
parent2519091f9983706958b56a46f3bcf97f36a01c98 (diff)
parameterize design of adaptive refill;
clean up comments
-rw-r--r--drivers/char/random.c226
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));