[PROPOSAL/PATCH] Fortuna PRNG in /dev/random

Jean-Luc Cooke
2004-09-23T23:58:50Z

[-- Attachment #1: Type: text/plain, Size: 3726 bytes --]

here we go ...

Team,

Here is a patch for the 2.6.8.1 Linux kernel which replaces the existing PRNG
in random.c with the Fortuna PRNG designed by Ferguson and Schneier (Practical
Cryptography). It is regarded in crypto circles as the current state-of-the-art
in cryptographically secure PRNGs.

Warning: Ted Ts'o and I talked about this at great length in sci.crypt and
in the end I failed on convince him that my patch was worth becoming main-line,
and he failed to convince me that status-quo is acceptable considering a better
solution exists.

I've made a page to capture my reasons and findings for this patch.
http://jlcooke.ca/random/
Please review this link. As a minimum the first table comparing status-quo
and Fortuna.

Changes in this patch (2 files):
include/linux/sysctl.h
+ added a RANDOM_DERIVE_SEED enum for the new
/proc/sys/kernel/random/derive_seed interface.

drivers/char/random.c
+ Kept all the event collection mechanisms, and interfaces.
+ Removed MD5-noPadding, SHA1-noPadding-endianIncorrect, halfMD4-noPadding (!?)
and twoThirdsMD4-noPadding (!?)
- Now uses Fortuna and the CryptoAPI (SHA-256, AES256)
+ Removed the one-of-a-kind (to my knowledge anyway) linear input mixing
function
- Now uses Fortuna and the CryptoAPI (SHA-256, AES256)
+ Removed the SHA1-feedback RNG output function
- Input/Output now uses the Fortuna PRNG
+ Removed the "HASH+HASH++++" system of SynCookies
- SynCookies now use block cipher CBC encryption
+ Removed the "HASH+++" system of TCPv4/v6 sequence number generation
- Now uses a block cipher CTR system to generate 32bit random value
+ Removed the "HASH" system of IPv4/v6 ID number generation
- Now uses a block cipher CTR system to generate 32bit random value
+ Removed entropy estimation
- Fortuna doesn't need it, vanilla-/dev/random and other Yarrow-like
PRNGs do to survive state compromise and other attacks.
- /dev/random is synonymous with /dev/urandom
- /proc/sys/kernel/random/entropy_avail is always the same as
/proc/sys/kernel/random/pool_size so ssh, dm-crypt and other apps who
block waiting for entropy don't seize up all together.
+ Added /proc/sys/kernel/random/derive_pool to save the pooling system's
state. This is a good thing because Fortuna will avoid using the entire
pooling system for output (this is a strength).

I expect much discussion on this. So let me lay out some facts:
- I have not broken /dev/random. I wrote this patch because I think we can
do better and Fortuna is the best there is right now.
- Current /dev/random is difficult to analyze because it doesn't use standards
compliant cryptographic primitives.
- Current /dev/random is slower then my proposed patch (5x on output, 2x on input)
- Current /dev/random's input mixing function is a linear function. This is bad in crypto-circles.
Why? Linear functions are communitive, associative and sometimes distributive.
Outputs from Linear function based PRNGs are very weak.
+ Note: Currently, output from /dev/random is feed-back into the input mixing
function making linear attacks of the PRNG more complex. But I fear
the combination of linear input mixing & knowing the feedback input
is a bad combination. Fortuna eliminates this and other theoretical
attacks. Read:
http://groups.google.com/groups?lr=&ie=UTF-8&th=2d80024f677ccadc&seekm=BemdnYeJjt2qMc3cRVn-jw%40comcast.com
- If need-be, I am prepared to take over maintainership of drivers/char/random.c
+ I don't want to push such a big change into Ted's lap, I am capable of taking
over for him.

I look forward to hearing from all of you.

JLC

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fortuna-2.6.8.1.patch --]
[-- Type: text/plain; charset=unknown-8bit, Size: 80118 bytes --]

diff -uNr linux-2.6.8.1-orig/include/linux/sysctl.h linux-2.6.8.1-fortuna/include/linux/sysctl.h
--- linux-2.6.8.1-orig/include/linux/sysctl.h 2004-08-14 12:55:33.000000000 +0200
+++ linux-2.6.8.1-fortuna/include/linux/sysctl.h 2004-09-13 18:55:43.000000000 +0200
@@ -198,7 +198,8 @@
RANDOM_READ_THRESH=3,
RANDOM_WRITE_THRESH=4,
RANDOM_BOOT_ID=5,
- RANDOM_UUID=6
+ RANDOM_UUID=6,
+ RANDOM_DERIVE_SEED=7
};

/* /proc/sys/kernel/pty */
--- linux-2.6.8.1/drivers/char/random.c 2004-08-14 06:54:48.000000000 -0400
+++ linux-2.6.8.1-rand2/drivers/char/random.c 2004-09-23 16:21:08.345499160 -0400
@@ -2,9 +2,11 @@
* random.c -- A strong random number generator
*
* Version 1.89, last modified 19-Sep-99
+ * Version 2.01, last modified 23-Sep-2004
*
* Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
* rights reserved.
+ * Copyright Jean-Luc Cooke, 2004. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -40,6 +42,180 @@
*/

/*
+ * Ammendum to Ts'o's comments by Jean-Luc Cooke Aug 2004
+ *
+ * The entire PRNG used in this file was replaced using a variant of the Fortuna
+ * PRNG described in Practical Cryptography by Ferguson and Schnier.
+ *
+ * The changes to their design include:
+ * - feeding the output of each pool back into their input to carry entropy
+ * forward (avoids pool overflow attacks like "dd if=/dev/zero of=/dev/random"
+ *
+ * Also, the entropy estimator was removed since it is not needed for cryptographically
+ * secure random data and such constructions are historically prone to attack
+ * [read Practical Cryptography].
+ *
+ * The new "start" and "stop" scripts are as follows:
+ *
+ * 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
+ * if [ -f $random_seed ]; then
+ * cat $random_seed >/dev/urandom
+ * else
+ * touch $random_seed
+ * fi
+ * chmod 600 $random_seed
+ * dd if=/proc/sys/kernel/random/derive_seed of=$random_seed
+ *
+ * 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
+ * echo "Saving random seed..."
+ * random_seed=/var/run/random-seed
+ * touch $random_seed
+ * chmod 600 $random_seed
+ * dd if=/proc/sys/kernel/random/derive_seed of=$random_seed
+ *
+ * The Fortuna PRNG as described in Practical Cryptography is implemented here.
+ *
+ * Pseudo-code follows.
+ *
+create_entropy_pool(r)
+ - create an entropy pool in "r"
+
+ r.pool0_len = 0;
+ r.reseed_count = 0;
+ r.derive_count = 0;
+ r.digestsize = // digest size for our hash
+ r.blocksize = // block size for our cipher
+ r.keysize = // key size for our cipher
+ for (i=0; i&lt;32; i++) {
+ crypto_digest_init(r.pool[i]);
+ }
+ memset(r.key, 0, r.keysize);
+ crypto_cipher_setkey(r.cipher, r.key, r.keysize);
+
+add_entropy_words(r, in, nwords)
+ - mix 32bit word array "in" which is "nwords" long into pool "r"
+
+ crypto_digest_update(r.pool[i], in, nwords*sizeof(in[0]));
+ if (r.pool_index == 0)
+ r.pool0_len += nwords*sizeof(in[0]);
+ r.pool_index = r.pool_index + 1 mod (2number of pools - 1)
+
+random_reseed(r)
+ - reseed the key from the pooling system
+
+ r.reseed_count++;
+
+ crypto_digest_init(hash);
+ crypto_digest_update(hash, r.key, r.keysize);
+
+ for (i=0; i&lt;32; i++) {
+ if (2i is a factor of r.reseed_count) {
+ crypto_digest_final(r.pool[i], tmp);
+ crypto_digest_init(r.poo[i]);
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ // jlcooke: small change from Ferguson
+ crypto_digest_update(r.pool[i], tmp, r.digestsize);
+ }
+ }
+
+ crypto_digest_final(hash, tmp);
+ crypto_cipher_setkey(r.cipher, tmp, r.keysize);
+ r.ctrValue = r.ctrValue + 1 mod (2number of pools - 1)
+
+extract_entropy(r, buf, nbytes, flags)
+ - fill byte array "buf" with "nbytes" of random data from entropy pool "r"
+
+ random_reseed(r);
+ r.pool0_len = 0;
+
+ while (nbytes &gt; 0) {
+ crypto_cipher_encrypt(r.cipher, tmp, r.ctrValue, r.blocksize);
+ r.ctrValue++; // modulo 2r.blocksize/8
+
+ //
+ // Copy r.blocksize of tmp to the user
+ // Unless nbytes is less than r.blocksize, in which case only copy nbytes
+ //
+
+ nbytes -= r.blocksize;
+ }
+
+ // generate a new key
+ crypto_cipher_encrypt(r.cipher, r.key, r.ctrValue, r.blocksize);
+ crypto_cipher_setkey(r.cipher, r.key, r.keysize);
+
+derive_pool(r, buf)
+ - Fill "buf" with the output from a 1-way transformation of all 32-pools
+
+ memset(tmp, 0, r.digestsize);
+ r.pool0_len = 0;
+
+ for (i=0; i&lt;32; i++) {
+ crypto_digest_init(hash);
+
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ crypto_digest_final(r.pool[i], tmp);
+ crypto_digest_init(r.pool[i]);
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ crypto_digest_update(hash, r.derive_count, sizeof(r.derive_count));
+
+ crypto_digest_final(hash, tmp);
+
+ // Replace all 0x00 in "tmp" with "0x01" because the API to return a byte
+ // array does not exist. Only a "return string" API is provided. This
+ // reduces the effective entropy of the output by 0.39%.
+ //
+
+ memcpy(&amp;buf[i*r.digestsize], tmp, r.digestsize);
+ r.derive_count++;
+ }
+ *
+ * Draft Security Statement/Analysis (Jean-Luc Cooke <jlcooke@certainkey.com>)
+ *
+ * The Fortuna PRNG is resilliant to all known and preventable PRNG attacks.
+ * Proof of strength to these attacks can be done by reduction to the security
+ * of the underlying cryptographic primitives.
+ * * H = HASH(M)
+ * + M={0,1}^Mlen 0 <= Mlen < infinity
+ * + H={0,1}^Hlen 256 <= Hlen
+ * * C = ENCRYPT(K,M)
+ * + K={0,1}^Klen 256 <= Klen
+ * + M={0,1}^Mlen Mlen = 128
+ * + C={0,1}^Clen Clen = 128
+ *
+ * - Invertability of the output function
+ * The state of the output function Output[i] = ENCRYPT(KEY, CTR++) is {KEY,CTR}
+ * To recover the state {KEY,CTR} the attacker must be able to mount a known-plaintext
+ * or a known-ciphertext attack on the block cipher C=ENCRYPT(K,M) with N blocks.
+ * N = ReseedIntervalInSeconds * OutputRateInBytesPerSecond / BytesPerBlock
+ * AES256 in CTR is secure from known-plaintext/ciphertext key recovery attacks with
+ * N < 2^128
+ * However, After 2^64 blocks (2^71 bits) an attacker would have a 0.5 chance to guessing
+ * the next 128bit output. N <<< 2^64
+ *
+ * - Invertability of the pool mixing function
+ * The pool mixing function H' = HASH(H' || M) is said to be non-inveretable
+ * if H=HASH(MSG) is invertable.
+ * There have been no invertability discoveries in SHA-256.
+ *
+ * - Manipulating pool mixing
+ * An attack who has access to one or all of the entropy event sources may be able to
+ * input mallicious event data to alter any one of the pool states into a degenerate
+ * state. This requires that the underlying H=HASH(MSG) function is suseptible to
+ * a 2nd pre-image attack. SHA-256 has no such known attacks.
+ */
+
+/*
* (now, with legal B.S. out of the way.....)
*
* This routine gathers environmental noise from device drivers, etc.,
@@ -254,94 +430,43 @@
#include <linux/interrupt.h>
#include <linux/spinlock.h>
#include <linux/percpu.h>
+#include <linux/crypto.h>
+#include <../crypto/internal.h>

+#include <asm/scatterlist.h>
#include <asm/processor.h>
#include <asm/uaccess.h>
#include <asm/irq.h>
#include <asm/io.h>

-/*
- * Configuration information
- */
-#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 be enough to do a significant reseed.
- */
-static int random_read_wakeup_thresh = 64;
+#if 0
+ #define DEBUG_PRINTK printk
+#else
+ #define DEBUG_PRINTK debug_printk
+static inline void debug_printk(const char *a, ...) {}
+#endif

