use random number generator to generate IPv6 fragment ID/flowlabel.

cleanup IPv6 flowlabel handling.  deraadt ok

10 files changed, 288 insertions, 31 deletions

diff --git a/sys/conf/files b/sys/conf/files
index 436e727dd25..886ed431948 100644
--- a/sys/conf/files
+++ b/sys/conf/files
@@ -1,4 +1,4 @@
-#	$OpenBSD: files,v 1.280 2003/09/26 00:19:23 mickey Exp $
+#	$OpenBSD: files,v 1.281 2003/10/01 21:41:05 itojun Exp $
 #	$NetBSD: files,v 1.87 1996/05/19 17:17:50 jonathan Exp $
 
 #	@(#)files.newconf	7.5 (Berkeley) 5/10/93
@@ -903,6 +903,7 @@ file netinet6/in6_proto.c		inet6
 file netinet6/dest6.c			inet6
 file netinet6/frag6.c			inet6
 file netinet6/icmp6.c			inet6
+file netinet6/ip6_id.c			inet6
 file netinet6/ip6_input.c		inet6
 file netinet6/ip6_forward.c		inet6
 file netinet6/ip6_mroute.c		inet6
diff --git a/sys/netinet/tcp_input.c b/sys/netinet/tcp_input.c
index 5b8b3270f41..5ceeb6ccc9b 100644
--- a/sys/netinet/tcp_input.c
+++ b/sys/netinet/tcp_input.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: tcp_input.c,v 1.132 2003/07/09 22:03:16 itojun Exp $	*/
+/*	$OpenBSD: tcp_input.c,v 1.133 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$NetBSD: tcp_input.c,v 1.23 1996/02/13 23:43:44 christos Exp $	*/
 
 /*
@@ -829,8 +829,6 @@ findpcb:
 			  if ((inp->inp_flags & INP_IPV6) != 0) {
 			    inp->inp_ipv6.ip6_hlim =
 			      oldinpcb->inp_ipv6.ip6_hlim;
-			    inp->inp_ipv6.ip6_flow =
-			      oldinpcb->inp_ipv6.ip6_flow;
 			  }
 			}
 #else /* INET6 */
@@ -1189,8 +1187,8 @@ findpcb:
 			sin6->sin6_len = sizeof(struct sockaddr_in6);
 			sin6->sin6_addr = ip6->ip6_src;
 			sin6->sin6_port = th->th_sport;
-			sin6->sin6_flowinfo = htonl(0x0fffffff) &
-				inp->inp_ipv6.ip6_flow;
+			sin6->sin6_flowinfo =
+			    ip6->ip6_flow & IPV6_FLOWINFO_MASK;
 			laddr6 = inp->inp_laddr6;
 			if (IN6_IS_ADDR_UNSPECIFIED(&inp->inp_laddr6))
 				inp->inp_laddr6 = ip6->ip6_dst;
diff --git a/sys/netinet/tcp_subr.c b/sys/netinet/tcp_subr.c
index 2706c5edb18..e5ecf5c0ee2 100644
--- a/sys/netinet/tcp_subr.c
+++ b/sys/netinet/tcp_subr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: tcp_subr.c,v 1.68 2003/07/09 22:03:16 itojun Exp $	*/
+/*	$OpenBSD: tcp_subr.c,v 1.69 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$NetBSD: tcp_subr.c,v 1.22 1996/02/13 23:44:00 christos Exp $	*/
 
 /*
@@ -274,7 +274,7 @@ tcp_template(tp)
 			ip6->ip6_src = inp->inp_laddr6;
 			ip6->ip6_dst = inp->inp_faddr6;
 			ip6->ip6_flow = htonl(0x60000000) |
-			    (inp->inp_ipv6.ip6_flow & htonl(0x0fffffff));
+			    (inp->inp_flowinfo & IPV6_FLOWLABEL_MASK);
 
 			ip6->ip6_nxt = IPPROTO_TCP;
 			ip6->ip6_plen = htons(sizeof(struct tcphdr)); /*XXX*/
