Date: Fri, 8 Jun 2001 00:56:16 -0500 (CDT) From: Mike Silbersack <silby@silby.com> To: <freebsd-net@freebsd.org>, <freebsd-arch@freebsd.org> Subject: New TCP sequence number generation algorithm; review needed Message-ID: <20010608005234.W92206-200000@achilles.silby.com>
next in thread | raw e-mail | index | archive | help
[-- Attachment #1 --]
The included patch implements what I believe to be a superior tcp sequence
number generation algorithm. I'd appreciate comments on all aspects of
the patch. If no objections are raised, I'd like to commit the patch to
-current in a week or so, with -stable following two weeks after.
I'm providing a quick FAQ to get people up to speed on what the patch does
and its alternatives. But, as always, you'll obtain the best
understanding of the code by reading it directly. Please do so before
commenting.
Q: How does this new patch generate sequence numbers?
A: In short, the patch provides a seperate sequence number space for each
host. These sequence spaces have no relation to the sequence spaces of
other hosts, and are re-randomized whenever a host becomes idle.
Q: How is this done?
A: We are able to store a 16-bit variable which corresponds to the upper
16 bits of a host's sequence number in the cloned route entry for that
host, thanks to extra space which exists in the routing metric structure.
When we need a new sequence number for a host, we load in that value. If
it is zero, as it is when the route is first cloned, we initialize it to a
random value. Then, on this connection and every one after, we shift it
left by 16 bits and increment it by a random value of up to 2^20.
Subsequently, we store the upper 16 bits of the resulting value back in
the cloned route entry, waiting for the next sequence number. Checks are
present to make sure that the sequence number always increments by more
than 2^16-1 and that the sequence number does not go to zero and cause a
re-randomization. If a host is idle for a long period of time, the cloned
route entry will be flushed and we will start the process over.
Q: Doesn't looking up this extra data during every connection attempt
take more time?
A: No. The routing metric structure is accessed whenever a connection is
established already. We are adding no additional searches, and the
generation function is less time consuming than the one currently used.
Q: How does all of this affect connections in the TIME_WAIT state?
A: These changes positively affect the operation of sockets in the
TIME_WAIT state. We are always monotonically incrementing the ISN within
the context of a given host, which is what is required for proper
operation. The re-randomization caused by a cloned route being flushed
out and recreated is inconsequential; in the time it takes an entry to
timeout and be flushed, any TIME_WAIT sockets would have expired.
Q: How does all of this affect someone trying to spoof a connection?
A: These changes make it very difficult to spoof connections. Since the
ISN returned to the attacker has no relation to the ISN of the host he's
trying to impersonate, he has no idea where to start. Even if he knew the
starting point of the high 16-bits, he would be unable to guess the
current state of the high 16-bits after a few random incrementations of
the value. With this system in place, spoofing a connection should become
a purely brute-force operation, requiring billions of attempts.
Q: You're using arc4random() to get all random values. Is it random
enough for this purpose?
A: Mark Murray says that it is. So, yes.
Q: What sequence number generation scheme is FreeBSD currently using?
A: FreeBSD 4.3+ uses a tcp sequence number generation algorithm borrowed
from OpenBSD. Roughly, this scheme uses a nonrepeating random number
generator to provide the upper 16 bits for each ISN, while the lower 15
bits of data is drawn directly from the entropy pool. (The 16th bit is
always 0.) Unless the nonrepeating random number generator is broken,
spoofing this algorithm would be nearly as tough as spoofing against the
new algorithm in this patch.
The problem with the OpenBSD algorithm is that because the upper 16 bits
of the sequence number are effectively random, monotonicity is broken.
Hence, sockets in the TIME_WAIT state will act funky.
Q: Ok, what's this RFC1948 sequence number generation scheme I keep
hearing about?
A: RFC1948 suggests segementing each hostA/portA/hostB/portB pair into a
seperate sequence number space using a hash function of the form:
ISN = timecounter + MD5(localhost, localport, remotehost, remoteport, shared secret)
While clever, this algorithm has a major weakness. The shared secret is
used in generating the ISN for all connections to the host in question.
To ensure monotonicity for each connection, this implies that the shared
secret must remain constant for the entire uptime of a machine. As a
result, attackers may make a few connection attempts, store the IPs/ports
used and the sequence number returned. This information can then be fed
into a cracking program which will determine the shared secret. Once the
shared secret is found, the attacker can perfectly spoof a connection to
the machine from any host until the machine is rebooted and the shared
secret changed.
While not currently a threat, such an attack will most likely become
possible if RFC1948 becomes widely used and attackers are sufficiently
motivated. If you do not believe that this is possible, please read up on
the history of RSA's DES challenges.
Q: Do you really hate the RFC1948 algorithm that much?
A: Yes. It's less secure than just random positive increments, IMHO.
Q: Do you really think anyone read this far into the FAQ?
A: I hope so.
Q: Do you have anything more to add before I go off and read your code?
A: Nope. Enjoy!
Mike "Silby" Silbersack
[-- Attachment #2 --]
diff -u -r netinet.old/tcp_input.c netinet/tcp_input.c
--- netinet.old/tcp_input.c Thu Jun 7 16:02:01 2001
+++ netinet/tcp_input.c Thu Jun 7 16:02:13 2001
@@ -1092,7 +1092,7 @@
if (iss)
tp->iss = iss;
else {
- tp->iss = tcp_rndiss_next();
+ tp->iss = tcp_next_isn(taop);
}
tp->irs = th->th_seq;
tcp_sendseqinit(tp);
@@ -1624,7 +1624,7 @@
if (thflags & TH_SYN &&
tp->t_state == TCPS_TIME_WAIT &&
SEQ_GT(th->th_seq, tp->rcv_nxt)) {
- iss = tcp_rndiss_next();
+ iss = tcp_next_isn(taop);
tp = tcp_close(tp);
goto findpcb;
}
Only in netinet/: tcp_input.c.orig
diff -u -r netinet.old/tcp_subr.c netinet/tcp_subr.c
--- netinet.old/tcp_subr.c Thu Jun 7 16:02:01 2001
+++ netinet/tcp_subr.c Thu Jun 7 17:39:53 2001
@@ -1096,63 +1096,6 @@
}
#endif /* INET6 */
-#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;
-
- getmicrotime(&time);
- read_random(tcp_rndiss_sbox, sizeof(tcp_rndiss_sbox));
-
- tcp_rndiss_reseed = time.tv_sec + TCP_RNDISS_OUT;
- tcp_rndiss_msb = tcp_rndiss_msb == 0x8000 ? 0 : 0x8000;
- tcp_rndiss_cnt = 0;
-}
-
-tcp_seq
-tcp_rndiss_next()
-{
- 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);
-}
-
-
/*
* When a source quench is received, close congestion window
* to one segment. We will gradually open it again as we proceed.
@@ -1421,4 +1364,42 @@
static void
tcp_cleartaocache()
{
+}
+
+tcp_seq tcp_next_isn(taop)
+ struct rmxp_tao *taop;
+{
+ tcp_seq isn;
+
+ /*
+ * If tao_isn equals zero, as it does when a route is created,
+ * we must initialize it to a random value.
+ */
+ if (taop->tao_isn == 0) {
+ taop->tao_isn = (u_short) arc4random();
+ }
+
+ /*
+ * Increment by up to 2^20. Although we have no time dependence,
+ * this should be a large enough jump to insure that there are
+ * no TIME_WAIT problems.
+ */
+ isn = (taop->tao_isn << 16) + (arc4random() & 0xfffff);
+
+ /*
+ * Since we only store the upper 16 bits, we must always
+ * add one to ensure that a random positive increment
+ * less than 2^16 does not cause a sequence number
+ * regression.
+ */
+ taop->tao_isn = (isn >> 16) + 1;
+
+ /*
+ * We must check to make sure that tao_isn does not equal zero;
+ * if it does, a false reinitialization of its value would occur.
+ */
+ if (taop->tao_isn == 0)
+ taop->tao_isn = 1;
+
+ return isn;
}
Only in netinet/: tcp_subr.c.orig
diff -u -r netinet.old/tcp_usrreq.c netinet/tcp_usrreq.c
--- netinet.old/tcp_usrreq.c Thu Jun 7 16:02:01 2001
+++ netinet/tcp_usrreq.c Thu Jun 7 16:02:13 2001
@@ -761,8 +761,6 @@
tcpstat.tcps_connattempt++;
tp->t_state = TCPS_SYN_SENT;
callout_reset(tp->tt_keep, tcp_keepinit, tcp_timer_keep, tp);
- tp->iss = tcp_rndiss_next();
- tcp_sendseqinit(tp);
/*
* Generate a CC value for this connection and
@@ -782,6 +780,9 @@
tp->t_flags |= TF_SENDCCNEW;
}
+ tp->iss = tcp_next_isn(taop);
+ tcp_sendseqinit(tp);
+
return 0;
}
@@ -853,8 +854,6 @@
tcpstat.tcps_connattempt++;
tp->t_state = TCPS_SYN_SENT;
callout_reset(tp->tt_keep, tcp_keepinit, tcp_timer_keep, tp);
- tp->iss = tcp_rndiss_next();
- tcp_sendseqinit(tp);
/*
* Generate a CC value for this connection and
@@ -873,6 +872,9 @@
taop->tao_ccsent = 0;
tp->t_flags |= TF_SENDCCNEW;
}
+
+ tp->iss = tcp_next_isn(taop);
+ tcp_sendseqinit(tp);
return 0;
}
Only in netinet/: tcp_usrreq.c.orig
diff -u -r netinet.old/tcp_var.h netinet/tcp_var.h
--- netinet.old/tcp_var.h Thu Jun 7 16:02:01 2001
+++ netinet/tcp_var.h Thu Jun 7 17:40:15 2001
@@ -189,6 +189,7 @@
tcp_cc tao_cc; /* latest CC in valid SYN */
tcp_cc tao_ccsent; /* latest CC sent to peer */
u_short tao_mssopt; /* peer's cached MSS */
+ u_short tao_isn; /* initial segment number to send to peer */
#ifdef notyet
u_short tao_flags; /* cache status flags */
#define TAOF_DONT 0x0001 /* peer doesn't understand rfc1644 */
@@ -409,10 +410,7 @@
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_next_isn __P((struct rmxp_tao *));
#endif /* _KERNEL */
Only in netinet/: tcp_var.h.orig
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010608005234.W92206-200000>