/*
- * 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.
+ * Configuration information
*/
-static int random_write_wakeup_thresh = 128;
+#define BATCH_ENTROPY_SIZE 512 /* how many events do we buffer? BATCH_ENTROPY_SIZE/2 == how many we need before batch-submitting them */
+#define RANDOM_RESEED_INTERVAL 600 /* reseed the PRNG output state every 5mins */
+#define RANDOM_DEFAULT_CIPHER_ALGO "aes"
+#define RANDOM_DEFAULT_DIGEST_ALGO "sha256"
+
+#define DEFAULT_POOL_NUMBER 5 /* 2^{5} = 32 pools */
+#define MAXIMUM_POOL_NUMBER DEFAULT_POOL_NUMBER
+#define MINIMUM_POOL_NUMBER 2 /* 2^{2} = 4 pools */
+#define USE_SHA256
+#define RANDOM_MAX_DIGEST_SIZE 64 /* SHA512/WHIRLPOOL have 64bytes == 512 bits */
+#define RANDOM_MAX_BLOCK_SIZE 16 /* AES256 has 16byte blocks == 128 bits */
+#define RANDOM_MAX_KEY_SIZE 32 /* AES256 has 32byte keys == 256 bits */
+#define USE_AES256

/*
- * When the input pool goes over trickle_thresh, start dropping most
- * samples to avoid wasting CPU time and reduce lock contention.
+ * Throttle mouse/keyboard/disk/interrupt entropy input to only add after this many jiffies/rdtsc counts
*/
-
-static int trickle_thresh = DEFAULT_POOL_SIZE * 7;
-
-static DEFINE_PER_CPU(int, trickle_count) = 0;
-
-/*
- * 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 },
-};
-
-#define POOLBITS poolwords*32
-#define POOLBYTES poolwords*4
+#define RANDOM_INPUT_THROTTLE 1000

/*
* For the purposes of better mixing, we use the CRC-32 polynomial as
@@ -399,8 +524,10 @@
/*
* Static global variables
*/
+static int random_entropy_count; // jlc & cam have been together for 5 and 2/3 years as of the time this was written;
+static int random_read_wakeup_thresh = 0; // ignored now.
+static int random_write_wakeup_thresh = 0; // ignored now.
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);

@@ -419,27 +546,6 @@
*****************************************************************/

/*
- * Unfortunately, while the GCC optimizer for the i386 understands how
- * to optimize a static rotate left of x bits, it doesn't know how to
- * deal with a variable rotate of x bits. So we use a bit of asm magic.
- */
-#if (!defined (__i386__))
-static inline __u32 rotate_left(int i, __u32 word)
-{
- return (word << i) | (word >> (32 - i));
-
-}
-#else
-static inline __u32 rotate_left(int i, __u32 word)
-{
- __asm__("roll %%cl,%0"
- :"=r" (word)
- :"0" (word),"c" (i));
- return word;
-}
-#endif
-
-/*
* More asm magic....
*
* For entropy estimation, we need to do an integral base 2
@@ -490,15 +596,28 @@
**********************************************************************/

struct entropy_store {
- /* mostly-read data: */
- struct poolinfo poolinfo;
- __u32 *pool;
+ const char *digestAlgo;
+ unsigned int digestsize;
+ struct crypto_tfm *pools[1<<MAXIMUM_POOL_NUMBER];
+ /* optional, handy for statistics */
+ unsigned int pools_bytes[1<<MAXIMUM_POOL_NUMBER];
+
+ const char *cipherAlgo;
+ unsigned char key[RANDOM_MAX_DIGEST_SIZE]; /* the key */
+ unsigned int keysize;
+ unsigned char iv[16]; /* the CTR value */
+ unsigned int blocksize;
+ struct crypto_tfm *cipher;
+
+ unsigned int pool_number; /* 2^pool_number # of pools */
+ unsigned int pool_index; /* current pool to add into */
+ unsigned int pool0_len; /* size of the first pool */
+ unsigned int reseed_count; /* number of time we have reset */
+ struct crypto_tfm *reseedHash; /* digest used during random_reseed() */
+ struct crypto_tfm *networkCipher; /* cipher used for network randomness */
+ char networkCipher_ready; /* flag indicating if networkCipher has been seeded */

- /* read-write data: */
spinlock_t lock ____cacheline_aligned_in_smp;
- unsigned add_ptr;
- int entropy_count;
- int input_rotate;
};

