summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--drivers/char/random.c274
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)