[PATCH] OpenBSD Networking-related randomization port

[PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

[-- Attachment #1.1: Type: text/plain, Size: 2045 bytes --]

Hi,

Attached you can find a split up patch ported from grSecurity [1], as
Linus commented that he wouldn't get a whole-sale patch, I was working
on it and also studying what features of grSecurity can be implemented
without a development or maintenance overhead, aka less-invasive
implementations.

It adds support for advanced networking-related randomization, in
concrete it adds support for TCP ISNs randomization, RPC XIDs
randomization, IP IDs randomization and finally a sub-key under the
Cryptographic options menu for Linux PRNG [2] enhancements (useful now
and also for future patch submissions), which currently has an only-one
option for poll sizes increasing (x2).

As it's impact is minimal (in performance and development/maintenance
terms), I recommend to merge it, as it gives a basic prevention for the
so-called system fingerprinting (which is used most by "kids" to know
how old and insecure could be a target system, many time used as the
first, even only-one, data to decide if attack or not the target host)
among other things.

There's only a missing feature that is present on grSecurity, the
sources ports randomization which seems achieved now by some changes
that can be checked out in the Linux BKBits repository:
http://linux.bkbits.net:8080/linux-2.6/diffs/net/ipv4/tcp_ipv4.c@1.105?nav=index.html|src/|src/net|src/net/ipv4|hist/net/ipv4/tcp_ipv4.c
(net/ipv4/tcp_ipv4.c@1.105)

I'm not sure of the effectiveness of that changes, but I just prefer to
keep it as most simple as possible.If there are thoughts on reverting to
the old schema, and using obsd_rand.c code instead, just drop me a line
and I will modify the patch.

I've uploaded the patches and obsd_rand.c source to:
http://cvs.tuxedo-es.org/cgi-bin/viewcvs.cgi/obsd-netrand/

References:	
 [1]: http://www.grsecurity.net
 [2]: http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #1.2: openbsd-netrand-2.6.11-rc2.patch --]
[-- Type: text/x-patch, Size: 16210 bytes --]

diff -Nur linux-2.6.11-rc2/crypto/Kconfig linux-2.6.11-rc2.tx1/crypto/Kconfig
--- linux-2.6.11-rc2/crypto/Kconfig	2005-01-26 19:54:06.000000000 +0100
+++ linux-2.6.11-rc2.tx1/crypto/Kconfig	2005-01-28 17:05:39.000000000 +0100
@@ -4,6 +4,26 @@
 
 menu "Cryptographic options"
 
+config RANDOM
+	bool "Random Numbers Generator enhancements"
+	help
+	  By enabling this option, you will be able to select
+	  a few enhancements for the Linux Random Numbers Generator
+	  (./drivers/char/random.{h,c}).
+	  
+	  If unsure: say Y.
+	  
+config RANDOM_INCREASED_POOLSIZES
+	bool "Larger entropy pools"
+	depends on RANDOM
+	help
+	  If you say Y here, the entropy pools used for many features of Linux
+          will be doubled in size. It is recommended that you say Y
+          here.  Saying Y here has a similar effect as modifying
+          /proc/sys/kernel/random/poolsize.
+	  
+	  If unsure: say Y.
+
 config CRYPTO
 	bool "Cryptographic API"
 	help
diff -Nur linux-2.6.11-rc2/drivers/char/random.c linux-2.6.11-rc2.tx1/drivers/char/random.c
--- linux-2.6.11-rc2/drivers/char/random.c	2005-01-26 19:54:07.000000000 +0100
+++ linux-2.6.11-rc2.tx1/drivers/char/random.c	2005-01-28 17:03:02.000000000 +0100
@@ -255,10 +255,20 @@
 
 /*
  * Configuration information
+ * If "increased pool sizes" option is enabled,
+ * then poll size default values get increased x2. 
  */
+ 
+#ifdef CONFIG_RANDOM_INCREASED_POOLSIZES
+#define DEFAULT_POOL_SIZE 1024
+#define SECONDARY_POOL_SIZE 256
+#define BATCH_ENTROPY_SIZE 512
+#else
 #define DEFAULT_POOL_SIZE 512
 #define SECONDARY_POOL_SIZE 128
 #define BATCH_ENTROPY_SIZE 256
+#endif
+
 #define USE_SHA
 
 /*
diff -Nur linux-2.6.11-rc2/include/linux/random.h linux-2.6.11-rc2.tx1/include/linux/random.h
--- linux-2.6.11-rc2/include/linux/random.h	2005-01-26 19:54:17.000000000 +0100
+++ linux-2.6.11-rc2.tx1/include/linux/random.h	2005-01-27 23:45:34.000000000 +0100
@@ -42,6 +42,12 @@
 
 #ifdef __KERNEL__
 
+#ifdef CONFIG_NET_SECURITY
+extern unsigned long obsd_get_random_long(void);
+extern __u16 ip_randomid(void);
+extern __u32 ip_randomisn(void);
+#endif
+
 extern void rand_initialize_irq(int irq);
 
 extern void add_input_randomness(unsigned int type, unsigned int code,
diff -Nur linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c
--- linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c	2005-01-26 19:54:19.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c	2005-01-28 17:16:09.000000000 +0100
@@ -539,10 +539,14 @@
 
 static inline __u32 tcp_v4_init_sequence(struct sock *sk, struct sk_buff *skb)
 {
+#ifdef CONFIG_NET_RANDISN
+		return ip_randomisn();
+#else
 	return secure_tcp_sequence_number(skb->nh.iph->daddr,
 					  skb->nh.iph->saddr,
 					  skb->h.th->dest,
 					  skb->h.th->source);
+#endif
 }
 
 /* called with local bh disabled */
@@ -833,14 +837,21 @@
 	tcp_v4_setup_caps(sk, &rt->u.dst);
 	tp->ext2_header_len = rt->u.dst.header_len;
 
-	if (!tp->write_seq)
+	if (!tp->write_seq) {
+#ifdef CONFIG_NET_RANDISN
+			tp->write_seq = ip_randomisn();
+#else
 		tp->write_seq = secure_tcp_sequence_number(inet->saddr,
 							   inet->daddr,
 							   inet->sport,
 							   usin->sin_port);
-
+#endif
+	}
+#ifdef CONFIG_NET_RANDID
+		inet->id = htons(ip_randomid());
+#else
 	inet->id = tp->write_seq ^ jiffies;
-
+#endif
 	err = tcp_connect(sk);
 	rt = NULL;
 	if (err)
@@ -1579,8 +1590,11 @@
 	if (newinet->opt)
 		newtp->ext_header_len = newinet->opt->optlen;
 	newtp->ext2_header_len = dst->header_len;
+#ifdef CONFIG_NET_RANDID
+	newinet->id = htons(ip_randomid());
+#else
 	newinet->id = newtp->write_seq ^ jiffies;
-
+#endif
 	tcp_sync_mss(newsk, dst_pmtu(dst));
 	newtp->advmss = dst_metric(dst, RTAX_ADVMSS);
 	tcp_initialize_rcv_mss(newsk);
diff -Nur linux-2.6.11-rc2/net/ipv4/udp.c linux-2.6.11-rc2.tx1/net/ipv4/udp.c
--- linux-2.6.11-rc2/net/ipv4/udp.c	2005-01-26 19:54:19.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/ipv4/udp.c	2005-01-27 23:02:32.000000000 +0100
@@ -94,6 +94,7 @@
 #include <linux/inet.h>
 #include <linux/ipv6.h>
 #include <linux/netdevice.h>
+#include <linux/random.h>
 #include <net/snmp.h>
 #include <net/tcp.h>
 #include <net/protocol.h>
diff -Nur linux-2.6.11-rc2/net/Kconfig linux-2.6.11-rc2.tx1/net/Kconfig
--- linux-2.6.11-rc2/net/Kconfig	2005-01-26 19:54:17.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/Kconfig	2005-01-28 17:04:30.608652680 +0100
@@ -81,6 +81,59 @@
 
 	  Say Y unless you know what you are doing.
 
+config NET_SECURITY
+	bool "Network Protections"
+	depends on NET
+	select INET
+	help
+	 By enabling this option, you will be able to choose a few options
+	 that will enhance the TCP/IP stack and network-related randomization.
+	 An example of results of this, is that the system will be a difficult
+	 subject of (remote) fingerprinting.
+	 
+	 These protections come from the grSecurity project by Brad Spengler,
+	 and based on OpenBSD extended networking security features.
+	 
+	 Ported to vanilla sources by Lorenzo Hernández García-Hierro
+	 <lorenzo@gnu.org>.
+	 Information at http://tuxedo-es.org and http://grsecurity.net.
+	 
+	 Short answer: say Y.
+
+config NET_RANDISN
+        bool "Truly random TCP ISN selection"
+        depends on NET_SECURITY
+        help
+          If you say Y here, Linux's default selection of TCP Initial Sequence
+          Numbers (ISNs) will be replaced with that of OpenBSD.  Linux uses
+          an MD4 hash based on the connection plus a time value to create the
+          ISN, while OpenBSD's selection is random.  If the sysctl option is
+          enabled, a sysctl option with name "rand_isns" is created.
+
+config NET_RANDID
+        bool "Randomized IP IDs"
+        depends on NET_SECURITY
+        help
+          If you say Y here, all the id field on all outgoing packets
+          will be randomized.  This hinders os fingerprinters and
+          keeps your machine from being used as a bounce for an untraceable
+          portscan.  Ids are used for fragmented packets, fragments belonging
+          to the same packet have the same id.  By default linux only
+          increments the id value on each packet sent to an individual host.
+          We use a port of the OpenBSD random ip id code to achieve the
+          randomness, while keeping the possibility of id duplicates to
+          near none.
+          
+config NET_RANDRPC
+        bool "Randomized RPC XIDs"
+        depends on NET_SECURITY
+        help
+          If you say Y here, the method of determining XIDs for RPC requests will
+          be randomized, instead of using linux's default behavior of simply
+          incrementing the XID.  If you want your RPC connections to be more
+          secure, say Y here.
+
+
 config INET
 	bool "TCP/IP networking"
 	---help---
diff -Nur linux-2.6.11-rc2/net/Makefile linux-2.6.11-rc2.tx1/net/Makefile
--- linux-2.6.11-rc2/net/Makefile	2005-01-26 19:50:49.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/Makefile	2005-01-27 23:04:02.000000000 +0100
@@ -11,6 +11,7 @@
 
 tmp-$(CONFIG_COMPAT) 		:= compat.o
 obj-$(CONFIG_NET)		+= $(tmp-y)
+obj-$(CONFIG_NET_SECURITY)	+= obsd_rand.o
 
 # LLC has to be linked before the files in net/802/
 obj-$(CONFIG_LLC)		+= llc/
diff -Nur linux-2.6.11-rc2/net/obsd_rand.c linux-2.6.11-rc2.tx1/net/obsd_rand.c
--- linux-2.6.11-rc2/net/obsd_rand.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/obsd_rand.c	2005-01-28 17:43:50.452901824 +0100
@@ -0,0 +1,269 @@
+/* $Id: openbsd-netrand-2.6.11-rc2.patch,v 1.2 2005/01/28 16:51:02 lorenzo Exp $
+ * Copyright (c) 2005 Lorenzo Hernandez Garcia-Hierro <lorenzo@gnu.org>.
+ * All rights reserved.
+ *
+ * Added some macros and stolen code from random.c, for individual and less
+ * "invasive" implementation.Also removed the get_random_long() macro definition,
+ * which is not good if we can simply call back obsd_get_random_long().
+ *
+ * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
+ * 
+ * Version 1.90, last modified 28-Jan-05
+ *    
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
+ * All rights reserved.
+ *
+ * Copyright 1998 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
+ * such a mathematical system to generate more random (yet non-repeating)
+ * ids to solve the resolver/named problem.  But Niels designed the
+ * actual system based on the constraints.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer,
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/time.h>
+#include <linux/timer.h>
+#include <linux/smp_lock.h>
+#include <linux/random.h>
+
+#define RU_OUT 180
+#define RU_MAX 30000
+#define RU_GEN 2
+#define RU_N 32749
+#define RU_AGEN 7
+#define RU_M 31104
+#define PFAC_N 3
+
+/*
+ * Stolen from ./drivers/char/random.c
+ */
+
+/* FOO, GEEK and HECK are basic geekish MD4 functions: foo selection, geek majority, heck parity */
+#define FOO(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
+#define GEEK(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
+#define HECK(x, y, z) ((x) ^ (y) ^ (z))
+#define OBROUND(f, a, b, c, d, x, s)	\
+	(a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
+#define obK1 0
+#define obK2 013240474631UL
+#define obK3 015666365641UL
+#define OB_REKEY_INTERVAL (300 * HZ)
+
+
+const static __u16 pfacts[PFAC_N] = { 2, 3, 2729 };
+
+static __u16 ru_x;
+static __u16 ru_seed, ru_seed2;
+static __u16 ru_a, ru_b;
+static __u16 ru_g;
+static __u16 ru_counter = 0;
+static __u16 ru_msb = 0;
+static unsigned long ru_reseed = 0;
+static __u32 tmp;
+
+#define TCP_RNDISS_ROUNDS	15
+#define TCP_RNDISS_OUT		7200
+#define TCP_RNDISS_MAX		30000
+
+static __u8 tcp_rndiss_sbox[128];
+static __u16 tcp_rndiss_msb;
+static __u16 tcp_rndiss_cnt;
+static unsigned long tcp_rndiss_reseed;
+
+static __u16 pmod(__u16, __u16, __u16);
+static void ip_initid(void);
+__u16 ip_randomid(void);
+
+/*
+ * Basic cut-down MD4 transform.  Returns only 32 bits of result.
+ */
+static __u32 half_md4_transform (__u32 const buf[4], __u32 const in[8])
+{
+	__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+	/* Round 1 */
+	OBROUND(FOO, a, b, c, d, in[0] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[1] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[2] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[3] + obK1, 19);
+	OBROUND(FOO, a, b, c, d, in[4] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[5] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[6] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[7] + obK1, 19);
+
+	/* Round 2 */
+	OBROUND(GEEK, a, b, c, d, in[1] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[3] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[5] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[7] + obK2, 13);
+	OBROUND(GEEK, a, b, c, d, in[0] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[2] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[4] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[6] + obK2, 13);
+
+	/* Round 3 */
+	OBROUND(HECK, a, b, c, d, in[3] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[7] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[2] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[6] + obK3, 15);
+	OBROUND(HECK, a, b, c, d, in[1] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[5] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[0] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[4] + obK3, 15);
+
+	return buf[1] + b;	/* "most hashed" word */
+	/* Alternative: return sum of all words? */
+}
+
+unsigned long obsd_get_random_long(void)
+{
+	static time_t   rekey_time;
+	static __u32    secret[12];
+	time_t          t;
+
+	/*
+	 * Pick a random secret every OB_REKEY_INTERVAL seconds.
+	 */
+	t = get_seconds();
+	if (!rekey_time || (t - rekey_time) > OB_REKEY_INTERVAL) {
+		rekey_time = t;
+		get_random_bytes(secret, sizeof(secret));
+	}
+
+	secret[1] = half_md4_transform(secret+8, secret);
+	secret[0] = half_md4_transform(secret+8, secret);
+	return *(unsigned long *)secret;
+}
+
+static __u16
+pmod(__u16 gen, __u16 exp, __u16 mod)
+{
+	__u16 s, t, u;
+
+	s = 1;
+	t = gen;
+	u = exp;
+
+	while (u) {
+		if (u & 1)
+			s = (s * t) % mod;
+		u >>= 1;
+		t = (t * t) % mod;
+	}
+	return (s);
+}
+
+static void
+ip_initid(void)
+{
+	__u16 j, i;
+	int noprime = 1;
+
+	ru_x = ((tmp = obsd_get_random_long()) & 0xFFFF) % RU_M;
+
+	ru_seed = (tmp >> 16) & 0x7FFF;
+	ru_seed2 = obsd_get_random_long() & 0x7FFF;
+
+	ru_b = ((tmp = obsd_get_random_long()) & 0xfffe) | 1;
+	ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
+	while (ru_b % 3 == 0)
+		ru_b += 2;
+
+	j = (tmp = obsd_get_random_long()) % RU_N;
+	tmp = tmp >> 16;
+
+	while (noprime) {
+		for (i = 0; i < PFAC_N; i++)
+			if (j % pfacts[i] == 0)
+				break;
+
+		if (i >= PFAC_N)
+			noprime = 0;
+		else
+			j = (j + 1) % RU_N;
+	}
+
+	ru_g = pmod(RU_GEN, j, RU_N);
+	ru_counter = 0;
+
+	ru_reseed = xtime.tv_sec + RU_OUT;
+	ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
+}
+
+__u16
+ip_randomid(void)
+{
+	int i, n;
+
+	if (ru_counter >= RU_MAX || time_after(get_seconds(), ru_reseed))
+		ip_initid();
+
+	if (!tmp)
+		tmp = obsd_get_random_long();
+
+	n = tmp & 0x3;
+	tmp = tmp >> 2;
+	if (ru_counter + n >= RU_MAX)
+		ip_initid();
+	for (i = 0; i <= n; i++)
+		ru_x = (ru_a * ru_x + ru_b) % RU_M;
+	ru_counter += i;
+
+	return ((ru_seed ^ pmod(ru_g, ru_seed2 ^ ru_x, RU_N)) | ru_msb);
+}
+
+static __u16
+tcp_rndiss_encrypt(__u16 val)
+{
+	__u16 sum = 0, i;
+
+	for (i = 0; i < TCP_RNDISS_ROUNDS; i++) {
+		sum += 0x79b9;
+		val ^= ((__u16) tcp_rndiss_sbox[(val ^ sum) & 0x7f]) << 7;
+		val = ((val & 0xff) << 7) | (val >> 8);
+	}
+
+	return val;
+}
+
+static void
+tcp_rndiss_init(void)
+{
+	get_random_bytes(tcp_rndiss_sbox, sizeof (tcp_rndiss_sbox));
+	tcp_rndiss_reseed = get_seconds() + TCP_RNDISS_OUT;
+	tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000;
+	tcp_rndiss_cnt = 0;
+}
+
+__u32
+ip_randomisn(void)
+{
+	if (tcp_rndiss_cnt >= TCP_RNDISS_MAX ||
+	    time_after(get_seconds(), tcp_rndiss_reseed))
+		tcp_rndiss_init();
+
+	return (((tcp_rndiss_encrypt(tcp_rndiss_cnt++) |
+		  tcp_rndiss_msb) << 16) | (obsd_get_random_long() & 0x7fff));
+}
diff -Nur linux-2.6.11-rc2/net/sunrpc/xprt.c linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c
--- linux-2.6.11-rc2/net/sunrpc/xprt.c	2005-01-26 19:54:20.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c	2005-01-28 00:07:18.000000000 +0100
@@ -1342,7 +1342,11 @@
  */
 static inline u32 xprt_alloc_xid(struct rpc_xprt *xprt)
 {
+#ifdef CONFIG_NET_RANDRPC
+		return (u32) obsd_get_random_long();
+#else
 	return xprt->xid++;
+#endif
 }
 
 static inline void xprt_init_xid(struct rpc_xprt *xprt)

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Adrian Bunk]

On Fri, Jan 28, 2005 at 06:17:17PM +0100, Lorenzo Hernández García-Hierro wrote:
>...
> As it's impact is minimal (in performance and development/maintenance
> terms), I recommend to merge it, as it gives a basic prevention for the
> so-called system fingerprinting (which is used most by "kids" to know
> how old and insecure could be a target system, many time used as the
> first, even only-one, data to decide if attack or not the target host)
> among other things.
>...