/*
@@ -507,61 +626,75 @@
*
* Returns an negative error if there is a problem.
*/
-static int create_entropy_store(int size, struct entropy_store **ret_bucket)
+static int create_entropy_store(int pool_number_arg, struct entropy_store **ret_bucket)
{
struct entropy_store *r;
- struct poolinfo *p;
- int poolwords;
-
- poolwords = (size + 3) / 4; /* Convert bytes->words */
- /* The pool size must be a multiple of 16 32-bit words */
- poolwords = ((poolwords + 15) / 16) * 16;
+ unsigned long pool_number;
+ int keysize, i, j;

- for (p = poolinfo_table; p->poolwords; p++) {
- if (poolwords == p->poolwords)
- break;
- }
- if (p->poolwords == 0)
- return -EINVAL;
+ pool_number = pool_number_arg;
+ if (pool_number < MINIMUM_POOL_NUMBER)
+ pool_number = MINIMUM_POOL_NUMBER;

r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
- if (!r)
+ if (!r) {
return -ENOMEM;
+ }

memset (r, 0, sizeof(struct entropy_store));
- r->poolinfo = *p;
+ r->pool_number = pool_number;
+ r->digestAlgo = RANDOM_DEFAULT_DIGEST_ALGO;

- r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
- if (!r->pool) {
- kfree(r);
- return -ENOMEM;
+DEBUG_PRINTK("create_entropy_store() pools=%u index=%u\n", 1<<pool_number, r->pool_index);
+ for (i=0; i<(1<<pool_number); i++) {
+DEBUG_PRINTK("create_entropy_store() i=%i index=%u\n", i, r->pool_index);
+ r->pools[i] = crypto_alloc_tfm(r->digestAlgo, 0);
+ if (r->pools[i] == NULL) {
+ for (j=0; j<i; j++) {
+ if (r->pools[j] != NULL) {
+ kfree(r->pools[j]);
+ }
+ }
+ kfree(r);
+ return -ENOMEM;
+ }
+ crypto_digest_init( r->pools[i] );
}
- memset(r->pool, 0, POOLBYTES);
r->lock = SPIN_LOCK_UNLOCKED;
*ret_bucket = r;
+
+ r->cipherAlgo = RANDOM_DEFAULT_CIPHER_ALGO;
+ if ((r->cipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
+
+ /* If the HASH's output is greater then the cipher's keysize, truncate to the
+ * cipher's keysize */
+ keysize = crypto_tfm_alg_max_keysize(r->cipher);
+ r->digestsize = crypto_tfm_alg_digestsize(r->pools[0]);
+ r->blocksize = crypto_tfm_alg_blocksize(r->cipher);
+
+ r->keysize = (keysize < r->digestsize) ? keysize : r->digestsize;
+
+ if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+ return -EINVAL;
+ }
+
+ /* digest used duing random-reseed() */
+ if ((r->reseedHash=crypto_alloc_tfm(r->digestAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
+ /* cipher used for network randomness, init to key={zerovector} for now */
+ if ((r->networkCipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
+
return 0;
}

-/* Clear the entropy pool and associated counters. */
-static void clear_entropy_store(struct entropy_store *r)
-{
- r->add_ptr = 0;
- r->entropy_count = 0;
- r->input_rotate = 0;
- memset(r->pool, 0, r->poolinfo.POOLBYTES);
-}
-#ifdef CONFIG_SYSCTL
-static void free_entropy_store(struct entropy_store *r)
-{
- if (r->pool)
- kfree(r->pool);
- kfree(r);
-}
-#endif
/*
* 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.
+ * update the entropy estimate.
*
* The pool is stirred with a primitive polynomial of the appropriate
* degree, and then twisted. We twist by three bits at a time because
@@ -571,87 +704,33 @@
static void add_entropy_words(struct entropy_store *r, const __u32 *in,
int nwords)
{
- static __u32 const twist_table[8] = {
- 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
- 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
- unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5;
- int new_rotate, input_rotate;
- int wordmask = r->poolinfo.poolwords - 1;
- __u32 w, next_w;
unsigned long flags;
+ struct scatterlist sg[1];
+ static unsigned int totalBytes=0;

- /* Taps are constant, so we can load them without holding r->lock. */
- tap1 = r->poolinfo.tap1;
- tap2 = r->poolinfo.tap2;
- tap3 = r->poolinfo.tap3;
- tap4 = r->poolinfo.tap4;
- tap5 = r->poolinfo.tap5;
- next_w = *in++;
-
- spin_lock_irqsave(&r->lock, flags);
- prefetch_range(r->pool, wordmask);
- input_rotate = r->input_rotate;
- add_ptr = r->add_ptr;
-
- while (nwords--) {
- w = rotate_left(input_rotate, next_w);
- if (nwords > 0)
- next_w = *in++;
- i = add_ptr = (add_ptr - 1) & wordmask;
- /*
- * 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 = input_rotate + 14;
- if (i)
- new_rotate = input_rotate + 7;
- input_rotate = new_rotate & 31;
-
- /* XOR in the various taps */
- 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->pool[i];
- r->pool[i] = (w >> 3) ^ twist_table[w & 7];
+ if (r == NULL) {
+ return;
}

- r->input_rotate = input_rotate;
- r->add_ptr = add_ptr;
-
- spin_unlock_irqrestore(&r->lock, flags);
-}
+ spin_lock_irqsave(&r->lock, flags);

-/*
- * Credit (or debit) the entropy store with n bits of entropy
- */
-static void credit_entropy_store(struct entropy_store *r, int nbits)
-{
- unsigned long flags;
+ totalBytes += nwords * sizeof(__u32);
+ r->pools_bytes[r->pool_index] += nwords * sizeof(__u32);

- spin_lock_irqsave(&r->lock, flags);
+ sg[0].page = virt_to_page(in);
+ sg[0].offset = offset_in_page(in);
+ sg[0].length = nwords*sizeof(__u32);
+ crypto_digest_update(r->pools[r->pool_index], sg, 1);

- if (r->entropy_count + nbits < 0) {
- DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
- r->entropy_count, nbits);
- r->entropy_count = 0;
- } else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) {
- r->entropy_count = r->poolinfo.POOLBITS;
- } else {
- r->entropy_count += nbits;
- if (nbits)
- DEBUG_ENT("%04d %04d : added %d bits to %s\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- nbits,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown");
+ if (r->pool_index == 0) {
+ r->pool0_len += nwords*sizeof(__u32);
}

+ /* idx = (idx + 1) mod ( (2^N)-1 ) */
+ r->pool_index = (r->pool_index + 1) & ((1<<r->pool_number)-1);
+
spin_unlock_irqrestore(&r->lock, flags);
+DEBUG_PRINTK("0 add_entropy_words() nwords=%u pool[i].bytes=%u total=%u\n", nwords, r->pools_bytes[r->pool_index], totalBytes);
}

/**********************************************************************
@@ -668,10 +747,10 @@
};

static struct sample *batch_entropy_pool, *batch_entropy_copy;
-static int batch_head, batch_tail;
+static int batch_head, batch_tail;
static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED;

-static int batch_max;
+static int batch_max;
static void batch_entropy_process(void *private_);
static DECLARE_WORK(batch_work, batch_entropy_process, NULL);

@@ -703,19 +782,20 @@
int new;
unsigned long flags;

- if (!batch_max)
+ if (!batch_max) {
return;
+ }

spin_lock_irqsave(&batch_lock, flags);

batch_entropy_pool[batch_head].data[0] = a;
batch_entropy_pool[batch_head].data[1] = b;
- batch_entropy_pool[batch_head].credit = num;
+ batch_entropy_pool[batch_head].credit = 0;

if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) {
/*
- * Schedule it for the next timer tick:
- */
+ * Schedule it for the next timer tick:
+ */
schedule_delayed_work(&batch_work, 1);
}

@@ -738,8 +818,7 @@
*/
static void batch_entropy_process(void *private_)
{
- struct entropy_store *r = (struct entropy_store *) private_, *p;
- int max_entropy = r->poolinfo.POOLBITS;
+ struct entropy_store *r = (struct entropy_store *) private_;
unsigned head, tail;

/* Mixing into the pool is expensive, so copy over the batch
@@ -750,7 +829,7 @@
spin_lock_irq(&batch_lock);

memcpy(batch_entropy_copy, batch_entropy_pool,
- batch_max*sizeof(struct sample));
+ batch_max*sizeof(struct sample));

head = batch_head;
tail = batch_tail;
@@ -758,39 +837,19 @@

spin_unlock_irq(&batch_lock);

- p = r;
while (head != tail) {
- if (r->entropy_count >= max_entropy) {
- r = (r == sec_random_state) ? random_state :
- sec_random_state;
- max_entropy = r->poolinfo.POOLBITS;
- }
add_entropy_words(r, batch_entropy_copy[tail].data, 2);
- credit_entropy_store(r, batch_entropy_copy[tail].credit);
tail = (tail+1) & (batch_max-1);
}
- if (p->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];
-
/*
* This function adds entropy to the entropy "pool" by using timing
* delays. It uses the timer_rand_state structure to make an estimate
@@ -803,16 +862,10 @@
* are used for a high-resolution timer.
*
*/
-static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
+static void add_timer_randomness(unsigned num)
{
- __u32 time;
- __s32 delta, delta2, delta3;
- int entropy = 0;
-
- /* if over the trickle threshold, use only 1 in 4096 samples */
- if ( random_state->entropy_count > trickle_thresh &&
- (__get_cpu_var(trickle_count)++ & 0xfff))
- return;
+ static __u32 lasttime=0;
+ __u32 time;

#if defined (__i386__) || defined (__x86_64__)
if (cpu_has_tsc) {
@@ -822,480 +875,57 @@
} else {
time = jiffies;
}
-#elif defined (__sparc_v9__)
- unsigned long tick = tick_ops->get_tick();
-
- time = (unsigned int) tick;
- num ^= (tick >> 32UL);
#else
time = jiffies;
#endif

- /*
- * 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 (!state->dont_count_entropy) {
- delta = time - state->last_time;
- state->last_time = time;
-
- delta2 = delta - state->last_delta;
- state->last_delta = delta;
-
- delta3 = delta2 - state->last_delta2;
- state->last_delta2 = delta2;
-
- if (delta < 0)
- delta = -delta;
- if (delta2 < 0)
- delta2 = -delta2;
- if (delta3 < 0)
- delta3 = -delta3;
- if (delta > delta2)
- delta = delta2;
- if (delta > delta3)
- delta = delta3;
-
- /*
- * delta is now minimum absolute delta.
- * Round down by 1 bit on general principles,
- * and limit entropy entimate to 12 bits.
- */
- delta >>= 1;
- delta &= (1 << 12) - 1;
-
- entropy = int_ln_12bits(delta);
+ /* jlcooke: ToDo: Throttle here? */
+ /* Throttle our input to add_entropy_words() */
+ if ((time-lasttime) < RANDOM_INPUT_THROTTLE) {
+ return;
}
- batch_entropy_store(num, time, entropy);
+ lasttime = time;
+
+ batch_entropy_store(num, time, 0);
}

void add_keyboard_randomness(unsigned char scancode)
{
- static unsigned char last_scancode;
- /* ignore autorepeat (multiple key down w/o key up) */
- if (scancode != last_scancode) {
- last_scancode = scancode;
- add_timer_randomness(&keyboard_timer_state, scancode);
- }
+ /* jlcooke: we don't care about auto-repeats, they can't hurt us */
+ add_timer_randomness(scancode);
}

EXPORT_SYMBOL(add_keyboard_randomness);

void add_mouse_randomness(__u32 mouse_data)
{
- add_timer_randomness(&mouse_timer_state, mouse_data);
+ add_timer_randomness(mouse_data);
}

EXPORT_SYMBOL(add_mouse_randomness);

void add_interrupt_randomness(int irq)
{
- if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
+ if (irq >= NR_IRQS)
return;

- add_timer_randomness(irq_timer_state[irq], 0x100+irq);
+ /* jlcooke: no need to add 0x100 ... not random! :P */
+ add_timer_randomness(irq);
}

EXPORT_SYMBOL(add_interrupt_randomness);

void add_disk_randomness(struct gendisk *disk)
{
- if (!disk || !disk->random)
+ if (!disk)
return;
/* first major is 1, so we get >= 0x200 here */
- add_timer_randomness(disk->random, 0x100+MKDEV(disk->major, disk->first_minor));
+ /* jlcooke: adding 0x100 is useless */
+ add_timer_randomness(MKDEV(disk->major, disk->first_minor));
}

EXPORT_SYMBOL(add_disk_randomness);

-/******************************************************************
- *
- * Hash function definition
- *
- *******************************************************************/
-
-/*
- * This chunk of code defines a function
- * void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
- * __u32 const data[16])
- *
- * The function hashes the input data to produce a digest in the first
- * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE
- * more words for internal purposes. (This buffer is exported so the
- * caller can wipe it once rather than this code doing it each call,
- * and tacking it onto the end of the digest[] array is the quick and
- * dirty way of doing it.)
- *
- * It so happens that MD5 and SHA share most of the initial vector
- * used to initialize the digest[] array before the first call:
- * 1) 0x67452301
- * 2) 0xefcdab89
- * 3) 0x98badcfe
- * 4) 0x10325476
- * 5) 0xc3d2e1f0 (SHA only)
- *
- * For /dev/random purposes, the length of the data being hashed is
- * fixed in length, so appending a bit count in the usual way is not
- * cryptographically necessary.
- */
-
-#ifdef USE_SHA
-
-#define HASH_BUFFER_SIZE 5
-#define HASH_EXTRA_SIZE 80
-#define HASH_TRANSFORM SHATransform
-
-/* Various size/speed tradeoffs are available. Choose 0..3. */
-#define SHA_CODE_SIZE 0
-
-/*
- * SHA transform algorithm, taken from code written by Peter Gutmann,
- * and placed in the public domain.
- */
-
-/* The SHA f()-functions. */
-
-#define f1(x,y,z) ( z ^ (x & (y^z)) ) /* Rounds 0-19: x ? y : z */
-#define f2(x,y,z) (x ^ y ^ z) /* Rounds 20-39: XOR */
-#define f3(x,y,z) ( (x & y) + (z & (x ^ y)) ) /* Rounds 40-59: majority */
-#define f4(x,y,z) (x ^ y ^ z) /* Rounds 60-79: XOR */
-
-/* The SHA Mysterious Constants */
-
-#define K1 0x5A827999L /* Rounds 0-19: sqrt(2) * 2^30 */
-#define K2 0x6ED9EBA1L /* Rounds 20-39: sqrt(3) * 2^30 */
-#define K3 0x8F1BBCDCL /* Rounds 40-59: sqrt(5) * 2^30 */
-#define K4 0xCA62C1D6L /* Rounds 60-79: sqrt(10) * 2^30 */
-
-#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
-
-#define subRound(a, b, c, d, e, f, k, data) \
- ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
-
-
-static void SHATransform(__u32 digest[85], __u32 const data[16])
-{
- __u32 A, B, C, D, E; /* Local vars */
- __u32 TEMP;
- int i;
-#define W (digest + HASH_BUFFER_SIZE) /* Expanded data array */
-
- /*
- * Do the preliminary expansion of 16 to 80 words. Doing it
- * out-of-line line this is faster than doing it in-line on
- * register-starved machines like the x86, and not really any
- * slower on real processors.
- */
- memcpy(W, data, 16*sizeof(__u32));
- for (i = 0; i < 64; i++) {
- TEMP = W[i] ^ W[i+2] ^ W[i+8] ^ W[i+13];
- W[i+16] = ROTL(1, TEMP);
- }
-
- /* Set up first buffer and local data buffer */
- A = digest[ 0 ];
- B = digest[ 1 ];
- C = digest[ 2 ];
- D = digest[ 3 ];
- E = digest[ 4 ];
-
- /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */
-#if SHA_CODE_SIZE == 0
- /*
- * Approximately 50% of the speed of the largest version, but
- * takes up 1/16 the space. Saves about 6k on an i386 kernel.
- */
- for (i = 0; i < 80; i++) {
- if (i < 40) {
- if (i < 20)
- TEMP = f1(B, C, D) + K1;
- else
- TEMP = f2(B, C, D) + K2;
- } else {
- if (i < 60)
- TEMP = f3(B, C, D) + K3;
- else
- TEMP = f4(B, C, D) + K4;
- }
- TEMP += ROTL(5, A) + E + W[i];
- E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
- }
-#elif SHA_CODE_SIZE == 1
- for (i = 0; i < 20; i++) {
- TEMP = f1(B, C, D) + K1 + ROTL(5, A) + E + W[i];
- E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
- }
- for (; i < 40; i++) {
- TEMP = f2(B, C, D) + K2 + ROTL(5, A) + E + W[i];
- E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
- }
- for (; i < 60; i++) {
- TEMP = f3(B, C, D) + K3 + ROTL(5, A) + E + W[i];
- E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
- }
- for (; i < 80; i++) {
- TEMP = f4(B, C, D) + K4 + ROTL(5, A) + E + W[i];
- E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
- }
-#elif SHA_CODE_SIZE == 2
- for (i = 0; i < 20; i += 5) {
- subRound( A, B, C, D, E, f1, K1, W[ i ] );
- subRound( E, A, B, C, D, f1, K1, W[ i+1 ] );
- subRound( D, E, A, B, C, f1, K1, W[ i+2 ] );
- subRound( C, D, E, A, B, f1, K1, W[ i+3 ] );
- subRound( B, C, D, E, A, f1, K1, W[ i+4 ] );
- }
- for (; i < 40; i += 5) {
- subRound( A, B, C, D, E, f2, K2, W[ i ] );
- subRound( E, A, B, C, D, f2, K2, W[ i+1 ] );
- subRound( D, E, A, B, C, f2, K2, W[ i+2 ] );
- subRound( C, D, E, A, B, f2, K2, W[ i+3 ] );
- subRound( B, C, D, E, A, f2, K2, W[ i+4 ] );
- }
- for (; i < 60; i += 5) {
- subRound( A, B, C, D, E, f3, K3, W[ i ] );
- subRound( E, A, B, C, D, f3, K3, W[ i+1 ] );
- subRound( D, E, A, B, C, f3, K3, W[ i+2 ] );
- subRound( C, D, E, A, B, f3, K3, W[ i+3 ] );
- subRound( B, C, D, E, A, f3, K3, W[ i+4 ] );
- }
- for (; i < 80; i += 5) {
- subRound( A, B, C, D, E, f4, K4, W[ i ] );
- subRound( E, A, B, C, D, f4, K4, W[ i+1 ] );
- subRound( D, E, A, B, C, f4, K4, W[ i+2 ] );
- subRound( C, D, E, A, B, f4, K4, W[ i+3 ] );
- subRound( B, C, D, E, A, f4, K4, W[ i+4 ] );
- }
-#elif SHA_CODE_SIZE == 3 /* Really large version */
- subRound( A, B, C, D, E, f1, K1, W[ 0 ] );
- subRound( E, A, B, C, D, f1, K1, W[ 1 ] );
- subRound( D, E, A, B, C, f1, K1, W[ 2 ] );
- subRound( C, D, E, A, B, f1, K1, W[ 3 ] );
- subRound( B, C, D, E, A, f1, K1, W[ 4 ] );
- subRound( A, B, C, D, E, f1, K1, W[ 5 ] );
- subRound( E, A, B, C, D, f1, K1, W[ 6 ] );
- subRound( D, E, A, B, C, f1, K1, W[ 7 ] );
- subRound( C, D, E, A, B, f1, K1, W[ 8 ] );
- subRound( B, C, D, E, A, f1, K1, W[ 9 ] );
- subRound( A, B, C, D, E, f1, K1, W[ 10 ] );
- subRound( E, A, B, C, D, f1, K1, W[ 11 ] );
- subRound( D, E, A, B, C, f1, K1, W[ 12 ] );
- subRound( C, D, E, A, B, f1, K1, W[ 13 ] );
- subRound( B, C, D, E, A, f1, K1, W[ 14 ] );
- subRound( A, B, C, D, E, f1, K1, W[ 15 ] );
- subRound( E, A, B, C, D, f1, K1, W[ 16 ] );
- subRound( D, E, A, B, C, f1, K1, W[ 17 ] );
- subRound( C, D, E, A, B, f1, K1, W[ 18 ] );
- subRound( B, C, D, E, A, f1, K1, W[ 19 ] );
-
- subRound( A, B, C, D, E, f2, K2, W[ 20 ] );
- subRound( E, A, B, C, D, f2, K2, W[ 21 ] );
- subRound( D, E, A, B, C, f2, K2, W[ 22 ] );
- subRound( C, D, E, A, B, f2, K2, W[ 23 ] );
- subRound( B, C, D, E, A, f2, K2, W[ 24 ] );
- subRound( A, B, C, D, E, f2, K2, W[ 25 ] );
- subRound( E, A, B, C, D, f2, K2, W[ 26 ] );
- subRound( D, E, A, B, C, f2, K2, W[ 27 ] );
- subRound( C, D, E, A, B, f2, K2, W[ 28 ] );
- subRound( B, C, D, E, A, f2, K2, W[ 29 ] );
- subRound( A, B, C, D, E, f2, K2, W[ 30 ] );
- subRound( E, A, B, C, D, f2, K2, W[ 31 ] );
- subRound( D, E, A, B, C, f2, K2, W[ 32 ] );
- subRound( C, D, E, A, B, f2, K2, W[ 33 ] );
- subRound( B, C, D, E, A, f2, K2, W[ 34 ] );
- subRound( A, B, C, D, E, f2, K2, W[ 35 ] );
- subRound( E, A, B, C, D, f2, K2, W[ 36 ] );
- subRound( D, E, A, B, C, f2, K2, W[ 37 ] );
- subRound( C, D, E, A, B, f2, K2, W[ 38 ] );
- subRound( B, C, D, E, A, f2, K2, W[ 39 ] );
-
- subRound( A, B, C, D, E, f3, K3, W[ 40 ] );
- subRound( E, A, B, C, D, f3, K3, W[ 41 ] );
- subRound( D, E, A, B, C, f3, K3, W[ 42 ] );
- subRound( C, D, E, A, B, f3, K3, W[ 43 ] );
- subRound( B, C, D, E, A, f3, K3, W[ 44 ] );
- subRound( A, B, C, D, E, f3, K3, W[ 45 ] );
- subRound( E, A, B, C, D, f3, K3, W[ 46 ] );
- subRound( D, E, A, B, C, f3, K3, W[ 47 ] );
- subRound( C, D, E, A, B, f3, K3, W[ 48 ] );
- subRound( B, C, D, E, A, f3, K3, W[ 49 ] );
- subRound( A, B, C, D, E, f3, K3, W[ 50 ] );
- subRound( E, A, B, C, D, f3, K3, W[ 51 ] );
- subRound( D, E, A, B, C, f3, K3, W[ 52 ] );
- subRound( C, D, E, A, B, f3, K3, W[ 53 ] );
- subRound( B, C, D, E, A, f3, K3, W[ 54 ] );
- subRound( A, B, C, D, E, f3, K3, W[ 55 ] );
- subRound( E, A, B, C, D, f3, K3, W[ 56 ] );
- subRound( D, E, A, B, C, f3, K3, W[ 57 ] );
- subRound( C, D, E, A, B, f3, K3, W[ 58 ] );
- subRound( B, C, D, E, A, f3, K3, W[ 59 ] );
-
- subRound( A, B, C, D, E, f4, K4, W[ 60 ] );
- subRound( E, A, B, C, D, f4, K4, W[ 61 ] );
- subRound( D, E, A, B, C, f4, K4, W[ 62 ] );
- subRound( C, D, E, A, B, f4, K4, W[ 63 ] );
- subRound( B, C, D, E, A, f4, K4, W[ 64 ] );
- subRound( A, B, C, D, E, f4, K4, W[ 65 ] );
- subRound( E, A, B, C, D, f4, K4, W[ 66 ] );
- subRound( D, E, A, B, C, f4, K4, W[ 67 ] );
- subRound( C, D, E, A, B, f4, K4, W[ 68 ] );
- subRound( B, C, D, E, A, f4, K4, W[ 69 ] );
- subRound( A, B, C, D, E, f4, K4, W[ 70 ] );
- subRound( E, A, B, C, D, f4, K4, W[ 71 ] );
- subRound( D, E, A, B, C, f4, K4, W[ 72 ] );
- subRound( C, D, E, A, B, f4, K4, W[ 73 ] );
- subRound( B, C, D, E, A, f4, K4, W[ 74 ] );
- subRound( A, B, C, D, E, f4, K4, W[ 75 ] );
- subRound( E, A, B, C, D, f4, K4, W[ 76 ] );
- subRound( D, E, A, B, C, f4, K4, W[ 77 ] );
- subRound( C, D, E, A, B, f4, K4, W[ 78 ] );
- subRound( B, C, D, E, A, f4, K4, W[ 79 ] );
-#else
-#error Illegal SHA_CODE_SIZE
-#endif
-
- /* Build message digest */
- digest[ 0 ] += A;
- digest[ 1 ] += B;
- digest[ 2 ] += C;
- digest[ 3 ] += D;
- digest[ 4 ] += E;
-
- /* W is wiped by the caller */
-#undef W
-}
-
-#undef ROTL
-#undef f1
-#undef f2
-#undef f3
-#undef f4
-#undef K1
-#undef K2
-#undef K3
-#undef K4
-#undef subRound
-
-#else /* !USE_SHA - Use MD5 */
-
-#define HASH_BUFFER_SIZE 4
-#define HASH_EXTRA_SIZE 0
-#define HASH_TRANSFORM MD5Transform
-
-/*
- * MD5 transform algorithm, taken from code written by Colin Plumb,
- * and put into the public domain
- */
-
-/* The four core functions - F1 is optimized somewhat */
-
-/* #define F1(x, y, z) (x & y | ~x & z) */
-#define F1(x, y, z) (z ^ (x & (y ^ z)))
-#define F2(x, y, z) F1(z, x, y)
-#define F3(x, y, z) (x ^ y ^ z)
-#define F4(x, y, z) (y ^ (x | ~z))
-
-/* This is the central step in the MD5 algorithm. */
-#define MD5STEP(f, w, x, y, z, data, s) \
- ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x )
-
-/*
- * The core of the MD5 algorithm, this alters an existing MD5 hash to
- * reflect the addition of 16 longwords of new data. MD5Update blocks
- * the data and converts bytes into longwords for this routine.
- */
-static void MD5Transform(__u32 buf[HASH_BUFFER_SIZE], __u32 const in[16])
-{
- __u32 a, b, c, d;
-
- a = buf[0];
- b = buf[1];
- c = buf[2];
- d = buf[3];
-
- MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478, 7);
- MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12);
- MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17);
- MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22);
- MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf, 7);
- MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12);
- MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17);
- MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22);
- MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8, 7);
- MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12);
- MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17);
- MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22);
- MD5STEP(F1, a, b, c, d, in[12]+0x6b901122, 7);
- MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12);
- MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17);
- MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22);
-
- MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562, 5);
- MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340, 9);
- MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14);
- MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20);
- MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d, 5);
- MD5STEP(F2, d, a, b, c, in[10]+0x02441453, 9);
- MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14);
- MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20);
- MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6, 5);
- MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6, 9);
- MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14);
- MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20);
- MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905, 5);
- MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8, 9);
- MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14);
- MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20);
-
- MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942, 4);
- MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11);
- MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16);
- MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23);
- MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44, 4);
- MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11);
- MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16);
- MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23);
- MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6, 4);
- MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11);
- MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16);
- MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23);
- MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039, 4);
- MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11);
- MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16);
- MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23);
-
- MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244, 6);
- MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10);
- MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15);
- MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21);
- MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3, 6);
- MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10);
- MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15);
- MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21);
- MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f, 6);
- MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10);
- MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15);
- MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21);
- MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82, 6);
- MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10);
- MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15);
- MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21);
-
- buf[0] += a;
- buf[1] += b;
- buf[2] += c;
- buf[3] += d;
-}
-
-#undef F1
-#undef F2
-#undef F3
-#undef F4
-#undef MD5STEP
-
-#endif /* !USE_SHA */
-
/*********************************************************************
*
* Entropy extraction routines
@@ -1305,37 +935,63 @@
#define EXTRACT_ENTROPY_USER 1
#define EXTRACT_ENTROPY_SECONDARY 2
#define EXTRACT_ENTROPY_LIMIT 4
-#define TMP_BUF_SIZE (HASH_BUFFER_SIZE + HASH_EXTRA_SIZE)
-#define SEC_XFER_SIZE (TMP_BUF_SIZE*4)
+#define CRYPTO_MAX_BLOCK_SIZE 32

static ssize_t extract_entropy(struct entropy_store *r, void * buf,
size_t nbytes, int flags);

+static inline void increment_iv(unsigned char *IV, const unsigned int IVsize) {
+ unsigned int i;
+ for (i=0; i<IVsize; i++) {
+ if ( ++(IV[i]) ) {
+ break;
+ }
+ }
+}
+
/*
- * This utility inline function is responsible for transfering entropy
- * from the primary pool to the secondary extraction pool. We make
- * sure we pull enough for a 'catastrophic reseed'.
- */
-static inline void xfer_secondary_pool(struct entropy_store *r,
- size_t nbytes, __u32 *tmp)
-{
- if (r->entropy_count < nbytes * 8 &&
- r->entropy_count < r->poolinfo.POOLBITS) {
- int bytes = max_t(int, random_read_wakeup_thresh / 8,
- min_t(int, nbytes, TMP_BUF_SIZE));
-
- DEBUG_ENT("%04d %04d : going to reseed %s with %d bits "
- "(%d of %d requested)\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- r == sec_random_state ? "secondary" : "unknown",
- bytes * 8, nbytes * 8, r->entropy_count);
-
- bytes=extract_entropy(random_state, tmp, bytes,
- EXTRACT_ENTROPY_LIMIT);
- add_entropy_words(r, tmp, bytes);
- credit_entropy_store(r, bytes*8);
+ * Fortuna's Reseed is ...
+ */
+static void random_reseed(struct entropy_store *r) {
+ struct scatterlist sg[1];
+ int i;
+ unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+
+ r->reseed_count++;
+
+ crypto_digest_init(r->reseedHash);
+
+ sg[0].page = virt_to_page(r->key);
+ sg[0].offset = offset_in_page(r->key);
+ sg[0].length = r->keysize;
+ crypto_digest_update(r->reseedHash, sg, 1);
+
+#define TESTBIT(VAL, N)\
+ ( ((VAL) >> (N)) & 1 )
+ for (i=0; i<(1<<r->pool_number); i++) {
+ /* using pool[i] if r->reseed_count is divisible by 2^i
+ * since 2^0 == 1, we always use pool[0]
+ */
+ if ( (i==0) || TESTBIT(r->reseed_count,i)==0 ) {
+ crypto_digest_final(r->pools[i], tmp);
+
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = r->keysize;
+ crypto_digest_update(r->reseedHash, sg, 1);
+
+ crypto_digest_init(r->pools[i]);
+ crypto_digest_update(r->pools[i], sg, 1); /* should each pool carry it's past state forward? */
+ } else {
+ /* pool N can only be used once every 2^N times */
+ break;
+ }
}
+#undef TESTBIT
+
+ crypto_digest_final(r->reseedHash, r->key);
+ crypto_cipher_setkey(r->cipher, r->key, r->keysize);
+ increment_iv(r->iv, r->blocksize);
}

/*
@@ -1355,119 +1011,76 @@
size_t nbytes, int flags)
{
ssize_t ret, i;
- __u32 tmp[TMP_BUF_SIZE];
- __u32 x;
+ __u32 tmp[CRYPTO_MAX_BLOCK_SIZE];
unsigned long cpuflags;
+ struct scatterlist sgiv[1],
+ sgtmp[1];

-
- /* Redundant, but just in case... */
- if (r->entropy_count > r->poolinfo.POOLBITS)
- r->entropy_count = r->poolinfo.POOLBITS;
-
- if (flags & EXTRACT_ENTROPY_SECONDARY)
- xfer_secondary_pool(r, nbytes, tmp);
-
- /* Hold lock while accounting */
+ /* lock while we're reseeding */
spin_lock_irqsave(&r->lock, cpuflags);

- DEBUG_ENT("%04d %04d : trying to extract %d bits from %s\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- nbytes * 8,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown");
-
- if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8)
- nbytes = r->entropy_count / 8;
-
- if (r->entropy_count / 8 >= nbytes)
- r->entropy_count -= nbytes*8;
- else
- r->entropy_count = 0;
+ random_reseed(r);
+ r->pool0_len = 0;

- if (r->entropy_count < random_write_wakeup_thresh)
- wake_up_interruptible(&random_write_wait);
+ spin_unlock_irqrestore(&r->lock, cpuflags);

- DEBUG_ENT("%04d %04d : debiting %d bits from %s%s\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- nbytes * 8,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown",
- flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
+ /*
+ * don't output any data until we reseed at least once
+ * But this causes problems at boot-time. So weĺl assume since they
+ * don't wait to the PRNG to setup, they don't really new strong random
+ * data
+ */
+ /*
+ if (r->reseed_count == 0)
+ return 0;
+ */

- spin_unlock_irqrestore(&r->lock, cpuflags);
+ sgiv[0].page = virt_to_page(r->iv);
+ sgiv[0].offset = offset_in_page(r->iv);
+ sgiv[0].length = r->blocksize;
+ sgtmp[0].page = virt_to_page(tmp);
+ sgtmp[0].offset = offset_in_page(tmp);
+ sgtmp[0].length = r->blocksize;

ret = 0;
while (nbytes) {
- /*
- * Check if we need to break out or reschedule....
- */
- if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
- if (signal_pending(current)) {
- if (ret == 0)
- ret = -ERESTARTSYS;
- break;
- }
-
- DEBUG_ENT("%04d %04d : extract feeling sleepy (%d bytes left)\n",
- random_state->entropy_count,
- sec_random_state->entropy_count, nbytes);
-
- schedule();
-
- DEBUG_ENT("%04d %04d : extract woke up\n",
- random_state->entropy_count,
- sec_random_state->entropy_count);
- }
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+ increment_iv(r->iv, r->blocksize);

- /* Hash the pool to get the output */
- tmp[0] = 0x67452301;
- tmp[1] = 0xefcdab89;
- tmp[2] = 0x98badcfe;
- tmp[3] = 0x10325476;
-#ifdef USE_SHA
- tmp[4] = 0xc3d2e1f0;
-#endif
- /*
- * 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, 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];
- 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);
+ i = (nbytes < 16) ? nbytes : 16;
if (flags & EXTRACT_ENTROPY_USER) {
i -= copy_to_user(buf, (__u8 const *)tmp, i);
if (!i) {
ret = -EFAULT;
break;
}
- } else
+ } else {
memcpy(buf, (__u8 const *)tmp, i);
+ }
nbytes -= i;
buf += i;
ret += i;
}
+
+ /* generate a new key */
+ /* take into account the possibility that keysize >= blocksize */
+ for (i=0; i+r->blocksize<=r->keysize; i+=r->blocksize) {
+ sgtmp[0].page = virt_to_page( r->key+i );
+ sgtmp[0].offset = offset_in_page( r->key+i );
+ sgtmp[0].length = r->blocksize;
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, 1);
+ increment_iv(r->iv, r->blocksize);
+ }
+ sgtmp[0].page = virt_to_page( r->key+i );
+ sgtmp[0].offset = offset_in_page( r->key+i );
+ sgtmp[0].length = r->blocksize-i;
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, 1);
+ increment_iv(r->iv, r->blocksize);
+
+ if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+ return -EINVAL;
+ }