diff --git a/sys/netinet6/frag6.c b/sys/netinet6/frag6.c
index 8febdc009c2..bc283e63e73 100644
--- a/sys/netinet6/frag6.c
+++ b/sys/netinet6/frag6.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: frag6.c,v 1.20 2003/05/14 14:24:44 itojun Exp $	*/
+/*	$OpenBSD: frag6.c,v 1.21 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$KAME: frag6.c,v 1.40 2002/05/27 21:40:31 itojun Exp $	*/
 
 /*
@@ -133,7 +133,7 @@ do {									\
 void
 frag6_init()
 {
-	ip6_id = arc4random();
+
 	ip6q.ip6q_next = ip6q.ip6q_prev = &ip6q;
 }
 
diff --git a/sys/netinet6/icmp6.c b/sys/netinet6/icmp6.c
index c15081e71ef..91295bfbf8a 100644
--- a/sys/netinet6/icmp6.c
+++ b/sys/netinet6/icmp6.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: icmp6.c,v 1.74 2003/08/07 09:11:24 itojun Exp $	*/
+/*	$OpenBSD: icmp6.c,v 1.75 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$KAME: icmp6.c,v 1.217 2001/06/20 15:03:29 jinmei Exp $	*/
 
 /*
@@ -1060,7 +1060,7 @@ icmp6_notify_error(m, off, icmp6len, code)
 		}
 #endif
 		icmp6src.sin6_flowinfo =
-			(eip6->ip6_flow & IPV6_FLOWLABEL_MASK);
+		    (eip6->ip6_flow & IPV6_FLOWLABEL_MASK);
 
 		if (finaldst == NULL)
 			finaldst = &eip6->ip6_dst;
diff --git a/sys/netinet6/in6_pcb.c b/sys/netinet6/in6_pcb.c
index ab7d7376f43..8ca104ca0a4 100644
--- a/sys/netinet6/in6_pcb.c
+++ b/sys/netinet6/in6_pcb.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: in6_pcb.c,v 1.36 2003/09/28 23:17:45 cloder Exp $	*/
+/*	$OpenBSD: in6_pcb.c,v 1.37 2003/10/01 21:41:05 itojun Exp $	*/
 
 /*
  * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
@@ -285,11 +285,6 @@ in6_pcbbind(inp, nam)
 				return EADDRINUSE;
 		}
 		inp->inp_laddr6 = sin6->sin6_addr;
-
-		if (!IN6_IS_ADDR_V4MAPPED(&sin6->sin6_addr)) {
-			inp->inp_ipv6.ip6_flow = htonl(0x60000000) |
-			    (sin6->sin6_flowinfo & htonl(0x0fffffff));
-		}
 	}
 
 	if (lport == 0) {
@@ -408,6 +403,10 @@ portloop:
 	inp->inp_lport = lport;
 	in_pcbrehash(inp);
 
+#if 0
+	inp->inp_flowinfo = 0;	/* XXX */
+#endif
+
 	return 0;
 }
 
@@ -522,11 +521,10 @@ in6_pcbconnect(inp, nam)
 	}
 	inp->inp_faddr6 = sin6->sin6_addr;
 	inp->inp_fport = sin6->sin6_port;
-	/*
-	 * xxx kazu flowlabel is necessary for connect?
-	 * but if this line is missing, the garbage value remains.
-	 */
-	inp->inp_ipv6.ip6_flow = sin6->sin6_flowinfo;
+	inp->inp_flowinfo &= ~IPV6_FLOWLABEL_MASK;
+	if (ip6_auto_flowlabel)
+		inp->inp_flowinfo |=
+		    (htonl(ip6_randomflowlabel()) & IPV6_FLOWLABEL_MASK);
 	in_pcbrehash(inp);
 	return (0);
 }
