Re: [PATCH] OpenBSD Networking-related randomization port

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

[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

[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

[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.)