/* Wipe data just returned from memory */
memset(tmp, 0, sizeof(tmp));
@@ -1482,10 +1095,7 @@
*/
void get_random_bytes(void *buf, int nbytes)
{
- if (sec_random_state)
- extract_entropy(sec_random_state, (char *) buf, nbytes,
- EXTRACT_ENTROPY_SECONDARY);
- else if (random_state)
+ if (random_state)
extract_entropy(random_state, (char *) buf, nbytes, 0);
else
printk(KERN_NOTICE "get_random_bytes called before "
@@ -1500,57 +1110,16 @@
*
*********************************************************************/

-/*
- * 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);
- }
-}
-
static int __init rand_initialize(void)
{
- int i;
-
- if (create_entropy_store(DEFAULT_POOL_SIZE, &random_state))
- goto err;
- if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
- goto err;
- if (create_entropy_store(SECONDARY_POOL_SIZE, &sec_random_state))
+ if (create_entropy_store(DEFAULT_POOL_NUMBER, &random_state))
goto err;
- clear_entropy_store(random_state);
- clear_entropy_store(sec_random_state);
- init_std_data(random_state);
+ if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+ goto err;
+
#ifdef CONFIG_SYSCTL
sysctl_init_random(random_state);
#endif
- for (i = 0; i < NR_IRQS; i++)
- irq_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;
return 0;
err:
return -1;
@@ -1559,139 +1128,33 @@

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;
- }
+ /* we don't use timers anymore, we just use the current time */
}

void rand_initialize_disk(struct gendisk *disk)
{
- struct timer_rand_state *state;
-
- /*
- * 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));
- disk->random = state;
- }
-}
-
-static ssize_t
-random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
-{
- DECLARE_WAITQUEUE(wait, current);
- ssize_t n, retval = 0, count = 0;
-
- if (nbytes == 0)
- return 0;
-
- while (nbytes > 0) {
- n = nbytes;
- if (n > SEC_XFER_SIZE)
- n = SEC_XFER_SIZE;
-
- DEBUG_ENT("%04d %04d : reading %d bits, p: %d s: %d\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- n*8, random_state->entropy_count,
- sec_random_state->entropy_count);
-
- n = extract_entropy(sec_random_state, buf, n,
- EXTRACT_ENTROPY_USER |
- EXTRACT_ENTROPY_LIMIT |
- EXTRACT_ENTROPY_SECONDARY);
-
- DEBUG_ENT("%04d %04d : read got %d bits (%d still needed)\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- n*8, (nbytes-n)*8);
-
- if (n == 0) {
- if (file->f_flags & O_NONBLOCK) {
- retval = -EAGAIN;
- break;
- }
- if (signal_pending(current)) {
- retval = -ERESTARTSYS;
- break;
- }
-
- DEBUG_ENT("%04d %04d : sleeping?\n",
- random_state->entropy_count,
- sec_random_state->entropy_count);
-
- set_current_state(TASK_INTERRUPTIBLE);
- add_wait_queue(&random_read_wait, &wait);
-
- if (sec_random_state->entropy_count / 8 == 0)
- schedule();
-
- set_current_state(TASK_RUNNING);
- remove_wait_queue(&random_read_wait, &wait);
-
- DEBUG_ENT("%04d %04d : waking up\n",
- random_state->entropy_count,
- sec_random_state->entropy_count);
-
- continue;
- }
-
- if (n < 0) {
- retval = n;
- break;
- }
- count += n;
- buf += n;
- nbytes -= n;
- break; /* This break makes the device work */
- /* like a named pipe */
- }
-
- /*
- * If we gave the user some bytes, update the access time.
- */
- if (count)
- file_accessed(file);
-
- return (count ? count : retval);
+ /* we don't use timers anymore, we just use the current time */
}