diff --git a/sys/netinet6/ip6_id.c b/sys/netinet6/ip6_id.c
new file mode 100644
index 00000000000..e509a6364a6
--- /dev/null
+++ b/sys/netinet6/ip6_id.c
@@ -0,0 +1,261 @@
+/*	$OpenBSD: ip6_id.c,v 1.1 2003/10/01 21:41:05 itojun Exp $	*/
+/*	$NetBSD: ip6_id.c,v 1.7 2003/09/13 21:32:59 itojun Exp $	*/
+/*	$KAME: ip6_id.c,v 1.8 2003/09/06 13:41:06 itojun Exp $	*/
+
+/*
+ * Copyright (C) 2003 WIDE Project.
+ * All rights reserved.
+ *
+ * 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.
+ * 3. Neither the name of the project nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``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 PROJECT OR CONTRIBUTORS 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.
+ */
+
+/*
+ * 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.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *      This product includes software developed by Niels Provos.
+ * 4. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * 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.
+ */
+
+/*
+ * seed = random (bits - 1) bit
+ * n = prime, g0 = generator to n,
+ * j = random so that gcd(j,n-1) == 1
+ * g = g0^j mod n will be a generator again.
+ *
+ * X[0] = random seed.
+ * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
+ * with a = 7^(even random) mod m,
+ *      b = random with gcd(b,m) == 1
+ *      m = constant and a maximal period of m-1.
+ *
+ * The transaction id is determined by:
+ * id[n] = seed xor (g^X[n] mod n)
+ *
+ * Effectivly the id is restricted to the lower (bits - 1) bits, thus
+ * yielding two different cycles by toggling the msb on and off.
+ * This avoids reuse issues caused by reseeding.
+ */
+
+#include <sys/types.h>
+#include <sys/param.h>
+#include <sys/kernel.h>
+#include <sys/socket.h>
+
+#include <net/if.h>
+#include <netinet/in.h>
+#include <netinet/ip6.h>
+#include <netinet6/ip6_var.h>
+
+#include <dev/rndvar.h>
+
+struct randomtab {
+	const int	ru_bits; /* resulting bits */
+	const long	ru_out;	/* Time after wich will be reseeded */
+	const u_int32_t ru_max;	/* Uniq cycle, avoid blackjack prediction */
+	const u_int32_t ru_gen;	/* Starting generator */
+	const u_int32_t ru_n;	/* ru_n: prime, ru_n - 1: product of pfacts[] */
+	const u_int32_t ru_agen; /* determine ru_a as ru_agen^(2*rand) */
+	const u_int32_t ru_m;	/* ru_m = 2^x*3^y */
+	const u_int32_t pfacts[4];	/* factors of ru_n */
+
+	u_int32_t ru_counter;
+	u_int32_t ru_msb;
+
+	u_int32_t ru_x;
+	u_int32_t ru_seed, ru_seed2;
+	u_int32_t ru_a, ru_b;
+	u_int32_t ru_g;
+	long ru_reseed;
+};
+
+static struct randomtab randomtab_32 = {
+	32,			/* resulting bits */
+	180,			/* Time after wich will be reseeded */
+	1000000000,		/* Uniq cycle, avoid blackjack prediction */
+	2,			/* Starting generator */
+	2147483629,		/* RU_N-1 = 2^2*3^2*59652323 */
+	7,			/* determine ru_a as RU_AGEN^(2*rand) */
+	1836660096,		/* RU_M = 2^7*3^15 - don't change */
+	{ 2, 3, 59652323, 0 },	/* factors of ru_n */
+};
+
+static struct randomtab randomtab_20 = {
+	20,			/* resulting bits */
+	180,			/* Time after wich will be reseeded */
+	200000,			/* Uniq cycle, avoid blackjack prediction */
+	2,			/* Starting generator */
+	524269,			/* RU_N-1 = 2^2*3^2*14563 */
+	7,			/* determine ru_a as RU_AGEN^(2*rand) */
+	279936,			/* RU_M = 2^7*3^7 - don't change */
+	{ 2, 3, 14563, 0 },	/* factors of ru_n */
+};
+
+static u_int32_t pmod(u_int32_t, u_int32_t, u_int32_t);
+static void initid(struct randomtab *);
+static u_int32_t randomid(struct randomtab *);
+
+/*
+ * Do a fast modular exponation, returned value will be in the range
+ * of 0 - (mod-1)
+ */
+
+static u_int32_t
+pmod(u_int32_t gen, u_int32_t expo, u_int32_t mod)
+{
+	u_int64_t s, t, u;
+
+	s = 1;
+	t = gen;
+	u = expo;
+
+	while (u) {
+		if (u & 1)
+			s = (s * t) % mod;
+		u >>= 1;
+		t = (t * t) % mod;
+	}
+	return (s);
+}
+
+/*
+ * Initalizes the seed and chooses a suitable generator. Also toggles
+ * the msb flag. The msb flag is used to generate two distinct
+ * cycles of random numbers and thus avoiding reuse of ids.
+ *
+ * This function is called from id_randomid() when needed, an
+ * application does not have to worry about it.
+ */
+static void
+initid(struct randomtab *p)
+{
+	u_int32_t j, i;
+	int noprime = 1;
+
+	p->ru_x = arc4random() % p->ru_m;
+
+	/* (bits - 1) bits of random seed */
+	p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));
+	p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
+
+	/* Determine the LCG we use */
+	p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;
+	p->ru_a = pmod(p->ru_agen,
+	    (arc4random() & (~0U >> (32 - p->ru_bits))) & (~1U), p->ru_m);
+	while (p->ru_b % 3 == 0)
+		p->ru_b += 2;
+
+	j = arc4random() % p->ru_n;
+
+	/*
+	 * Do a fast gcd(j, RU_N - 1), so we can find a j with
+	 * gcd(j, RU_N - 1) == 1, giving a new generator for
+	 * RU_GEN^j mod RU_N
+	 */
+	while (noprime) {
+		for (i = 0; p->pfacts[i] > 0; i++)
+			if (j % p->pfacts[i] == 0)
+				break;
+
+		if (p->pfacts[i] == 0)
+			noprime = 0;
+		else
+			j = (j + 1) % p->ru_n;
+	}
+
+	p->ru_g = pmod(p->ru_gen, j, p->ru_n);
+	p->ru_counter = 0;
+
+	p->ru_reseed = time.tv_sec + p->ru_out;
+	p->ru_msb = p->ru_msb ? 0 : (1U << (p->ru_bits - 1));
+}
+
+static u_int32_t
+randomid(struct randomtab *p)
+{
+	int i, n;
+	u_int32_t tmp;
+
+	if (p->ru_counter >= p->ru_max || time.tv_sec > p->ru_reseed)
+		initid(p);
+
+	tmp = arc4random();
+
+	/* Skip a random number of ids */
+	n = tmp & 0x3; tmp = tmp >> 2;
+	if (p->ru_counter + n >= p->ru_max)
+		initid(p);
+
+	for (i = 0; i <= n; i++) {
+		/* Linear Congruential Generator */
+		p->ru_x = (u_int32_t)((u_int64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m;
+	}
+
+	p->ru_counter += i;
+
+	return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 ^ p->ru_x, p->ru_n)) |
+	    p->ru_msb;
+}
+
+u_int32_t
+ip6_randomid(void)
+{
+
+	return randomid(&randomtab_32);
+}
+
+u_int32_t
+ip6_randomflowlabel(void)
+{
+
+	return randomid(&randomtab_20) & 0xfffff;
+}
diff --git a/sys/netinet6/ip6_output.c b/sys/netinet6/ip6_output.c
index 2b7ed382a1e..1d5b07ccc9d 100644
--- a/sys/netinet6/ip6_output.c
+++ b/sys/netinet6/ip6_output.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_output.c,v 1.77 2003/10/01 21:35:50 itojun Exp $	*/
+/*	$OpenBSD: ip6_output.c,v 1.78 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$KAME: ip6_output.c,v 1.172 2001/03/25 09:55:56 itojun Exp $	*/
 
 /*
@@ -817,7 +817,7 @@ ip6_output(m0, opt, ro, flags, im6o, ifpp)
 	} else {
 		struct mbuf **mnext, *m_frgpart;
 		struct ip6_frag *ip6f;
-		u_int32_t id = htonl(ip6_id++);
+		u_int32_t id = htonl(ip6_randomid());
 		u_char nextproto;
 
 		/*
diff --git a/sys/netinet6/ip6_var.h b/sys/netinet6/ip6_var.h
index 68b23f2a163..9d27f7ca43d 100644
--- a/sys/netinet6/ip6_var.h
+++ b/sys/netinet6/ip6_var.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ip6_var.h,v 1.23 2003/08/07 09:11:53 itojun Exp $	*/
+/*	$OpenBSD: ip6_var.h,v 1.24 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$KAME: ip6_var.h,v 1.33 2000/06/11 14:59:20 jinmei Exp $	*/
 
 /*
@@ -203,7 +203,6 @@ struct	ip6stat {
 #define	IPV6_MINMTU		0x04	/* use minimum MTU (IPV6_USE_MIN_MTU) */
 
 extern struct	ip6stat ip6stat;	/* statistics */