"basic prevention"?
I hardly see how this patch makes OS fingerprinting by e.g. Nmap 
impossible.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El vie, 28-01-2005 a las 18:40 +0100, Adrian Bunk escribió:
> On Fri, Jan 28, 2005 at 06:17:17PM +0100, Lorenzo Hernández García-Hierro wrote:
> >...
> > As it's impact is minimal (in performance and development/maintenance
> > terms), I recommend to merge it, as it gives a basic prevention for the
> > so-called system fingerprinting (which is used most by "kids" to know
> > how old and insecure could be a target system, many time used as the
> > first, even only-one, data to decide if attack or not the target host)
> > among other things.
> >...
> 
> "basic prevention"?
> I hardly see how this patch makes OS fingerprinting by e.g. Nmap 
> impossible.

That's an example, as you can find at the grsecurity handbook [1]:

"The default Linux TCP/IP-stack has some properties that make it more
vulnerable to prediction-based hacks. By randomizing several items,
predicting the behaviour will be a lot more difficult."

"Randomized IP IDs hinders OS fingerprinting and will keep your machine
from being a bounce for an untraceable portscan."

References:
 [1]: http://www.gentoo.org/proj/en/hardened/grsecurity.xml

Cheers,
PS: Thanks for CC'ing me, I forgot to mention that I'm not subscribed to
the list, I just read the archives and reply by getting the original
mbox-formatted messages. 
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Stephen Hemminger]

> Attached you can find a split up patch ported from grSecurity [1], as
> Linus commented that he wouldn't get a whole-sale patch, I was working
> on it and also studying what features of grSecurity can be implemented
> without a development or maintenance overhead, aka less-invasive
> implementations.
> 
> It adds support for advanced networking-related randomization, in
> concrete it adds support for TCP ISNs randomization, RPC XIDs
> randomization, IP IDs randomization and finally a sub-key under the
> Cryptographic options menu for Linux PRNG [2] enhancements (useful now
> and also for future patch submissions), which currently has an only-one
> option for poll sizes increasing (x2).
> 
> As it's impact is minimal (in performance and development/maintenance
> terms), I recommend to merge it, as it gives a basic prevention for the
> so-called system fingerprinting (which is used most by "kids" to know
> how old and insecure could be a target system, many time used as the
> first, even only-one, data to decide if attack or not the target host)
> among other things.
> 
> There's only a missing feature that is present on grSecurity, the
> sources ports randomization which seems achieved now by some changes
> that can be checked out in the Linux BKBits repository:
> http://linux.bkbits.net:8080/linux-2.6/diffs/net/ipv4/tcp_ipv4.c@1.105?nav=index.html|src/|src/net|src/net/ipv4|hist/net/ipv4/tcp_ipv4.c
> (net/ipv4/tcp_ipv4.c@1.105)
> 
> I'm not sure of the effectiveness of that changes, but I just prefer to
> keep it as most simple as possible.If there are thoughts on reverting to
> the old schema, and using obsd_rand.c code instead, just drop me a line
> and I will modify the patch.

Okay, but:
* Need to give better explanation of why this is required, 
  existing randomization code in network is compromise between
  performance and security. So you need to quantify the performance
  impact of this, and the security threat reduction.

* Why are the OpenBSD random functions better? because they have more
  security coolness factor?

* It is hard to have two levels of security based on config options.
  Think of a distro vendor, do they ship the fast or the secure system??

As always:
* Send networking stuff to netdev@oss.sgi.com
* Please split up patches.

Re: [PATCH] OpenBSD Networking-related randomization port

[Jörn Engel]

On Fri, 28 January 2005 18:17:17 +0100, Lorenzo Hernández García-Hierro wrote:
> 
> Attached you can find a split up patch ported from grSecurity [1], as
> Linus commented that he wouldn't get a whole-sale patch, I was working
> on it and also studying what features of grSecurity can be implemented
> without a development or maintenance overhead, aka less-invasive
> implementations.

I can see why Linus isn't too excited about this patch:

o Increased entropy pool sizes are independent.  Should be a seperate
  patch.
o Huge numbers of #ifdef's in the code are Plain Wrong(tm).
o Replacing current randomization functions with new ones without
  lengthy explanation doesn't make me happy.

Also, if the patch was inline instead of an attachment, I could easily
quote it while commenting.


Not sure whether there are useful things in the patch, but in the
current form I wouldn't want to take it.  And usually I'm less picky
than Linus.

Jörn

-- 
Eighty percent of success is showing up.
-- Woody Allen

Re: [PATCH] OpenBSD Networking-related randomization port

[Arjan van de Ven]

On Fri, 2005-01-28 at 18:17 +0100, Lorenzo Hernández García-Hierro
wrote:
> Hi,
> 
> Attached you can find a split up patch ported from grSecurity [1], as
> Linus commented that he wouldn't get a whole-sale patch, I was working
> on it and also studying what features of grSecurity can be implemented
> without a development or maintenance overhead, aka less-invasive
> implementations.


why did you make it a config option? This is the kind of thing that is
either good or isn't... at which point you can get rid of a lot of, if
not all the ugly ifdefs the patch adds.

Also, why does it need to enhance the random driver this much, the
random driver already has a facility to provide pseudorandom numbers
good enough for networking use (eg the PRNG rekeys often enough with
real entropy that brute forcing it shouldn't be possible).

If you can fix those 2 things the patch will look a lot cleaner and has
a lot higher chance to be merged.

Re: [PATCH] OpenBSD Networking-related randomization port

[Stephen Hemminger]

On Fri, 28 Jan 2005 18:47:55 +0100
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:

> El vie, 28-01-2005 a las 18:40 +0100, Adrian Bunk escribió:
> > On Fri, Jan 28, 2005 at 06:17:17PM +0100, Lorenzo Hernández García-Hierro wrote:
> > >...
> > > As it's impact is minimal (in performance and development/maintenance
> > > terms), I recommend to merge it, as it gives a basic prevention for the
> > > so-called system fingerprinting (which is used most by "kids" to know
> > > how old and insecure could be a target system, many time used as the
> > > first, even only-one, data to decide if attack or not the target host)
> > > among other things.
> > >...
> > 
> > "basic prevention"?
> > I hardly see how this patch makes OS fingerprinting by e.g. Nmap 
> > impossible.
> 
> That's an example, as you can find at the grsecurity handbook [1]:
> 
> "The default Linux TCP/IP-stack has some properties that make it more
> vulnerable to prediction-based hacks. By randomizing several items,
> predicting the behaviour will be a lot more difficult."

No it just changes the fingerprint table.  "Hmm, this looks like a
newer generation system, must be OpenBSD or Linux".

> "Randomized IP IDs hinders OS fingerprinting and will keep your machine
> from being a bounce for an untraceable portscan."
> 
> References:
>  [1]: http://www.gentoo.org/proj/en/hardened/grsecurity.xml

This is a very transitory effect, it works only because your machine
is then different from the typical Linux machine; therefore the scanner
will go on to the next obvious ones. But if this gets incorporated widely
then the rarity factor goes away and this defense becomes useless.