static ssize_t
urandom_read(struct file * file, char __user * buf,
size_t nbytes, loff_t *ppos)
{
- return extract_entropy(sec_random_state, buf, nbytes,
+ return extract_entropy(random_state, buf, nbytes,
EXTRACT_ENTROPY_USER |
EXTRACT_ENTROPY_SECONDARY);
}

+static ssize_t
+random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
+{
+ return urandom_read(file, buf, nbytes, ppos);
+}
+
static unsigned int
random_poll(struct file *file, poll_table * wait)
{
- unsigned int mask;
-
- poll_wait(file, &random_read_wait, wait);
- poll_wait(file, &random_write_wait, wait);
- mask = 0;
- if (random_state->entropy_count >= random_read_wakeup_thresh)
- mask |= POLLIN | POLLRDNORM;
- if (random_state->entropy_count < random_write_wakeup_thresh)
- mask |= POLLOUT | POLLWRNORM;
- return mask;
+ return POLLIN | POLLRDNORM | POLLOUT | POLLWRNORM;
}

static ssize_t
@@ -1701,12 +1164,13 @@
int ret = 0;
size_t bytes;
__u32 buf[16];
- const char __user *p = buffer;
+ const char __user *p = buffer;
size_t c = count;

while (c > 0) {
bytes = min(c, sizeof(buf));

+DEBUG_PRINTK("random_write() %p, %p, %u\n", &buf, p, bytes);
bytes -= copy_from_user(&buf, p, bytes);
if (!bytes) {
ret = -EFAULT;
@@ -1730,67 +1194,25 @@
random_ioctl(struct inode * inode, struct file * file,
unsigned int cmd, unsigned long arg)
{
- int *tmp, size, ent_count;
- int __user *p = (int __user *)arg;
+ int size, ent_count;
+ int __user *p = (int __user *) arg;
int retval;
- unsigned long flags;

switch (cmd) {
case RNDGETENTCNT:
- ent_count = random_state->entropy_count;
- if (put_user(ent_count, p))
+ if (put_user(random_entropy_count, p))
return -EFAULT;
return 0;
case RNDADDTOENTCNT:
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- if (get_user(ent_count, p))
- return -EFAULT;
- credit_entropy_store(random_state, ent_count);
- /*
- * Wake up waiting processes if we have enough
- * entropy.
- */
- if (random_state->entropy_count >= random_read_wakeup_thresh)
- wake_up_interruptible(&random_read_wait);
+ /* entropy accounting removed. */
return 0;
case RNDGETPOOL:
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- if (get_user(size, p) ||
- put_user(random_state->poolinfo.poolwords, p++))
- return -EFAULT;
- if (size < 0)
- return -EFAULT;
- if (size > random_state->poolinfo.poolwords)
- size = random_state->poolinfo.poolwords;
-
- /* prepare to atomically snapshot pool */
-
- tmp = kmalloc(size * sizeof(__u32), GFP_KERNEL);
-
- if (!tmp)
- return -ENOMEM;
-
- spin_lock_irqsave(&random_state->lock, flags);
- ent_count = random_state->entropy_count;
- memcpy(tmp, random_state->pool, size * sizeof(__u32));
- spin_unlock_irqrestore(&random_state->lock, flags);
-
- if (!copy_to_user(p, tmp, size * sizeof(__u32))) {
- kfree(tmp);
- return -EFAULT;
- }
-
- kfree(tmp);
-
- if(put_user(ent_count, p++))
- return -EFAULT;
-
+ /* jlcooke: never get the raw pool!!! */
return 0;
case RNDADDENTROPY:
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
+ p = (int *) arg;
if (get_user(ent_count, p++))
return -EFAULT;
if (ent_count < 0)
@@ -1801,25 +1223,12 @@
size, &file->f_pos);
if (retval < 0)
return retval;
- credit_entropy_store(random_state, ent_count);
- /*
- * Wake up waiting processes if we have enough
- * entropy.
- */
- 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;
+ /* entropy accounting removed. */
return 0;
case RNDCLEARPOOL:
- /* Clear the entropy pool and associated counters. */
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- clear_entropy_store(random_state);
- init_std_data(random_state);
+ /* jlcooke: this is maddness! Never clear the entropy pool */
return 0;
default:
return -EINVAL;
@@ -1875,71 +1284,96 @@
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_work.data = new_store;
- free_entropy_store(old_store);
- return 0;
-}
-
static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
void __user *buffer, size_t *lenp, loff_t *ppos)
{
- int ret;
+ int ret;

- sysctl_poolsize = random_state->poolinfo.POOLBYTES;
+ if (write) {
+ // you can't change the poolsize, but we'll let you think you can for legacy reasons.
+ return 0;
+ }

+ sysctl_poolsize = (1<<random_state->pool_number) * random_state->pools[0]->__crt_alg->cra_ctxsize;
ret = proc_dointvec(table, write, filp, buffer, lenp, ppos);
- if (ret || !write ||
- (sysctl_poolsize == random_state->poolinfo.POOLBYTES))
- return ret;

- return change_poolsize(sysctl_poolsize);
+ return ret;
}

-static int poolsize_strategy(ctl_table *table, int __user *name, int nlen,
+static int poolsize_strategy(ctl_table *table, int *name, int nlen,
void __user *oldval, size_t __user *oldlenp,
void __user *newval, size_t newlen, void **context)
{
- int len;
-
- sysctl_poolsize = random_state->poolinfo.POOLBYTES;
+ /* you can't set a poolsize strtegy because it doesn't change in size anymore */
+ return 0;
+}

- /*
- * 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;
+static int proc_derive_seed(ctl_table *table, int write, struct file *filp,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ static unsigned char *hextab = "0123456789abcdef";
+ static unsigned int derive_count=0;
+ static unsigned char buf[(1<<MAXIMUM_POOL_NUMBER) * RANDOM_MAX_DIGEST_SIZE *8/4]; /* hex length of derived seed */
+ unsigned long flags;
+ ctl_table fake_table;
+ unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+ unsigned int i,j;
+ struct scatterlist sg[3];
+ int ret;
+ void *p;
+
+DEBUG_PRINTK("proc_derive_seed() 0\n");
+
+ spin_lock_irqsave(&random_state->lock, flags);
+ random_state->pool0_len = 0;
+
+ memset(buf, 0, random_state->pool_number * 2*random_state->digestsize);
+
+ /* the carry-state from pool to pool */
+ memset(tmp, 0, random_state->digestsize);
+
+ for (i=0; i<(1<<random_state->pool_number); i++) {
+ crypto_digest_init(random_state->reseedHash);
+
+ /* carry the digest from the previous output so a derive seed from a lightly seeded state is indistinguishavble from a heavily seeded one */
+ p = &tmp;
+ sg[0].page = virt_to_page(p);
+ sg[0].offset = offset_in_page(p);
+ sg[0].length = sizeof(tmp);
+
+ /* finalize and digest the i-th pool */
+ crypto_digest_final(random_state->pools[i], tmp);
+ crypto_digest_init(random_state->pools[i]);
+ p = &tmp;
+ sg[1].page = virt_to_page(p);
+ sg[1].offset = offset_in_page(p);
+ sg[1].length = sizeof(tmp);
+
+ /* digest in a counter to ensure the final hash can change even if the message does not */
+ p = &derive_count;
+ sg[2].page = virt_to_page(p);
+ sg[2].offset = offset_in_page(p);
+ sg[2].length = sizeof(derive_count);
+
+ crypto_digest_digest(random_state->reseedHash, sg, 3, tmp);
+ for (j=0; j<random_state->digestsize; j++) {
+ buf[2*(i*random_state->digestsize +j) ] = hextab[ (tmp[j] >> 4) & 0xf ];
+ buf[2*(i*random_state->digestsize +j)+1] = hextab[ (tmp[j] ) & 0xf ];
+ }
+ derive_count++;
}

- if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)
- return change_poolsize(sysctl_poolsize);
+ spin_unlock_irqrestore(&random_state->lock, flags);

- return 0;
+ fake_table.data = buf;
+ fake_table.maxlen = (1<<random_state->pool_number) * 2*random_state->digestsize;
+
+ ret = proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
+
+ return ret;
}

+
/*
* 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,
@@ -1975,7 +1409,7 @@
return proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
}

-static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
+static int uuid_strategy(ctl_table *table, int *name, int nlen,
void __user *oldval, size_t __user *oldlenp,
void __user *newval, size_t newlen, void **context)
{
@@ -2011,38 +1445,38 @@
.procname = "poolsize",
.data = &sysctl_poolsize,
.maxlen = sizeof(int),
- .mode = 0644,
+ .mode = 0644, // you can't change the poolsize, but we'll let you think you can for legacy reasons.
.proc_handler = &proc_do_poolsize,
.strategy = &poolsize_strategy,
},
{
- .ctl_name = RANDOM_ENTROPY_COUNT,
- .procname = "entropy_avail",
- .maxlen = sizeof(int),
- .mode = 0444,
- .proc_handler = &proc_dointvec,
- },
+ .ctl_name = RANDOM_ENTROPY_COUNT,
+ .procname = "entropy_avail",
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = &proc_dointvec,
+ },
{
- .ctl_name = RANDOM_READ_THRESH,
- .procname = "read_wakeup_threshold",
- .data = &random_read_wakeup_thresh,
- .maxlen = sizeof(int),
- .mode = 0644,
- .proc_handler = &proc_dointvec_minmax,
- .strategy = &sysctl_intvec,
- .extra1 = &min_read_thresh,
- .extra2 = &max_read_thresh,
+ .ctl_name = RANDOM_READ_THRESH,
+ .procname = "read_wakeup_threshold",
+ .data = &random_read_wakeup_thresh,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = &proc_dointvec_minmax,
+ .strategy = &sysctl_intvec,
+ .extra1 = &min_read_thresh,
+ .extra2 = &max_read_thresh,
},
{
- .ctl_name = RANDOM_WRITE_THRESH,
- .procname = "write_wakeup_threshold",
- .data = &random_write_wakeup_thresh,
- .maxlen = sizeof(int),
- .mode = 0644,
- .proc_handler = &proc_dointvec_minmax,
- .strategy = &sysctl_intvec,
- .extra1 = &min_write_thresh,
- .extra2 = &max_write_thresh,
+ .ctl_name = RANDOM_WRITE_THRESH,
+ .procname = "write_wakeup_threshold",
+ .data = &random_write_wakeup_thresh,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = &proc_dointvec_minmax,
+ .strategy = &sysctl_intvec,
+ .extra1 = &min_write_thresh,
+ .extra2 = &max_write_thresh,
},
{
.ctl_name = RANDOM_BOOT_ID,
@@ -2061,15 +1495,23 @@
.proc_handler = &proc_do_uuid,
.strategy = &uuid_strategy,
},
+ {
+ .ctl_name = RANDOM_DERIVE_SEED,
+ .procname = "derive_seed",
+ .maxlen = MAXIMUM_POOL_NUMBER * RANDOM_MAX_DIGEST_SIZE,
+ .mode = 0400,
+ .proc_handler = &proc_derive_seed,
+ },
{ .ctl_name = 0 }
};

-static void sysctl_init_random(struct entropy_store *random_state)
+static void sysctl_init_random(struct entropy_store *r)
{
min_read_thresh = 8;
min_write_thresh = 0;
- max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS;
- random_table[1].data = &random_state->entropy_count;
+ random_entropy_count =
+ max_read_thresh = max_write_thresh = (1<<r->pool_number) * r->pools[0]->__crt_alg->cra_ctxsize;
+ random_table[1].data = &random_entropy_count;
}
#endif /* CONFIG_SYSCTL */

@@ -2092,124 +1534,6 @@
* compensated for by changing the secret periodically.
*/

-/* F, G and H are basic MD4 functions: selection, majority, parity */
-#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
-#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
-#define H(x, y, z) ((x) ^ (y) ^ (z))
-
-/*
- * The generic round function. The application is so specific that
- * we don't bother protecting all the arguments with parens, as is generally
- * good macro practice, in favor of extra legibility.
- * Rotation is separate from addition to prevent recomputation
- */
-#define ROUND(f, a, b, c, d, x, s) \
- (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s)))
-#define K1 0
-#define K2 013240474631UL
-#define K3 015666365641UL
-
-/*
- * Basic cut-down MD4 transform. Returns only 32 bits of result.
- */
-static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8])
-{
- __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
-
- /* Round 1 */
- ROUND(F, a, b, c, d, in[0] + K1, 3);
- ROUND(F, d, a, b, c, in[1] + K1, 7);
- ROUND(F, c, d, a, b, in[2] + K1, 11);
- ROUND(F, b, c, d, a, in[3] + K1, 19);
- ROUND(F, a, b, c, d, in[4] + K1, 3);
- ROUND(F, d, a, b, c, in[5] + K1, 7);
- ROUND(F, c, d, a, b, in[6] + K1, 11);
- ROUND(F, b, c, d, a, in[7] + K1, 19);
-
- /* Round 2 */
- ROUND(G, a, b, c, d, in[1] + K2, 3);
- ROUND(G, d, a, b, c, in[3] + K2, 5);
- ROUND(G, c, d, a, b, in[5] + K2, 9);
- ROUND(G, b, c, d, a, in[7] + K2, 13);
- ROUND(G, a, b, c, d, in[0] + K2, 3);
- ROUND(G, d, a, b, c, in[2] + K2, 5);
- ROUND(G, c, d, a, b, in[4] + K2, 9);
- ROUND(G, b, c, d, a, in[6] + K2, 13);
-
- /* Round 3 */
- ROUND(H, a, b, c, d, in[3] + K3, 3);
- ROUND(H, d, a, b, c, in[7] + K3, 9);
- ROUND(H, c, d, a, b, in[2] + K3, 11);
- ROUND(H, b, c, d, a, in[6] + K3, 15);
- ROUND(H, a, b, c, d, in[1] + K3, 3);
- ROUND(H, d, a, b, c, in[5] + K3, 9);
- ROUND(H, c, d, a, b, in[0] + K3, 11);
- ROUND(H, b, c, d, a, in[4] + K3, 15);
-
- return buf[1] + b; /* "most hashed" word */
- /* Alternative: return sum of all words? */
-}
-
-#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
-
-static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12])
-{
- __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
-
- /* Round 1 */
- ROUND(F, a, b, c, d, in[ 0] + K1, 3);
- ROUND(F, d, a, b, c, in[ 1] + K1, 7);
- ROUND(F, c, d, a, b, in[ 2] + K1, 11);
- ROUND(F, b, c, d, a, in[ 3] + K1, 19);
- ROUND(F, a, b, c, d, in[ 4] + K1, 3);
- ROUND(F, d, a, b, c, in[ 5] + K1, 7);
- ROUND(F, c, d, a, b, in[ 6] + K1, 11);
- ROUND(F, b, c, d, a, in[ 7] + K1, 19);
- ROUND(F, a, b, c, d, in[ 8] + K1, 3);
- ROUND(F, d, a, b, c, in[ 9] + K1, 7);
- ROUND(F, c, d, a, b, in[10] + K1, 11);
- ROUND(F, b, c, d, a, in[11] + K1, 19);
-
- /* Round 2 */
- ROUND(G, a, b, c, d, in[ 1] + K2, 3);
- ROUND(G, d, a, b, c, in[ 3] + K2, 5);
- ROUND(G, c, d, a, b, in[ 5] + K2, 9);
- ROUND(G, b, c, d, a, in[ 7] + K2, 13);
- ROUND(G, a, b, c, d, in[ 9] + K2, 3);
- ROUND(G, d, a, b, c, in[11] + K2, 5);
- ROUND(G, c, d, a, b, in[ 0] + K2, 9);
- ROUND(G, b, c, d, a, in[ 2] + K2, 13);
- ROUND(G, a, b, c, d, in[ 4] + K2, 3);
- ROUND(G, d, a, b, c, in[ 6] + K2, 5);
- ROUND(G, c, d, a, b, in[ 8] + K2, 9);
- ROUND(G, b, c, d, a, in[10] + K2, 13);
-
- /* Round 3 */
- ROUND(H, a, b, c, d, in[ 3] + K3, 3);
- ROUND(H, d, a, b, c, in[ 7] + K3, 9);
- ROUND(H, c, d, a, b, in[11] + K3, 11);
- ROUND(H, b, c, d, a, in[ 2] + K3, 15);
- ROUND(H, a, b, c, d, in[ 6] + K3, 3);
- ROUND(H, d, a, b, c, in[10] + K3, 9);
- ROUND(H, c, d, a, b, in[ 1] + K3, 11);
- ROUND(H, b, c, d, a, in[ 5] + K3, 15);
- ROUND(H, a, b, c, d, in[ 9] + K3, 3);
- ROUND(H, d, a, b, c, in[ 0] + K3, 9);
- ROUND(H, c, d, a, b, in[ 4] + K3, 11);
- ROUND(H, b, c, d, a, in[ 8] + K3, 15);
-
- return buf[1] + b; /* "most hashed" word */
- /* Alternative: return sum of all words? */
-}
-#endif
-
-#undef ROUND
-#undef F
-#undef G
-#undef H
-#undef K1
-#undef K2
-#undef K3