-extern u_int32_t ip6_id;		/* fragment identifier */
 extern int	ip6_defhlim;		/* default hop limit */
 extern int	ip6_defmcasthlim;	/* default multicast hop limit */
 extern int	ip6_forwarding;		/* act as router? */
@@ -282,6 +281,9 @@ int	none_input(struct mbuf **, int *, int);
 
 struct 	in6_addr *in6_selectsrc(struct sockaddr_in6 *, struct ip6_pktopts *,
 	struct ip6_moptions *, struct route_in6 *, struct in6_addr *, int *);
+
+u_int32_t ip6_randomid(void);
+u_int32_t ip6_randomflowlabel(void);
 #endif /* _KERNEL */
 
 #endif /* !_NETINET6_IP6_VAR_H_ */
diff --git a/sys/netinet6/raw_ip6.c b/sys/netinet6/raw_ip6.c
index 588c1ae8600..33c8f977f38 100644
--- a/sys/netinet6/raw_ip6.c
+++ b/sys/netinet6/raw_ip6.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: raw_ip6.c,v 1.20 2003/08/14 19:00:13 jason Exp $	*/
+/*	$OpenBSD: raw_ip6.c,v 1.21 2003/10/01 21:41:05 itojun Exp $	*/
 /*	$KAME: raw_ip6.c,v 1.69 2001/03/04 15:55:44 itojun Exp $	*/
 
 /*
@@ -173,9 +173,6 @@ rip6_input(mp, offp, proto)
 	bzero(&rip6src, sizeof(rip6src));
 	rip6src.sin6_len = sizeof(struct sockaddr_in6);
 	rip6src.sin6_family = AF_INET6;
-#if 0 /* XXX inbound flowlabel */
-	rip6src.sin6_flowinfo = ip6->ip6_flow & IPV6_FLOWINFO_MASK;
-#endif
 	/* KAME hack: recover scopeid */
 	(void)in6_recoverscope(&rip6src, &ip6->ip6_src, m->m_pkthdr.rcvif);