lkml.org 
[lkml]   [1997]   [Apr]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: WARNING: that patch from Ted...
   Date: Sat, 26 Apr 97 15:31:23 MDT
From: colin@nyx.net (Colin Plumb)

With memories of that /dev/random false alarm still echoing in my
head, I hope I'm not causing unnecessary panic, but Linus, *please*
don't put that patch from Ted in until he's confirmed that I'm wrong.
(Likewise, linuxhq, please don't archive it, etc.)

OK, here's another patch. If anyone has applied my pervious patch, I
wouldn't worry too much about it. Yes, Colin is right that the cut-down
MD4 is pretty badly weakened as it currently stands, but this section of
code is also not really all that cryptographically critical, and it's
not clear that an attacker really would be able to do enough to be able
to exploit the weaker checksum algorithm (remember, we're starting with
12 bytes of TCP connection data and 36 bytes of secret data, and only
revealing 4 bytes of offset data; the attacker doesn't get the whole MD4
result).

Also, the worst case that would happen is someone would install a 2.1
kernel with a potentially weakened secure TCP connection number, and in
the time it would take for hackers to be able to come up with attack
scripts, the next 2.1 kernel would have patches that would fix things
up. (Remeber, the 2.1 series is a development series. :-)

- Ted

This patch is against a clean 2.1.36 kernel; so if you applied my
previous patch, you'll need to back it out before applying this one.

Patch generated: on Sun Apr 27 08:06:48 EDT 1997 by tytso@rsts-11
against Linux version 2.1.36

===================================================================
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/04/25 02:57:40 1.1
+++ drivers/char/random.c 1997/04/27 12:04:21
@@ -1,7 +1,7 @@
/*
* random.c -- A strong random number generator
*
- * Version 1.01, last modified 13-Feb-97
+ * Version 1.03, last modified 26-Apr-97
*
* Copyright Theodore Ts'o, 1994, 1995, 1996, 1997. All rights reserved.
*
@@ -839,6 +839,18 @@
digest[ 4 ] += E;
}

+#undef ROTL
+#undef f1
+#undef f2
+#undef f3
+#undef f4
+#undef K1
+#undef K2
+#undef K3
+#undef K4
+#undef expand
+#undef subRound
+
#else
#define HASH_BUFFER_SIZE 4
#define HASH_TRANSFORM MD5Transform
@@ -1323,49 +1335,128 @@
* 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) ((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 ) ) )
+
+/* FF, GG and HH are MD4 transformations for rounds 1, 2 and 3 */
+/* Rotation is separate from addition to prevent recomputation */
+#define FF(a, b, c, d, x, s) \
+ {(a) += F ((b), (c), (d)) + (x); \
+ (a) = ROTL ((s), (a));}
+#define GG(a, b, c, d, x, s) \
+ {(a) += G ((b), (c), (d)) + (x) + 013240474631UL; \
+ (a) = ROTL ((s), (a));}
+#define HH(a, b, c, d, x, s) \
+ {(a) += H ((b), (c), (d)) + (x) + 015666365641UL; \
+ (a) = ROTL ((s), (a));}
+
+/*
+ * 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 */
+ FF (a, b, c, d, in[ 0], 3);
+ FF (d, a, b, c, in[ 1], 7);
+ FF (c, d, a, b, in[ 2], 11);
+ FF (b, c, d, a, in[ 3], 19);
+ FF (a, b, c, d, in[ 4], 3);
+ FF (d, a, b, c, in[ 5], 7);
+ FF (c, d, a, b, in[ 6], 11);
+ FF (b, c, d, a, in[ 7], 19);
+
+ /* Round 2 */
+ GG (a, b, c, d, in[ 0], 3);
+ GG (d, a, b, c, in[ 4], 5);
+ 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 (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 (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 (d, a, b, c, in[ 5], 9);
+ HH (c, d, a, b, in[ 3], 11);
+ HH (b, c, d, a, in[ 7], 15);
+
+ 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
+
__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
__u16 sport, __u16 dport)
{
- static int is_init = 0;
- static __u32 secret[16];
+ static __u32 rekey_time = 0;
+ static __u32 count = 0;
+ static __u32 secret[12];
struct timeval tv;
- __u32 tmp[16];
__u32 seq;

/*
- * Pick a random secret the first time we open a TCP
- * connection.
+ * Pick a random secret every REKEY_INTERVAL seconds.
*/
- if (is_init == 0) {
- get_random_bytes(&secret, sizeof(secret));
- is_init = 1;
+ do_gettimeofday(&tv); /* We need the usecs below... */
+
+ if (!rekey_time ||
+ (tv.tv_sec - rekey_time) > REKEY_INTERVAL) {
+ rekey_time = tv.tv_sec;
+ /* 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
- * TCP connection endpoints (saddr, daddr, sport, dport)
+ * Pick a unique starting offset for each TCP connection endpoints
+ * (saddr, daddr, sport, dport).
+ * 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[8]=saddr;
- tmp[9]=daddr;
- tmp[10]=(sport << 16) + dport;
- HASH_TRANSFORM(tmp, tmp);
+ secret[0]=saddr;
+ secret[1]=daddr;
+ 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?)
*/
- do_gettimeofday(&tv);
- seq = tmp[1] + tv.tv_usec+tv.tv_sec*1000000;
+ 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 seq;
}

#ifdef RANDOM_BENCHMARK
\
 
 \ /
  Last update: 2005-03-22 13:39    [W:0.033 / U:3.748 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site