[12341] in bugtraq
predictable ip->id patch
daemon@ATHENA.MIT.EDU (antirez)
Tue Oct 26 14:55:54 1999
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary=LQksG6bCIzRHxTLp
Message-Id: <19991026181630.A9347@invece.org>
Date: Tue, 26 Oct 1999 18:16:33 +0200
Reply-To: antirez@invece.org
From: antirez <antirez@INVECE.ORG>
X-To: bugtraq@SECURITYFOCUS.COM
To: BUGTRAQ@SECURITYFOCUS.COM
--LQksG6bCIzRHxTLp
Content-Type: text/plain; charset=us-ascii
Hi,
I guess from linux-kernel ml that linux developers are looking
for a solution about predictable ip ID.
While you can use this patch. It is just the OpenBSD ip_id.c
ported to Linux. The patch also implements the RFC 793 ABORT Call
when SO_LINGER enabled with linger == 1 and lingertime == 0 (but
only if /proc/sys/net/ipv4/rfc1337 is "0").
Porting is based on OpenBSD's ip_id 1.2 since David Wagner proposed
an attack against 1.1 ver (seems that also linux-kernel's guys are able
to predict next IDs with 7 known IDs).
I Hope this patch is sane (it seems to work properly), if you find
some problem please send me an email.
The patch is for linux 2.2.13.
regards,
antirez
--
Salvatore Sanfilippo antirez@invece.org antirez@alicomitalia.it
ALICOM snc Tel: +39-0871-403522 Fax: +39-0871-41960 Web: www.alicom.com
pgp key: finger antirez@tella.alicom.com [2852F54A49653429 1D1BF6DA24C712BF]
'un ciclo macellati, un ciclo macellai'
--LQksG6bCIzRHxTLp
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="ip.patch"
--- 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 @@
int sysctl_ip_dynaddr = 0;
-
-int ip_id_count = 0;
-
/* Generate a checksum for an outgoing IP datagram. */
__inline__ void ip_send_check(struct iphdr *iph)
{
@@ -120,7 +117,7 @@
iph->saddr = rt->rt_src;
iph->protocol = sk->protocol;
iph->tot_len = htons(skb->len);
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
skb->nh.iph = iph;
if (opt && opt->optlen) {
@@ -289,7 +286,7 @@
tot_len = skb->len;
iph->tot_len = htons(tot_len);
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
dev = rt->u.dst.dev;
@@ -481,7 +478,7 @@
* Get an identifier
*/
- id = htons(ip_id_count++);
+ id = htons(ip_randomid());
/*
* Begin outputting the bytes.
@@ -669,7 +666,7 @@
iph->ihl=5;
iph->tos=sk->ip_tos;
iph->tot_len = htons(length);
- iph->id=htons(ip_id_count++);
+ iph->id=htons(ip_randomid());
iph->frag_off = df;
iph->ttl=sk->ip_mc_ttl;
if (rt->rt_type != RTN_MULTICAST)
--- linux/net/ipv4/ipip.c Thu Mar 25 18:23:34 1999
+++ linux-2.2.13-H/net/ipv4/ipip.c Tue Oct 26 16:28:12 1999
@@ -597,7 +597,7 @@
iph->ttl = old_iph->ttl;
iph->tot_len = htons(skb->len);
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
ip_send_check(iph);
stats->tx_bytes += skb->len;
--- linux/net/ipv4/ipmr.c Mon Aug 9 21:04:41 1999
+++ linux-2.2.13-H/net/ipv4/ipmr.c Tue Oct 26 16:28:20 1999
@@ -1012,7 +1012,7 @@
iph->protocol = IPPROTO_IPIP;
iph->ihl = 5;
iph->tot_len = htons(skb->len);
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
ip_send_check(iph);
skb->h.ipiph = skb->nh.iph;
--- linux/net/ipv4/raw.c Mon Aug 9 21:04:41 1999
+++ linux-2.2.13-H/net/ipv4/raw.c Tue Oct 26 16:28:34 1999
@@ -236,7 +236,7 @@
* ip_build_xmit clean (well less messy).
*/
if (!iph->id)
- iph->id = htons(ip_id_count++);
+ iph->id = htons(ip_randomid());
iph->check=ip_fast_csum((unsigned char *)iph, iph->ihl);
}
return 0;
--- linux/net/ipv4/Makefile Tue Jan 5 00:31:35 1999
+++ linux-2.2.13-H/net/ipv4/Makefile Tue Oct 26 15:43:56 1999
@@ -9,7 +9,7 @@
O_TARGET := ipv4.o
IPV4_OBJS := utils.o route.o proc.o timer.o protocol.o \
- ip_input.o ip_fragment.o ip_forward.o ip_options.o \
+ ip_id.o ip_input.o ip_fragment.o ip_forward.o ip_options.o \
ip_output.o ip_sockglue.o \
tcp.o tcp_input.o tcp_output.o tcp_timer.o tcp_ipv4.o\
raw.o udp.o arp.o icmp.o devinet.o af_inet.o igmp.o \
--- linux/net/netsyms.c Fri Oct 22 01:56:47 1999
+++ linux-2.2.13-H/net/netsyms.c Tue Oct 26 16:47:19 1999
@@ -231,7 +231,6 @@
EXPORT_SYMBOL(ip_options_compile);
EXPORT_SYMBOL(arp_send);
EXPORT_SYMBOL(arp_broken_ops);
-EXPORT_SYMBOL(ip_id_count);
EXPORT_SYMBOL(ip_send_check);
EXPORT_SYMBOL(ip_fragment);
EXPORT_SYMBOL(inet_family_ops);
--LQksG6bCIzRHxTLp--