/* This should not be decreased so low that ISNs wrap too fast. */
#define REKEY_INTERVAL 300
@@ -2237,79 +1561,67 @@
#define HASH_BITS 24
#define HASH_MASK ( (1<<HASH_BITS)-1 )

-static struct keydata {
- time_t rekey_time;
- __u32 count; // already shifted to the final position
- __u32 secret[12];
-} ____cacheline_aligned ip_keydata[2];
-
static spinlock_t ip_lock = SPIN_LOCK_UNLOCKED;
-static unsigned int ip_cnt;

-static struct keydata *__check_and_rekey(time_t time)
+static __u32 network_random_read32(void)
{
- struct keydata *keyptr;
+ static u8 ctr[16]; /* max block size? */
+ static struct scatterlist sgctr[1];
+ static unsigned int master_count=0;
+ static time_t lastRekey=0;
+
+ struct scatterlist sgtmp[1];
+ unsigned int count;
+ unsigned char tmp[16];
+ struct timeval tv;
+
+ rmb();
spin_lock_bh(&ip_lock);
- keyptr = &ip_keydata[ip_cnt&1];
- if (!keyptr->rekey_time || (time - keyptr->rekey_time) > REKEY_INTERVAL) {
- keyptr = &ip_keydata[1^(ip_cnt&1)];
- keyptr->rekey_time = time;
- get_random_bytes(keyptr->secret, sizeof(keyptr->secret));
- keyptr->count = (ip_cnt&COUNT_MASK)<<HASH_BITS;
+
+ count = ++master_count;
+ increment_iv(ctr, random_state->blocksize);
+
+ do_gettimeofday(&tv);
+ if (lastRekey==0 || (tv.tv_sec - lastRekey) < REKEY_INTERVAL) {
+ lastRekey = tv.tv_sec;
+
+ sgctr[0].page = virt_to_page(ctr);
+ sgctr[0].offset = offset_in_page(ctr);
+ sgctr[0].length = 16;
+
+ if (!random_state->networkCipher_ready) {
+ u8 secret[32]; /* max key size? */
+ get_random_bytes(secret, random_state->keysize);
+ crypto_cipher_setkey(random_state->networkCipher, (const u8*)secret, random_state->keysize);
+ random_state->networkCipher_ready = 1;
+ }
+
mb();
- ip_cnt++;
- }
- spin_unlock_bh(&ip_lock);
- return keyptr;
-}
+ }