-- 
Stephen Hemminger	<shemminger@osdl.org>

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El vie, 28-01-2005 a las 10:02 -0800, Stephen Hemminger escribió:
> > Attached you can find a split up patch ported from grSecurity [1], as
> > Linus commented that he wouldn't get a whole-sale patch, I was working
> > on it and also studying what features of grSecurity can be implemented
> > without a development or maintenance overhead, aka less-invasive
> > implementations.
> > 
> > It adds support for advanced networking-related randomization, in
> > concrete it adds support for TCP ISNs randomization, RPC XIDs
> > randomization, IP IDs randomization and finally a sub-key under the
> > Cryptographic options menu for Linux PRNG [2] enhancements (useful now
> > and also for future patch submissions), which currently has an only-one
> > option for poll sizes increasing (x2).
> > 
> > As it's impact is minimal (in performance and development/maintenance
> > terms), I recommend to merge it, as it gives a basic prevention for the
> > so-called system fingerprinting (which is used most by "kids" to know
> > how old and insecure could be a target system, many time used as the
> > first, even only-one, data to decide if attack or not the target host)
> > among other things.
> > 
> > There's only a missing feature that is present on grSecurity, the
> > sources ports randomization which seems achieved now by some changes
> > that can be checked out in the Linux BKBits repository:
> > http://linux.bkbits.net:8080/linux-2.6/diffs/net/ipv4/tcp_ipv4.c@1.105?nav=index.html|src/|src/net|src/net/ipv4|hist/net/ipv4/tcp_ipv4.c
> > (net/ipv4/tcp_ipv4.c@1.105)
> > 
> > I'm not sure of the effectiveness of that changes, but I just prefer to
> > keep it as most simple as possible.If there are thoughts on reverting to
> > the old schema, and using obsd_rand.c code instead, just drop me a line
> > and I will modify the patch.
> 
> Okay, but:
> * Need to give better explanation of why this is required, 
>   existing randomization code in network is compromise between
>   performance and security. So you need to quantify the performance
>   impact of this, and the security threat reduction.

Performance impact is none AFAIK.
I've explained them in an early reply to Adrian [1].

> * Why are the OpenBSD random functions better? because they have more
>   security coolness factor?

I'm not an OpenBSD user, and no intention to being a one.
I just recognize that the functions do the same job better, as explained
in the Kconfig diffs.

> * It is hard to have two levels of security based on config options.
>   Think of a distro vendor, do they ship the fast or the secure system??
> 
> As always:
> * Send networking stuff to netdev@oss.sgi.com

Added to CC list.

> * Please split up patches.

If you talk about removing the pool sizes increasing, then i will do it,
but i would like to know if this has any chances to get merged.

[1]: http://lkml.org/lkml/2005/1/28/139

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El vie, 28-01-2005 a las 19:07 +0100, Arjan van de Ven escribió:
> On Fri, 2005-01-28 at 18:17 +0100, Lorenzo Hernández García-Hierro
> wrote:
> > Hi,
> > 
> > Attached you can find a split up patch ported from grSecurity [1], as
> > Linus commented that he wouldn't get a whole-sale patch, I was working
> > on it and also studying what features of grSecurity can be implemented
> > without a development or maintenance overhead, aka less-invasive
> > implementations.
> 
> 
> why did you make it a config option? This is the kind of thing that is
> either good or isn't... at which point you can get rid of a lot of, if
> not all the ugly ifdefs the patch adds.

I will remove the ifdef's, I've made it just from the usability POV,
users may want the standard "randomization" schema, dunno.
Anyway, I will remove those ifdef's and make it enabled-by-default.

> Also, why does it need to enhance the random driver this much, the
> random driver already has a facility to provide pseudorandom numbers
> good enough for networking use (eg the PRNG rekeys often enough with
> real entropy that brute forcing it shouldn't be possible).

I will also remove the pool sizes increasing diffs from the patch.

> If you can fix those 2 things the patch will look a lot cleaner and has
> a lot higher chance to be merged.

Sure, many thanks for pointing out that clearly.
It will take a few minutes and then re-send the patch.

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Stephen Hemminger]

On Fri, 28 Jan 2005 19:31:50 +0100
L
> > Okay, but:
> > * Need to give better explanation of why this is required, 
> >   existing randomization code in network is compromise between
> >   performance and security. So you need to quantify the performance
> >   impact of this, and the security threat reduction.
> 
> Performance impact is none AFAIK.
> I've explained them in an early reply to Adrian [1].

When I did the port randomization patch the benchmark that was most impacted
was LMBENCH.  The biggest change was in the communications latency results.

If you want, you can sign up for a free access to OSDL test machines
and use STP to run lmbench and easily get before/after results.

1. Go to osdl.org and get associate account http://osdl.org/join_form

2. Submit patch to Patch Lifecycle Manager http://osdl.org/plm-cgi/plm

3. Choose test to run Scalable Test Platform (STP) 
http://osdl.org/lab_activities/kernel_testing/stp/


-- 
Stephen Hemminger	<shemminger@osdl.org>

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El vie, 28-01-2005 a las 10:18 -0800, Stephen Hemminger escribió:
> This is a very transitory effect, it works only because your machine
> is then different from the typical Linux machine; therefore the scanner
> will go on to the next obvious ones. But if this gets incorporated widely
> then the rarity factor goes away and this defense becomes useless.

I would prefer to say that such "rarity factor" comes directly from the
"rarity factor" given by the PRNG.

So, we should take "rarity factor" as the PRNG seed entropy and not as a
predictable value (not in a reasonable time manner, which is the goal of
most crypto-related developments, to make as much difficult as possible
to cause an information leak, and if such leak happens, ensure that the
information is no longer needed, private, confidential, critical,
whateverelse) (AFAIK).

So, there's no point at that claim.

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El vie, 28-01-2005 a las 10:52 -0800, Stephen Hemminger escribió:
> On Fri, 28 Jan 2005 19:31:50 +0100
> When I did the port randomization patch the benchmark that was most impacted
> was LMBENCH.  The biggest change was in the communications latency results.
> 
> If you want, you can sign up for a free access to OSDL test machines
> and use STP to run lmbench and easily get before/after results.
> 
> 1. Go to osdl.org and get associate account http://osdl.org/join_form
> 
> 2. Submit patch to Patch Lifecycle Manager http://osdl.org/plm-cgi/plm
> 
> 3. Choose test to run Scalable Test Platform (STP) 
> http://osdl.org/lab_activities/kernel_testing/stp/

OK, many thanks.
Haven't noticed that (maybe 'cos I'm new in kernel hacking ;) )

I will submit there the new patch ASAP.

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Adrian Bunk]

On Fri, Jan 28, 2005 at 06:47:55PM +0100, Lorenzo Hernández García-Hierro wrote:
> El vie, 28-01-2005 a las 18:40 +0100, Adrian Bunk escribió:
> > On Fri, Jan 28, 2005 at 06:17:17PM +0100, Lorenzo Hernández García-Hierro wrote:
> > >...
> > > As it's impact is minimal (in performance and development/maintenance
> > > terms), I recommend to merge it, as it gives a basic prevention for the
> > > so-called system fingerprinting (which is used most by "kids" to know
> > > how old and insecure could be a target system, many time used as the
> > > first, even only-one, data to decide if attack or not the target host)
> > > among other things.
> > >...
> > 
> > "basic prevention"?
> > I hardly see how this patch makes OS fingerprinting by e.g. Nmap 
> > impossible.
> 
> That's an example, as you can find at the grsecurity handbook [1]:
>...
> "Randomized IP IDs hinders OS fingerprinting and will keep your machine
> from being a bounce for an untraceable portscan."
>...

The OS detection in Nmap [1], which is AFAIK the most popular port 
scanner today works by e.g. checking the answer of an ACK to a closed 
port.

I do still not understand how your patch has any impact on these issues.

> Cheers,
>...

cu
Adrian

[1] http://www.insecure.org/nmap/nmap-fingerprinting-article.html

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] OpenBSD Networking-related randomization port

[Horst von Brand]

Lorenzo =?ISO-8859-1?Q?Hern=E1ndez_?=
 	 =?ISO-8859-1?Q?Garc=EDa-Hierro?= <lorenzo@gnu.org> said:
> Attached you can find a split up patch ported from grSecurity [1], as
> Linus commented that he wouldn't get a whole-sale patch, I was working
> on it and also studying what features of grSecurity can be implemented
> without a development or maintenance overhead, aka less-invasive
> implementations.

OK.

> It adds support for advanced networking-related randomization, in
> concrete it adds support for TCP ISNs randomization,

1.

>                                                      RPC XIDs
> randomization,

2.

>                IP IDs randomization

3.

>                                     and finally a sub-key under the
> Cryptographic options menu for Linux PRNG [2] enhancements

4.                                                           (useful now
> and also for future patch submissions), which currently has an only-one
> option for poll sizes increasing (x2).

5 (it seems).

Needs way more splitting?

> As it's impact is minimal (in performance and development/maintenance
> terms), I recommend to merge it, as it gives a basic prevention for the
> so-called system fingerprinting (which is used most by "kids" to know
> how old and insecure could be a target system, many time used as the
> first, even only-one, data to decide if attack or not the target host)
> among other things.

How does it prevent fingerprinting?

And a huge, compressed patch attached.
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

[-- Attachment #1.1: Type: text/plain, Size: 372 bytes --]

Hi,

Attached the new patch following Arjan's recommendations.
I'm sorry about not making it "inlined", but my mail agent messes up the
diffs if I do so.
Still waiting for the OSDL STP tests results, they will take a while to
finish.

Cheers,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]



