diff options
| -rw-r--r-- | drivers/char/random.c | 226 |
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)); |