-static inline struct keydata *check_and_rekey(time_t time)
-{
- struct keydata *keyptr = &ip_keydata[ip_cnt&1];
+ spin_unlock_bh(&ip_lock);

- rmb();
- if (!keyptr->rekey_time || (time - keyptr->rekey_time) > REKEY_INTERVAL) {
- keyptr = __check_and_rekey(time);
- }
+ sgtmp[0].page = virt_to_page(tmp);
+ sgtmp[0].offset = offset_in_page(tmp);
+ sgtmp[0].length = random_state->blocksize;
+ crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgctr, 1); /* tmp[]/sg[0] = Enc(Sec, CTR++) */
+ increment_iv(ctr, random_state->blocksize);

- return keyptr;
+ /* seq# needs to be random-ish, but incresing */
+ return tmp[0] + (count << (32-COUNT_BITS));
}

#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
__u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr,
__u16 sport, __u16 dport)
{
- struct timeval tv;
- __u32 seq;
- __u32 hash[12];
- struct keydata *keyptr;
-
- /* The procedure is the same as for IPv4, but addresses are longer.
- * Thus we must use twothirdsMD4Transform.
- */
-
- do_gettimeofday(&tv); /* We need the usecs below... */
- keyptr = check_and_rekey(tv.tv_sec);
-
- memcpy(hash, saddr, 16);
- hash[4]=(sport << 16) + dport;
- memcpy(&hash[5],keyptr->secret,sizeof(__u32)*7);
-
- seq = twothirdsMD4Transform(daddr, hash) & HASH_MASK;
- seq += keyptr->count;
- seq += tv.tv_usec + tv.tv_sec*1000000;
-
- return seq;
+ return network_random_read32();
}
EXPORT_SYMBOL(secure_tcpv6_sequence_number);