[-- Attachment #1.2: openbsd-netrand-2.6.11-rc2.patch --]
[-- Type: text/x-patch, Size: 11272 bytes --]

diff -Nur linux-2.6.11-rc2/include/linux/random.h linux-2.6.11-rc2.tx1/include/linux/random.h
--- linux-2.6.11-rc2/include/linux/random.h	2005-01-26 19:54:17.000000000 +0100
+++ linux-2.6.11-rc2.tx1/include/linux/random.h	2005-01-28 19:45:31.359923392 +0100
@@ -42,6 +42,12 @@
 
 #ifdef __KERNEL__
 
+/* OpenBSD Networking-related randomization functions - lorenzo@gnu.org */
+extern unsigned long obsd_get_random_long(void);
+extern __u16 ip_randomid(void);
+extern __u32 ip_randomisn(void);
+
+
 extern void rand_initialize_irq(int irq);
 
 extern void add_input_randomness(unsigned int type, unsigned int code,
diff -Nur linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c
--- linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c	2005-01-26 19:54:19.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c	2005-01-28 19:39:48.000000000 +0100
@@ -539,10 +539,8 @@
 
 static inline __u32 tcp_v4_init_sequence(struct sock *sk, struct sk_buff *skb)
 {
-	return secure_tcp_sequence_number(skb->nh.iph->daddr,
-					  skb->nh.iph->saddr,
-					  skb->h.th->dest,
-					  skb->h.th->source);
+
+		return ip_randomisn();
 }
 
 /* called with local bh disabled */
@@ -833,14 +831,11 @@
 	tcp_v4_setup_caps(sk, &rt->u.dst);
 	tp->ext2_header_len = rt->u.dst.header_len;
 
-	if (!tp->write_seq)
-		tp->write_seq = secure_tcp_sequence_number(inet->saddr,
-							   inet->daddr,
-							   inet->sport,
-							   usin->sin_port);
-
-	inet->id = tp->write_seq ^ jiffies;
-
+	if (!tp->write_seq) {
+			tp->write_seq = ip_randomisn();
+	}
+	
+	inet->id = htons(ip_randomid());
 	err = tcp_connect(sk);
 	rt = NULL;
 	if (err)
@@ -1579,8 +1574,8 @@
 	if (newinet->opt)
 		newtp->ext_header_len = newinet->opt->optlen;
 	newtp->ext2_header_len = dst->header_len;
-	newinet->id = newtp->write_seq ^ jiffies;
-
+	newinet->id = htons(ip_randomid());
+	
 	tcp_sync_mss(newsk, dst_pmtu(dst));
 	newtp->advmss = dst_metric(dst, RTAX_ADVMSS);
 	tcp_initialize_rcv_mss(newsk);
diff -Nur linux-2.6.11-rc2/net/Makefile linux-2.6.11-rc2.tx1/net/Makefile
--- linux-2.6.11-rc2/net/Makefile	2005-01-26 19:50:49.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/Makefile	2005-01-28 21:01:21.870140688 +0100
@@ -11,6 +11,7 @@
 
 tmp-$(CONFIG_COMPAT) 		:= compat.o
 obj-$(CONFIG_NET)		+= $(tmp-y)
+obj-y				+= obsd_rand.o
 
 # LLC has to be linked before the files in net/802/
 obj-$(CONFIG_LLC)		+= llc/
diff -Nur linux-2.6.11-rc2/net/obsd_rand.c linux-2.6.11-rc2.tx1/net/obsd_rand.c
--- linux-2.6.11-rc2/net/obsd_rand.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/obsd_rand.c	2005-01-28 17:43:50.000000000 +0100
@@ -0,0 +1,269 @@
+/* $Id: openbsd-netrand-2.6.11-rc2.patch,v 1.5 2005/01/28 20:16:21 lorenzo Exp $
+ * Copyright (c) 2005 Lorenzo Hernandez Garcia-Hierro <lorenzo@gnu.org>.
+ * All rights reserved.
+ *
+ * Added some macros and stolen code from random.c, for individual and less
+ * "invasive" implementation.Also removed the get_random_long() macro definition,
+ * which is not good if we can simply call back obsd_get_random_long().
+ *
+ * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
+ * 
+ * Version 1.90, last modified 28-Jan-05
+ *    
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
+ * All rights reserved.
+ *
+ * Copyright 1998 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
+ * such a mathematical system to generate more random (yet non-repeating)
+ * ids to solve the resolver/named problem.  But Niels designed the
+ * actual system based on the constraints.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer,
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/time.h>
+#include <linux/timer.h>
+#include <linux/smp_lock.h>
+#include <linux/random.h>
+
+#define RU_OUT 180
+#define RU_MAX 30000
+#define RU_GEN 2
+#define RU_N 32749
+#define RU_AGEN 7
+#define RU_M 31104
+#define PFAC_N 3
+
+/*
+ * Stolen from ./drivers/char/random.c
+ */
+
+/* FOO, GEEK and HECK are basic geekish MD4 functions: foo selection, geek majority, heck parity */
+#define FOO(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
+#define GEEK(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
+#define HECK(x, y, z) ((x) ^ (y) ^ (z))
+#define OBROUND(f, a, b, c, d, x, s)	\
+	(a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
+#define obK1 0
+#define obK2 013240474631UL
+#define obK3 015666365641UL
+#define OB_REKEY_INTERVAL (300 * HZ)
+
+
+const static __u16 pfacts[PFAC_N] = { 2, 3, 2729 };
+
+static __u16 ru_x;
+static __u16 ru_seed, ru_seed2;
+static __u16 ru_a, ru_b;
+static __u16 ru_g;
+static __u16 ru_counter = 0;
+static __u16 ru_msb = 0;
+static unsigned long ru_reseed = 0;
+static __u32 tmp;
+
+#define TCP_RNDISS_ROUNDS	15
+#define TCP_RNDISS_OUT		7200
+#define TCP_RNDISS_MAX		30000
+
+static __u8 tcp_rndiss_sbox[128];
+static __u16 tcp_rndiss_msb;
+static __u16 tcp_rndiss_cnt;
+static unsigned long tcp_rndiss_reseed;
+
+static __u16 pmod(__u16, __u16, __u16);
+static void ip_initid(void);
+__u16 ip_randomid(void);
+
+/*
+ * Basic cut-down MD4 transform.  Returns only 32 bits of result.
+ */
+static __u32 half_md4_transform (__u32 const buf[4], __u32 const in[8])
+{
+	__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+	/* Round 1 */
+	OBROUND(FOO, a, b, c, d, in[0] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[1] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[2] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[3] + obK1, 19);
+	OBROUND(FOO, a, b, c, d, in[4] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[5] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[6] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[7] + obK1, 19);
+
+	/* Round 2 */
+	OBROUND(GEEK, a, b, c, d, in[1] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[3] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[5] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[7] + obK2, 13);
+	OBROUND(GEEK, a, b, c, d, in[0] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[2] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[4] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[6] + obK2, 13);
+
+	/* Round 3 */
+	OBROUND(HECK, a, b, c, d, in[3] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[7] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[2] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[6] + obK3, 15);
+	OBROUND(HECK, a, b, c, d, in[1] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[5] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[0] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[4] + obK3, 15);
+
+	return buf[1] + b;	/* "most hashed" word */
+	/* Alternative: return sum of all words? */
+}
+
+unsigned long obsd_get_random_long(void)
+{
+	static time_t   rekey_time;
+	static __u32    secret[12];
+	time_t          t;
+
+	/*
+	 * Pick a random secret every OB_REKEY_INTERVAL seconds.
+	 */
+	t = get_seconds();
+	if (!rekey_time || (t - rekey_time) > OB_REKEY_INTERVAL) {
+		rekey_time = t;
+		get_random_bytes(secret, sizeof(secret));
+	}
+
+	secret[1] = half_md4_transform(secret+8, secret);
+	secret[0] = half_md4_transform(secret+8, secret);
+	return *(unsigned long *)secret;
+}
+
+static __u16
+pmod(__u16 gen, __u16 exp, __u16 mod)
+{
+	__u16 s, t, u;
+
+	s = 1;
+	t = gen;
+	u = exp;
+
+	while (u) {
+		if (u & 1)
+			s = (s * t) % mod;
+		u >>= 1;
+		t = (t * t) % mod;
+	}
+	return (s);
+}
+
+static void
+ip_initid(void)
+{
+	__u16 j, i;
+	int noprime = 1;
+
+	ru_x = ((tmp = obsd_get_random_long()) & 0xFFFF) % RU_M;
+
+	ru_seed = (tmp >> 16) & 0x7FFF;
+	ru_seed2 = obsd_get_random_long() & 0x7FFF;
+
+	ru_b = ((tmp = obsd_get_random_long()) & 0xfffe) | 1;
+	ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
+	while (ru_b % 3 == 0)
+		ru_b += 2;
+
+	j = (tmp = obsd_get_random_long()) % RU_N;
+	tmp = tmp >> 16;
+
+	while (noprime) {
+		for (i = 0; i < PFAC_N; i++)
+			if (j % pfacts[i] == 0)
+				break;
+
+		if (i >= PFAC_N)
+			noprime = 0;
+		else
+			j = (j + 1) % RU_N;
+	}
+
+	ru_g = pmod(RU_GEN, j, RU_N);
+	ru_counter = 0;
+
+	ru_reseed = xtime.tv_sec + RU_OUT;
+	ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
+}
+
+__u16
+ip_randomid(void)
+{
+	int i, n;
+
+	if (ru_counter >= RU_MAX || time_after(get_seconds(), ru_reseed))
+		ip_initid();
+
+	if (!tmp)
+		tmp = obsd_get_random_long();
+
+	n = tmp & 0x3;
+	tmp = tmp >> 2;
+	if (ru_counter + n >= RU_MAX)
+		ip_initid();
+	for (i = 0; i <= n; i++)
+		ru_x = (ru_a * ru_x + ru_b) % RU_M;
+	ru_counter += i;
+
+	return ((ru_seed ^ pmod(ru_g, ru_seed2 ^ ru_x, RU_N)) | ru_msb);
+}
+
+static __u16
+tcp_rndiss_encrypt(__u16 val)
+{
+	__u16 sum = 0, i;
+
+	for (i = 0; i < TCP_RNDISS_ROUNDS; i++) {
+		sum += 0x79b9;
+		val ^= ((__u16) tcp_rndiss_sbox[(val ^ sum) & 0x7f]) << 7;
+		val = ((val & 0xff) << 7) | (val >> 8);
+	}
+
+	return val;
+}
+
+static void
+tcp_rndiss_init(void)
+{
+	get_random_bytes(tcp_rndiss_sbox, sizeof (tcp_rndiss_sbox));
+	tcp_rndiss_reseed = get_seconds() + TCP_RNDISS_OUT;
+	tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000;
+	tcp_rndiss_cnt = 0;
+}
+
+__u32
+ip_randomisn(void)
+{
+	if (tcp_rndiss_cnt >= TCP_RNDISS_MAX ||
+	    time_after(get_seconds(), tcp_rndiss_reseed))
+		tcp_rndiss_init();
+
+	return (((tcp_rndiss_encrypt(tcp_rndiss_cnt++) |
+		  tcp_rndiss_msb) << 16) | (obsd_get_random_long() & 0x7fff));
+}
diff -Nur linux-2.6.11-rc2/net/sunrpc/xprt.c linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c
--- linux-2.6.11-rc2/net/sunrpc/xprt.c	2005-01-26 19:54:20.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c	2005-01-28 19:42:46.000000000 +0100
@@ -1342,7 +1342,9 @@
  */
 static inline u32 xprt_alloc_xid(struct rpc_xprt *xprt)
 {
-	return xprt->xid++;
+	/* Return randomized xprt->xid instead of prt->xid++ */
+	return (u32) obsd_get_random_long();
+
 }
 
 static inline void xprt_init_xid(struct rpc_xprt *xprt)

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[David S. Miller]

On Fri, 28 Jan 2005 21:34:52 +0100
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:

> Attached the new patch following Arjan's recommendations.

No SMP protection on the SBOX, better look into that.
The locking you'll likely need to add will make this
routine serialize many networking operations which is
one thing we've been trying to avoid.

Re: [PATCH] OpenBSD Networking-related randomization port

[Arjan van de Ven]

On Fri, 2005-01-28 at 21:34 +0100, Lorenzo Hernández García-Hierro
wrote:
> Hi,
> 
> Attached the new patch following Arjan's recommendations.
> I'm sorry about not making it "inlined", but my mail agent messes up the
> diffs if I do so.
> Still waiting for the OSDL STP tests results, they will take a while to
> finish.
> 
> Cheers,

lots better already! Some more comments (now that the patch got a lot
easier to read :)

 static inline __u32 tcp_v4_init_sequence(struct sock *sk, struct
sk_buff *skb)
 {
-       return secure_tcp_sequence_number(skb->nh.iph->daddr,
-                                         skb->nh.iph->saddr,
-                                         skb->h.th->dest,
-                                         skb->h.th->source);
+
+               return ip_randomisn();
 }

is there a reason for the weird indentation?

+       if (!tp->write_seq) {
+                       tp->write_seq = ip_randomisn();
+       }

spare { } pare that's not needed, also looks like one tab too many


as for obsd_get_random_long().. would it be possible to use the
get_random_int() function from the patches I posted the other day? They
use the existing random.c infrastructure instead of making a copy...

I still don't understand why you need a obsd_rand.c and can't use the
normal random.c


  
 static inline u32 xprt_alloc_xid(struct rpc_xprt *xprt)
 {
-       return xprt->xid++;
+       /* Return randomized xprt->xid instead of prt->xid++ */
+       return (u32) obsd_get_random_long();
+
 }
 

that cast looks quite redundant...

Re: [PATCH] OpenBSD Networking-related randomization port

[Stephen Hemminger]

On Fri, 28 Jan 2005 12:45:17 -0800
"David S. Miller" <davem@davemloft.net> wrote:

> On Fri, 28 Jan 2005 21:34:52 +0100
> Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:
> 
> > Attached the new patch following Arjan's recommendations.
> 
> No SMP protection on the SBOX, better look into that.
> The locking you'll likely need to add will make this
> routine serialize many networking operations which is
> one thing we've been trying to avoid.
> 

per-cpu would be the way to go here.

-- 
Stephen Hemminger	<shemminger@osdl.org>

Re: [PATCH] OpenBSD Networking-related randomization port

[David S. Miller]

On Fri, 28 Jan 2005 13:34:08 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> per-cpu would be the way to go here.

Does the sbox get somehow seeded from use to use?
If not, then yes that's the thing to do.

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

[-- Attachment #1.1: Type: text/plain, Size: 1301 bytes --]

El vie, 28-01-2005 a las 21:47 +0100, Arjan van de Ven escribió:
> as for obsd_get_random_long().. would it be possible to use the
> get_random_int() function from the patches I posted the other day? They
> use the existing random.c infrastructure instead of making a copy...

As seen at
http://www.kernel.org/pub/linux/kernel/people/arjan/execshield/00-randomize-A0 you can suppose that there's no point to use that, we can easily maintain the functions at obsd_rand.c so we wouldn't need to add more maintenance overhead, I hope you can understand why I want it like that and not depending on random.c in more than the function exports (which make it even more independent as we don't need to use our proper header and add each proper include entry in the modified files, as most of them use or have already random.h included).

Attached you can find the new patch with the indentation fixes.

The tests on the patch are the following ones:
http://www.osdl.org/plm-cgi/plm?module=patch_info&patch_id=4136
(above one shows that there are no SMP-related issues)
http://khack.osdl.org/stp/300417
http://khack.osdl.org/stp/300420

Cheers and thanks for the information,
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #1.2: openbsd-netrand-2.6.11-rc2.patch --]
[-- Type: text/x-patch, Size: 11925 bytes --]

diff -Nur linux-2.6.11-rc2/include/linux/random.h linux-2.6.11-rc2.tx1/include/linux/random.h
--- linux-2.6.11-rc2/include/linux/random.h	2005-01-26 19:54:17.000000000 +0100
+++ linux-2.6.11-rc2.tx1/include/linux/random.h	2005-01-28 19:45:31.359923392 +0100
@@ -42,6 +42,12 @@
 
 #ifdef __KERNEL__
 
+/* OpenBSD Networking-related randomization functions - lorenzo@gnu.org */
+extern unsigned long obsd_get_random_long(void);
+extern __u16 ip_randomid(void);
+extern __u32 ip_randomisn(void);
+
+
 extern void rand_initialize_irq(int irq);
 
 extern void add_input_randomness(unsigned int type, unsigned int code,
diff -Nur linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c
--- linux-2.6.11-rc2/net/ipv4/tcp_ipv4.c	2005-01-26 19:54:19.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/ipv4/tcp_ipv4.c	2005-01-28 22:28:24.991105608 +0100
@@ -539,10 +539,7 @@
 
 static inline __u32 tcp_v4_init_sequence(struct sock *sk, struct sk_buff *skb)
 {
-	return secure_tcp_sequence_number(skb->nh.iph->daddr,
-					  skb->nh.iph->saddr,
-					  skb->h.th->dest,
-					  skb->h.th->source);
+	return ip_randomisn();
 }
 
 /* called with local bh disabled */
@@ -834,13 +830,9 @@
 	tp->ext2_header_len = rt->u.dst.header_len;
 
 	if (!tp->write_seq)
-		tp->write_seq = secure_tcp_sequence_number(inet->saddr,
-							   inet->daddr,
-							   inet->sport,
-							   usin->sin_port);
-
-	inet->id = tp->write_seq ^ jiffies;
+		tp->write_seq = ip_randomisn();
 
+	inet->id = htons(ip_randomid());
 	err = tcp_connect(sk);
 	rt = NULL;
 	if (err)
@@ -1566,20 +1555,20 @@
 	newsk->sk_dst_cache = dst;
 	tcp_v4_setup_caps(newsk, dst);
 
-	newtp		      = tcp_sk(newsk);
-	newinet		      = inet_sk(newsk);
-	newinet->daddr	      = req->af.v4_req.rmt_addr;
-	newinet->rcv_saddr    = req->af.v4_req.loc_addr;
-	newinet->saddr	      = req->af.v4_req.loc_addr;
-	newinet->opt	      = req->af.v4_req.opt;
-	req->af.v4_req.opt    = NULL;
-	newinet->mc_index     = tcp_v4_iif(skb);
-	newinet->mc_ttl	      = skb->nh.iph->ttl;
+	newtp = tcp_sk(newsk);
+	newinet = inet_sk(newsk);
+	newinet->daddr = req->af.v4_req.rmt_addr;
+	newinet->rcv_saddr = req->af.v4_req.loc_addr;
+	newinet->saddr = req->af.v4_req.loc_addr;
+	newinet->opt = req->af.v4_req.opt;
+	req->af.v4_req.opt = NULL;
+	newinet->mc_index = tcp_v4_iif(skb);
+	newinet->mc_ttl = skb->nh.iph->ttl;
 	newtp->ext_header_len = 0;
 	if (newinet->opt)
 		newtp->ext_header_len = newinet->opt->optlen;
 	newtp->ext2_header_len = dst->header_len;
-	newinet->id = newtp->write_seq ^ jiffies;
+	newinet->id = htons(ip_randomid());
 
 	tcp_sync_mss(newsk, dst_pmtu(dst));
 	newtp->advmss = dst_metric(dst, RTAX_ADVMSS);

diff -Nur linux-2.6.11-rc2/net/Makefile linux-2.6.11-rc2.tx1/net/Makefile
--- linux-2.6.11-rc2/net/Makefile	2005-01-26 19:50:49.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/Makefile	2005-01-28 21:01:21.870140688 +0100
@@ -11,6 +11,7 @@
 
 tmp-$(CONFIG_COMPAT) 		:= compat.o
 obj-$(CONFIG_NET)		+= $(tmp-y)
+obj-y				+= obsd_rand.o
 
 # LLC has to be linked before the files in net/802/
 obj-$(CONFIG_LLC)		+= llc/
diff -Nur linux-2.6.11-rc2/net/obsd_rand.c linux-2.6.11-rc2.tx1/net/obsd_rand.c
--- linux-2.6.11-rc2/net/obsd_rand.c	1970-01-01 01:00:00.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/obsd_rand.c	2005-01-28 17:43:50.000000000 +0100
@@ -0,0 +1,269 @@
+/* $Id: openbsd-netrand-2.6.11-rc2.patch,v 1.6 2005/01/28 22:10:30 lorenzo Exp $
+ * Copyright (c) 2005 Lorenzo Hernandez Garcia-Hierro <lorenzo@gnu.org>.
+ * All rights reserved.
+ *
+ * Added some macros and stolen code from random.c, for individual and less
+ * "invasive" implementation.Also removed the get_random_long() macro definition,
+ * which is not good if we can simply call back obsd_get_random_long().
+ *
+ * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
+ * 
+ * Version 1.90, last modified 28-Jan-05
+ *    
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
+ * All rights reserved.
+ *
+ * Copyright 1998 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
+ * such a mathematical system to generate more random (yet non-repeating)
+ * ids to solve the resolver/named problem.  But Niels designed the
+ * actual system based on the constraints.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer,
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <linux/kernel.h>
+#include <linux/sched.h>
+#include <linux/time.h>
+#include <linux/timer.h>
+#include <linux/smp_lock.h>
+#include <linux/random.h>
+
+#define RU_OUT 180
+#define RU_MAX 30000
+#define RU_GEN 2
+#define RU_N 32749
+#define RU_AGEN 7
+#define RU_M 31104
+#define PFAC_N 3
+
+/*
+ * Stolen from ./drivers/char/random.c
+ */
+
+/* FOO, GEEK and HECK are basic geekish MD4 functions: foo selection, geek majority, heck parity */
+#define FOO(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
+#define GEEK(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
+#define HECK(x, y, z) ((x) ^ (y) ^ (z))
+#define OBROUND(f, a, b, c, d, x, s)	\
+	(a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
+#define obK1 0
+#define obK2 013240474631UL
+#define obK3 015666365641UL
+#define OB_REKEY_INTERVAL (300 * HZ)
+
+
+const static __u16 pfacts[PFAC_N] = { 2, 3, 2729 };
+
+static __u16 ru_x;
+static __u16 ru_seed, ru_seed2;
+static __u16 ru_a, ru_b;
+static __u16 ru_g;
+static __u16 ru_counter = 0;
+static __u16 ru_msb = 0;
+static unsigned long ru_reseed = 0;
+static __u32 tmp;
+
+#define TCP_RNDISS_ROUNDS	15
+#define TCP_RNDISS_OUT		7200
+#define TCP_RNDISS_MAX		30000
+
+static __u8 tcp_rndiss_sbox[128];
+static __u16 tcp_rndiss_msb;
+static __u16 tcp_rndiss_cnt;
+static unsigned long tcp_rndiss_reseed;
+
+static __u16 pmod(__u16, __u16, __u16);
+static void ip_initid(void);
+__u16 ip_randomid(void);
+
+/*
+ * Basic cut-down MD4 transform.  Returns only 32 bits of result.
+ */
+static __u32 half_md4_transform (__u32 const buf[4], __u32 const in[8])
+{
+	__u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
+
+	/* Round 1 */
+	OBROUND(FOO, a, b, c, d, in[0] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[1] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[2] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[3] + obK1, 19);
+	OBROUND(FOO, a, b, c, d, in[4] + obK1,  3);
+	OBROUND(FOO, d, a, b, c, in[5] + obK1,  7);
+	OBROUND(FOO, c, d, a, b, in[6] + obK1, 11);
+	OBROUND(FOO, b, c, d, a, in[7] + obK1, 19);
+
+	/* Round 2 */
+	OBROUND(GEEK, a, b, c, d, in[1] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[3] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[5] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[7] + obK2, 13);
+	OBROUND(GEEK, a, b, c, d, in[0] + obK2,  3);
+	OBROUND(GEEK, d, a, b, c, in[2] + obK2,  5);
+	OBROUND(GEEK, c, d, a, b, in[4] + obK2,  9);
+	OBROUND(GEEK, b, c, d, a, in[6] + obK2, 13);
+
+	/* Round 3 */
+	OBROUND(HECK, a, b, c, d, in[3] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[7] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[2] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[6] + obK3, 15);
+	OBROUND(HECK, a, b, c, d, in[1] + obK3,  3);
+	OBROUND(HECK, d, a, b, c, in[5] + obK3,  9);
+	OBROUND(HECK, c, d, a, b, in[0] + obK3, 11);
+	OBROUND(HECK, b, c, d, a, in[4] + obK3, 15);
+
+	return buf[1] + b;	/* "most hashed" word */
+	/* Alternative: return sum of all words? */
+}
+
+unsigned long obsd_get_random_long(void)
+{
+	static time_t   rekey_time;
+	static __u32    secret[12];
+	time_t          t;
+
+	/*
+	 * Pick a random secret every OB_REKEY_INTERVAL seconds.
+	 */
+	t = get_seconds();
+	if (!rekey_time || (t - rekey_time) > OB_REKEY_INTERVAL) {
+		rekey_time = t;
+		get_random_bytes(secret, sizeof(secret));
+	}
+
+	secret[1] = half_md4_transform(secret+8, secret);
+	secret[0] = half_md4_transform(secret+8, secret);
+	return *(unsigned long *)secret;
+}
+
+static __u16
+pmod(__u16 gen, __u16 exp, __u16 mod)
+{
+	__u16 s, t, u;
+
+	s = 1;
+	t = gen;
+	u = exp;
+
+	while (u) {
+		if (u & 1)
+			s = (s * t) % mod;
+		u >>= 1;
+		t = (t * t) % mod;
+	}
+	return (s);
+}
+
+static void
+ip_initid(void)
+{
+	__u16 j, i;
+	int noprime = 1;
+
+	ru_x = ((tmp = obsd_get_random_long()) & 0xFFFF) % RU_M;
+
+	ru_seed = (tmp >> 16) & 0x7FFF;
+	ru_seed2 = obsd_get_random_long() & 0x7FFF;
+
+	ru_b = ((tmp = obsd_get_random_long()) & 0xfffe) | 1;
+	ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
+	while (ru_b % 3 == 0)
+		ru_b += 2;
+
+	j = (tmp = obsd_get_random_long()) % RU_N;
+	tmp = tmp >> 16;
+
+	while (noprime) {
+		for (i = 0; i < PFAC_N; i++)
+			if (j % pfacts[i] == 0)
+				break;
+
+		if (i >= PFAC_N)
+			noprime = 0;
+		else
+			j = (j + 1) % RU_N;
+	}
+
+	ru_g = pmod(RU_GEN, j, RU_N);
+	ru_counter = 0;
+
+	ru_reseed = xtime.tv_sec + RU_OUT;
+	ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
+}
+
+__u16
+ip_randomid(void)
+{
+	int i, n;
+
+	if (ru_counter >= RU_MAX || time_after(get_seconds(), ru_reseed))
+		ip_initid();
+
+	if (!tmp)
+		tmp = obsd_get_random_long();
+
+	n = tmp & 0x3;
+	tmp = tmp >> 2;
+	if (ru_counter + n >= RU_MAX)
+		ip_initid();
+	for (i = 0; i <= n; i++)
+		ru_x = (ru_a * ru_x + ru_b) % RU_M;
+	ru_counter += i;
+
+	return ((ru_seed ^ pmod(ru_g, ru_seed2 ^ ru_x, RU_N)) | ru_msb);
+}
+
+static __u16
+tcp_rndiss_encrypt(__u16 val)
+{
+	__u16 sum = 0, i;
+
+	for (i = 0; i < TCP_RNDISS_ROUNDS; i++) {
+		sum += 0x79b9;
+		val ^= ((__u16) tcp_rndiss_sbox[(val ^ sum) & 0x7f]) << 7;
+		val = ((val & 0xff) << 7) | (val >> 8);
+	}
+
+	return val;
+}
+
+static void
+tcp_rndiss_init(void)
+{
+	get_random_bytes(tcp_rndiss_sbox, sizeof (tcp_rndiss_sbox));
+	tcp_rndiss_reseed = get_seconds() + TCP_RNDISS_OUT;
+	tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000;
+	tcp_rndiss_cnt = 0;
+}
+
+__u32
+ip_randomisn(void)
+{
+	if (tcp_rndiss_cnt >= TCP_RNDISS_MAX ||
+	    time_after(get_seconds(), tcp_rndiss_reseed))
+		tcp_rndiss_init();
+
+	return (((tcp_rndiss_encrypt(tcp_rndiss_cnt++) |
+		  tcp_rndiss_msb) << 16) | (obsd_get_random_long() & 0x7fff));
+}
diff -Nur linux-2.6.11-rc2/net/sunrpc/xprt.c linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c
--- linux-2.6.11-rc2/net/sunrpc/xprt.c	2005-01-26 19:54:20.000000000 +0100
+++ linux-2.6.11-rc2.tx1/net/sunrpc/xprt.c	2005-01-28 22:27:18.644191872 +0100
@@ -1342,7 +1342,7 @@
  */
 static inline u32 xprt_alloc_xid(struct rpc_xprt *xprt)
 {
-	return xprt->xid++;
+	return (u32) obsd_get_random_long();
 }
 
 static inline void xprt_init_xid(struct rpc_xprt *xprt)

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Andi Kleen]

Stephen Hemminger <shemminger@osdl.org> writes:

> On Fri, 28 Jan 2005 12:45:17 -0800
> "David S. Miller" <davem@davemloft.net> wrote:
>
>> On Fri, 28 Jan 2005 21:34:52 +0100
>> Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:
>> 
>> > Attached the new patch following Arjan's recommendations.
>> 
>> No SMP protection on the SBOX, better look into that.
>> The locking you'll likely need to add will make this
>> routine serialize many networking operations which is
>> one thing we've been trying to avoid.
>> 
>
> per-cpu would be the way to go here.

I don't think so no - just doing per cpu counters you
risk nearby duplicates, which can cause even easier data corruption 
(e.g. during ip fragment reassembly - it is already very weak
and making it weaker is probably not a good idea) 

If you want SMP performance for ipids you can resurrect
the old "cookie jar" approach I used in 2.4 time frame to get
rid of inetpeers. The idea was that you have global state,
and each CPU would regenerate some numbers from the state,
then store them in a private "jar" and use them use, then
look at the global state with locking again etc.

This can be tuned on how big the jar is - the bigger the
smaller the sequence space (risky for 16bit ipids), but
the better the scalability.

But before doing anything like this I would recommend
that someone skilled in cryptography evaluates the security
of these functions carefully and see if it actually has any 
advantages. I remember that Andrey S. broke
some of the "cool" "secure" openbsd IDs easily some years ago.

At least for ipids I'm utterly sceptical. 16bits are just
hopeless.

-Andi

Re: [PATCH] OpenBSD Networking-related randomization port

[Arjan van de Ven]

On Fri, 2005-01-28 at 23:12 +0100, Lorenzo Hernández García-Hierro
wrote:
> El vie, 28-01-2005 a las 21:47 +0100, Arjan van de Ven escribió:
> > as for obsd_get_random_long().. would it be possible to use the
> > get_random_int() function from the patches I posted the other day? They
> > use the existing random.c infrastructure instead of making a copy...
> 
> As seen at
> http://www.kernel.org/pub/linux/kernel/people/arjan/execshield/00-randomize-A0 you can suppose that there's 


I actually meant
http://www.kernel.org/pub/linux/kernel/people/arjan/randomize/02-
randomize-infrastructure
which I posted for inclusion in the main kernel 2 or 3 days ago.
That's nice and stand alone to get a random value; we should be able to
share that.

Re: [PATCH] OpenBSD Networking-related randomization port

[Arjan van de Ven]

On Fri, 2005-01-28 at 23:12 +0100, Lorenzo Hernández García-Hierro
wrote:
> El vie, 28-01-2005 a las 21:47 +0100, Arjan van de Ven escribió:
> > as for obsd_get_random_long().. would it be possible to use the
> > get_random_int() function from the patches I posted the other day? They
> > use the existing random.c infrastructure instead of making a copy...
> 
> As seen at
>  the functions at obsd_rand.c so we wouldn't need to add more maintenance overhead, I hope you can understand why I want it like that

I actually DON'T understand that. 
What you say kinda sorta makes sense if you're an external patch. But if
you are inside the kernel (that was the goal of this patch, right?) then
the argument is actually entirely the wrong way around...

Re: [PATCH] OpenBSD Networking-related randomization port

[Valdis.Kletnieks]

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

On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:

> as for obsd_get_random_long().. would it be possible to use the
> get_random_int() function from the patches I posted the other day? They
> use the existing random.c infrastructure instead of making a copy...
> 
> I still don't understand why you need a obsd_rand.c and can't use the
> normal random.c

Note that obsd_rand.c started off life as a BSD-licensed file - I was told
that was a show-stopper when I submitted basically the same patch a while back.

So re-working it to use get_random_int()  would be a good idea, I think....

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Florian Weimer]

* Lorenzo Hernández García-Hierro:

> As it's impact is minimal (in performance and development/maintenance
> terms), I recommend to merge it, as it gives a basic prevention for the
> so-called system fingerprinting (which is used most by "kids" to know
> how old and insecure could be a target system, many time used as the
> first, even only-one, data to decide if attack or not the target host)
> among other things.

The most important result of such a patch is source port randomization
for DNS queries to resolvers.  This gives you a few more bits (DNS
itself has just a 16 bit "unique" ID, which isn't too hard to
brute-force these days, unfortunately).

Re: [PATCH] OpenBSD Networking-related randomization port

[Adrian Bunk]

On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:
> On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:
> 
> > as for obsd_get_random_long().. would it be possible to use the
> > get_random_int() function from the patches I posted the other day? They
> > use the existing random.c infrastructure instead of making a copy...
> > 
> > I still don't understand why you need a obsd_rand.c and can't use the
> > normal random.c
> 
> Note that obsd_rand.c started off life as a BSD-licensed file - I was told
> that was a show-stopper when I submitted basically the same patch a while back.
>...

At least the three clause BSD license is GPL compatible.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El lun, 31-01-2005 a las 17:50 +0100, Adrian Bunk escribió:
> On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:
> > On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:
> > 
> > > as for obsd_get_random_long().. would it be possible to use the
> > > get_random_int() function from the patches I posted the other day? They
> > > use the existing random.c infrastructure instead of making a copy...
> > > 
> > > I still don't understand why you need a obsd_rand.c and can't use the
> > > normal random.c
> > 
> > Note that obsd_rand.c started off life as a BSD-licensed file - I was told
> > that was a show-stopper when I submitted basically the same patch a while back.
> >...
> 
> At least the three clause BSD license is GPL compatible.
> 

Yes, AFAIK :)

I will try to follow Arjan's recommendations on using his functions
instead of obsd ones, even if I think it should be alone in the current
file.
Also I will split up the patch.

I will do it as soon as I get time for it, I need first to work out a
cleaner vsec (no more code in headers and such) and also a sys_chroot()
hook that I requested yesterday on the bugzilla, among the SELinux 2.4
backport which needs several fixes due to last 2.6 bk-commits reports.

Thanks for the comments,
Cheers.
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Valdis.Kletnieks]

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

On Mon, 31 Jan 2005 17:50:25 +0100, Adrian Bunk said:
> On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:

> > Note that obsd_rand.c started off life as a BSD-licensed file - I was told
> > that was a show-stopper when I submitted basically the same patch a while back.
> >...
> 
> At least the three clause BSD license is GPL compatible.

The copy of obsd_rand.c I have hass the problematic 4-clause version.  It looks
to me like we'd need to get Michael Shalayeff, Theodore T'so, and Niels Provos
to all agree to re-license under the 3-clause variant.  Using Arjan's code is
most likely the better approach...

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El lun, 31-01-2005 a las 14:42 -0500, Valdis.Kletnieks@vt.edu escribió:
> On Mon, 31 Jan 2005 17:50:25 +0100, Adrian Bunk said:
> > On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:
> 
> > > Note that obsd_rand.c started off life as a BSD-licensed file - I was told
> > > that was a show-stopper when I submitted basically the same patch a while back.
> > >...
> > 
> > At least the three clause BSD license is GPL compatible.
> 
> The copy of obsd_rand.c I have hass the problematic 4-clause version.  It looks
> to me like we'd need to get Michael Shalayeff, Theodore T'so, and Niels Provos
> to all agree to re-license under the 3-clause variant.  Using Arjan's code is
> most likely the better approach...

Then we would in that way ;)

