An unofficial patch for the Linux predictable IP-ID problem
31 Oct. 1999
Summary
An unofficial patch for the Linux operating system vulnerability has been released. The patch is a port from the OpenBSD operating system, and it fixes the usage of predictable IP Ids. The patch also implements the RFC 793 ABORT Call.
The patch is for Linux 2.2.13 kernels.
The following patch can be used against this vulnerability:
--- linux/net/ipv4/tcp.c Mon Aug 9 21:05:45 1999
+++ linux-2.2.13-H/net/ipv4/tcp.c Tue Oct 26 17:24:52 1999
@@ -202,6 +202,8 @@
* Eric Schenk : Fix fast close down bug with
* shutdown() followed by close().
* Andi Kleen : Make poll agree with SIGIO
+ * Salvatore Sanfilippo : Support SO_LINGER with linger == 1 and
+ * lingertime == 0 (RFC 793 ABORT Call)
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
@@ -423,6 +425,7 @@
#include <asm/uaccess.h>
int sysctl_tcp_fin_timeout = TCP_FIN_TIMEOUT;
+extern int sysctl_tcp_rfc1337;
struct tcp_mib tcp_statistics;
@@ -1522,6 +1525,37 @@
release_sock(sk);
sk->dead = 1;
return;
+ }
+
+ /* SO_LINGER with linger == 1 and lingertime == 0
+ * We must discard recv and send buffers and send
+ * a RST [ ABORT Call in RFC 793 ].
+ * TCP_LISTEN state is handled above.
+ * TCP_SYN_RECV is mentioned by RFC 793 but
+ * it is impossible to call close() in this state.
+ * After RST was sent we go in TCP_CLOSE state.
+ * This isn't totally safe (see RFC 1337) but if we
+ * want ABORT the assumption is that we know what
+ * we are doing.
+ */
+ if (sk->linger && sk->lingertime == 0 && sysctl_tcp_rfc1337)
+ {
+ switch (sk->state)
+ {
+ /* case TCP_SYN_RECV: */
+ case TCP_ESTABLISHED:
+ case TCP_FIN_WAIT1:
+ case TCP_FIN_WAIT2:
+ case TCP_CLOSE_WAIT:
+ tcp_set_state(sk, TCP_CLOSE);
+ tcp_send_active_reset(sk);
+ sk->dead = 1;
+ release_sock(sk);
+ return;
+ /* unreached */
+ default:
+ /* other states follow normal close */
+ }
}
/* It is questionable, what the role of this is now.
--- linux/include/net/ip.h Mon Oct 25 14:57:35 1999
+++ linux-2.2.13-H/include/net/ip.h Tue Oct 26 16:29:31 1999
@@ -96,7 +96,6 @@
extern void ip_fragment(struct sk_buff *skb, int (*out)(struct sk_buff*));
extern int ip_do_nat(struct sk_buff *skb);
extern void ip_send_check(struct iphdr *ip);
-extern int ip_id_count;
extern void ip_queue_xmit(struct sk_buff *skb);
extern void ip_init(void);
extern int ip_build_xmit(struct sock *sk,
@@ -263,5 +262,11 @@
u16 port, u32 info, u8 *payload);
extern void ip_local_error(struct sock *sk, int err, u32 daddr, u16 dport,
u32 info);
+
+/*
+ * Functions provided by ip_id.c
+ */
+
+extern __u16 ip_randomid(void);
#endif /* _IP_H */
--- linux/net/ipv4/igmp.c Mon Aug 9 21:05:10 1999
+++ linux-2.2.13-H/net/ipv4/igmp.c Tue Oct 26 16:26:05 1999
@@ -192,7 +192,7 @@
iph->saddr = rt->rt_src;
iph->protocol = IPPROTO_IGMP;
iph->tot_len = htons(IGMP_SIZE);
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
((u8*)&iph[1])[0] = IPOPT_RA;
((u8*)&iph[1])[1] = 4;
((u8*)&iph[1])[2] = 0;
--- linux/net/ipv4/ip_id.c Tue Oct 26 16:22:50 1999
+++ linux-2.2.13-H/net/ipv4/ip_id.c Tue Oct 26 16:03:14 1999
@@ -0,0 +1,220 @@
+/*
+ * This code is based on OpenBSD's ip_id.c, by Niels Provos.
+ * Ported to Linux by Salvatore Sanfilippo.
+ *
+ * 26-10-1999: Ported from OpenBSD's ip_id.c version 1.2
+ * (previous versions seems to be predictable
+ * after David Wagner's auditing)
+ * Salvatore Sanfilippo <antirez@invece.org>
+ *
+ * TODO:
+ * - Make this code SMP safe
+ */
+
+/*
+ * 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 15bit
+ * 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 = 31104 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 15 bits, thus
+ * yielding two different cycles by toggling the msb on and off.
+ * This avoids reuse issues caused by reseeding.
+ */
+
+#ifndef __SMP__
+
+#include <linux/types.h>
+#include <linux/sched.h>
+
+#include <linux/random.h>
+
+#define RU_OUT 180 /* Time after wich will be reseeded */
+#define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */
+#define RU_GEN 2 /* Starting generator */
+#define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */
+#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */
+#define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */
+
+#define PFAC_N 3
+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 __u32 ru_reseed;
+static __u32 tmp; /* Storage for unused random */
+
+static __u16 pmod (u_int16_t, u_int16_t, u_int16_t);
+static void ip_initid (void);
+__u16 ip_randomid (void);
+
+/*
+ * Do a fast modular exponation, returned value will be in the range
+ * of 0 - (mod-1)
+ */
+
+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);
+}
+
+/*
+ * 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
+ip_initid(void)
+{
+ __u16 j, i;
+ int noprime = 1;
+
+ get_random_bytes((void *) &tmp, sizeof(tmp));
+ ru_x = (tmp & 0xFFFF) % RU_M;
+
+ /* 15 bits of random seed */
+ ru_seed = (tmp >> 16) & 0x7FFF;
+ get_random_bytes((void *) &tmp, sizeof(tmp));
+ ru_seed2 = tmp & 0x7FFF;
+
+ get_random_bytes((void *) &tmp, sizeof(tmp));
+
+ /* Determine the LCG we use */
+ ru_b = (tmp & 0xfffe) | 1;
+ ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
+ while (ru_b % 3 == 0)
+ ru_b += 2;
+
+ get_random_bytes((void *) &tmp, sizeof(tmp));
+ j = tmp % RU_N;
+ tmp = tmp >> 16;
+
+ /*
+ * 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; 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 = jiffies + (RU_OUT * HZ);
+ ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
+}
+
+__u16
+ip_randomid(void)
+{
+ int i, n;
+
+ if (ru_counter >= RU_MAX || jiffies > ru_reseed)
+ ip_initid();
+
+ if (!tmp)
+ get_random_bytes((void *) &tmp, sizeof(tmp));
+
+ /* Skip a random number of ids */
+ n = tmp & 0x3; tmp = tmp >> 2;
+ if (ru_counter + n >= RU_MAX)
+ ip_initid();
+
+ for (i = 0; i <= n; i++)
+ /* Linear Congruential Generator */
+ 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;
+}
+
+#else /* __SMP__ */
+
+#include <linux/types.h>
+
+static __u16 ipid = 0;
+
+__u16 ip_randomid(void)
+{
+ return ipid++;
+}
+
+#endif /* !__SMP__ */
--- linux/net/ipv4/ip_output.c Fri Oct 22 01:56:47 1999
+++ linux-2.2.13-H/net/ipv4/ip_output.c Tue Oct 26 16:30:38 1999
@@ -83,9 +83,6 @@
