Much delayed but now present: RFC 1948 style sequence numbers

In order to ensure security and functionality, RFC 1948 style
initial sequence number generation has been implemented.  Barring
any major crypographic breakthroughs, this algorithm should be
unbreakable.  In addition, the problems with TIME_WAIT recycling
which affect our currently used algorithm are not present.

Reviewed by: jesper

8 files changed, 199 insertions, 178 deletions

diff --git a/sys/netinet/tcp_input.c b/sys/netinet/tcp_input.c
index 37b6492..a49c07d 100644
--- a/sys/netinet/tcp_input.c
+++ b/sys/netinet/tcp_input.c
@@ -101,7 +101,6 @@ struct tcphdr tcp_savetcp;
 MALLOC_DEFINE(M_TSEGQ, "tseg_qent", "TCP segment queue entry");
 
 static int	tcprexmtthresh = 3;
-tcp_seq	tcp_iss;
 tcp_cc	tcp_ccgen;
 
 struct	tcpstat tcpstat;
@@ -1135,7 +1134,7 @@ findpcb:
 		if (iss)
 			tp->iss = iss;
 		else {
-			tp->iss = tcp_new_isn();
+			tp->iss = tcp_new_isn(tp);
  		}
 		tp->irs = th->th_seq;
 		tcp_sendseqinit(tp);
@@ -1667,7 +1666,7 @@ trimthenstep6:
 			if (thflags & TH_SYN &&
 			    tp->t_state == TCPS_TIME_WAIT &&
 			    SEQ_GT(th->th_seq, tp->rcv_nxt)) {
-				iss = tcp_new_isn();
+				iss = tcp_new_isn(tp);
 				tp = tcp_close(tp);
 				goto findpcb;
 			}
diff --git a/sys/netinet/tcp_reass.c b/sys/netinet/tcp_reass.c
index 37b6492..a49c07d 100644
--- a/sys/netinet/tcp_reass.c
+++ b/sys/netinet/tcp_reass.c
@@ -101,7 +101,6 @@ struct tcphdr tcp_savetcp;
 MALLOC_DEFINE(M_TSEGQ, "tseg_qent", "TCP segment queue entry");
 
 static int	tcprexmtthresh = 3;
-tcp_seq	tcp_iss;
 tcp_cc	tcp_ccgen;
 
 struct	tcpstat tcpstat;
@@ -1135,7 +1134,7 @@ findpcb:
 		if (iss)
 			tp->iss = iss;
 		else {
-			tp->iss = tcp_new_isn();
+			tp->iss = tcp_new_isn(tp);
  		}
 		tp->irs = th->th_seq;
 		tcp_sendseqinit(tp);
@@ -1667,7 +1666,7 @@ trimthenstep6:
 			if (thflags & TH_SYN &&
 			    tp->t_state == TCPS_TIME_WAIT &&
 			    SEQ_GT(th->th_seq, tp->rcv_nxt)) {
-				iss = tcp_new_isn();
+				iss = tcp_new_isn(tp);
 				tp = tcp_close(tp);
 				goto findpcb;
 			}
diff --git a/sys/netinet/tcp_seq.h b/sys/netinet/tcp_seq.h
index 9307347..c1d36d3 100644
--- a/sys/netinet/tcp_seq.h
+++ b/sys/netinet/tcp_seq.h
@@ -80,26 +80,5 @@
 
 #ifdef _KERNEL
 extern tcp_cc	tcp_ccgen;		/* global connection count */
-
-/*
- * Increment for tcp_iss each second.
- * This is designed to increment at the standard 250 KB/s,
- * but with a random component averaging 128 KB.
- * We also increment tcp_iss by a quarter of this amount
- * each time we use the value for a new connection.
- * If defined, the tcp_random18() macro should produce a
- * number in the range [0-0x3ffff] that is hard to predict.
- * 
- * The variable tcp_iss and tcp_random18() are only used
- * by sequence number generation scheme 0.
- */
-#ifndef tcp_random18
-#define	tcp_random18()	(arc4random() & 0x3ffff)
-#endif
-#define	TCP_ISSINCR	(122*1024 + tcp_random18())
-
-extern tcp_seq	tcp_iss;
-#else
-#define	TCP_ISSINCR	(250*1024)	/* increment for tcp_iss each second */
 #endif /* _KERNEL */
 #endif /* _NETINET_TCP_SEQ_H_ */