Arjan, I will give it a further look, is there anything you want to
comment about it before I start?

I will re-code it to put the helper functions in random.c.

Thanks in advance,
Cheers.
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Ingo Molnar]

* Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:

> > At least the three clause BSD license is GPL compatible.
> 
> Yes, AFAIK :)
> 
> I will try to follow Arjan's recommendations on using his functions
> instead of obsd ones, even if I think it should be alone in the
> current file. Also I will split up the patch.

could you please also react to this feedback:

  http://marc.theaimsgroup.com/?l=linux-kernel&m=110698371131630&w=2

to quote a couple of key points from that very detailed security
analysis:

" I'm not sure how the OpenBSD code is better in any way.  (Notice that
  it uses the same "half_md4_transform" as Linux; you just added another
  copy.) Is there a design note on how the design was chosen? "

that mail also includes a much smaller patch to random.c.

( Obviously the more fundamental questions have to be solved prior
solving code-level problems, patch splitup and patch ordering - often
one ends up having a much smaller patch to work with, by thinking more
about the fundamentals. )

	Ingo

Re: [PATCH] OpenBSD Networking-related randomization port

[linux]

> could you please also react to this feedback:
>
>   http://marc.theaimsgroup.com/?l=linux-kernel&m=110698371131630&w=2
> 
> to quote a couple of key points from that very detailed security
> analysis:
> 
> " I'm not sure how the OpenBSD code is better in any way.  (Notice that
>   it uses the same "half_md4_transform" as Linux; you just added another
>   copy.) Is there a design note on how the design was chosen? "

