From owner-freebsd-net Fri May 25 23:38:29 2001 Delivered-To: freebsd-net@freebsd.org Received: from obsecurity.dyndns.org (adsl-63-207-60-119.dsl.lsan03.pacbell.net [63.207.60.119]) by hub.freebsd.org (Postfix) with ESMTP id D48E437B422 for ; Fri, 25 May 2001 23:38:13 -0700 (PDT) (envelope-from kris@obsecurity.org) Received: by obsecurity.dyndns.org (Postfix, from userid 1000) id AFEDE66B21; Fri, 25 May 2001 23:38:12 -0700 (PDT) Date: Fri, 25 May 2001 23:38:12 -0700 From: Kris Kennaway To: net@FreeBSD.org Subject: Randomized IP ID patch Message-ID: <20010525233811.A44455@xor.obsecurity.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="n8g4imXOkfNTN/H1" Content-Disposition: inline User-Agent: Mutt/1.2.5i Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org --n8g4imXOkfNTN/H1 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable A while back I posted a version of this which was activated by sysctl, but people didn't like the per-packet performance overhead, so here's an updated version which uses a compile-time option. Please review; I'd like to commit this soon. Kris Index: conf/files =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/conf/files,v retrieving revision 1.517 diff -u -r1.517 files --- conf/files 2001/05/16 07:31:56 1.517 +++ conf/files 2001/05/26 05:09:59 @@ -1010,6 +1010,7 @@ netinet/in.c optional inet netinet/in_gif.c optional gif inet #netinet/in_hostcache.c optional inet +netinet/ip_id.c optional inet netinet/in_pcb.c optional inet netinet/in_proto.c optional inet netinet/in_rmx.c optional inet Index: conf/options =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/conf/options,v retrieving revision 1.271 diff -u -r1.271 options --- conf/options 2001/05/13 20:52:36 1.271 +++ conf/options 2001/05/26 05:10:39 @@ -283,6 +283,7 @@ PPP_BSDCOMP opt_ppp.h PPP_DEFLATE opt_ppp.h PPP_FILTER opt_ppp.h +RANDOM_IP_ID SLIP_IFF_OPTS opt_slip.h TCPDEBUG TCP_DROP_SYNFIN opt_tcp_input.h Index: netinet/ip_input.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet/ip_input.c,v retrieving revision 1.165 diff -u -r1.165 ip_input.c --- netinet/ip_input.c 2001/03/19 09:16:16 1.165 +++ netinet/ip_input.c 2001/05/26 06:15:51 @@ -44,6 +44,7 @@ #include "opt_ipstealth.h" #include "opt_ipsec.h" #include "opt_pfil_hooks.h" +#include "opt_random_ip_id.h" =20 #include #include @@ -249,7 +250,9 @@ =20 maxnipq =3D nmbclusters/4; =20 +#ifndef RANDOM_IP_ID ip_id =3D time_second & 0xffff; +#endif ipintrq.ifq_maxlen =3D ipqmaxlen; mtx_init(&ipintrq.ifq_mtx, "ip_inq", MTX_DEF); =20 Index: netinet/ip_mroute.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet/ip_mroute.c,v retrieving revision 1.62 diff -u -r1.62 ip_mroute.c --- netinet/ip_mroute.c 2001/02/06 11:20:42 1.62 +++ netinet/ip_mroute.c 2001/05/26 06:16:07 @@ -13,6 +13,7 @@ */ =20 #include "opt_mrouting.h" +#include "opt_random_ip_id.h" =20 #include #include @@ -1581,7 +1582,11 @@ */ ip_copy =3D mtod(mb_copy, struct ip *); *ip_copy =3D multicast_encap_iphdr; +#ifdef RANDOM_IP_ID + ip_copy->ip_id =3D ip_randomid(); +#else ip_copy->ip_id =3D htons(ip_id++); +#endif ip_copy->ip_len +=3D len; ip_copy->ip_src =3D vifp->v_lcl_addr; ip_copy->ip_dst =3D vifp->v_rmt_addr; Index: netinet/ip_output.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet/ip_output.c,v retrieving revision 1.124 diff -u -r1.124 ip_output.c --- netinet/ip_output.c 2001/03/13 17:07:06 1.124 +++ netinet/ip_output.c 2001/05/26 06:16:24 @@ -42,6 +42,7 @@ #include "opt_ipfilter.h" #include "opt_ipsec.h" #include "opt_pfil_hooks.h" +#include "opt_random_ip_id.h" =20 #include #include @@ -208,7 +209,11 @@ if ((flags & (IP_FORWARDING|IP_RAWOUTPUT)) =3D=3D 0) { ip->ip_vhl =3D IP_MAKE_VHL(IPVERSION, hlen >> 2); ip->ip_off &=3D IP_DF; +#ifdef RANDOM_IP_ID + ip->ip_id =3D ip_randomid(); +#else ip->ip_id =3D htons(ip_id++); +#endif ipstat.ips_localout++; } else { hlen =3D IP_VHL_HL(ip->ip_vhl) << 2; Index: netinet/ip_var.h =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet/ip_var.h,v retrieving revision 1.54 diff -u -r1.54 ip_var.h --- netinet/ip_var.h 2001/03/19 09:16:16 1.54 +++ netinet/ip_var.h 2001/05/26 03:15:06 @@ -138,7 +138,9 @@ struct sockopt; =20 extern struct ipstat ipstat; +#ifndef RANDOM_IP_ID extern u_short ip_id; /* ip packet ctr, for ids */ +#endif extern int ip_defttl; /* default IP ttl */ extern int ipforwarding; /* ip forwarding */ extern struct route ipforward_rt; /* ip forwarding cached route */ @@ -164,6 +166,10 @@ struct mbuf * ip_srcroute __P((void)); void ip_stripoptions __P((struct mbuf *, struct mbuf *)); +#ifdef RANDOM_IP_ID +u_int16_t=09 + ip_randomid __P((void)); +#endif int rip_ctloutput __P((struct socket *, struct sockopt *)); void rip_ctlinput __P((int, struct sockaddr *, void *)); void rip_init __P((void)); Index: netinet/raw_ip.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet/raw_ip.c,v retrieving revision 1.76 diff -u -r1.76 raw_ip.c --- netinet/raw_ip.c 2001/05/11 14:37:34 1.76 +++ netinet/raw_ip.c 2001/05/26 06:16:51 @@ -36,6 +36,7 @@ =20 #include "opt_inet6.h" #include "opt_ipsec.h" +#include "opt_random_ip_id.h" =20 #include #include @@ -220,7 +221,11 @@ return EINVAL; } if (ip->ip_id =3D=3D 0) +#ifdef RANDOM_IP_ID + ip->ip_id =3D ip_randomid(); +#else ip->ip_id =3D htons(ip_id++); +#endif /* XXX prevent ip_output from overwriting header fields */ flags |=3D IP_RAWOUTPUT; ipstat.ips_rawout++; Index: netinet6/ipsec.c =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /home/ncvs/src/sys/netinet6/ipsec.c,v retrieving revision 1.10 diff -u -r1.10 ipsec.c --- netinet6/ipsec.c 2001/03/16 17:52:48 1.10 +++ netinet6/ipsec.c 2001/05/26 03:12:20 @@ -2045,7 +2045,11 @@ ipseclog((LOG_ERR, "IPv4 ipsec: size exceeds limit: " "leave ip_len as is (invalid packet)\n")); } +#ifdef RANDOM_IP_ID + ip->ip_id =3D ip_randomid(); +#else ip->ip_id =3D htons(ip_id++); +#endif bcopy(&((struct sockaddr_in *)&sav->sah->saidx.src)->sin_addr, &ip->ip_src, sizeof(ip->ip_src)); bcopy(&((struct sockaddr_in *)&sav->sah->saidx.dst)->sin_addr, Index: i386/conf/NOTES =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D RCS file: /mnt/ncvs/src/sys/i386/conf/NOTES,v retrieving revision 1.914 diff -u -r1.914 NOTES --- i386/conf/NOTES 2001/05/13 20:52:39 1.914 +++ i386/conf/NOTES 2001/05/26 06:34:01 @@ -590,6 +590,12 @@ options IPSTEALTH #support for stealth forwarding options TCPDEBUG =20 +# RANDOM_IP_ID causes the ID field in IP packets to be randomized +# instead of incremented by 1. This option prevents remote observers +# from determining the traffic load on the machine by watching the +# counter. +options RANDOM_IP_ID + # Statically Link in accept filters options ACCEPT_FILTER_DATA options ACCEPT_FILTER_HTTP --- /dev/null Fri May 25 23:33:00 2001 +++ netinet/ip_id.c Fri May 25 23:26:26 2001 @@ -0,0 +1,214 @@ +/* $OpenBSD: ip_id.c,v 1.2 1999/08/26 13:37:01 provos Exp $ */ + +/* + * Copyright 1998 Niels Provos + * All rights reserved. + * + * Theo de Raadt 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 WARRANTI= ES + * 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 US= E, + * 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. + * + * $FreeBSD$ + */ + +/*=20 + * seed =3D random 15bit + * n =3D prime, g0 =3D generator to n, + * j =3D random so that gcd(j,n-1) =3D=3D 1 + * g =3D g0^j mod n will be a generator again. + * + * X[0] =3D random seed. + * X[n] =3D a*X[n-1]+b mod m is a Linear Congruential Generator + * with a =3D 7^(even random) mod m,=20 + * b =3D random with gcd(b,m) =3D=3D 1 + * m =3D 31104 and a maximal period of m-1. + * + * The transaction id is determined by: + * id[n] =3D 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. + */ + +#include "opt_random_ip_id.h" +#include +#include +#include +#include + +#ifdef RANDOM_IP_ID +#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 =3D 2*2*3*2729 */ +#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */ +#define RU_M 31104 /* RU_M =3D 2^7*3^5 - don't change */ + +#define PFAC_N 3 +const static u_int16_t pfacts[PFAC_N] =3D { + 2,=20 + 3, + 2729 +}; + +static u_int16_t ru_x; +static u_int16_t ru_seed, ru_seed2; +static u_int16_t ru_a, ru_b; +static u_int16_t ru_g; +static u_int16_t ru_counter =3D 0; +static u_int16_t ru_msb =3D 0; +static long ru_reseed; +static u_int32_t tmp; /* Storage for unused random */ +static int randomize =3D 0; + +static u_int16_t pmod __P((u_int16_t, u_int16_t, u_int16_t)); +static void ip_initid __P((void)); +u_int16_t ip_randomid __P((void)); + +/* + * Do a fast modular exponation, returned value will be in the range + * of 0 - (mod-1) + */ + +#ifdef __STDC__ +static u_int16_t +pmod(u_int16_t gen, u_int16_t exp, u_int16_t mod) +#else +static u_int16_t +pmod(gen, exp, mod) + u_int16_t gen, exp, mod; +#endif +{ + u_int16_t s, t, u; + + s =3D 1; + t =3D gen; + u =3D exp; + + while (u) { + if (u & 1) + s =3D (s*t) % mod; + u >>=3D 1; + t =3D (t*t) % mod; + } + return (s); +} + +/*=20 + * Initalizes the seed and chooses a suitable generator. Also toggles=20 + * 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=20 + * application does not have to worry about it. + */ +static void=20 +ip_initid(void) +{ + u_int16_t j, i; + int noprime =3D 1; + struct timeval time; + + getmicrotime(&time); + read_random((void *) &tmp, sizeof(tmp)); + ru_x =3D (tmp & 0xFFFF) % RU_M; + + /* 15 bits of random seed */ + ru_seed =3D (tmp >> 16) & 0x7FFF; + read_random((void *) &tmp, sizeof(tmp)); + ru_seed2 =3D tmp & 0x7FFF; + + read_random((void *) &tmp, sizeof(tmp)); + + /* Determine the LCG we use */ + ru_b =3D (tmp & 0xfffe) | 1; + ru_a =3D pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M); + while (ru_b % 3 =3D=3D 0) + ru_b +=3D 2; +=09 + read_random((void *) &tmp, sizeof(tmp)); + j =3D tmp % RU_N; + tmp =3D tmp >> 16; + + /*=20 + * Do a fast gcd(j,RU_N-1), so we can find a j with + * gcd(j, RU_N-1) =3D=3D 1, giving a new generator for + * RU_GEN^j mod RU_N + */ + + while (noprime) { + for (i=3D0; i=3DPFAC_N) + noprime =3D 0; + else=20 + j =3D (j+1) % RU_N; + } + + ru_g =3D pmod(RU_GEN,j,RU_N); + ru_counter =3D 0; + + ru_reseed =3D time.tv_sec + RU_OUT; + ru_msb =3D ru_msb =3D=3D 0x8000 ? 0 : 0x8000;=20 +} + +u_int16_t +ip_randomid(void) +{ + int i, n; + static u_short ip_id =3D 0; /* ip packet ctr, for ids */ + static int ip_id_init =3D 0; + struct timeval time; + + getmicrotime(&time); + if (ru_counter >=3D RU_MAX || time.tv_sec > ru_reseed) + ip_initid(); + + if (!tmp) + read_random((void *) &tmp, sizeof(tmp)); + + /* Skip a random number of ids */ + n =3D tmp & 0x3; tmp =3D tmp >> 2; + if (ru_counter + n >=3D RU_MAX) + ip_initid(); + + for (i =3D 0; i <=3D n; i++) + /* Linear Congruential Generator */ + ru_x =3D (ru_a*ru_x + ru_b) % RU_M; + + ru_counter +=3D i; + + return (ru_seed ^ pmod(ru_g,ru_seed2 ^ ru_x,RU_N)) | ru_msb; + } +} + +#endif /* RANDOM_IP_ID */ --n8g4imXOkfNTN/H1 Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.5 (FreeBSD) Comment: For info see http://www.gnupg.org iD8DBQE7D09TWry0BWjoQKURArqeAKD6MVsG4BfaC9perXRxzUqj1QEzKQCgpwBI rYJYEEzyJuJuqNgdjHFlJXk= =Ug87 -----END PGP SIGNATURE----- --n8g4imXOkfNTN/H1-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message