# Patches to the random driver

Theodore Y. Ts'o (tytso@MIT.EDU)
Sat, 21 Jun 1997 02:13:17 -0400

Enclosed a find a patch to the 2.1.43 random driver; it improves the TCP
initial sequence number generated that had been in the 1.02 version of
random.c.

- Ted

Patch generated: on Wed Jun 18 15:09:08 EDT 1997 by tytso@rsts-11
against Linux version 2.1.43

===================================================================
RCS file: drivers/char/RCS/random.c,v
retrieving revision 1.1
diff -u -r1.1 drivers/char/random.c
--- drivers/char/random.c 1997/06/17 18:19:58 1.1
+++ drivers/char/random.c 1997/06/17 18:20:15
@@ -1,7 +1,7 @@
/*
* random.c -- A strong random number generator
*
*
*
@@ -1335,11 +1335,15 @@
* starting point for each pair of TCP endpoints. This defeats
* attacks which rely on guessing the initial TCP sequence number.
* This algorithm was suggested by Steve Bellovin.
+ *
+ * Using a very strong hash was taking an appreciable amount of the total
+ * TCP connection establishment time, so this is a weaker hash,
+ * compensated for by changing the secret periodically.
*/

/* F, G and H are basic MD4 functions: selection, majority, parity */
-#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
-#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
+#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))

#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
@@ -1357,9 +1361,9 @@
(a) = ROTL ((s), (a));}

/*
- * Basic cut-down MD4 transform
+ * Basic cut-down MD4 transform. Returns only 32 bits of result.
*/
-static void halfMD4Transform (__u32 buf[4], __u32 in[8])
+static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8])
{
__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];

@@ -1376,76 +1380,83 @@
/* Round 2 */
GG (a, b, c, d, in[ 0], 3);
GG (d, a, b, c, in[ 4], 5);
- GG (a, b, c, d, in[ 1], 9);
- GG (d, a, b, c, in[ 5], 13);
+ GG (c, d, a, b, in[ 1], 9);
+ GG (b, c, d, a, in[ 5], 13);
GG (a, b, c, d, in[ 2], 3);
GG (d, a, b, c, in[ 6], 5);
- GG (a, b, c, d, in[ 3], 9);
- GG (d, a, b, c, in[ 7], 13);
+ GG (c, d, a, b, in[ 3], 9);
+ GG (b, c, d, a, in[ 7], 13);

/* Round 3 */
HH (a, b, c, d, in[ 0], 3);
- HH (c, d, a, b, in[ 4], 9);
- HH (a, b, c, d, in[ 2], 11);
- HH (c, d, a, b, in[ 6], 15);
+ HH (d, a, b, c, in[ 4], 9);
+ HH (c, d, a, b, in[ 2], 11);
+ HH (b, c, d, a, in[ 6], 15);
HH (a, b, c, d, in[ 1], 3);
- HH (c, d, a, b, in[ 5], 9);
- HH (a, b, c, d, in[ 3], 11);
- HH (c, d, a, b, in[ 7], 15);
+ HH (d, a, b, c, in[ 5], 9);
+ HH (c, d, a, b, in[ 3], 11);
+ HH (b, c, d, a, in[ 7], 15);

- buf[0] += a;
- buf[1] += b;
- buf[2] += c;
- buf[3] += d;
+ return buf[1] + b; /* "most hashed" word */
+ /* Alternative: return sum of all words? */
}

+/* This should not be decreased so low that ISNs wrap too fast. */
#define REKEY_INTERVAL 300
+#define HASH_BITS 24

__u16 sport, __u16 dport)
{
static __u32 rekey_time = 0;
+ static __u32 count = 0;
static __u32 secret[12];
- static char count = 0;
struct timeval tv;
- __u32 tmp[12];
__u32 seq;

/*
- * Pick a random secret every REKEY_INTERVAL seconds
+ * Pick a random secret every REKEY_INTERVAL seconds.
*/
- do_gettimeofday(&tv);
+ do_gettimeofday(&tv); /* We need the usecs below... */
+
if (!rekey_time ||
(tv.tv_sec - rekey_time) > REKEY_INTERVAL) {
- get_random_bytes(&secret, sizeof(secret));
rekey_time = tv.tv_sec;
- count++;
+ /* First three words are overwritten below. */
+ get_random_bytes(&secret+3, sizeof(secret)-12);
+ count = (tv.tv_sec/REKEY_INTERVAL) << HASH_BITS;
}

- memcpy(tmp, secret, sizeof(tmp));
/*
- * Pick a unique starting offset for each
+ * Pick a unique starting offset for each TCP connection endpoints
+ * Note that the words are placed into the first words to be
+ * mixed in with the halfMD4. This is because the starting
+ * vector is also a random secret (at secret+8), and further
+ * hashing fixed data into it isn't going to improve anything,
+ * so we should get started with the variable data.
*/
- tmp[10]=(sport << 16) + dport;
- halfMD4Transform(tmp, tmp+4);
+ secret[2]=(sport << 16) + dport;
+
+ seq = (halfMD4Transform(secret+8, secret) &
+ ((1<<HASH_BITS)-1)) + (count << HASH_BITS);

/*
* As close as possible to RFC 793, which
* suggests using a 250kHz clock.
- * Further reading shows this assumes 2MB/s networks.
- * For 10MB/s ethernet, a 1MHz clock is appropriate.
+ * Further reading shows this assumes 2Mb/s networks.
+ * For 10Mb/s ethernet, a 1MHz clock is appropriate.
* That's funny, Linux has one built in! Use it!
+ * (Networks are faster now - should this be increased?)
*/
- seq = (tmp[1]&0xFFFFFF) + (tv.tv_usec+tv.tv_sec*1000000) +
- (count << 24);
+ seq += tv.tv_usec + tv.tv_sec*1000000;
#if 0
printk("init_seq(%lx, %lx, %d, %d) = %d\n",