Just note that, in addition to the security aspects, there are also a
whole set of multiprocessor issues.  OpenBSD added SMP support in June
2004, and it looks like this code dates back to before that.  It might
be worth looking at what OpenBSD does now.

Note that I have NOT looked at the patch other than the TCP ISN
generation.  However, given the condition of the ISN code, I am inclined
to take a "guilty until proven innocent" view of the rest of it.
Don't merge it until someone has really grokked it, not just kibitzed
about code style issues.

(The homebrew 15-bit block cipher in this code does show how much the
world needs a small block cipher for some of these applications.)

Re: [PATCH] OpenBSD Networking-related randomization port

[Bill Davidsen]

Arjan van de Ven wrote:
> On Fri, 2005-01-28 at 18:17 +0100, Lorenzo Hernández García-Hierro
> wrote:
> 
>>Hi,
>>
>>Attached you can find a split up patch ported from grSecurity [1], as
>>Linus commented that he wouldn't get a whole-sale patch, I was working
>>on it and also studying what features of grSecurity can be implemented
>>without a development or maintenance overhead, aka less-invasive
>>implementations.
> 
> 
> 
> why did you make it a config option? This is the kind of thing that is
> either good or isn't... at which point you can get rid of a lot of, if
> not all the ugly ifdefs the patch adds.

If there is a performance hit (there is), it's not bad to have it be an 
option, since some people will choose to go fast ("damn the torpedos, 
full speed ahead). Your point on ifdefs *may* be able to be addressed 
somewhat by putting them in macros, or similar tricks. But some are 
going to be visible even so, and you're right, they are distracting.
> 
> Also, why does it need to enhance the random driver this much, the
> random driver already has a facility to provide pseudorandom numbers
> good enough for networking use (eg the PRNG rekeys often enough with
> real entropy that brute forcing it shouldn't be possible).

I'm curious about this one as well, unless there's some proof that the 
output is "better" by actual analysis, why change? And that's better in 
terms of realized security, not by some change in the 5th insignificant 
digit of a statistical measure.

In general I do like to have the option of more security as a tradeoff, 
even if it is more than is generally needed.


-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: [PATCH] OpenBSD Networking-related randomization port

[Matt Mackall]

On Mon, Jan 31, 2005 at 09:03:19PM +0100, Lorenzo Hern?ndez Garc?a-Hierro wrote:
> Arjan, I will give it a further look, is there anything you want to
> comment about it before I start?
> 
> I will re-code it to put the helper functions in random.c.

Do it against -mm, please, there are something like 30 patches against
random.c there already. And please cc: me on any changes there.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH] OpenBSD Networking-related randomization port

[linux]

*Sigh*.  This thread is heading into the weeds.

I have things I should be doing instead, but since nobody seems to
actually be looking at what the patch *does*, I guess I'll have
to dig into it a bit more...

Yes, licensing issues need to be resolved before a patch can go in.
Yes, code style standards needs to be kept up.
And yes, SMP-locking issues need to be looked at.
(And yes, ipv6 needs to be looked at, too!)

But before getting sidetracked into the fine details, could
folks please take a step back from the trees and look at the forest?

Several people have asked (especially when the first patch came out),
but I haven't seen any answers to the Big Questions:

1) Does this patch improve Linux's networking behaviour in any way?
2) Are the techniques in this patch a good way to achieve those
   improvements?


Let's look at the various parts of the change:

- Increases the default random pool size.
  Opinion: whatever.  No real cost, except memory.  Increases the
  maximum amount that can be read from /dev/random without blocking.
  Note that this is already adjustable at run time, so the question
  is why put it in the kernel config.

  If you want this, I'd suggest instead an option under CONFIG_EMBEDDED to
  shrink the pools and possibly get rid of the run-time changing code,
  then you could increase the default with less concern.

- Changes the TCP ISN generation algorithm.
  I have't seen any good side to this.  The current algorithm can be
  used for OS fingerprinting based on starting two TCP connections from
  different sources (ports or IPs) and noticing that the ISNs
  only differ in the low 24 bits, but is that a serious issue?
  If it is, there are better ways to deal with it that still preserve
  the valuable timer property.

  I point out that the entire reason for the cryptographically
  marginal half_md4_transform oprtation was that a full MD5 was a very
  noticeable performance bottleneck; the hash was only justified by
  the significant real-world attacks.  obsd_get_random uses two calls
  to half_md4_transform.  Which is the same cost as a full MD4 call.
  Frankly, they could just change half_md4_transform to return 64 bits
  instead of 32 and make do with one call.

