Home page logo
/

bugtraq logo Bugtraq mailing list archives

predictable ip->id patch
From: antirez () INVECE ORG (antirez)
Date: Tue, 26 Oct 1999 18:16:33 +0200


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'


--- 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);



  By Date           By Thread  

Current thread:
[ Nmap | Sec Tools | Mailing Lists | Site News | About/Contact | Advertising | Privacy ]
AlienVault