__u32 secure_ipv6_id(__u32 *daddr)
{
- struct keydata *keyptr;
-
- keyptr = check_and_rekey(get_seconds());
-
- return halfMD4Transform(daddr, keyptr->secret);
+ return network_random_read32();
}

EXPORT_SYMBOL(secure_ipv6_id);
@@ -2319,69 +1631,14 @@
__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
__u16 sport, __u16 dport)
{
- struct timeval tv;
- __u32 seq;
- __u32 hash[4];
- struct keydata *keyptr;
-
- /*
- * Pick a random secret every REKEY_INTERVAL seconds.
- */
- do_gettimeofday(&tv); /* We need the usecs below... */
- keyptr = check_and_rekey(tv.tv_sec);
-
- /*
- * Pick a unique starting offset for each TCP connection endpoints
- * (saddr, daddr, sport, dport).
- * Note that the words are placed into the starting vector, which is
- * then mixed with a partial MD4 over random data.
- */
- hash[0]=saddr;
- hash[1]=daddr;
- hash[2]=(sport << 16) + dport;
- hash[3]=keyptr->secret[11];
-
- seq = halfMD4Transform(hash, keyptr->secret) & HASH_MASK;
- seq += keyptr->count;
- /*
- * As close as possible to RFC 793, which
- * suggests using a 250 kHz clock.
- * Further reading shows this assumes 2 Mb/s networks.
- * For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
- * That's funny, Linux has one built in! Use it!
- * (Networks are faster now - should this be increased?)
- */
- seq += tv.tv_usec + tv.tv_sec*1000000;
-#if 0
- printk("init_seq(%lx, %lx, %d, %d) = %d\n",
- saddr, daddr, sport, dport, seq);
-#endif
- return seq;
+ return network_random_read32();
}

EXPORT_SYMBOL(secure_tcp_sequence_number);

-/* The code below is shamelessly stolen from secure_tcp_sequence_number().
- * All blames to Andrey V. Savochkin <saw@msu.ru>.
- */
__u32 secure_ip_id(__u32 daddr)
{
- struct keydata *keyptr;
- __u32 hash[4];
-
- keyptr = check_and_rekey(get_seconds());
-
- /*
- * Pick a unique starting offset for each IP destination.
- * The dest ip address is placed in the starting vector,
- * which is then hashed with random data.
- */
- hash[0] = daddr;
- hash[1] = keyptr->secret[9];
- hash[2] = keyptr->secret[10];
- hash[3] = keyptr->secret[11];
-
- return halfMD4Transform(hash, keyptr->secret);
+ return network_random_read32();
}

#ifdef CONFIG_SYN_COOKIES
@@ -2389,6 +1646,8 @@
* Secure SYN cookie computation. This is the algorithm worked out by
* Dan Bernstein and Eric Schenk.
*
+ * Replaced by Jean-Luc Cooke <jlcooke@certainkey.com> and Tom St. Denis <tstdenis@certainkey.com>
+ *
* For linux I implement the 1 minute counter by looking at the jiffies clock.
* The count is passed in as a parameter, so this code doesn't much care.
*/
@@ -2396,25 +1655,32 @@
#define COOKIEBITS 24 /* Upper bits store count */
#define COOKIEMASK (((__u32)1 << COOKIEBITS) - 1)

-static int syncookie_init;
-static __u32 syncookie_secret[2][16-3+HASH_BUFFER_SIZE];
-
__u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport,
__u16 dport, __u32 sseq, __u32 count, __u32 data)
{
- __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE];
- __u32 seq;
-
- /*
- * Pick two random secrets the first time we need a cookie.
- */
- if (syncookie_init == 0) {
- get_random_bytes(syncookie_secret, sizeof(syncookie_secret));
- syncookie_init = 1;
- }
+ struct scatterlist sg[1];
+ __u32 tmp[4];

/*
* Compute the secure sequence number.
+ *
+ * jlcooke
+ * Output is the 32bit tag of a CBC-MAC of PT={count,0,0,0} with IV={addr,daddr,sport|dport,sseq}
+ * cookie = <8bit count> || truncate_24bit( Encrypt(Sec, {saddr,daddr,sport|dport,sseq}) )
+ *
+ * DJB wrote (http://cr.yp.to/syncookies/archive) about how to do this with hash algorithms
+ * - we can replace two SHA1s used in the previous kernel with two AESs and make things 3x faster
+ * - I'd like to propose we remove the use of two whittenings with a single operation since we
+ * were only using addition modulo 2^32 of all these values anyways. Not to mention the hashs
+ * differ only in that the second processes more data... why drop the first hash? We did learn
+ * that addition is commutative and associative long ago.
+ * - by replacing two SHA1s and addition modulo 2^32 with encryption of a 32bit value using AES-CTR
+ * we've made it 1,000,000,000 times easier to understand what is going on.
+ * - Todo: we should rekey the cipher peridoically... if we do this, some packets will now fail
+ * our checking system... is this ok? How can we get around this? Rekey's would ideally happen
+ * once per minute (6 million TCP connections per minute is a unrealistic enough security margin)
+ * jlcooke
+ *
* The output should be:
* HASH(sec1,saddr,sport,daddr,dport,sec1) + sseq + (count * 2^24)
* + (HASH(sec2,saddr,sport,daddr,dport,count,sec2) % 2^24).
@@ -2424,22 +1690,26 @@
* MSS into the second hash value.
*/

- memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0]));
- tmp[0]=saddr;
- tmp[1]=daddr;
- tmp[2]=(sport << 16) + dport;
- HASH_TRANSFORM(tmp+16, tmp);
- seq = tmp[17] + sseq + (count << COOKIEBITS);
-
- memcpy(tmp+3, syncookie_secret[1], sizeof(syncookie_secret[1]));
- tmp[0]=saddr;
- tmp[1]=daddr;
- tmp[2]=(sport << 16) + dport;
- tmp[3] = count; /* minute counter */
- HASH_TRANSFORM(tmp+16, tmp);
+ tmp[0] = saddr;
+ tmp[1] = daddr;
+ tmp[2] = (sport << 16) + dport;
+ tmp[3] = sseq;
+
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = 16;
+ if (!random_state->networkCipher_ready) {
+ u8 secret[32];
+ get_random_bytes(secret, sizeof(secret));
+ if (crypto_cipher_setkey(random_state->networkCipher, secret, random_state->keysize)) {
+ return 0;
+ }
+ random_state->networkCipher_ready = 1;
+ }
+ crypto_cipher_encrypt(random_state->networkCipher, sg, sg, 1); /* tmp[]/sg[0] = Enc(Sec, {saddr,daddr,sport|dport,sseq}) */

- /* Add in the second hash and the data */
- return seq + ((tmp[17] + data) & COOKIEMASK);
+ /* cookie = CTR encrypt of 8-bit-count and 24-bit-data */
+ return tmp[0] ^ ( (count << COOKIEBITS) | (data >> (sizeof(__u32)*8-COOKIEBITS)) );
}

/*
@@ -2454,32 +1724,29 @@
__u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport,
__u16 dport, __u32 sseq, __u32 count, __u32 maxdiff)
{
- __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE];
- __u32 diff;
+ struct scatterlist sg[1];
+ __u32 tmp[4], thiscount, diff;

- if (syncookie_init == 0)
+ if (random_state == NULL || !random_state->networkCipher_ready)
return (__u32)-1; /* Well, duh! */

- /* Strip away the layers from the cookie */
- memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0]));
- tmp[0]=saddr;
- tmp[1]=daddr;
- tmp[2]=(sport << 16) + dport;
- HASH_TRANSFORM(tmp+16, tmp);
- cookie -= tmp[17] + sseq;
- /* Cookie is now reduced to (count * 2^24) ^ (hash % 2^24) */
-
- diff = (count - (cookie >> COOKIEBITS)) & ((__u32)-1 >> COOKIEBITS);
- if (diff >= maxdiff)
- return (__u32)-1;
-
- memcpy(tmp+3, syncookie_secret[1], sizeof(syncookie_secret[1]));
tmp[0] = saddr;
tmp[1] = daddr;
tmp[2] = (sport << 16) + dport;
- tmp[3] = count - diff; /* minute counter */
- HASH_TRANSFORM(tmp+16, tmp);
+ tmp[3] = sseq;
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = 16;
+ crypto_cipher_encrypt(random_state->networkCipher, sg, sg, 1);
+
+ cookie ^= tmp[0]; /* CTR decrypt the cookie */
+
+ thiscount = cookie >> COOKIEBITS; /* top 8 bits are 'count' */
+
+ diff = count - thiscount;
+ if (diff >= maxdiff)
+ return (__u32)-1;

- return (cookie - tmp[17]) & COOKIEMASK; /* Leaving the data behind */
+ return cookie >> (sizeof(__u32)*8-COOKIEBITS); /* bottom 24 bits are 'data' */
}
#endif