Enclosed please find updates to the /dev/random driver versus Linux
2.3.15. It significantly improves the security of the /dev/urandom
driver, and allows for dynamic resizing of the /dev/random entropy pool
via the sysctl interface.
I've also included a random UUID generator, which may come in handy for
device driver authors. The random UUID generator is also used to
generate a unique boot_id, as requested by a GNU emacs developer who
wanted it for portable locking; this way if the boot_id is different,
the lock is known to be stale. I imagine this may be useful for a
number of other application developers.
I'd appreciate it if you would merge this into the 2.3 kernel tree.
Thanks!!
- Ted
Patch generated: on Tue Aug 31 15:21:42 EDT 1999 by tytso@snap.thunk.org
against Linux version 2.3.15
===================================================================
RCS file: include/linux/RCS/random.h,v
retrieving revision 1.1
diff -u -r1.1 include/linux/random.h
--- include/linux/random.h 1999/08/30 03:55:56 1.1
+++ include/linux/random.h 1999/08/30 04:09:39
@@ -52,6 +52,7 @@
extern void add_blkdev_randomness(int major);
extern void get_random_bytes(void *buf, int nbytes);
+void generate_random_uuid(unsigned char uuid_out[16]);
extern __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
__u16 sport, __u16 dport);
===================================================================
RCS file: include/linux/RCS/sysctl.h,v
retrieving revision 1.1
diff -u -r1.1 include/linux/sysctl.h
--- include/linux/sysctl.h 1999/08/29 23:07:52 1.1
+++ include/linux/sysctl.h 1999/08/30 03:31:36
@@ -100,9 +100,10 @@
KERN_SHMMAX=34, /* int: Maximum shared memory segment */
KERN_MSGMAX=35, /* int: Maximum size of a messege */
KERN_MSGMNB=36, /* int: Maximum message queue size */
- KERN_MSGPOOL=37, /* int: Maximum system message pool size */
+ KERN_MSGPOOL=37, /* int: Maximum system message pool size */
KERN_SYSRQ=38, /* int: Sysreq enable */
- KERN_MAX_THREADS=39 /* int: Maximum nr of threads in the system */
+ KERN_MAX_THREADS=39, /* int: Maximum nr of threads in the system */
+ KERN_RANDOM=40 /* Random driver */
};
@@ -142,6 +143,17 @@
NET_DECNET=15,
NET_ECONET=16,
NET_KHTTPD=17
+};
+
+/* /proc/sys/kernel/random */
+enum
+{
+ RANDOM_POOLSIZE=1,
+ RANDOM_ENTROPY_COUNT=2,
+ RANDOM_READ_THRESH=3,
+ RANDOM_WRITE_THRESH=4,
+ RANDOM_BOOT_ID=5,
+ RANDOM_UUID=6
};
/* /proc/sys/bus/isa */
===================================================================
RCS file: kernel/RCS/sysctl.c,v
retrieving revision 1.1
diff -u -r1.1 kernel/sysctl.c
--- kernel/sysctl.c 1999/08/29 23:07:52 1.1
+++ kernel/sysctl.c 1999/08/29 23:07:56
@@ -86,6 +86,7 @@
static ctl_table fs_table[];
static ctl_table debug_table[];
static ctl_table dev_table[];
+extern ctl_table random_table[];
/* /proc declarations: */
@@ -221,6 +222,7 @@
#endif
{KERN_MAX_THREADS, "threads-max", &max_threads, sizeof(int),
0644, NULL, &proc_dointvec},
+ {KERN_RANDOM, "random", NULL, 0, 0555, random_table},
{0}
};
===================================================================
RCS file: drivers/char/RCS/random.c,v
retrieving revision 1.1
diff -u -r1.1 drivers/char/random.c
--- drivers/char/random.c 1999/08/29 23:07:52 1.1
+++ drivers/char/random.c 1999/08/31 19:07:05
@@ -1,10 +1,10 @@
/*
* random.c -- A strong random number generator
*
- * Version 1.04, last modified 26-Apr-98
+ * Version 1.88, last modified 30-Aug-99
*
- * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998. All rights
- * reserved.
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
+ * rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -27,15 +27,16 @@
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
- * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
- * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
- * OF THE POSSIBILITY OF SUCH DAMAGE.
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
*/
/*
@@ -223,8 +224,8 @@
* The code for SHA transform was taken from Peter Gutmann's
* implementation, which has been placed in the public domain.
* The code for MD5 transform was taken from Colin Plumb's
- * implementation, which has been placed in the public domain. The
- * MD5 cryptographic checksum was devised by Ronald Rivest, and is
+ * implementation, which has been placed in the public domain.
+ * The MD5 cryptographic checksum was devised by Ronald Rivest, and is
* documented in RFC 1321, "The MD5 Message Digest Algorithm".
*
* Further background information on this topic may be obtained from
@@ -232,11 +233,6 @@
* Eastlake, Steve Crocker, and Jeff Schiller.
*/
-/*
- * Added a check for signal pending in the extract_entropy() loop to allow
- * the read(2) syscall to be interrupted. Copyright (C) 1998 Andrea Arcangeli
- */
-
#include <linux/utsname.h>
#include <linux/config.h>
#include <linux/kernel.h>
@@ -256,72 +252,77 @@
/*
* Configuration information
*/
-#undef RANDOM_BENCHMARK
-#undef BENCHMARK_NOINT
-#define ROTATE_PARANOIA
-
-#define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
-#define POOLBITS (POOLWORDS*32)
-/*
- * The pool is stirred with a primitive polynomial of degree POOLWORDS
- * over GF(2). The taps for various sizes are defined below. They are
- * chosen to be evenly spaced (minimum RMS distance from evenly spaced;
- * the numbers in the comments are a scaled squared error sum) except
- * for the last tap, which is 1 to get the twisting happening as fast
- * as possible.
- */
-#if POOLWORDS == 2048 /* 115 x^2048+x^1638+x^1231+x^819+x^411+x^1+1 */
-#define TAP1 1638
-#define TAP2 1231
-#define TAP3 819
-#define TAP4 411
-#define TAP5 1
-#elif POOLWORDS == 1024 /* 290 x^1024+x^817+x^615+x^412+x^204+x^1+1 */
-/* Alt: 115 x^1024+x^819+x^616+x^410+x^207+x^2+1 */
-#define TAP1 817
-#define TAP2 615
-#define TAP3 412
-#define TAP4 204
-#define TAP5 1
-#elif POOLWORDS == 512 /* 225 x^512+x^411+x^308+x^208+x^104+x+1 */
-/* Alt: 95 x^512+x^409+x^307+x^206+x^102+x^2+1
- * 95 x^512+x^409+x^309+x^205+x^103+x^2+1 */
-#define TAP1 411
-#define TAP2 308
-#define TAP3 208
-#define TAP4 104
-#define TAP5 1
-#elif POOLWORDS == 256 /* 125 x^256+x^205+x^155+x^101+x^52+x+1 */
-#define TAP1 205
-#define TAP2 155
-#define TAP3 101
-#define TAP4 52
-#define TAP5 1
-#elif POOLWORDS == 128 /* 105 x^128+x^103+x^76+x^51+x^25+x+1 */
-/* Alt: 70 x^128+x^103+x^78+x^51+x^27+x^2+1 */
-#define TAP1 103
-#define TAP2 76
-#define TAP3 51
-#define TAP4 25
-#define TAP5 1
-#elif POOLWORDS == 64 /* 15 x^64+x^52+x^39+x^26+x^14+x+1 */
-#define TAP1 52
-#define TAP2 39
-#define TAP3 26
-#define TAP4 14
-#define TAP5 1
-#elif POOLWORDS == 32 /* 15 x^32+x^26+x^20+x^14+x^7+x^1+1 */
-#define TAP1 26
-#define TAP2 20
-#define TAP3 14
-#define TAP4 7
-#define TAP5 1
-#elif POOLWORDS & (POOLWORDS-1)
-#error POOLWORDS must be a power of 2
-#else
-#error No primitive polynomial available for chosen POOLWORDS
+#define DEFAULT_POOL_SIZE 512
+#define SECONDARY_POOL_SIZE 128
+#define BATCH_ENTROPY_SIZE 256
+#define USE_SHA
+
+/*
+ * The minimum number of bits of entropy before we wake up a read on
+ * /dev/random. Should always be at least 8, or at least 1 byte.
+ */
+static int random_read_wakeup_thresh = 8;
+
+/*
+ * If the entropy count falls under this number of bits, then we
+ * should wake up processes which are selecting or polling on write
+ * access to /dev/random.
+ */
+static int random_write_wakeup_thresh = 128;
+
+/*
+ * A pool of size POOLWORDS is stirred with a primitive polynomial
+ * of degree POOLWORDS over GF(2). The taps for various sizes are
+ * defined below. They are chosen to be evenly spaced (minimum RMS
+ * distance from evenly spaced; the numbers in the comments are a
+ * scaled squared error sum) except for the last tap, which is 1 to
+ * get the twisting happening as fast as possible.
+ */
+static struct poolinfo {
+ int poolwords;
+ int tap1, tap2, tap3, tap4, tap5;
+} poolinfo_table[] = {
+ /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */
+ { 2048, 1638, 1231, 819, 411, 1 },
+
+ /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
+ { 1024, 817, 615, 412, 204, 1 },
+
+#if 0 /* Alternate polynomial */
+ /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
+ { 1024, 819, 616, 410, 207, 2 },
+#endif
+
+ /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
+ { 512, 411, 308, 208, 104, 1 },
+
+#if 0 /* Alternates */
+ /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
+ { 512, 409, 307, 206, 102, 2 },
+ /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
+ { 512, 409, 309, 205, 103, 2 },
+#endif
+
+ /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
+ { 256, 205, 155, 101, 52, 1 },
+
+ /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
+ { 128, 103, 76, 51, 25, 1 },
+
+#if 0 /* Alternate polynomial */
+ /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
+ { 128, 103, 78, 51, 27, 2 },
#endif
+ /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
+ { 64, 52, 39, 26, 14, 1 },
+
+ /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
+ { 32, 26, 20, 14, 7, 1 },
+
+ { 0, 0, 0, 0, 0, 0 },
+};
+
/*
* For the purposes of better mixing, we use the CRC-32 polynomial as
* well to make a twisted Generalized Feedback Shift Reigster
@@ -332,25 +333,26 @@
* II. ACM Transactions on Mdeling and Computer Simulation 4:254-266)
*
* Thanks to Colin Plumb for suggesting this.
+ *
* We have not analyzed the resultant polynomial to prove it primitive;
* 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.
+ *
+ * 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
+ * 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
@@ -365,82 +367,36 @@
*/
/*
- * The minimum number of bits to release a "wait on input". Should
- * probably always be 8, since a /dev/random read can return a single
- * byte.
- */
-#define WAIT_INPUT_BITS 8
-/*
- * The limit number of bits under which to release a "wait on
- * output". Should probably always be the same as WAIT_INPUT_BITS, so
- * that an output wait releases when and only when a wait on input
- * would block.
- */
-#define WAIT_OUTPUT_BITS WAIT_INPUT_BITS
-
-/* There is actually only one of these, globally. */
-struct random_bucket {
- unsigned add_ptr;
- unsigned entropy_count;
-#ifdef ROTATE_PARANOIA
- int input_rotate;
+ * Linux 2.2 compatibility
+ */
+#ifndef DECLARE_WAITQUEUE
+#define DECLARE_WAITQUEUE(WAIT, PTR) struct wait_queue WAIT = { PTR, NULL }
#endif
- __u32 pool[POOLWORDS];
-};
-
-#ifdef RANDOM_BENCHMARK
-/* For benchmarking only */
-struct random_benchmark {
- unsigned long long start_time;
- int times; /* # of samples */
- unsigned long min;
- unsigned long max;
- unsigned long accum; /* accumulator for average */
- const char *descr;
- int unit;
- unsigned long flags;
-};
-
-#define BENCHMARK_INTERVAL 500
-
-static void initialize_benchmark(struct random_benchmark *bench,
- const char *descr, int unit);
-static void begin_benchmark(struct random_benchmark *bench);
-static void end_benchmark(struct random_benchmark *bench);
-
-struct random_benchmark timer_benchmark;
+#ifndef DECLARE_WAIT_QUEUE_HEAD
+#define DECLARE_WAIT_QUEUE_HEAD(WAIT) struct wait_queue *WAIT
#endif
-/* There is one of these per entropy source */
-struct timer_rand_state {
- __u32 last_time;
- __s32 last_delta,last_delta2;
- int dont_count_entropy:1;
-};
-
-static struct random_bucket random_state;
-static struct timer_rand_state keyboard_timer_state;
-static struct timer_rand_state mouse_timer_state;
-static struct timer_rand_state extract_timer_state;
-static struct timer_rand_state *irq_timer_state[NR_IRQS];
-static struct timer_rand_state *blkdev_timer_state[MAX_BLKDEV];
+/*
+ * Static global variables
+ */
+static struct entropy_store *random_state; /* The default global store */
+static struct entropy_store *sec_random_state; /* secondary store */
static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
-static ssize_t random_read(struct file * file, char * buf,
- size_t nbytes, loff_t *ppos);
-static ssize_t random_read_unlimited(struct file * file, char * buf,
- size_t nbytes, loff_t *ppos);
-static unsigned int random_poll(struct file *file, poll_table * wait);
-static ssize_t random_write(struct file * file, const char * buffer,
- size_t count, loff_t *ppos);
-static int random_ioctl(struct inode * inode, struct file * file,
- unsigned int cmd, unsigned long arg);
-
-static inline void fast_add_entropy_words(struct random_bucket *r,
- __u32 x, __u32 y);
+/*
+ * Forward procedure declarations
+ */
+#ifdef CONFIG_SYSCTL
+static void sysctl_init_random(struct entropy_store *random_state);
+#endif
-static void add_entropy_words(struct random_bucket *r, __u32 x, __u32 y);
+/*****************************************************************
+ *
+ * Utility functions, with some ASM defined functions for speed
+ * purposes
+ *
+ *****************************************************************/
#ifndef MIN
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
@@ -504,185 +460,236 @@
}
#endif
-
-/*
- * Initialize the random pool with standard stuff.
+/**********************************************************************
*
- * NOTE: This is an OS-dependent function.
+ * OS independent entropy store. Here are the functions which handle
+ * storing entropy in an entropy pool.
+ *
+ **********************************************************************/
+
+struct entropy_store {
+ unsigned add_ptr;
+ int entropy_count;
+ int input_rotate;
+ int extract_count;
+ struct poolinfo poolinfo;
+ __u32 *pool;
+};
+
+/*
+ * Initialize the entropy store. The input argument is the size of
+ * the random pool.
+ *
+ * Returns an negative error if there is a problem.
*/
-static void init_std_data(struct random_bucket *r)
+static int create_entropy_store(int size, struct entropy_store **ret_bucket)
{
- __u32 words[2], *p;
- int i;
- struct timeval tv;
+ struct entropy_store *r;
+ struct poolinfo *p;
+ int poolwords;
- do_gettimeofday(&tv);
- add_entropy_words(r, tv.tv_sec, tv.tv_usec);
+ poolwords = (size + 3) / 4; /* Convert bytes->words */
+ /* The pool size must be a multiple of 16 32-bit words */
+ poolwords = ((poolwords + 15) / 16) * 16;
- /*
- * This doesnt lock system.utsname. Howeve we are generating
- * entropy so a race with a name set here is fine.
- */
- p = (__u32 *)&system_utsname;
- for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
- memcpy(words, p, sizeof(words));
- add_entropy_words(r, words[0], words[1]);
- p += sizeof(words)/sizeof(*words);
+ for (p = poolinfo_table; p->poolwords; p++) {
+ if (poolwords == p->poolwords)
+ break;
}
-
+ if (p->poolwords == 0)
+ return -EINVAL;
+
+ r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
+ if (!r)
+ return -ENOMEM;
+
+ memset (r, 0, sizeof(struct entropy_store));
+ r->poolinfo = *p;
+
+ r->pool = kmalloc(poolwords*4, GFP_KERNEL);
+ if (!r->pool) {
+ kfree_s(r, sizeof(struct entropy_store));
+ return -ENOMEM;
+ }
+ memset(r->pool, 0, poolwords*4);
+ *ret_bucket = r;
+ return 0;
}
/* Clear the entropy pool and associated counters. */
-static void rand_clear_pool(void)
+static void clear_entropy_store(struct entropy_store *r)
{
- memset(&random_state, 0, sizeof(random_state));
- init_std_data(&random_state);
+ r->add_ptr = 0;
+ r->entropy_count = 0;
+ r->input_rotate = 0;
+ r->extract_count = 0;
+ memset(r->pool, 0, r->poolinfo.poolwords*4);
}
-void __init rand_initialize(void)
+static void free_entropy_store(struct entropy_store *r)
{
- int i;
-
- rand_clear_pool();
- for (i = 0; i < NR_IRQS; i++)
- irq_timer_state[i] = NULL;
- for (i = 0; i < MAX_BLKDEV; i++)
- blkdev_timer_state[i] = NULL;
- memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state));
- memset(&mouse_timer_state, 0, sizeof(struct timer_rand_state));
- memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
-#ifdef RANDOM_BENCHMARK
- initialize_benchmark(&timer_benchmark, "timer", 0);
-#endif
- extract_timer_state.dont_count_entropy = 1;
+ if (r->pool)
+ kfree(r->pool);
+ kfree_s(r, sizeof(struct entropy_store));
}
-void rand_initialize_irq(int irq)
+/*
+ * This function adds a byte into the entropy "pool". It does not
+ * update the entropy estimate. The caller should call
+ * credit_entropy_store if this is appropriate.
+ *
+ * The pool is stirred with a primitive polynomial of the appropriate
+ * degree, and then twisted. We twist by three bits at a time because
+ * 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 add_entropy_words(struct entropy_store *r, const __u32 *in,
+ int num)
{
- struct timer_rand_state *state;
-
- if (irq >= NR_IRQS || irq_timer_state[irq])
- return;
-
- /*
- * If kmalloc returns null, we just won't use that entropy
- * source.
- */
- state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
- if (state) {
- irq_timer_state[irq] = state;
- memset(state, 0, sizeof(struct timer_rand_state));
+ static __u32 const twist_table[8] = {
+ 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
+ 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
+ unsigned i;
+ int new_rotate;
+ __u32 w;
+
+ while (num--) {
+ w = rotate_left(r->input_rotate, *in);
+ i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
+ /*
+ * Normally, we add 7 bits of rotation to the pool.
+ * At the beginning of the pool, add an extra 7 bits
+ * rotation, so that successive passes spread the
+ * input bits across the pool evenly.
+ */
+ new_rotate = r->input_rotate + 14;
+ if (i)
+ new_rotate = r->input_rotate + 7;
+ r->input_rotate = new_rotate & 31;
+
+ /* XOR in the various taps */
+ w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
+ w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
+ w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
+ w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
+ w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
+ w ^= r->pool[i];
+ r->pool[i] = (w >> 3) ^ twist_table[w & 7];
}
}
-void rand_initialize_blkdev(int major, int mode)
+/*
+ * Credit (or debit) the entropy store with n bits of entropy
+ */
+static void credit_entropy_store(struct entropy_store *r, int num)
{
- struct timer_rand_state *state;
-
- if (major >= MAX_BLKDEV || blkdev_timer_state[major])
- return;
+ int max_entropy = r->poolinfo.poolwords*32;
- /*
- * If kmalloc returns null, we just won't use that entropy
- * source.
- */
- state = kmalloc(sizeof(struct timer_rand_state), mode);
- if (state) {
- blkdev_timer_state[major] = state;
- memset(state, 0, sizeof(struct timer_rand_state));
- }
+ if (r->entropy_count + num < 0)
+ r->entropy_count = 0;
+ else if (r->entropy_count + num > max_entropy)
+ r->entropy_count = max_entropy;
+ else
+ r->entropy_count = r->entropy_count + num;
}
-/*
- * This function adds a byte into the entropy "pool". It does not
- * update the entropy estimate. The caller must do this if appropriate.
+/**********************************************************************
*
- * This function is tuned for speed above most other considerations.
+ * Entropy batch input management
*
- * The pool is stirred with a primitive polynomial of the appropriate degree,
- * and then twisted. We twist by three bits at a time because it's
- * cheap to do so and helps slightly in the expected case where the
- * entropy is concentrated in the low-order bits.
- */
-#define MASK(x) ((x) & (POOLWORDS-1)) /* Convenient abreviation */
-static inline void fast_add_entropy_words(struct random_bucket *r,
- __u32 x, __u32 y)
-{
- static __u32 const twist_table[8] = {
- 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
- 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
- unsigned i, j;
+ * We batch entropy to be added to avoid increasing interrupt latency
+ *
+ **********************************************************************/
- i = MASK(r->add_ptr - 2); /* i is always even */
- r->add_ptr = i;
+static __u32 *batch_entropy_pool;
+static int *batch_entropy_credit;
+static int batch_max;
+static int batch_head, batch_tail;
+static struct tq_struct batch_tqueue;
+static void batch_entropy_process(void *private_);
-#ifdef ROTATE_PARANOIA
- j = r->input_rotate + 14;
- if (i)
- j -= 7;
- r->input_rotate = j & 31;
+/* note: the size must be a power of 2 */
+static int batch_entropy_init(int size, struct entropy_store *r)
+{
+ batch_entropy_pool = kmalloc(2*size*sizeof(__u32), GFP_KERNEL);
+ if (!batch_entropy_pool)
+ return -1;
+ batch_entropy_credit =kmalloc(size*sizeof(int), GFP_KERNEL);
+ if (!batch_entropy_credit) {
+ kfree(batch_entropy_pool);
+ return -1;
+ }
+ batch_head = batch_tail = 0;
+ batch_max = size;
+ batch_tqueue.routine = batch_entropy_process;
+ batch_tqueue.data = r;
+ return 0;
+}
- x = rotate_left(r->input_rotate, x);
- y = rotate_left(r->input_rotate, y);
-#endif
+static void batch_entropy_store(__u32 a, __u32 b, int num)
+{
+ int new;
- /*
- * XOR in the various taps. Even though logically, we compute
- * x and then compute y, we read in y then x order because most
- * caches work slightly better with increasing read addresses.
- * If a tap is even then we can use the fact that i is even to
- * avoid a masking operation. Every polynomial has at least one
- * even tap, so j is always used.
- * (Is there a nicer way to arrange this code?)
- */
-#if TAP1 & 1
- y ^= r->pool[MASK(i+TAP1)]; x ^= r->pool[MASK(i+TAP1+1)];
-#else
- j = MASK(i+TAP1); y ^= r->pool[j]; x ^= r->pool[j+1];
-#endif
-#if TAP2 & 1
- y ^= r->pool[MASK(i+TAP2)]; x ^= r->pool[MASK(i+TAP2+1)];
-#else
- j = MASK(i+TAP2); y ^= r->pool[j]; x ^= r->pool[j+1];
-#endif
-#if TAP3 & 1
- y ^= r->pool[MASK(i+TAP3)]; x ^= r->pool[MASK(i+TAP3+1)];
-#else
- j = MASK(i+TAP3); y ^= r->pool[j]; x ^= r->pool[j+1];
-#endif
-#if TAP4 & 1
- y ^= r->pool[MASK(i+TAP4)]; x ^= r->pool[MASK(i+TAP4+1)];
-#else
- j = MASK(i+TAP4); y ^= r->pool[j]; x ^= r->pool[j+1];
-#endif
-#if TAP5 == 1
- /* We need to pretend to write pool[i+1] before computing y */
- y ^= r->pool[i];
- x ^= r->pool[i+1];
- x ^= r->pool[MASK(i+TAP5+1)];
- y ^= r->pool[i+1] = x = (x >> 3) ^ twist_table[x & 7];
- r->pool[i] = (y >> 3) ^ twist_table[y & 7];
-#else
-# if TAP5 & 1
- y ^= r->pool[MASK(i+TAP5)]; x ^= r->pool[MASK(i+TAP5+1)];
-# else
- j = MASK(i+TAP5); y ^= r->pool[j]; x ^= r->pool[j+1];
-# endif
- y ^= r->pool[i];
- x ^= r->pool[i+1];
- r->pool[i] = (y >> 3) ^ twist_table[y & 7];
- r->pool[i+1] = (x >> 3) ^ twist_table[x & 7];
+ if (!batch_max)
+ return;
+
+ batch_entropy_pool[2*batch_head] = a;
+ batch_entropy_pool[(2*batch_head) + 1] = b;
+ batch_entropy_credit[batch_head] = num;
+
+ new = (batch_head+1) & (batch_max-1);
+ if (new != batch_tail) {
+ queue_task(&batch_tqueue, &tq_timer);
+ batch_head = new;
+ } else {
+#if 0
+ printk(KERN_NOTICE "random: batch entropy buffer full\n");
#endif
+ }
}
-/*
- * For places where we don't need the inlined version
- */
-static void add_entropy_words(struct random_bucket *r, __u32 x, __u32 y)
+static void batch_entropy_process(void *private_)
{
- fast_add_entropy_words(r, x, y);
+ int num = 0;
+ int max_entropy;
+ struct entropy_store *r = (struct entropy_store *) private_, *p;
+
+ if (!batch_max)
+ return;
+
+ max_entropy = r->poolinfo.poolwords*32;
+ while (batch_head != batch_tail) {
+ add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
+ p = r;
+ if (r->entropy_count > max_entropy && (num & 1))
+ r = sec_random_state;
+ credit_entropy_store(r, batch_entropy_credit[batch_tail]);
+ batch_tail = (batch_tail+1) & (batch_max-1);
+ num++;
+ }
+ if (r->entropy_count >= random_read_wakeup_thresh)
+ wake_up_interruptible(&random_read_wait);
}
+/*********************************************************************
+ *
+ * Entropy input management
+ *
+ *********************************************************************/
+
+/* There is one of these per entropy source */
+struct timer_rand_state {
+ __u32 last_time;
+ __s32 last_delta,last_delta2;
+ int dont_count_entropy:1;
+};
+
+static struct timer_rand_state keyboard_timer_state;
+static struct timer_rand_state mouse_timer_state;
+static struct timer_rand_state extract_timer_state;
+static struct timer_rand_state *irq_timer_state[NR_IRQS];
+static struct timer_rand_state *blkdev_timer_state[MAX_BLKDEV];
+
/*
* This function adds entropy to the entropy "pool" by using timing
* delays. It uses the timer_rand_state structure to make an estimate
@@ -695,15 +702,12 @@
* are used for a high-resolution timer.
*
*/
-static void add_timer_randomness(struct random_bucket *r,
- struct timer_rand_state *state, unsigned num)
+static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
{
__u32 time;
__s32 delta, delta2, delta3;
+ int entropy = 0;
-#ifdef RANDOM_BENCHMARK
- begin_benchmark(&timer_benchmark);
-#endif
#if defined (__i386__)
if (boot_cpu_data.x86_capability & X86_FEATURE_TSC) {
__u32 high;
@@ -717,14 +721,12 @@
time = jiffies;
#endif
- fast_add_entropy_words(r, (__u32)num, time);
-
/*
* Calculate number of bits of randomness we probably added.
* We take into account the first, second and third-order deltas
* in order to make our estimate.
*/
- if ((r->entropy_count < POOLBITS) && !state->dont_count_entropy) {
+ if (!state->dont_count_entropy) {
delta = time - state->last_time;
state->last_time = time;
@@ -753,30 +755,19 @@
delta >>= 1;
delta &= (1 << 12) - 1;
- r->entropy_count += int_ln_12bits(delta);
-
- /* Prevent overflow */
- if (r->entropy_count > POOLBITS)
- r->entropy_count = POOLBITS;
-
- /* Wake up waiting processes, if we have enough entropy. */
- if (r->entropy_count >= WAIT_INPUT_BITS)
- wake_up_interruptible(&random_read_wait);
+ entropy = int_ln_12bits(delta);
}
-
-#ifdef RANDOM_BENCHMARK
- end_benchmark(&timer_benchmark);
-#endif
+ batch_entropy_store(num, time, entropy);
}
void add_keyboard_randomness(unsigned char scancode)
{
- add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
+ add_timer_randomness(&keyboard_timer_state, scancode);
}
void add_mouse_randomness(__u32 mouse_data)
{
- add_timer_randomness(&random_state, &mouse_timer_state, mouse_data);
+ add_timer_randomness(&mouse_timer_state, mouse_data);
}
void add_interrupt_randomness(int irq)
@@ -784,7 +775,7 @@
if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
return;
- add_timer_randomness(&random_state, irq_timer_state[irq], 0x100+irq);
+ add_timer_randomness(irq_timer_state[irq], 0x100+irq);
}
void add_blkdev_randomness(int major)
@@ -798,10 +789,15 @@
return;
}
- add_timer_randomness(&random_state, blkdev_timer_state[major],
- 0x200+major);
+ add_timer_randomness(blkdev_timer_state[major], 0x200+major);
}
+/******************************************************************
+ *
+ * Hash function definition
+ *
+ *******************************************************************/
+
/*
* This chunk of code defines a function
* void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
@@ -821,12 +817,11 @@
* 3) 0x98badcfe
* 4) 0x10325476
* 5) 0xc3d2e1f0 (SHA only)
- *
+ *
* For /dev/random purposes, the length of the data being hashed is
- * fixed in length (at POOLWORDS words), so appending a bit count in
- * the usual way is not cryptographically necessary.
+ * fixed in length, so appending a bit count in the usual way is not
+ * cryptographically necessary.
*/
-#define USE_SHA
#ifdef USE_SHA
@@ -1074,9 +1069,6 @@
/*
* MD5 transform algorithm, taken from code written by Colin Plumb,
* and put into the public domain
- *
- * QUESTION: Replace this with SHA, which as generally received better
- * reviews from the cryptographic community?
*/
/* The four core functions - F1 is optimized somewhat */
@@ -1187,39 +1179,94 @@
#endif /* !USE_SHA */
+/*********************************************************************
+ *
+ * Entropy extraction routines
+ *
+ *********************************************************************/
+
+#define EXTRACT_ENTROPY_USER 1
+#define EXTRACT_ENTROPY_SECONDARY 2
+#define TMP_BUF_SIZE (HASH_BUFFER_SIZE + HASH_EXTRA_SIZE)
+#define SEC_XFER_SIZE (TMP_BUF_SIZE*4)
+
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+ size_t nbytes, int flags);
+
+/*
+ * This utility inline function is responsible for transfering entropy
+ * from the primary pool to the secondary extraction pool. We pull
+ * randomness under two conditions; one is if there isn't enough entropy
+ * in the secondary pool. The other is after we have extract 1024 bytes,
+ * at which point we do a "catastrophic reseeding".
+ */
+static inline void xfer_secondary_pool(struct entropy_store *r,
+ size_t nbytes)
+{
+ __u32 tmp[TMP_BUF_SIZE];
+
+ if (r->entropy_count < nbytes*8) {
+ extract_entropy(random_state, tmp, sizeof(tmp), 0);
+ add_entropy_words(r, tmp, TMP_BUF_SIZE);
+ credit_entropy_store(r, TMP_BUF_SIZE*8);
+ }
+ if (r->extract_count > 1024) {
+ extract_entropy(random_state, tmp, sizeof(tmp), 0);
+ add_entropy_words(r, tmp, TMP_BUF_SIZE);
+ r->extract_count = 0;
+ }
+}
-#if POOLWORDS % 16 != 0
-#error extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
-#endif
/*
* This function extracts randomness from the "entropy pool", and
* returns it in a buffer. This function computes how many remaining
* bits of entropy are left in the pool, but it does not restrict the
- * number of bytes that are actually obtained.
+ * number of bytes that are actually obtained. If the EXTRACT_ENTROPY_USER
+ * flag is given, then the buf pointer is assumed to be in user space.
+ * If the EXTRACT_ENTROPY_SECONDARY flag is given, then this function will
+ *
+ * Note: extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
*/
-static ssize_t extract_entropy(struct random_bucket *r, char * buf,
- size_t nbytes, int to_user)
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+ size_t nbytes, int flags)
{
ssize_t ret, i;
- __u32 tmp[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE];
+ __u32 tmp[TMP_BUF_SIZE];
__u32 x;
- add_timer_randomness(r, &extract_timer_state, nbytes);
+ add_timer_randomness(&extract_timer_state, nbytes);
/* Redundant, but just in case... */
- if (r->entropy_count > POOLBITS)
- r->entropy_count = POOLBITS;
+ if (r->entropy_count > r->poolinfo.poolwords)
+ r->entropy_count = r->poolinfo.poolwords;
+
+ if (flags & EXTRACT_ENTROPY_SECONDARY)
+ xfer_secondary_pool(r, nbytes);
- ret = nbytes;
if (r->entropy_count / 8 >= nbytes)
r->entropy_count -= nbytes*8;
else
r->entropy_count = 0;
- if (r->entropy_count < WAIT_OUTPUT_BITS)
+ if (r->entropy_count < random_write_wakeup_thresh)
wake_up_interruptible(&random_write_wait);
+
+ r->extract_count += nbytes;
+ ret = 0;
while (nbytes) {
+ /*
+ * Check if we need to break out or reschedule....
+ */
+ if ((flags & EXTRACT_ENTROPY_USER) && current->need_resched) {
+ if (signal_pending(current)) {
+ if (ret == 0)
+ ret = -ERESTARTSYS;
+ break;
+ }
+ schedule();
+ }
+
/* Hash the pool to get the output */
tmp[0] = 0x67452301;
tmp[1] = 0xefcdab89;
@@ -1228,39 +1275,34 @@
#ifdef USE_SHA
tmp[4] = 0xc3d2e1f0;
#endif
- for (i = 0; i < POOLWORDS; i += 16)
- HASH_TRANSFORM(tmp, r->pool+i);
-
/*
- * The following code does two separate things that happen
- * to both work two words at a time, so are convenient
- * to do together.
- *
- * First, this feeds the output back into the pool so
- * that the next call will return different results.
- * Any perturbation of the pool's state would do, even
- * changing one bit, but this mixes the pool nicely.
- *
- * Second, this folds the output in half to hide the data
- * fed back into the pool from the user and further mask
- * any patterns in the hash output. (The exact folding
- * pattern is not important; the one used here is quick.)
+ * As we hash the pool, we mix intermediate values of
+ * the hash back into the pool. This eliminates
+ * backtracking attacks (where the attacker knows
+ * the state of the pool plus the current outputs, and
+ * attempts to find previous ouputs), unless the hash
+ * function can be inverted.
*/
- for (i = 0; i < HASH_BUFFER_SIZE/2; i++) {
- x = tmp[i + (HASH_BUFFER_SIZE+1)/2];
- add_entropy_words(r, tmp[i], x);
- tmp[i] ^= x;
+ for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
+ HASH_TRANSFORM(tmp, r->pool+i);
+ add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
}
+
+ /*
+ * In case the hash function has some recognizable
+ * output pattern, we fold it in half.
+ */
+ for (i = 0; i < HASH_BUFFER_SIZE/2; i++)
+ tmp[i] ^= tmp[i + (HASH_BUFFER_SIZE+1)/2];
#if HASH_BUFFER_SIZE & 1 /* There's a middle word to deal with */
x = tmp[HASH_BUFFER_SIZE/2];
- add_entropy_words(r, x, (__u32)((unsigned long)buf));
x ^= (x >> 16); /* Fold it in half */
((__u16 *)tmp)[HASH_BUFFER_SIZE-1] = (__u16)x;
#endif
/* Copy data to destination buffer */
i = MIN(nbytes, HASH_BUFFER_SIZE*sizeof(__u32)/2);
- if (to_user) {
+ if (flags & EXTRACT_ENTROPY_USER) {
i -= copy_to_user(buf, (__u8 const *)tmp, i);
if (!i) {
ret = -EFAULT;
@@ -1270,16 +1312,8 @@
memcpy(buf, (__u8 const *)tmp, i);
nbytes -= i;
buf += i;
- add_timer_randomness(r, &extract_timer_state, nbytes);
- if (to_user && current->need_resched)
- {
- if (signal_pending(current))
- {
- ret = -EINTR;
- break;
- }
- schedule();
- }
+ ret += i;
+ add_timer_randomness(&extract_timer_state, nbytes);
}
/* Wipe data just returned from memory */
@@ -1295,9 +1329,108 @@
*/
void get_random_bytes(void *buf, int nbytes)
{
- extract_entropy(&random_state, (char *) buf, nbytes, 0);
+ extract_entropy(sec_random_state, (char *) buf, nbytes,
+ EXTRACT_ENTROPY_SECONDARY);
+}
+
+/*********************************************************************
+ *
+ * Functions to interface with Linux
+ *
+ *********************************************************************/
+
+/*
+ * Initialize the random pool with standard stuff.
+ *
+ * NOTE: This is an OS-dependent function.
+ */
+static void init_std_data(struct entropy_store *r)
+{
+ struct timeval tv;
+ __u32 words[2];
+ char *p;
+ int i;
+
+ do_gettimeofday(&tv);
+ words[0] = tv.tv_sec;
+ words[1] = tv.tv_usec;
+ add_entropy_words(r, words, 2);
+
+ /*
+ * This doesn't lock system.utsname. However, we are generating
+ * entropy so a race with a name set here is fine.
+ */
+ p = (char *) &system_utsname;
+ for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
+ memcpy(words, p, sizeof(words));
+ add_entropy_words(r, words, sizeof(words)/4);
+ p += sizeof(words);
+ }
+}
+
+void __init rand_initialize(void)
+{
+ int i;
+
+ if (create_entropy_store(DEFAULT_POOL_SIZE, &random_state))
+ return; /* Error, return */
+ if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+ return; /* Error, return */
+ if (create_entropy_store(SECONDARY_POOL_SIZE, &sec_random_state))
+ return; /* Error, return */
+ clear_entropy_store(random_state);
+ clear_entropy_store(sec_random_state);
+ init_std_data(random_state);
+#ifdef CONFIG_SYSCTL
+ sysctl_init_random(random_state);
+#endif
+ for (i = 0; i < NR_IRQS; i++)
+ irq_timer_state[i] = NULL;
+ for (i = 0; i < MAX_BLKDEV; i++)
+ blkdev_timer_state[i] = NULL;
+ memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state));
+ memset(&mouse_timer_state, 0, sizeof(struct timer_rand_state));
+ memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
+ extract_timer_state.dont_count_entropy = 1;
+}
+
+void rand_initialize_irq(int irq)
+{
+ struct timer_rand_state *state;
+
+ if (irq >= NR_IRQS || irq_timer_state[irq])
+ return;
+
+ /*
+ * If kmalloc returns null, we just won't use that entropy
+ * source.
+ */
+ state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
+ if (state) {
+ memset(state, 0, sizeof(struct timer_rand_state));
+ irq_timer_state[irq] = state;
+ }
+}
+
+void rand_initialize_blkdev(int major, int mode)
+{
+ struct timer_rand_state *state;
+
+ if (major >= MAX_BLKDEV || blkdev_timer_state[major])
+ return;
+
+ /*
+ * If kmalloc returns null, we just won't use that entropy
+ * source.
+ */
+ state = kmalloc(sizeof(struct timer_rand_state), mode);
+ if (state) {
+ memset(state, 0, sizeof(struct timer_rand_state));
+ blkdev_timer_state[major] = state;
+ }
}
+
static ssize_t
random_read(struct file * file, char * buf, size_t nbytes, loff_t *ppos)
{
@@ -1312,8 +1445,10 @@
current->state = TASK_INTERRUPTIBLE;
n = nbytes;
- if (n > random_state.entropy_count / 8)
- n = random_state.entropy_count / 8;
+ if (n > SEC_XFER_SIZE)
+ n = SEC_XFER_SIZE;
+ if (n > random_state->entropy_count / 8)
+ n = random_state->entropy_count / 8;
if (n == 0) {
if (file->f_flags & O_NONBLOCK) {
retval = -EAGAIN;
@@ -1326,7 +1461,9 @@
schedule();
continue;
}
- n = extract_entropy(&random_state, buf, n, 1);
+ n = extract_entropy(sec_random_state, buf, n,
+ EXTRACT_ENTROPY_USER |
+ EXTRACT_ENTROPY_SECONDARY);
if (n < 0) {
retval = n;
break;
@@ -1351,10 +1488,12 @@
}
static ssize_t
-random_read_unlimited(struct file * file, char * buf,
+urandom_read(struct file * file, char * buf,
size_t nbytes, loff_t *ppos)
{
- return extract_entropy(&random_state, buf, nbytes, 1);
+ return extract_entropy(sec_random_state, buf, nbytes,
+ EXTRACT_ENTROPY_USER |
+ EXTRACT_ENTROPY_SECONDARY);
}
static unsigned int
@@ -1365,9 +1504,9 @@
poll_wait(file, &random_read_wait, wait);
poll_wait(file, &random_write_wait, wait);
mask = 0;
- if (random_state.entropy_count >= WAIT_INPUT_BITS)
+ if (random_state->entropy_count >= random_read_wakeup_thresh)
mask |= POLLIN | POLLRDNORM;
- if (random_state.entropy_count < WAIT_OUTPUT_BITS)
+ if (random_state->entropy_count < random_write_wakeup_thresh)
mask |= POLLOUT | POLLWRNORM;
return mask;
}
@@ -1378,7 +1517,6 @@
{
int ret = 0;
size_t bytes;
- unsigned i;
__u32 buf[16];
const char *p = buffer;
size_t c = count;
@@ -1393,11 +1531,10 @@
}
c -= bytes;
p += bytes;
-
- i = (unsigned)((bytes-1) / (2 * sizeof(__u32)));
- do {
- add_entropy_words(&random_state, buf[2*i], buf[2*i+1]);
- } while (i--);
+
+ /* Convert bytes to words */
+ bytes = (bytes + 3) / sizeof(__u32);
+ add_entropy_words(random_state, buf, bytes);
}
if (p == buffer) {
return (ssize_t)ret;
@@ -1417,7 +1554,7 @@
switch (cmd) {
case RNDGETENTCNT:
- ent_count = random_state.entropy_count;
+ ent_count = random_state->entropy_count;
if (put_user(ent_count, (int *) arg))
return -EFAULT;
return 0;
@@ -1426,45 +1563,31 @@
return -EPERM;
if (get_user(ent_count, (int *) arg))
return -EFAULT;
- /*
- * Add i to entropy_count, limiting the result to be
- * between 0 and POOLBITS.
- */
- if (ent_count < -random_state.entropy_count)
- random_state.entropy_count = 0;
- else if (ent_count > POOLBITS)
- random_state.entropy_count = POOLBITS;
- else {
- random_state.entropy_count += ent_count;
- if (random_state.entropy_count > POOLBITS)
- random_state.entropy_count = POOLBITS;
- if (random_state.entropy_count < 0)
- random_state.entropy_count = 0;
- }
+ credit_entropy_store(random_state, ent_count);
/*
* Wake up waiting processes if we have enough
* entropy.
*/
- if (random_state.entropy_count >= WAIT_INPUT_BITS)
+ if (random_state->entropy_count >= random_read_wakeup_thresh)
wake_up_interruptible(&random_read_wait);
return 0;
case RNDGETPOOL:
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
p = (int *) arg;
- ent_count = random_state.entropy_count;
+ ent_count = random_state->entropy_count;
if (put_user(ent_count, p++))
return -EFAULT;
if (get_user(size, p))
return -EFAULT;
- if (put_user(POOLWORDS, p++))
+ if (put_user(random_state->poolinfo.poolwords, p++))
return -EFAULT;
if (size < 0)
return -EINVAL;
- if (size > POOLWORDS)
- size = POOLWORDS;
- if (copy_to_user(p, random_state.pool, size*sizeof(__u32)))
+ if (size > random_state->poolinfo.poolwords)
+ size = random_state->poolinfo.poolwords;
+ if (copy_to_user(p, random_state->pool, size*sizeof(__u32)))
return -EFAULT;
return 0;
case RNDADDENTROPY:
@@ -1481,36 +1604,25 @@
size, &file->f_pos);
if (retval < 0)
return retval;
- /*
- * Add ent_count to entropy_count, limiting the result to be
- * between 0 and POOLBITS.
- */
- if (ent_count > POOLBITS)
- random_state.entropy_count = POOLBITS;
- else {
- random_state.entropy_count += ent_count;
- if (random_state.entropy_count > POOLBITS)
- random_state.entropy_count = POOLBITS;
- if (random_state.entropy_count < 0)
- random_state.entropy_count = 0;
- }
+ credit_entropy_store(random_state, ent_count);
/*
* Wake up waiting processes if we have enough
* entropy.
*/
- if (random_state.entropy_count >= WAIT_INPUT_BITS)
+ if (random_state->entropy_count >= random_read_wakeup_thresh)
wake_up_interruptible(&random_read_wait);
return 0;
case RNDZAPENTCNT:
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
- random_state.entropy_count = 0;
+ random_state->entropy_count = 0;
return 0;
case RNDCLEARPOOL:
/* Clear the entropy pool and associated counters. */
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
- rand_clear_pool();
+ clear_entropy_store(random_state);
+ init_std_data(random_state);
return 0;
default:
return -EINVAL;
@@ -1532,7 +1644,7 @@
struct file_operations urandom_fops = {
NULL, /* unrandom_lseek */
- random_read_unlimited,
+ urandom_read,
random_write,
NULL, /* urandom_readdir */
NULL, /* urandom_poll */
@@ -1543,6 +1655,210 @@
NULL /* no special release code */
};
+/***************************************************************
+ * Random UUID interface
+ *
+ * Used here for a Boot ID, but can be useful for other kernel
+ * drivers.
+ ***************************************************************/
+
+/*
+ * Generate random UUID
+ */
+void generate_random_uuid(unsigned char uuid_out[16])
+{
+ get_random_bytes(uuid_out, 16);
+ /* Set UUID version to 4 --- truely random generation */
+ uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
+ /* Set the UUID variant to DCE */
+ uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+}
+
+/********************************************************************
+ *
+ * Sysctl interface
+ *
+ ********************************************************************/
+
+#ifdef CONFIG_SYSCTL
+
+#include <linux/sysctl.h>
+
+static int sysctl_poolsize;
+static int min_read_thresh, max_read_thresh;
+static int min_write_thresh, max_write_thresh;
+static char sysctl_bootid[16];
+
+/*
+ * This function handles a request from the user to change the pool size
+ * of the primary entropy store.
+ */
+static int change_poolsize(int poolsize)
+{
+ struct entropy_store *new_store, *old_store;
+ int ret;
+
+ if ((ret = create_entropy_store(poolsize, &new_store)))
+ return ret;
+
+ add_entropy_words(new_store, random_state->pool,
+ random_state->poolinfo.poolwords);
+ credit_entropy_store(new_store, random_state->entropy_count);
+
+ sysctl_init_random(new_store);
+ old_store = random_state;
+ random_state = batch_tqueue.data = new_store;
+ free_entropy_store(old_store);
+ return 0;
+}
+
+static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
+ void *buffer, size_t *lenp)
+{
+ int ret;
+
+ sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+
+ ret = proc_dointvec(table, write, filp, buffer, lenp);
+ if (ret || !write ||
+ (sysctl_poolsize == random_state->poolinfo.poolwords * 4))
+ return ret;
+
+ return change_poolsize(sysctl_poolsize);
+}
+
+static int poolsize_strategy(ctl_table *table, int *name, int nlen,
+ void *oldval, size_t *oldlenp,
+ void *newval, size_t newlen, void **context)
+{
+ int len;
+
+ sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+
+ /*
+ * We only handle the write case, since the read case gets
+ * handled by the default handler (and we don't care if the
+ * write case happens twice; it's harmless).
+ */
+ if (newval && newlen) {
+ len = newlen;
+ if (len > table->maxlen)
+ len = table->maxlen;
+ if (copy_from_user(table->data, newval, len))
+ return -EFAULT;
+ }
+
+ if (sysctl_poolsize != random_state->poolinfo.poolwords * 4)
+ return change_poolsize(sysctl_poolsize);
+
+ return 0;
+}
+
+/*
+ * These functions is used to return both the bootid UUID, and random
+ * UUID. The difference is in whether table->data is NULL; if it is,
+ * then a new UUID is generated and returned to the user.
+ *
+ * If the user accesses this via the proc interface, it will be returned
+ * as an ASCII string in the standard UUID format. If accesses via the
+ * sysctl system call, it is returned as 16 bytes of binary data.
+ */
+static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
+ void *buffer, size_t *lenp)
+{
+ ctl_table fake_table;
+ unsigned char buf[64], tmp_uuid[16], *uuid;
+
+ uuid = table->data;
+ if (!uuid) {
+ uuid = tmp_uuid;
+ uuid[8] = 0;
+ }
+ if (uuid[8] == 0)
+ generate_random_uuid(uuid);
+
+ sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
+ "%02x%02x%02x%02x%02x%02x",
+ uuid[0], uuid[1], uuid[2], uuid[3],
+ uuid[4], uuid[5], uuid[6], uuid[7],
+ uuid[8], uuid[9], uuid[10], uuid[11],
+ uuid[12], uuid[13], uuid[14], uuid[15]);
+ fake_table.data = buf;
+ fake_table.maxlen = sizeof(buf);
+
+ return proc_dostring(&fake_table, write, filp, buffer, lenp);
+}
+
+static int uuid_strategy(ctl_table *table, int *name, int nlen,
+ void *oldval, size_t *oldlenp,
+ void *newval, size_t newlen, void **context)
+{
+ unsigned char tmp_uuid[16], *uuid;
+ int len;
+
+ if (!oldval || !oldlenp)
+ return 1;
+
+ uuid = table->data;
+ if (!uuid) {
+ uuid = tmp_uuid;
+ uuid[8] = 0;
+ }
+ if (uuid[8] == 0)
+ generate_random_uuid(uuid);
+
+ get_user(len, oldlenp);
+ if (len) {
+ if (len > 16)
+ len = 16;
+ if (copy_to_user(oldval, table->data, len))
+ return -EFAULT;
+ if (put_user(len, oldlenp))
+ return -EFAULT;
+ }
+ return 1;
+}
+
+ctl_table random_table[] = {
+ {RANDOM_POOLSIZE, "poolsize",
+ &sysctl_poolsize, sizeof(int), 0644, NULL,
+ &proc_do_poolsize, &poolsize_strategy},
+ {RANDOM_ENTROPY_COUNT, "entropy_avail",
+ NULL, sizeof(int), 0444, NULL,
+ &proc_dointvec},
+ {RANDOM_READ_THRESH, "read_wakeup_threshold",
+ &random_read_wakeup_thresh, sizeof(int), 0644, NULL,
+ &proc_dointvec_minmax, &sysctl_intvec, 0,
+ &min_read_thresh, &max_read_thresh},
+ {RANDOM_WRITE_THRESH, "write_wakeup_threshold",
+ &random_write_wakeup_thresh, sizeof(int), 0644, NULL,
+ &proc_dointvec_minmax, &sysctl_intvec, 0,
+ &min_write_thresh, &max_write_thresh},
+ {RANDOM_BOOT_ID, "boot_id",
+ &sysctl_bootid, 16, 0444, NULL,
+ &proc_do_uuid, &uuid_strategy},
+ {RANDOM_UUID, "uuid",
+ NULL, 16, 0444, NULL,
+ &proc_do_uuid, &uuid_strategy},
+ {0}
+};
+
+static void sysctl_init_random(struct entropy_store *random_state)
+{
+ min_read_thresh = 8;
+ min_write_thresh = 0;
+ max_read_thresh = max_write_thresh =
+ random_state->poolinfo.poolwords * 32;
+ random_table[1].data = &random_state->entropy_count;
+}
+#endif /* CONFIG_SYSCTL */
+
+/********************************************************************
+ *
+ * Random funtions for networking
+ *
+ ********************************************************************/
+
/*
* TCP initial sequence number picking. This uses the random number
* generator to pick an initial secret value. This value is hashed
@@ -1831,71 +2147,3 @@
return (cookie - tmp[17]) & COOKIEMASK; /* Leaving the data behind */
}
#endif
-
-
-#ifdef RANDOM_BENCHMARK
-/*
- * This is so we can do some benchmarking of the random driver, to see
- * how much overhead add_timer_randomness really takes. This only
- * works on a Pentium, since it depends on the timer clock...
- *
- * Note: the results of this benchmark as of this writing (5/27/96)
- *
- * On a Pentium, add_timer_randomness() takes between 150 and 1000
- * clock cycles, with an average of around 600 clock cycles. On a 75
- * MHz Pentium, this translates to 2 to 13 microseconds, with an
- * average time of 8 microseconds. This should be fast enough so we
- * can use add_timer_randomness() even with the fastest of interrupts...
- */
-static inline unsigned long long get_clock_cnt(void)
-{
- unsigned long low, high;
- __asm__(".byte 0x0f,0x31" :"=a" (low), "=d" (high));
- return (((unsigned long long) high << 32) | low);
-}
-
-static void __init
-initialize_benchmark(struct random_benchmark *bench,
- const char *descr, int unit)
-{
- bench->times = 0;
- bench->accum = 0;
- bench->max = 0;
- bench->min = 1 << 31;
- bench->descr = descr;
- bench->unit = unit;
-}
-
-static void begin_benchmark(struct random_benchmark *bench)
-{
-#ifdef BENCHMARK_NOINT
- save_flags(bench->flags); cli();
-#endif
- bench->start_time = get_clock_cnt();
-}
-
-static void end_benchmark(struct random_benchmark *bench)
-{
- unsigned long ticks;
-
- ticks = (unsigned long) (get_clock_cnt() - bench->start_time);
-#ifdef BENCHMARK_NOINT
- restore_flags(bench->flags);
-#endif
- if (ticks < bench->min)
- bench->min = ticks;
- if (ticks > bench->max)
- bench->max = ticks;
- bench->accum += ticks;
- bench->times++;
- if (bench->times == BENCHMARK_INTERVAL) {
- printk("Random benchmark: %s %d: %lu min, %lu avg, "
- "%lu max\n", bench->descr, bench->unit, bench->min,
- bench->accum / BENCHMARK_INTERVAL, bench->max);
- bench->times = 0;
- bench->accum = 0;
- bench->max = 0;
- bench->min = 1 << 31;
- }
-}
-#endif /* RANDOM_BENCHMARK */
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/