- Changes to the IP ID generation algorithm.
  All it actually does is change the way the initial inet->id is
  initialized for the inet_opt structure associated with the TCP socket.
  And if you look at ip_output.c:ip_push_pending_frames(), you'll see
  that, if DF is set (as is usual for a TCP connection), iph->id (the
  actual IP header ID) is set to htons(inet->id++).  So it's still
  an incrementing sequence.

  This is in fact (see the comment in ip.h:ip_select_ident()) a workaround
  for a Microsoft VJ compression bug.  The fix was added in 2.4.4 (via
  DaveM's zerocopy-beta-3 patch); before that, Linux 2.4 sent a constant
  zero as the IP ID of DF packets.  See discussion at
	http://www.postel.org/pipermail/end2end-interest/2001-May/thread.html
	http://tcp-impl.lerc.nasa.gov/tcp-impl/list/archive/2378.html
  I'm not finding the diagnosis of the problem.  I saw one report at
	http://oss.sgi.com/projects/netdev/archive/2001-01/msg00006.html
  and Dave Miller is pretty much on top of it when he posts
	http://marc.theaimsgroup.com/?l=linux-kernel&m=98275316400452&w=2
  but I haven't found the actual debugging leading to the conclusion.

  This also led to some discussion of the OpenBSD IP ID algorithm that
  I haven't fully waded through at
	http://mail-index.netbsd.org/tech-net/2003/11/

  If the packet is fragmentable (the only time the IP ID is really
  needed by the receiver), it's done by route.c:__ip_select_ident().
  Wherein the system uses inet_getid to assign p->ip_id_count++
  based on the route cache's struct inet_peer *p.

  (If the route cache is OOM, the system falls back on random IP ID
  assignment.)

  This latter technique nicely prevents the sort of stealth port
  scanning that was mentioned earlier in this thread, and prevents
  a person at address A from guessing the IP ID range I'm using to
  talk to address B.  So note that the boast about "Randomized IP IDs"
  in the grsecurity description at
	http://www.gentoo.org/proj/en/hardened/grsecurity.xml
  is, as far as I can tell from a quick look at the code, simply false.

  As for the algorithm itself, it's described at
	http://www.usenix.org/events/usenix99/full_papers/deraadt/deraadt_html/node18.html
  but it's not obvious to me that it'd be hard to cryptanalyze given
  a stream of consecutive IDs.  You need to recover:
  - The n value for each inter-ID gap,
  - The LCRNG state ru_a, ru_x, ru_b,
  - The 15-bit XOR masks ru_seed and ru_seed2, and
  - The discrete log generator ru_j (ru_g = 2^ru_j mod RU_N).
    Which is actually just a multiplier (mod RU_N-1  = 32748) on
    the input to the pmod() operation.

  So the IP ID generation can be summarized as:

  ru_x = (ru_a * ru_x + ru_b) % 31104;	/* Repeated 1..4 times */
  exp = ((ru_x ^ ru_seed2) + ru_j) % 32748;
  return ru_seed ^ pmod(2, exp, 32749);

  Now, if you can guess ru_seed, then the pmod() operation is simply a
  bijection that can be looked up in a table, and then it's just
  a matter of untangling a slightly elaborated LCRNG.

- Changes the sun RPC XID allocation algorithm.
  Note that each connection is already initialized with a secure random
  number; the only change is whether the IDs used are simply incrementing
  from there or randomized each time one is needed.

  First of all and very importantly, obsd_get_random_long() does
  indeed generate a *random* number, which could be the *same* number as
  the last one.  This could be VERY BAD for RPC XIDs, which have to be
  unique so the client can match the reply with the request.  Note that
  Theo de Raadt knows better than do do that:
	http://www.usenix.org/events/usenix99/full_papers/deraadt/deraadt_html/node18.html
  Looking at the OpenBSD code at
	http://www.openbsd.org/cgi-bin/cvsweb/src/sys/nfs/
  you can see that the NFS code in nfs_subs.c:nfsm_rpchead() generates
  a random starting xid and increments it by a random number 1..255
  each time.  The more general RPC code in krpc_subr.c:krpc_call()
  generates a fully random XID, constrained only to differ from the
  previous one.  This is because the call is synchronous and does
  not permit more than one outstanding request at a time.
  
  Anyway, if you wanted to do this, you'd have to add some checking
  to ensure that a request with that ID isn't already on the rq_list.
  Also, there appear to be some retransmit issues that mitigate against
  recycling them too fast (which is why OpenBSD forbids adjacent
  duplicates), but I haven't studied that in detail.


So in summary:
- Random pool: Few security issues, but on the other hand, why bother?
  It's run-time tunable already.
- TCP ISN: Proposed patch increases chance of TPC ISN reuse by breaking
  timer-based design specified in TCP RFC.  It doesn't appear to have
  any more cryptographic security.
- IP ID: Doesn't change the uses where it matters (DF flag clear).
  Doesn't change the fact that the IDs are still consecutive.  What's the
  freaking point?  And all that modular exponentiation that OpenBSD does
  is a pretty dubious security improvement.
- RPC XID: Broken; don't use.  And what's wrong with incrementing from
  a random start?  If an attacker can see your requests, he can generate
  a fake reply no matter what algorithm you use, and if he can't, then
  the random start is all you need to limit his chances.  The only thing
  a fully random sequence prevents against is that if an attacker can
  somehow tell when they've succeeded, an incrementing sequence lets
  them spoof furter replies easily.  You could apply a first level of
  protection by incrementing them by a random odd number rather than 1,
  but even then, why bother?

And, of ocurse, all of this has performance implications.  Linux is
justifiably proud of keeping down performance bloat by not wasting cycles
on fast paths if it can possibly be helped.  If we *do* find something to
improve, we should look at the goals and design the fastest way possible
to achieve that.  It's not at all clear that the current code patch is
the right implementation even if it *did* do something useful.

Before worrying about the small stuff, could we take a good look at the
Big Stuff?


I like to try to be polite to people contributing patches.  It's a lot
of work and I don't want to dishearten someone just starting.  I'd like
to be polite and encouraging when rejecting patches.

But everyone is so busy ignoring the elephant in the kitchen that I
shall have to forego politeness and shout a little.

It doesn't matter what the license is or whether it's against the Linus
tree or -mm or how the functions are names.

	 ********************************************** 
	************************************************
	*****                                      *****
	****  THIS PATCH DOESN'T FREAKING WORK!!!!  ****
	*****                                      *****
	************************************************
	 ********************************************** 

Ignoring all the *implementation* brokenness, it breaks the network
protocols, doesn't do what it claims to do, and what it tries to do
isn't of any benefit over the existing code.  It's not resting, it's not
stunned, and it's not pining for the fjords.  It just plain doesn't work.

If there are any claimed benefits that you want, the first thing to do
is throw it away, go back to square one, and come up with an algorithm
that actually achieves that benefit.

I keep hearing people boast about how the many eyes reviewing open
source code improves the code quality and makes it harder to insert
back doors into the system.  If something this bad can get this many
comments without anyone pointing out the emperor's clothing arrangements,
the situation is pretty pitiful.


There *are* things in OpenBSD, like randomized port assignment (as opposed
to the linear scan in tcp_v4_get_port()) that would be worth emulating.
Maybe worry about that first?

Re: [PATCH] OpenBSD Networking-related randomization port

[Lorenzo Hernández García-Hierro]

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

El mié, 02-02-2005 a las 17:17 +0000, linux@horizon.com escribió:
> There *are* things in OpenBSD, like randomized port assignment (as opposed
> to the linear scan in tcp_v4_get_port()) that would be worth emulating.
> Maybe worry about that first?
> 

Completely agreed with you, I was just trying to help with split up
patches, but, as your analysis shows, it's more a weak implementation
than a real security improvement.

All I can say, just ignore the patch.I will work on other (worthy)
issues that are in a bigger need.

Maybe I would work something out on randomized source ports, as soon as
I get time for it.

Note also that Brad fixed obsd_rand.c code this week, I've added him to
the CC list because there are things that may concern grSecurity he
should be able to comment further on it and discuss whatever concerns
*his* work (which is, BTW, a good thing (tm) to have in mind even if he
didn't send split up patches for each feature, which I really don't
know).

I've just ported it out of grsecurity.

Thanks for your meaningful comments,
Cheers.
-- 
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

[-- Attachment #2: Esta parte del mensaje está firmada digitalmente --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] OpenBSD Networking-related randomization port

[Stephen Hemminger]

On Wed, 02 Feb 2005 18:38:37 +0100
Lorenzo Hernández García-Hierro <lorenzo@gnu.org> wrote:

> El mié, 02-02-2005 a las 17:17 +0000, linux@horizon.com escribió:
> > There *are* things in OpenBSD, like randomized port assignment (as opposed
> > to the linear scan in tcp_v4_get_port()) that would be worth emulating.
> > Maybe worry about that first?
> > 

Recent 2.6 does a more advanced form of port randomization already
using address hash at connect time.  tcp_v4_get_port is only used for the case
of applications that explicitly bind to port zero to find a free port.

So the sequence:
	socket(); connect(); 
will assign a random port in a manner similar to sequence number creation

The sequence:
	socket(); bind(); connect();
assigns a simple linear increasing port value.  It could be randomized, but
most applications don't bother binding, so the first case is sufficient.

-- 
Stephen Hemminger	<shemminger@osdl.org>

Re: [PATCH] OpenBSD Networking-related randomization port

[Lennert Buytenhek]

On Thu, Feb 03, 2005 at 11:51:27AM -0800, Stephen Hemminger wrote:

> Recent 2.6 does a more advanced form of port randomization already
> using address hash at connect time.  tcp_v4_get_port is only used for
> the case of applications that explicitly bind to port zero to find a
> free port.

Is any such randomisation done or planned for UDP?


--L

Re: [PATCH] OpenBSD Networking-related randomization port

[Andi Kleen]

linux@horizon.com writes:
>
> (The homebrew 15-bit block cipher in this code does show how much the
> world needs a small block cipher for some of these applications.)

Doesn't TEA fill this niche? It's certainly used for this in the Linux
kernel, e.g. in reiserfs (although I have my doubts it is really useful
there) 

-Andi

Re: [PATCH] OpenBSD Networking-related randomization port

[linux]

> linux@horizon.com writes:
>> (The homebrew 15-bit block cipher in this code does show how much the
>> world needs a small block cipher for some of these applications.)
>
> Doesn't TEA fill this niche? It's certainly used for this in the Linux
> kernel, e.g. in reiserfs (although I have my doubts it is really useful
> there) 

Sorry; ambiguous parsing.  I meant "(small block) cipher", not "small
(block cipher)".  TEA is intended for the latter niche.  What I meant
was a cipher that could encrypt blocks smaller than 64 bits.

It's easy to make a smaller hash by just thowing bits away, but a block
cipher is a permutation, and has to be invertible.

For example, if I take a k-bit counter and encrypt it with a k-bit
block cipher, the output is guaranteed not to repeat in less than 2^k
steps, but the value after a given value is hard to predict.

There is a well-known technique for reducing the block size of a cipher
by a small factor, such as from a power of 2 to a prime number
slightly lower.  That is:

unsigned
encrypt_mod_n(unsigned x, unsigned n)
{
	assert(x < n);
	do {
		x = encrypt(x);
	} while (x >= n);
	return x;
}

It takes a bit of thinking to realize why this creates an bijection from
[0..n-1] -> [0..n-1], but it's kind of a neat "aha!" when it does.

Remember, encrypt() is a bijection from [0..N-1] -> [0..N-1] for some
N >= n.  Typically N = 2^k for some k.

However, this technique requires N/n calls to encrypt().  I.e.
n calls to encrypt_mod_n() will cause N calls to encrypt().

It's generally considered practical up to N/n = 2, so we can encrypt
modulo any modulus n if we have encrypt() functions for any N = 2^k a
power of 2.  I.e. a k-bit block cipher.

For example, suppose we want to encrypt 7-digit North American telephone
numbers.  These are of the form NXX-XXXX, where N is a digit other than
0 or 1, and X is any digit.  there are 8e6 possibilities.  Using this
scheme and a 23-bit block cipher, we can encrypt them to different valid
7-digit telephone numbers.

Likewise, 10-digit number with area codes, +1 NXX NXX-XXXX (but not
starting with N11) are also possible.  There are 792 area codes and
8e6 numbers for a total of 7776000000 < 2^33 combinations.

This sort of thing is very useful for adding encryption to protocols and
file formats not designed for it.


However, the standard literature is notably lacking in block ciphers
in funny block sizes.  There was one AES submission (The Hasty Pudding
Cipher, http://www.cs.arizona.edu/~rcs/hpc/) that supported variable
block sizes, but it was eliminated fairly early.


To start with, consider very small blocks: 1, 2 or 3 bits.
There are only two possible things encrypt() can do with a 1-bit value:
either invert it or leave it alone.

There are 4! = 24 possible 2-bit encryption operations.  Ideally, the
key should specify them all with equal probability, but 24 does not
evenly divide the (power of 2 sized) keyspace.  It is interesting to
look at how iniformly the possibilities are covered.

It's fun to consider a Feistel network, dividing the plaintext into 1-bit
L and R values, and alternating L ^= f(R), R ^= f(L) for (not nexessarily
invertible) round functions f.  Since there are only 4 possible 1-bit
functions (1, 0, x and !x), you can consider each round to have an
independent 2-bit round subkey and see how the cipher's uniformity
develops as you increase the number of rounds and the key length to go
with it.

There are 8! = 40320 3-bit encryption operations.  Again, all should be
covered uniformly.  An odd number of bits makes a Feistel design more
challenging.  But if you don't allow odd numbers of bits, you have to push
the shrinking technique it to N/n = 4, which starts to get unpleasant.

Re: [PATCH] OpenBSD Networking-related randomization port

[Roland Dreier]

    linux> It's easy to make a smaller hash by just thowing bits away,
    linux> but a block cipher is a permutation, and has to be
    linux> invertible.

    linux> For example, if I take a k-bit counter and encrypt it with
    linux> a k-bit block cipher, the output is guaranteed not to
    linux> repeat in less than 2^k steps, but the value after a given
    linux> value is hard to predict.

Huh?  What if my cipher consists of XOR-ing with a k-bit pattern?
That's a permutation on the set of k-bit blocks but it happens to
decompose as a product of (non-overlapping) swaps.

In general for more realistic block ciphers like DES it seems
extremely unlikely that the cipher has only a single orbit when viewed
as a permutation.  I would expect a real block cipher to behave more
like a random permutation, which means that the expected number of
orbits for a k-bit cipher should be about ln(2^k) or roughly .7 * k.

 - R.

Re: [PATCH] OpenBSD Networking-related randomization port

[linux]

    linux> It's easy to make a smaller hash by just thowing bits away,
    linux> but a block cipher is a permutation, and has to be
    linux> invertible.

    linux> For example, if I take a k-bit counter and encrypt it with
    linux> a k-bit block cipher, the output is guaranteed not to
    linux> repeat in less than 2^k steps, but the value after a given
    linux> value is hard to predict.

> Huh?  What if my cipher consists of XOR-ing with a k-bit pattern?
> That's a permutation on the set of k-bit blocks but it happens to
> decompose as a product of (non-overlapping) swaps.
> 
> In general for more realistic block ciphers like DES it seems
> extremely unlikely that the cipher has only a single orbit when viewed
> as a permutation.  I would expect a real block cipher to behave more
> like a random permutation, which means that the expected number of
> orbits for a k-bit cipher should be about ln(2^k) or roughly .7 * k.

I think you misunderstand; your comments don't seem to make sense unless
I assume you're imagining output feedback mode:

x[0] = encrypt(IV)
x[1] = encrypt(x[0])
x[2] = encrypt(x[1])
etc.

Obviously, this pattern will repeat after some unpredictable interval.
(However, owing to the invertibility of encryption, looping can
be easily detected by noticing that x[i] = IV.)

But I was talking about counter mode:

x[0] = encrypt(0)
x[1] = encrypt(1)
x[2] = encrypt(2)
etc.

It should be obvious that this will not repeat until the counter
overflows k bits and you try to compute encrypt(2^k) = encrypt(0).

One easy way to generate unpredictable 16-bit port numbers that don't
repeat too fast is:

highbit = 0;
for (;;) {
	generate_random_encryption_key(key);
	for (i = 0; i < 20000; i++)
		use(highbit | encrypt15(i, key));
	highbit ^= 0x8000;
}

Note that this does NOT use all 32K values before switching to another
key; if that were the case, an attacker who kept a big bitmap of reviously
seen values could preduct the last few values based on knowing what
hadn't been seen already.


Of course, you can always wrap a layer of Knuth's Algorithm B
(randomization by shuffling) around anything:

#include "basic_rng.h"

#define SHUFFLE_SIZE 32	/* Power of 2 is more efficient */

struct better_rng_state {
	struct basic_rng_state basic;
	unsigned y;
	unsigned z[SHUFFLE_SIZE];
};

void
better_rng_seed(struct better_rng_state *state, unsigned seed)
{
	unsigned i;
	basic_rng_seed(&state->basic, seed);

	for (i = 0; i < SHUFFLE_SIZE; i++)
		state->z[i] = basic_rng(&state->basic);
	state->y = basic_rng(&state->basic) % SHUFFLE_SIZE;
}

unsigned
better_rng(struct better_rng_state *state)
{
	unsigned x = state->z[state->y];
	state->y = (state->z = basic_rng(&state->basic)) % SHUFFLE_SIZE;
	return x;
}

(You can reduce code size by reducing modulo SHUFFLE_SIZE when you use
state->y rather than when storing into it, but I have done it the other
way to make clear exactly how much "effective" state is stored.  You can
also just initialize state->y to a fixed value.)

Re: [PATCH] OpenBSD Networking-related randomization port

[linux]

> It adds support for advanced networking-related randomization, in
> concrete it adds support for TCP ISNs randomization

Er... did you read the existing Linux TCP ISN generation code?
Which is quite thoroughly randomized already?

I'm not sure how the OpenBSD code is better in any way.  (Notice that it
uses the same "half_md4_transform" as Linux; you just added another copy.)
Is there a design note on how the design was chosen?


I don't wish to be *too* discouraging to someone who's *trying* to help,
but could you *please* check a little more carefully in future to
make sire it's actually an improvement?

I fear there's some ignorance of what the TCP ISN does, why it's chosen
the way it is, and what the current Linux algorithm is designed to do.
So here's a summary of what's going on.  But even as a summary, it's
pretty long...


First, a little background on the selection of the TCP ISN...

TCP is designed to work in an environment where packets are delayed.
If a packet is delayed enough, TCP will retransmit it.  If one of
the copies floats around the Internet for long enough and then arrives
long after it is expected, this is a "delayed duplicate".

TCP connections are between (host, port, host port) quadruples, and
packets that don't match some "current connection" in all four fields
will have no effect on the current connection.  This is why systems try
to avoid re-using source port numbers when making connections to
well-known destination ports.

However, sometimes the source port number is explicitly specified and
must be reused.  The problem then arises, how do we avoid having any
possible delayed packets from the previous use of this address pair show
up during the current connection and confuse the heck out of things by
acknowledging data that was never received, or shutting down a connection
that's supposed to stay open, or something like that?

First of all, protocols assume a maximum packet lifetime in the Internet.
The "Maximum Segment Lifetime" was originally specified as 120 seconds,
but many implementations optimize this to 60 or 30 seconds.  The longest
time that a response can be delayed is 2*MSL - one delay for the packet
eliciting the response, and another for the response.

In truth, there are few really-hard guarantees on how long a packet can
be delayed.  IP does have a TTL field, and a requirement that a packet's
TTL field be decremented for each hop between routers *or each second of
delay within a router*, but that latter portion isn't widely implemented.
Still, it is an identified design goal, and is pretty reliable in
practice.


The solution is twofold: First, refuse to accept packets whose
acks aren't in the current transmission window.  That is, if the
last ack I got was for byte 1000, and I have sent 1100 bytes
(numbers 0 through 1099), then if the incoming packet's ack isn't
somewhere between 1000 and 1100, it's not relevant.  If it's
950, it might be an old ack from the current connection (which
doesn't include anything interesting), but in any case it can be
safely ignored, and should be.

The only remaining issue is, how to choose the first sequence number
to use in a connection, the Initial Sequence Number (ISN)?

If you start every connection at zero, then you have the risk that
packets from an old connection between the same endpoints will
show up at a bad time, with in-range sequence numbers, and confuse
the current connection.

So what you do is, start at a sequence number higher than the
last one used in the old connection.  Then there can't be any
confusion.  But this requires remembering the last sequence number
used on every connection ever.  And there are at least 2^48 addresses
allowed to connect to each port on the local machine.  At 4 bytes
per sequence number, that's a Petabyte of storage...

Well, first of all, after 2*MSL, you can forget about it and use
whatever sequence number you like, because you know that there won't
be any old packets floating around to crash the party.

But still, it can be quite a burden on a busy web server.  And you might
crash and lose all your notes.  Do you want to have to wait 2*MSL before
rebooting?


So the TCP designers (I'm not on page 27 of RFC 793, if you want to follow
along) specified a time of day based ISN.  If you use a clock to generate
an ISN which counts up faster than your network connection can send
data (and thus crank up its sequence numbers), you can be sure that your
ISN is always higher than the last one used by an old connection without
having to remember it explicitly.

RFC 793 specifies a 250,000 bytes/second counting rate.  Most
implementations since Ethernet used a 1,000,000 byte/second counting
rate, which matches the capabilities of 10base5 and 10base2 quite well,
and is easy to get from the gettimeofday() call.

Note that there are two risks with this.  First, if the connection actually
manages to go faster than the ISN clock, the next connection's ISN will
be in the middle of the space the earlier connection used.  Fortunately,
the kind of links where significant routing delay appear are generally
slower ones where 1 Mbyte/sec is a not too unreasonable limit.  Your
gigabit LAN isn't going to be delaying packets by seconds.

The second is that a connection will be made and do nothing for 4294
seconds until the ISN clock is about to wrap around and then start
doing packets "ahead of" the ISN clock.  If it then closes the connection
and a new one opens, once again you have sequence number overlap.

If you read old networking papers, there were a bunch of proposals for
occasional sequence number renegotiation to solve this problem, but in the
end people decided to not worry about it, and it hasn't been a problem
in practice.



Anyway... fast forward out of the peace and love decade and welcome to
the modern Internet, with people *trying* to mess up TCP connections.
This kind of attack from within was, unfortunately, not one of the
scenarios that the initial Internet designers considered, and it's
been a bit of a problem since.

All this careful worry about packets left over from an old connection
randomly showing up and messing things up, when we have people *creating*
packets deliberately crafted to mess things up!  A whole separate problem.
In particular, using the simple timer-based algorithm, I can connect to
a server, look at the ISN it offers me, and know that thats the same
ISN it's offering to other people connecting at the same time.  So I
can create packets with a forged source address and approximately-valid
sequence numbers and bombard the connection with them, cutting off that
server's connection to some third party.  Even if I can't see any of
the traffic on the connection.

So people sat down and did some thinking.  How to deal with this?
Harder yet, how to deal with this without redesigning TCP from scratch?

Well, if a person wants to mess up their *own* connections, we can't
stop them.  The fundamental problem is that an attacker A can figure
out the sequence numbers that machines B and C are using to talk to
each other.  So we'd like to make the sequence numbers for every
connection unique and not related to the sequence numbers used on any
other connections.  So A can talk to B and A can talk to C and still not
be able to figure out the sequence numbers that B and C are using between
themselves.


Fortunately, it is entirely possible to combine this with the clock-based
algorithm and get the best of both worlds!  All we need is a random offset,
unique for every (address, port, address, port) quadruple, to add to
the clock value, and we have all of the clock-based guarantees preserved
within every pair of endpoints, but unrelated endpoints have their ISNs
at some unpredictable offset relative to each other.

And for generating such a random offset, we can use cryptography.
Keep a single secret key, and hash together the endpoint addresses,
and you can generate a random 32-bit ISN offset.  Add that to the
current time, and everything is golden.  A can connect to B and
see and ISN, but would need to do some serious cryptanalysis to
figure out what ISN B is using to talk to C.


Linux actually adds one refinement.  For speed, it uses a very
stripped-down cryptographic hash function.  To guard against that
being broken, it generates a new secret every 5 minutes.  So an
attacker only has 5 minutes to break it.

The cryptographic offset is divided into 2 parts.  The high 8 bits are
a sequence number, incremented every time the secret is regenerated.
The low 24 bits are produced by the hash.  So 5 minutes after booting,
the secret offset changes from 0x00yyyyyy to 0x01zzzzzz.  This is at
least +1, and at most +0x1ffffff.  On average, the count is going up
by 2^24 = 16 million every 300 seconds.  Which just adds a bit to the
basic "1 million per second" ISN timer.

The cost is that the per-connection part of the ISN offset is limited
to 24 and not 32 bits, but a cryptanalytic attack is pretty much
precluded by the every-5-minutes thing.  The rekey time and the number of
really-unpredictable bits have to add up to not wrapping the ISN space
too fast.  (Although the 24 bits could be increased to 28 bits without
quite doubling the ISN counting speed.  Or 27 bits if you want plenty
of margin.  Could I suggest that as an improvement?)

--- drivers/char/random.c	2004-12-04 09:24:19.000000000 +0000
+++ drivers/char/random.c	2005-01-29 07:20:37.000000000 +0000
@@ -2183,26 +2183,26 @@
 #define REKEY_INTERVAL	(300*HZ)
 /*
  * Bit layout of the tcp sequence numbers (before adding current time):
- * bit 24-31: increased after every key exchange
- * bit 0-23: hash(source,dest)
+ * bit 27-31: increased after every key exchange
+ * bit 0-26: hash(source,dest)
  *
  * The implementation is similar to the algorithm described
  * in the Appendix of RFC 1185, except that
  * - it uses a 1 MHz clock instead of a 250 kHz clock
  * - it performs a rekey every 5 minutes, which is equivalent
- * 	to a (source,dest) tulple dependent forward jump of the
+ * 	to a (source,dest) tuple dependent forward jump of the
  * 	clock by 0..2^(HASH_BITS+1)
  *
- * Thus the average ISN wraparound time is 68 minutes instead of
- * 4.55 hours.
+ * Thus the average ISN wraparound time is 49 minutes instead of
+ * 4.77 hours.
  *
  * SMP cleanup and lock avoidance with poor man's RCU.
  * 			Manfred Spraul <manfred@colorfullife.com>
  * 		
  */
-#define COUNT_BITS	8
+#define COUNT_BITS	5
 #define COUNT_MASK	( (1<<COUNT_BITS)-1)
-#define HASH_BITS	24
+#define HASH_BITS	27
 #define HASH_MASK	( (1<<HASH_BITS)-1 )
 
 static struct keydata {


Anyway, in comparison, the algorithm in your patch (and presumably
OpenBSD, although I haven't personally compared it) uses a clock
offset generated fresh for each connection.  There's a global counter
(tcp_rndiss_cnt; I notice you don't have any SMP locking on it) which
is incremented every time an ISN is needed.  It's rekeyed periodically,
and the high bit (tcp_rndiss_msb) of the delta is used like the COUNT_BITS
in the Linux algorithm.

The ISN is generated as the high sequence bit, then 15 bits of encrypted
count (with some homebrew cipher I don't recognize), then a constant
zero bit (am I reading that right), then the 15 low-order bits are
purely random.


It's a slightly different algorithm, but it does a very similar function.
The main downsides are that the sequence number can easily go backwards
(there's no guarantee that consecutive calls will return increasing
numbers since tcp_rndiss_encrypt scrambles the high 15 bits), and
that it's not SMP-safe.  Two processors could read and use the same
tcp_rndiss_cnt value at the same time, or (more likely) both call
tcp_rndiss_init at the same time and end up toggling tcp_rndiss_msb twice,
thereby destroying the no-rollback property it's trying to achieve.

Oh, and the single sequence bit in the offsets means that the
TCP ISN will wrap around very fast.  Every 10 minutes, or every
60000 TCP connections, whichever comes first.

Regarding the first issue, it's possible that the OpenBSD network stack
takes care to remember all connections for 2*MSL and continues the
sequence number if the endpoints are reused, thereby avoiding a call to
ip_randomisn entirely.

But the second deserves some attention.  The Linux code takes some care
to avoid having to lock anything in the common case.  The global count
makes that difficult.

Re: [PATCH] OpenBSD Networking-related randomization port

[Hank Leininger]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 2005-01-28, Stephen Hemminger said on linux-kernel:

> > "Randomized IP IDs hinders OS fingerprinting and will keep your
> > machine from being a bounce for an untraceable portscan."
> > 
> > References: [1]:
> > http://www.gentoo.org/proj/en/hardened/grsecurity.xml

> This is a very transitory effect, it works only because your machine
> is then different from the typical Linux machine; therefore the
> scanner will go on to the next obvious ones. But if this gets
> incorporated widely then the rarity factor goes away and this defense
> becomes useless.

This is true and not true.  Its utility for hindering OS fingerprints
will indeed diminish towards zero as it gets more popular.  But the bit
about keeping you from being used for untraceable port scans is real.

The way those scans work is basically:

  - I send something boring to you, an innocent bystander, and get your
    current IPID from your response
  - I send SYN packets to my target spoofed with your source address
    - If the target filters that port, it drops the SYN on the floor
    - If the target is not listening, it sends you an RST; you drop it on
      the floor
    - If the target is listening, it sends you a SYNACK; you reply with
      an RST which increments your IPID
  - I send another something boring to you, get your IPID from your
    response
  - I draw the conclusion that you did, or did not send an RST inbetween,
    thus I know if you received a SYNACK and the port is listening

It's rather nice, because the target saw only packets / a portscan
coming from you, and if anything you saw some unsolicited SYNACKs, and
whatever the "something boring" I've chosen to send to you for the IPID
heartbeats.

Of course this is only effective if:
  - the bystander (you) is quiescent
  - the bystander uses predictable (incrementing) IPIDs
  - the bystander will answer to "something boring" (ICMP, SYNs from
    source port 20, SYNACKs from source port 80, UDP from source port 53,
    whatever)

Only the user can do something about the first; distributions can do
something about the last, but the kernel can do something about the
middle.

And in a more general sense: why do I need to know how busy your network
stack is?  How popular (IPID, pkts/sec) your corporate webserver is?
How busy (TCP source ports, conns/sec) your outbound proxy is?  I don't.
If I want to know that stuff I should go pound sand.  That's why
network-stack randomness is a Good Thing[TM] if you can get it.

Thanks,

Hank Leininger <hlein@progressive-comp.com>
E407 AEF4 761E D39C D401  D4F4 22F8 EF11 861A A6F1
-----BEGIN PGP SIGNATURE-----

iD8DBQFB+pF/IvjvEYYapvERArpGAJ9fe8zWMEKbHdobvRS3Xa9V02LxLACfUx4i
VQnx7UmriLwF5niX4FCIr7A=
=HX4V
-----END PGP SIGNATURE-----