diff options
Diffstat (limited to 'drivers')
| -rw-r--r-- | drivers/char/random.c | 284 |
1 files changed, 152 insertions, 132 deletions
diff --git a/drivers/char/random.c b/drivers/char/random.c index 13d5164..4a2487c 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -41,46 +41,46 @@ /* * (now, with legal B.S. out of the way.....) - * + * This routine gathers environmental noise from device drivers, etc., - * and returns good random numbers, suitable for cryptographic use. - * Besides the obvious cryptographic uses, these numbers are also good - * for seeding TCP sequence numbers, and other places where it is - * desirable to have numbers which are not only random, but hard to - * predict by an attacker. - * + * and returns good randomly distributed numbers, suitable for + * cryptographic use. Besides the obvious cryptographic uses, these + * numbers are also good for seeding TCP sequence numbers, and other + * places where it is desirable to have numbers which are not only + * random, but hard to predict by an attacker. + * Theory of operation * =================== - * + * Computers are very predictable devices. Hence it is extremely hard - * to produce truly random numbers on a computer --- as opposed to - * pseudo-random numbers, which can easily generated by using a - * algorithm. Unfortunately, it is very easy for attackers to guess - * the sequence of pseudo-random number generators, and for some - * applications this is not acceptable. So instead, we must try to - * gather "environmental noise" from the computer's environment, which - * 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 true randomness from the environment include + * to implement a truly random distribution on a computer --- as + * opposed to a pseudo-random distribution, which can easily + * implemented by an algorithm. Unfortunately, it is sometimes + * possible for attackers to guess the output sequence of + * pseudo-random generators, and for some applications this is not + * acceptable. So instead, we must try to gather "noise" from the + * computer's environment, i.e. signals that contain an element of + * actual entropy, and that are hard for outside attackers to observe, + * and use that to generate randomly-distributed numbers. + + * Environmental sources that are available to the kernel 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. + * interrupts, and similar events. Again, these must be 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 + * fast events --> fast pool --\ /--> blocking pool + * --> input pool -- + * slower, larger events ------/ \--> 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 + * doing it on every interrupt is affordable. 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. @@ -90,21 +90,21 @@ * 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 - * 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. + * 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. + * 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 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 @@ -136,8 +136,8 @@ * * void get_random_bytes(void *buf, int nbytes); * - * This interface will return the requested number of random bytes, - * and place it in the requested buffer. + * This interface will return the requested number of bytes, and place + * it them 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 @@ -216,6 +216,11 @@ * 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. + * echo "Initializing random number generator..." * random_seed=/var/run/random-seed * # Carry a random seed from start-up to start-up @@ -226,7 +231,7 @@ * touch $random_seed * fi * chmod 600 $random_seed - * dd if=/dev/urandom of=$random_seed count=1 bs=128 + * 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: @@ -237,8 +242,8 @@ * random_seed=/var/run/random-seed * touch $random_seed * chmod 600 $random_seed - * dd if=/dev/urandom of=$random_seed count=1 bs=128 - * + * dd if=/dev/urandom of=$random_seed count=1 bs=512 + * 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 @@ -325,7 +330,8 @@ #include <trace/events/random.h> /* - * Configuration information + * Configuration information. + * Here, a "word" is of type __u32 */ #define INPUT_POOL_WORDS 128 #define OUTPUT_POOL_WORDS 32 @@ -334,20 +340,16 @@ /* Choose 160 bits. Seems reasonable. Recommended in the Yarrow paper. */ #define RESEED_BATCH 160 /* bits */ - -/* - * The nonblocking output pool will not drag the input pool below this - * fill fraction: - */ -#define FILL_FRAC(X) ((X)*3/4) +/* Saturation point of extraction subttl counters; large round number: */ +#define SUBTTL_SAT 1000000000000000000LL typedef unsigned long long int ulonglong; #if defined __SIZEOF_LONG_LONG__ && __SIZEOF_LONG_LONG__ == 8 -/* This is how it should be using gcc - * on Intel x86_32 and also Intel 64 architectures. +/* This is how we expect things to be when using gcc + * on both Intel x86_32 and Intel 64 architectures. * I don't know how to extrapolate to other architectures * or other compilers ... - * but at least we are being properly defensive. + * but at least we are being clear about the assumptions being made. */ #else #error Broken assumption: __SIZEOF_LONG_LONG__ should be defined and equal to 8 @@ -446,28 +448,29 @@ static struct poolinfo { * in fact it almost certainly isn't. Nonetheless, the irreducible factors * of a random large-degree polynomial over GF(2) are more than large enough * that periodicity is not a concern. - * + * The input hash is much less sensitive than the output hash. All - * that we want of it is that it be a good non-cryptographic hash; - * i.e. it not produce collisions when fed "random" data of the sort - * we expect to see. As long as the pool state differs for different - * inputs, we have preserved the input entropy and done a good job. - * The fact that an intelligent attacker can construct inputs that - * will produce controlled alterations to the pool's state is not - * important because we don't consider such inputs to contribute any - * randomness. The only property we need with respect to them is that - * the attacker can't increase his/her knowledge of the pool's state. - * Since all additions are reversible (knowing the final state and the - * input, you can reconstruct the initial state), if an attacker has - * any uncertainty about the initial state, he/she can only shuffle - * that uncertainty about, but never cause any collisions (which would + * that we want of it is that it be a good hash in the sense that it + * not produce collisions when fed "random" data of the sort we expect + * to see. It need not be a cryptographically-strong hash. As long + * as the pool state differs for different inputs, we have preserved + * the input entropy and done a good job. The fact that an + * intelligent attacker can construct inputs that will produce + * controlled alterations to the pool's state is not important because + * we don't consider such inputs to contribute any randomness. The + * only property we need with respect to them is that the attacker + * can't increase his/her knowledge of the pool's state. Since all + * additions are reversible (knowing the final state and the input, + * you can reconstruct the initial state), if an attacker has any + * uncertainty about the initial state, he/she can only shuffle that + * uncertainty about, but never cause any collisions (which would * decrease the uncertainty). - * + * The chosen system lets the state of the pool be (essentially) the input * modulo the generator polymnomial. Now, for random primitive polynomials, * this is a universal class of hash functions, meaning that the chance * of a collision is limited by the attacker's knowledge of the generator - * polynomail, so if it is chosen at random, an attacker can never force + * polynomial, so if it is chosen at random, an attacker can never force * a collision. Here, we use a fixed polynomial, but we *can* assume that * ###--> it is unknown to the processes generating the input entropy. <-### * Because of this important property, this is a good, collision-resistant @@ -488,8 +491,8 @@ module_param(debug, bool, 0644); printk(KERN_DEBUG "random %04d %04d %04d: " \ fmt,\ input_pool.entropy_count,\ - blocking_pool.entropy_count,\ - nonblocking_pool.entropy_count,\ + devrand_pool.entropy_count,\ + prng_pool.entropy_count,\ ## arg); } while (0) /********************************************************************** @@ -506,7 +509,7 @@ struct Pool { __u32 *pooldata; const char *name; struct Pool *pull; - int limit; + int blockable; /* read-write data: */ spinlock_t lock; @@ -522,32 +525,38 @@ struct Pool { }; static __u32 input_pool_data[INPUT_POOL_WORDS]; -static __u32 blocking_pool_data[OUTPUT_POOL_WORDS]; -static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS]; +#ifdef OVERCOMPLICATED +static __u32 devrand_pool_data[OUTPUT_POOL_WORDS]; +#endif +static __u32 prng_pool_data[OUTPUT_POOL_WORDS]; static struct Pool input_pool = { .poolinfo = &poolinfo_table[0], .name = "input", - .limit = 1, + .blockable = 1, .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), .pooldata = input_pool_data }; -static struct Pool blocking_pool = { +#ifdef OVERCOMPLICATED +static struct Pool devrand_pool = { .poolinfo = &poolinfo_table[1], .name = "blocking", - .limit = 1, + .blockable = 1, .pull = &input_pool, - .lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock), - .pooldata = blocking_pool_data + .lock = __SPIN_LOCK_UNLOCKED(devrand_pool.lock), + .pooldata = devrand_pool_data }; +#else +#define devrand_pool input_pool +#endif -static struct Pool nonblocking_pool = { +static struct Pool prng_pool = { .poolinfo = &poolinfo_table[1], .name = "nonblocking", .pull = &input_pool, - .lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock), - .pooldata = nonblocking_pool_data + .lock = __SPIN_LOCK_UNLOCKED(prng_pool.lock), + .pooldata = prng_pool_data }; static __u32 const twist_table[8] = { @@ -666,7 +675,7 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes) } /* - * Credit the entropy store with n bits of entropy. + * Credit the pool with n bits of entropy. * Normally n is positive. * Sufficiently large n will wake up a blocked reader. * Negative n values are allowed, but the resulting behavior @@ -735,15 +744,15 @@ void add_device_randomness(const void *buf, unsigned int size) mix_pool_bytes(&input_pool, buf, size, NULL); mix_pool_bytes(&input_pool, &time, sizeof(time), NULL); - mix_pool_bytes(&nonblocking_pool, buf, size, NULL); - mix_pool_bytes(&nonblocking_pool, &time, sizeof(time), NULL); + mix_pool_bytes(&prng_pool, buf, size, NULL); + mix_pool_bytes(&prng_pool, &time, sizeof(time), NULL); } EXPORT_SYMBOL(add_device_randomness); static struct timer_rand_state input_timer_state; /* - * This function adds entropy to the entropy "pool" by using timing + * This function adds entropy to the input 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. * @@ -853,7 +862,7 @@ void add_interrupt_randomness(int irq, int irq_flags) fast_pool->last = now; - r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool; + r = prng_pool.initialized ? &input_pool : &prng_pool; __mix_pool_bytes(r, &fast_pool->pooldata, sizeof(fast_pool->pooldata), NULL); /* * If we don't have a valid cycle counter, and we see @@ -887,16 +896,17 @@ void add_disk_randomness(struct gendisk *disk) /********************************************************************* * * Extraction routines. - * - * These routines extract bytes that are "random" in some unspecified - * sense, but may _or may not_ contain any appreciable amount of - * entropy. Therefore, please do not call them "entropy" extraction - * routines. - * + + * These routines extract bytes from the pools. The extracted bytes + * exhibit a random distribution, possibly "random" in the sense of + * pseudorandom, or possibly "random" in the sense of actual entropy. + * 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, * the extracted bytes may have an entropy density that is vastly less * than 8 bits per byte, orders of magnitude less. - * + * ********************************************************************/ /* Forward reference */ @@ -930,8 +940,8 @@ static void fill_pool( 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->limit) { -/* Here if we are limited i.e. blocking i.e. /dev/random i.e. TRNG. */ + if (r->blockable) { +/* 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; @@ -944,7 +954,7 @@ static void fill_pool( mybatch = rsvd = 0; } else { /* - * Here if we are non-limited i.e. non-blocking i.e. urandom i.e. PRNG. + * 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. * @@ -961,7 +971,10 @@ static void fill_pool( /* When the appetite gets to 20, rsvd goes to zero: */ rsvd = rsvd - appetite*rsvd/20; if (rsvd < 0) rsvd = 0; -/* For the PRNG, make the request big enough to be "significant" to any attacker: */ +/* + * For the PRNG, make the request big enough to be + * "significant" to any attacker: + */ mybatch = txbits = RESEED_BATCH; } @@ -1027,8 +1040,8 @@ static size_t debit(struct Pool *r, size_t nbytes, int min, int entropy_count, orig; retry: entropy_count = orig = ACCESS_ONCE(r->entropy_count); - /* If limited, never pull more than available */ - if (r->limit && nbytes + reserved >= entropy_count / 8) + /* If blockable, never pull more than available */ + if (r->blockable && nbytes + reserved >= entropy_count / 8) nbytes = entropy_count/8 - reserved; if (entropy_count / 8 >= nbytes + reserved) { @@ -1046,7 +1059,7 @@ retry: } DEBUG_ENT("debiting %zu entropy credits from %s%s\n", - nbytes * 8, r->name, r->limit ? "" : " (unlimited)"); + nbytes * 8, r->name, r->blockable ? "" : " (nonblocking)"); spin_unlock_irqrestore(&r->lock, flags); @@ -1144,6 +1157,8 @@ static ssize_t extract_rnd(struct Pool *r, void *buf, trace_extract_rnd(r->name, EXTRACT_SIZE, r->entropy_count, _RET_IP_); fill_pool(r, EXTRACT_SIZE); +/* FIXME: */ +/* why is there no debit() associated with this extract_buf()? */ extract_buf(r, tmp); spin_lock_irqsave(&r->lock, flags); memcpy(r->last_data, tmp, EXTRACT_SIZE); @@ -1185,7 +1200,8 @@ static ssize_t extract_rnd(struct Pool *r, void *buf, if (ret > 0) { /* Subttl does not overflow; it saturates at a user-friendly round number: */ r->extracted_subttl += BYTE2BIT(ret); - if (r->extracted_subttl > 1000000000000000000LL) r->extracted_subttl = 1000000000000000000LL; + if (r->extracted_subttl > SUBTTL_SAT) + r->extracted_subttl = SUBTTL_SAT; /* Total does not saturate; it just overflows and wraps around. */ r->extracted_total += BYTE2BIT(ret); } @@ -1238,13 +1254,14 @@ static ssize_t extract_rnd_user(struct Pool *r, void __user *buf, /* * This function is the exported kernel interface. It returns some - * number of good random numbers, suitable for key generation, seeding - * TCP sequence numbers, etc. It does not use the hw random number - * generator, if available; use get_random_bytes_arch() for that. + * number of good pseudorandomly distributed numbers, suitable for key + * generation, seeding TCP sequence numbers, etc. It does not use the + * hw random number generator, if available; use + * get_random_bytes_arch() for that. */ void get_random_bytes(void *buf, int nbytes) { - extract_rnd(&nonblocking_pool, buf, nbytes, 0, 0); + extract_rnd(&prng_pool, buf, nbytes, 0, 0); } EXPORT_SYMBOL(get_random_bytes); @@ -1276,7 +1293,7 @@ void get_random_bytes_arch(void *buf, int nbytes) } if (nbytes) - extract_rnd(&nonblocking_pool, p, nbytes, 0, 0); + extract_rnd(&prng_pool, p, nbytes, 0, 0); } EXPORT_SYMBOL(get_random_bytes_arch); @@ -1323,8 +1340,8 @@ static void init_std_data(struct Pool *r) static int rand_initialize(void) { init_std_data(&input_pool); - init_std_data(&blocking_pool); - init_std_data(&nonblocking_pool); + init_std_data(&devrand_pool); + init_std_data(&prng_pool); return 0; } module_init(rand_initialize); @@ -1359,7 +1376,7 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) * Kludge: zero-byte read: Fill the pool from upstream sources. */ if (nbytes == 0){ - fill_pool(&blocking_pool, 0); + fill_pool(&devrand_pool, 0); return 0; } @@ -1370,7 +1387,7 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) DEBUG_ENT("reading %zu bits\n", n*8); - n = extract_rnd_user(&blocking_pool, buf, n); + n = extract_rnd_user(&devrand_pool, buf, n); if (n < 0) { retval = n; @@ -1415,7 +1432,7 @@ random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) static ssize_t urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { - return extract_rnd_user(&nonblocking_pool, buf, nbytes); + return extract_rnd_user(&prng_pool, buf, nbytes); } static unsigned int @@ -1460,10 +1477,10 @@ static ssize_t random_write(struct file *file, const char __user *buffer, { size_t ret; - ret = write_pool(&blocking_pool, buffer, count); + ret = write_pool(&devrand_pool, buffer, count); if (ret) return ret; /* some error */ - ret = write_pool(&nonblocking_pool, buffer, count); + ret = write_pool(&prng_pool, buffer, count); if (ret) return ret; /* some error */ @@ -1480,8 +1497,8 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) case RNDGETENTCNT: /* inherently racy, no point locking */ if (put_user(input_pool.entropy_count - + blocking_pool.entropy_count - + nonblocking_pool.entropy_count, p)) + + devrand_pool.entropy_count + + prng_pool.entropy_count, p)) return -EFAULT; return 0; case RNDADDTOENTCNT: @@ -1548,7 +1565,7 @@ const struct file_operations urandom_fops = { ***************************************************************/ /* - * Generate random UUID + * Generate randomly-distributed UUID */ void generate_random_uuid(unsigned char uuid_out[16]) { @@ -1616,8 +1633,10 @@ static int total_entropy_count; static int sum_entropy_count(struct ctl_table *table, int write, void __user *buffer, size_t *lenp, loff_t *ppos){ total_entropy_count = input_pool.entropy_count - + blocking_pool.entropy_count - + nonblocking_pool.entropy_count; +#ifdef OVERCOMPLICATED + + devrand_pool.entropy_count +#endif + + prng_pool.entropy_count; return proc_dointvec(table, write, buffer, lenp, ppos); } @@ -1650,14 +1669,14 @@ struct ctl_table random_table[] = { .maxlen = sizeof(int), .mode = 0444, .proc_handler = proc_dointvec, - .data = &blocking_pool.entropy_count, + .data = &devrand_pool.entropy_count, }, { .procname = "entropy_avail_ur", .maxlen = sizeof(int), .mode = 0444, .proc_handler = proc_dointvec, - .data = &nonblocking_pool.entropy_count, + .data = &prng_pool.entropy_count, }, { .procname = "extracted_total_inp", @@ -1671,14 +1690,14 @@ struct ctl_table random_table[] = { .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, - .data = &blocking_pool.extracted_total, + .data = &devrand_pool.extracted_total, }, { .procname = "extracted_total_ur", .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, - .data = &nonblocking_pool.extracted_total, + .data = &prng_pool.extracted_total, }, { .procname = "extracted_subttl_inp", @@ -1692,14 +1711,14 @@ struct ctl_table random_table[] = { .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, - .data = &blocking_pool.extracted_subttl, + .data = &devrand_pool.extracted_subttl, }, { .procname = "extracted_subttl_ur", .maxlen = sizeof(ulonglong), .mode = 0644, .proc_handler = proc_doulonglongvec_minmax, - .data = &nonblocking_pool.extracted_subttl, + .data = &prng_pool.extracted_subttl, }, { .procname = "read_wakeup_threshold", @@ -1746,11 +1765,12 @@ static int __init random_int_secret_init(void) late_initcall(random_int_secret_init); /* - * Get a random word for internal kernel use only. Similar to urandom but - * 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. - * + * Get a word from a random distribution, for internal kernel use + * only. Similar to urandom but with the goal of minimal consumption + * of entropy. As a result, the random distribution is not + * cryptographically secure but for several uses the cost of depleting + * entropy is too high. + * Presumably no longer needed, now that /dev/urandom * no longer consumes entropy so rapaciously. */ |