diff --git a/sys/netinet/tcp_subr.c b/sys/netinet/tcp_subr.c
index 5872d79..8896f3f 100644
--- a/sys/netinet/tcp_subr.c
+++ b/sys/netinet/tcp_subr.c
@@ -98,6 +98,7 @@
 #endif /*IPSEC*/
 
 #include <machine/in_cksum.h>
+#include <sys/md5.h>
 
 int 	tcp_mssdflt = TCP_MSS;
 SYSCTL_INT(_net_inet_tcp, TCPCTL_MSSDFLT, mssdflt, CTLFLAG_RW, 
@@ -139,9 +140,13 @@ static int	icmp_may_rst = 1;
 SYSCTL_INT(_net_inet_tcp, OID_AUTO, icmp_may_rst, CTLFLAG_RW, &icmp_may_rst, 0, 
     "Certain ICMP unreachable messages may abort connections in SYN_SENT");
 
-static int	tcp_seq_genscheme = 1;
-SYSCTL_INT(_net_inet_tcp, OID_AUTO, tcp_seq_genscheme, CTLFLAG_RW,
-    &tcp_seq_genscheme, 0, "TCP ISN generation scheme");
+static int	tcp_strict_rfc1948 = 0;
+SYSCTL_INT(_net_inet_tcp, OID_AUTO, strict_rfc1948, CTLFLAG_RW,
+    &tcp_strict_rfc1948, 0, "Determines if RFC1948 is followed exactly");
+
+static int	tcp_isn_reseed_interval = 0;
+SYSCTL_INT(_net_inet_tcp, OID_AUTO, isn_reseed_interval, CTLFLAG_RW,
+    &tcp_isn_reseed_interval, 0, "Seconds between reseeding of ISN secret");
 
 static void	tcp_cleartaocache __P((void));
 static void	tcp_notify __P((struct inpcb *, int));
@@ -186,7 +191,6 @@ tcp_init()
 {
 	int hashsize = TCBHASHSIZE;
 	
-	tcp_iss = arc4random();	/* wrong, but better than a constant */
 	tcp_ccgen = 1;
 	tcp_cleartaocache();
 
@@ -1112,81 +1116,102 @@ tcp6_ctlinput(cmd, sa, d)
 }
 #endif /* INET6 */
 
-tcp_seq
-tcp_new_isn()
-{
-
-	if (tcp_seq_genscheme > 1 || tcp_seq_genscheme < 0)
-		tcp_seq_genscheme = 1;
-
-	switch (tcp_seq_genscheme) {
-	case 0:			/* Random positive increments */
-		tcp_iss += TCP_ISSINCR/2;
-		return tcp_iss;
-	case 1:			/* OpenBSD randomized scheme */
-		return tcp_rndiss_next();
-	default:
-		panic("cannot happen");
-	}
-}
-
-#define TCP_RNDISS_ROUNDS	16
-#define TCP_RNDISS_OUT	7200
-#define TCP_RNDISS_MAX	30000
-
-u_int8_t tcp_rndiss_sbox[128];
-u_int16_t tcp_rndiss_msb;
-u_int16_t tcp_rndiss_cnt;
-long tcp_rndiss_reseed;
-
-u_int16_t
-tcp_rndiss_encrypt(val)
-	u_int16_t val;
-{
-	u_int16_t sum = 0, i;
-  
-	for (i = 0; i < TCP_RNDISS_ROUNDS; i++) {
-		sum += 0x79b9;
-		val ^= ((u_int16_t)tcp_rndiss_sbox[(val^sum) & 0x7f]) << 7;
-		val = ((val & 0xff) << 7) | (val >> 8);
-	}
-
-	return val;
-}
 
-void
-tcp_rndiss_init()
-{
-	struct timeval time;
+/*
+ * Following is where TCP initial sequence number generation occurs.
+ *
+ * There are two places where we must use initial sequence numbers:
+ * 1.  In SYN-ACK packets.
+ * 2.  In SYN packets.
+ *
+ * The ISNs in SYN-ACK packets have no monotonicity requirement, 
+ * and should be as unpredictable as possible to avoid the possibility
+ * of spoofing and/or connection hijacking.  To satisfy this
+ * requirement, SYN-ACK ISNs are generated via the arc4random()
+ * function.  If exact RFC 1948 compliance is requested via sysctl,
+ * these ISNs will be generated just like those in SYN packets.
+ *
+ * The ISNs in SYN packets must be monotonic; TIME_WAIT recycling
+ * depends on this property.  In addition, these ISNs should be
+ * unguessable so as to prevent connection hijacking.  To satisfy
+ * the requirements of this situation, the algorithm outlined in
+ * RFC 1948 is used to generate sequence numbers.
+ *
+ * For more information on the theory of operation, please see
+ * RFC 1948.
+ *
+ * Implementation details:
+ *
+ * Time is based off the system timer, and is corrected so that it
+ * increases by one megabyte per second.  This allows for proper
+ * recycling on high speed LANs while still leaving over an hour
+ * before rollover.
+ *
+ * Two sysctls control the generation of ISNs:
+ *
+ * net.inet.tcp.isn_reseed_interval controls the number of seconds
+ * between seeding of isn_secret.  This is normally set to zero,
+ * as reseeding should not be necessary.
+ *
+ * net.inet.tcp.strict_rfc1948 controls whether RFC 1948 is followed
+ * strictly.  When strict compliance is requested, reseeding is
+ * disabled and SYN-ACKs will be generated in the same manner as
+ * SYNs.  Strict mode is disabled by default.
+ *
+ */
 
-	getmicrotime(&time);
-	read_random(tcp_rndiss_sbox, sizeof(tcp_rndiss_sbox));
+#define ISN_BYTES_PER_SECOND 1048576
 
-	tcp_rndiss_reseed = time.tv_sec + TCP_RNDISS_OUT;
-	tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000; 
-	tcp_rndiss_cnt = 0;
-}
+u_char isn_secret[32];
+int isn_last_reseed;
+MD5_CTX isn_ctx;
 
 tcp_seq
-tcp_rndiss_next()
+tcp_new_isn(tp)
+	struct tcpcb *tp;
 {
-	u_int16_t tmp;
-	struct timeval time;
-
-	getmicrotime(&time);
-
-        if (tcp_rndiss_cnt >= TCP_RNDISS_MAX ||
-	    time.tv_sec > tcp_rndiss_reseed)
-                tcp_rndiss_init();
-	
-	read_random(&tmp, sizeof(tmp));
-
-	/* (tmp & 0x7fff) ensures a 32768 byte gap between ISS */
-	return ((tcp_rndiss_encrypt(tcp_rndiss_cnt++) | tcp_rndiss_msb) <<16) |
-		(tmp & 0x7fff);
+	u_int32_t md5_buffer[4];
+	tcp_seq new_isn;
+
+	/* Use arc4random for SYN-ACKs when not in exact RFC1948 mode. */
+	if (((tp->t_state == TCPS_LISTEN) || (tp->t_state == TCPS_TIME_WAIT))
+	   && tcp_strict_rfc1948 == 0)
+		return arc4random();
+
+	/* Seed if this is the first use, reseed if requested. */
+	if ((isn_last_reseed == 0) ||
+	    ((tcp_strict_rfc1948 == 0) && (tcp_isn_reseed_interval > 0) &&
+	     (((u_int)isn_last_reseed + (u_int)tcp_isn_reseed_interval*hz)
+		< (u_int)ticks))) {
+		read_random(&isn_secret, sizeof(isn_secret));
+		isn_last_reseed = ticks;
+	}
+		
+	/* Compute the md5 hash and return the ISN. */
+	MD5Init(&isn_ctx);
+	MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_fport, sizeof(u_short));
+	MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_lport, sizeof(u_short));
+#ifdef INET6
+	if ((tp->t_inpcb->inp_vflag & INP_IPV6) != 0) {
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->in6p_faddr,
+			  sizeof(struct in6_addr));
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->in6p_laddr,
+			  sizeof(struct in6_addr));
+	} else
+#endif
+	{
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_faddr,
+			  sizeof(struct in_addr));
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_laddr,
+			  sizeof(struct in_addr));
+	}
+	MD5Update(&isn_ctx, (u_char *) &isn_secret, sizeof(isn_secret));
+	MD5Final((u_char *) &md5_buffer, &isn_ctx);
+	new_isn = (tcp_seq) md5_buffer[0];
+	new_isn += ticks * (ISN_BYTES_PER_SECOND / hz);
+	return new_isn;
 }
 
