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