--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 antirezat_private antirezat_private ALICOM snc Tel: +39-0871-403522 Fax: +39-0871-41960 Web: www.alicom.com pgp key: finger antirezat_private [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 <antirezat_private> + * + * TODO: + * - Make this code SMP safe + */ + +/* + * Copyright 1998 Niels Provos <provosat_private> + * All rights reserved. + * + * Theo de Raadt <deraadtat_private> 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--
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 15:08:46 PDT