-
 /*
  * When a source quench is received, close congestion window
  * to one segment.  We will gradually open it again as we proceed.
diff --git a/sys/netinet/tcp_timer.c b/sys/netinet/tcp_timer.c
index 7891945..488c293 100644
--- a/sys/netinet/tcp_timer.c
+++ b/sys/netinet/tcp_timer.c
@@ -133,8 +133,6 @@ tcp_slowtimo()
 
 	tcp_maxidle = tcp_keepcnt * tcp_keepintvl;
 
-	tcp_iss += TCP_ISSINCR/PR_SLOWHZ;
-
 	splx(s);
 }
 
diff --git a/sys/netinet/tcp_timewait.c b/sys/netinet/tcp_timewait.c
index 5872d79..8896f3f 100644
--- a/sys/netinet/tcp_timewait.c
+++ b/sys/netinet/tcp_timewait.c
@@ -98,6 +98,7 @@
 #endif /*IPSEC*/
 
 #include <machine/in_cksum.h>
+#include <sys/md5.h>
 
 int 	tcp_mssdflt = TCP_MSS;
 SYSCTL_INT(_net_inet_tcp, TCPCTL_MSSDFLT, mssdflt, CTLFLAG_RW, 
@@ -139,9 +140,13 @@ static int	icmp_may_rst = 1;
 SYSCTL_INT(_net_inet_tcp, OID_AUTO, icmp_may_rst, CTLFLAG_RW, &icmp_may_rst, 0, 
     "Certain ICMP unreachable messages may abort connections in SYN_SENT");
 
-static int	tcp_seq_genscheme = 1;
-SYSCTL_INT(_net_inet_tcp, OID_AUTO, tcp_seq_genscheme, CTLFLAG_RW,
-    &tcp_seq_genscheme, 0, "TCP ISN generation scheme");
+static int	tcp_strict_rfc1948 = 0;
+SYSCTL_INT(_net_inet_tcp, OID_AUTO, strict_rfc1948, CTLFLAG_RW,
+    &tcp_strict_rfc1948, 0, "Determines if RFC1948 is followed exactly");
+
+static int	tcp_isn_reseed_interval = 0;
+SYSCTL_INT(_net_inet_tcp, OID_AUTO, isn_reseed_interval, CTLFLAG_RW,
+    &tcp_isn_reseed_interval, 0, "Seconds between reseeding of ISN secret");
 
 static void	tcp_cleartaocache __P((void));
 static void	tcp_notify __P((struct inpcb *, int));
@@ -186,7 +191,6 @@ tcp_init()
 {
 	int hashsize = TCBHASHSIZE;
 	
-	tcp_iss = arc4random();	/* wrong, but better than a constant */
 	tcp_ccgen = 1;
 	tcp_cleartaocache();
 
@@ -1112,81 +1116,102 @@ tcp6_ctlinput(cmd, sa, d)
 }
 #endif /* INET6 */
 
-tcp_seq
-tcp_new_isn()
-{
-
-	if (tcp_seq_genscheme > 1 || tcp_seq_genscheme < 0)
-		tcp_seq_genscheme = 1;
-
-	switch (tcp_seq_genscheme) {
-	case 0:			/* Random positive increments */
-		tcp_iss += TCP_ISSINCR/2;
-		return tcp_iss;
-	case 1:			/* OpenBSD randomized scheme */
-		return tcp_rndiss_next();
-	default:
-		panic("cannot happen");
-	}
-}
-
-#define TCP_RNDISS_ROUNDS	16
-#define TCP_RNDISS_OUT	7200
-#define TCP_RNDISS_MAX	30000
-
-u_int8_t tcp_rndiss_sbox[128];
-u_int16_t tcp_rndiss_msb;
-u_int16_t tcp_rndiss_cnt;
-long tcp_rndiss_reseed;
-
-u_int16_t
-tcp_rndiss_encrypt(val)
-	u_int16_t val;
-{
-	u_int16_t sum = 0, i;
-  
-	for (i = 0; i < TCP_RNDISS_ROUNDS; i++) {
-		sum += 0x79b9;
-		val ^= ((u_int16_t)tcp_rndiss_sbox[(val^sum) & 0x7f]) << 7;
-		val = ((val & 0xff) << 7) | (val >> 8);
-	}
-
-	return val;
-}
 
-void
-tcp_rndiss_init()
-{
-	struct timeval time;
+/*
+ * Following is where TCP initial sequence number generation occurs.
+ *
+ * There are two places where we must use initial sequence numbers:
+ * 1.  In SYN-ACK packets.
+ * 2.  In SYN packets.
+ *
+ * The ISNs in SYN-ACK packets have no monotonicity requirement, 
+ * and should be as unpredictable as possible to avoid the possibility
+ * of spoofing and/or connection hijacking.  To satisfy this
+ * requirement, SYN-ACK ISNs are generated via the arc4random()
+ * function.  If exact RFC 1948 compliance is requested via sysctl,
+ * these ISNs will be generated just like those in SYN packets.
+ *
+ * The ISNs in SYN packets must be monotonic; TIME_WAIT recycling
+ * depends on this property.  In addition, these ISNs should be
+ * unguessable so as to prevent connection hijacking.  To satisfy
+ * the requirements of this situation, the algorithm outlined in
+ * RFC 1948 is used to generate sequence numbers.
+ *
+ * For more information on the theory of operation, please see
+ * RFC 1948.
+ *
+ * Implementation details:
+ *
+ * Time is based off the system timer, and is corrected so that it
+ * increases by one megabyte per second.  This allows for proper
+ * recycling on high speed LANs while still leaving over an hour
+ * before rollover.
+ *
+ * Two sysctls control the generation of ISNs:
+ *
+ * net.inet.tcp.isn_reseed_interval controls the number of seconds
+ * between seeding of isn_secret.  This is normally set to zero,
+ * as reseeding should not be necessary.
+ *
+ * net.inet.tcp.strict_rfc1948 controls whether RFC 1948 is followed
+ * strictly.  When strict compliance is requested, reseeding is
+ * disabled and SYN-ACKs will be generated in the same manner as
+ * SYNs.  Strict mode is disabled by default.
+ *
+ */
 
-	getmicrotime(&time);
-	read_random(tcp_rndiss_sbox, sizeof(tcp_rndiss_sbox));
+#define ISN_BYTES_PER_SECOND 1048576
 
-	tcp_rndiss_reseed = time.tv_sec + TCP_RNDISS_OUT;
-	tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000; 
-	tcp_rndiss_cnt = 0;
-}
+u_char isn_secret[32];
+int isn_last_reseed;
+MD5_CTX isn_ctx;
 
 tcp_seq
-tcp_rndiss_next()
+tcp_new_isn(tp)
+	struct tcpcb *tp;
 {
-	u_int16_t tmp;
-	struct timeval time;
-
-	getmicrotime(&time);
-
-        if (tcp_rndiss_cnt >= TCP_RNDISS_MAX ||
-	    time.tv_sec > tcp_rndiss_reseed)
-                tcp_rndiss_init();
-	
-	read_random(&tmp, sizeof(tmp));
-
-	/* (tmp & 0x7fff) ensures a 32768 byte gap between ISS */
-	return ((tcp_rndiss_encrypt(tcp_rndiss_cnt++) | tcp_rndiss_msb) <<16) |
-		(tmp & 0x7fff);
+	u_int32_t md5_buffer[4];
+	tcp_seq new_isn;
+
+	/* Use arc4random for SYN-ACKs when not in exact RFC1948 mode. */
+	if (((tp->t_state == TCPS_LISTEN) || (tp->t_state == TCPS_TIME_WAIT))
+	   && tcp_strict_rfc1948 == 0)
+		return arc4random();
+
+	/* Seed if this is the first use, reseed if requested. */
+	if ((isn_last_reseed == 0) ||
+	    ((tcp_strict_rfc1948 == 0) && (tcp_isn_reseed_interval > 0) &&
+	     (((u_int)isn_last_reseed + (u_int)tcp_isn_reseed_interval*hz)
+		< (u_int)ticks))) {
+		read_random(&isn_secret, sizeof(isn_secret));
+		isn_last_reseed = ticks;
+	}
+		
+	/* Compute the md5 hash and return the ISN. */
+	MD5Init(&isn_ctx);
+	MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_fport, sizeof(u_short));
+	MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_lport, sizeof(u_short));
+#ifdef INET6
+	if ((tp->t_inpcb->inp_vflag & INP_IPV6) != 0) {
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->in6p_faddr,
+			  sizeof(struct in6_addr));
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->in6p_laddr,
+			  sizeof(struct in6_addr));
+	} else
+#endif
+	{
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_faddr,
+			  sizeof(struct in_addr));
+		MD5Update(&isn_ctx, (u_char *) &tp->t_inpcb->inp_laddr,
+			  sizeof(struct in_addr));
+	}
+	MD5Update(&isn_ctx, (u_char *) &isn_secret, sizeof(isn_secret));
+	MD5Final((u_char *) &md5_buffer, &isn_ctx);
+	new_isn = (tcp_seq) md5_buffer[0];
+	new_isn += ticks * (ISN_BYTES_PER_SECOND / hz);
+	return new_isn;
 }
 
-
 /*
  * When a source quench is received, close congestion window
  * to one segment.  We will gradually open it again as we proceed.
diff --git a/sys/netinet/tcp_usrreq.c b/sys/netinet/tcp_usrreq.c
index c28875e..6f761a0 100644
--- a/sys/netinet/tcp_usrreq.c
+++ b/sys/netinet/tcp_usrreq.c
@@ -758,7 +758,7 @@ tcp_connect(tp, nam, p)
 	tcpstat.tcps_connattempt++;
 	tp->t_state = TCPS_SYN_SENT;
 	callout_reset(tp->tt_keep, tcp_keepinit, tcp_timer_keep, tp);
-	tp->iss = tcp_new_isn();
+	tp->iss = tcp_new_isn(tp);
 	tcp_sendseqinit(tp);
 
 	/*
@@ -844,7 +844,7 @@ tcp6_connect(tp, nam, p)
 	tcpstat.tcps_connattempt++;
 	tp->t_state = TCPS_SYN_SENT;
 	callout_reset(tp->tt_keep, tcp_keepinit, tcp_timer_keep, tp);
-	tp->iss = tcp_new_isn();
+	tp->iss = tcp_new_isn(tp);
 	tcp_sendseqinit(tp);
 
 	/*
diff --git a/sys/netinet/tcp_var.h b/sys/netinet/tcp_var.h
index 299968e..40bc7e9 100644
--- a/sys/netinet/tcp_var.h
+++ b/sys/netinet/tcp_var.h
@@ -410,11 +410,7 @@ void	 tcp_trace __P((int, int, struct tcpcb *, void *, struct tcphdr *,
 extern	struct pr_usrreqs tcp_usrreqs;
 extern	u_long tcp_sendspace;
 extern	u_long tcp_recvspace;
-void	tcp_rndiss_init __P((void));
-tcp_seq	tcp_rndiss_next __P((void));
-u_int16_t
-	tcp_rndiss_encrypt __P((u_int16_t));
-tcp_seq tcp_new_isn __P((void));
+tcp_seq tcp_new_isn __P((struct tcpcb *));
 
 #endif /* _KERNEL */