From ac04a74e55b78112d96b5d55c5443258b4090f67 Mon Sep 17 00:00:00 2001 From: Niels Provos Date: Sat, 26 Dec 1998 12:35:13 +0000 Subject: make ip_id random but ensure that ids dont repeat for some period. --- sys/conf/files | 3 +- sys/netinet/ip_id.c | 199 ++++++++++++++++++++++++++++++++++++++++++++++++ sys/netinet/ip_input.c | 3 +- sys/netinet/ip_ip4.c | 5 +- sys/netinet/ip_mroute.c | 8 +- sys/netinet/ip_output.c | 4 +- sys/netinet/ip_var.h | 5 +- sys/netinet/raw_ip.c | 4 +- 8 files changed, 213 insertions(+), 18 deletions(-) create mode 100644 sys/netinet/ip_id.c diff --git a/sys/conf/files b/sys/conf/files index 0a0758be0f0..49e1f392c13 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -1,4 +1,4 @@ -# $OpenBSD: files,v 1.100 1998/11/28 04:06:04 mickey Exp $ +# $OpenBSD: files,v 1.101 1998/12/26 12:35:10 provos Exp $ # $NetBSD: files,v 1.87 1996/05/19 17:17:50 jonathan Exp $ # @(#)files.newconf 7.5 (Berkeley) 5/10/93 @@ -346,6 +346,7 @@ file netinet/in.c inet file netinet/in_pcb.c inet file netinet/in_proto.c inet file netinet/ip_icmp.c inet +file netinet/ip_id.c inet file netinet/ip_input.c inet file netinet/ip_mroute.c inet file netinet/ip_output.c inet diff --git a/sys/netinet/ip_id.c b/sys/netinet/ip_id.c new file mode 100644 index 00000000000..54ab20fbf42 --- /dev/null +++ b/sys/netinet/ip_id.c @@ -0,0 +1,199 @@ +/* $OpenBSD: ip_id.c,v 1.1 1998/12/26 12:35:12 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 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. + */ + +#include +#include +#include + +#include + +#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 u_int16_t pfacts[PFAC_N] = { + 2, + 3, + 2729 +}; + +static u_int16_t ru_x; +static u_int16_t ru_seed; +static u_int16_t ru_a, ru_b; +static u_int16_t ru_g; +static u_int16_t ru_counter = 0; +static u_int16_t ru_msb = 0; +static long ru_reseed; +static u_int32_t tmp; /* Storage for unused random */ + +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 = 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) +{ + u_int16_t 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)); + + /* 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) + noprime = 0; + else + j = (j+1) % RU_N; + } + + ru_g = pmod(RU_GEN,j,RU_N); + ru_counter = 0; + + ru_reseed = time.tv_sec + RU_OUT; + ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; +} + +u_int16_t +ip_randomid(void) +{ + int i, n; + + if (ru_counter >= RU_MAX || time.tv_sec > 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_x,RU_N)) | ru_msb; +} diff --git a/sys/netinet/ip_input.c b/sys/netinet/ip_input.c index 40e0edfc105..9b1f9cd4a02 100644 --- a/sys/netinet/ip_input.c +++ b/sys/netinet/ip_input.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ip_input.c,v 1.32 1998/11/13 22:24:17 provos Exp $ */ +/* $OpenBSD: ip_input.c,v 1.33 1998/12/26 12:35:11 provos Exp $ */ /* $NetBSD: ip_input.c,v 1.30 1996/03/16 23:53:58 christos Exp $ */ /* @@ -171,7 +171,6 @@ ip_init() pr->pr_protocol && pr->pr_protocol != IPPROTO_RAW) ip_protox[pr->pr_protocol] = pr - inetsw; LIST_INIT(&ipq); - ip_id = time.tv_sec & 0xffff; ipintrq.ifq_maxlen = ipqmaxlen; TAILQ_INIT(&in_ifaddr); diff --git a/sys/netinet/ip_ip4.c b/sys/netinet/ip_ip4.c index 4cbaa19b23f..50a819b4246 100644 --- a/sys/netinet/ip_ip4.c +++ b/sys/netinet/ip_ip4.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ip_ip4.c,v 1.20 1998/07/29 22:18:49 angelos Exp $ */ +/* $OpenBSD: ip_ip4.c,v 1.21 1998/12/26 12:35:11 provos Exp $ */ /* * The authors of this code are John Ioannidis (ji@tla.org), @@ -224,8 +224,7 @@ ipe4_output(struct mbuf *m, struct sockaddr_encap *gw, struct tdb *tdb, ipo->ip_hl = 5; ipo->ip_tos = ipi->ip_tos; ipo->ip_len = htons(ilen + sizeof(struct ip)); -/* ipo->ip_id = htons(ip_id++); */ - get_random_bytes((void *) &(ipo->ip_id), sizeof(ipo->ip_id)); + ipo->ip_id = htons(ip_randomid()); ipo->ip_off = ipi->ip_off & ~(IP_MF | IP_OFFMASK); /* keep C and DF */ if (tdb->tdb_flags & TDBF_SAME_TTL) diff --git a/sys/netinet/ip_mroute.c b/sys/netinet/ip_mroute.c index eecb148aaa6..0bdde09c3ea 100644 --- a/sys/netinet/ip_mroute.c +++ b/sys/netinet/ip_mroute.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ip_mroute.c,v 1.10 1998/07/29 22:18:50 angelos Exp $ */ +/* $OpenBSD: ip_mroute.c,v 1.11 1998/12/26 12:35:11 provos Exp $ */ /* $NetBSD: ip_mroute.c,v 1.27 1996/05/07 02:40:50 thorpej Exp $ */ /* @@ -1397,11 +1397,7 @@ encap_send(ip, vifp, m) */ ip_copy = mtod(mb_copy, struct ip *); *ip_copy = multicast_encap_iphdr; -#ifdef IPSEC - get_random_bytes((void *)&(ip_copy->ip_id), sizeof(ip_copy->ip_id)); -#else - ip_copy->ip_id = htons(ip_id++); -#endif + ip_copy->ip_id = htons(ip_randomid()); ip_copy->ip_len = len; ip_copy->ip_src = vifp->v_lcl_addr; ip_copy->ip_dst = vifp->v_rmt_addr; diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c index 44bb99c432b..cae2c256a0a 100644 --- a/sys/netinet/ip_output.c +++ b/sys/netinet/ip_output.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ip_output.c,v 1.36 1998/08/02 22:20:30 provos Exp $ */ +/* $OpenBSD: ip_output.c,v 1.37 1998/12/26 12:35:11 provos Exp $ */ /* $NetBSD: ip_output.c,v 1.28 1996/02/13 23:43:07 christos Exp $ */ /* @@ -151,7 +151,7 @@ ip_output(m0, va_alist) if ((flags & (IP_FORWARDING|IP_RAWOUTPUT)) == 0) { ip->ip_v = IPVERSION; ip->ip_off &= IP_DF; - ip->ip_id = htons(ip_id++); + ip->ip_id = htons(ip_randomid()); ip->ip_hl = hlen >> 2; ipstat.ips_localout++; } else { diff --git a/sys/netinet/ip_var.h b/sys/netinet/ip_var.h index 77afb80f922..d249293406a 100644 --- a/sys/netinet/ip_var.h +++ b/sys/netinet/ip_var.h @@ -1,4 +1,4 @@ -/* $OpenBSD: ip_var.h,v 1.8 1998/02/14 18:50:36 mickey Exp $ */ +/* $OpenBSD: ip_var.h,v 1.9 1998/12/26 12:35:12 provos Exp $ */ /* $NetBSD: ip_var.h,v 1.16 1996/02/13 23:43:20 christos Exp $ */ /* @@ -160,7 +160,6 @@ struct ipstat { struct ipstat ipstat; LIST_HEAD(ipqhead, ipq) ipq; /* ip reass. queue */ -u_int16_t ip_id; /* ip packet ctr, for ids */ int ip_defttl; /* default IP ttl */ int ip_ctloutput __P((int, struct socket *, int, int, struct mbuf **)); @@ -181,6 +180,8 @@ struct in_ifaddr * in_iawithaddr __P((struct in_addr, struct mbuf *)); struct in_ifaddr * ip_rtaddr __P((struct in_addr)); +u_int16_t + ip_randomid __P((void)); int ip_setmoptions __P((int, struct ip_moptions **, struct mbuf *)); void ip_slowtimo __P((void)); struct mbuf * diff --git a/sys/netinet/raw_ip.c b/sys/netinet/raw_ip.c index 36a70c186b5..11cf3f5b69e 100644 --- a/sys/netinet/raw_ip.c +++ b/sys/netinet/raw_ip.c @@ -1,4 +1,4 @@ -/* $OpenBSD: raw_ip.c,v 1.12 1998/12/15 02:26:35 deraadt Exp $ */ +/* $OpenBSD: raw_ip.c,v 1.13 1998/12/26 12:35:12 provos Exp $ */ /* $NetBSD: raw_ip.c,v 1.25 1996/02/18 18:58:33 christos Exp $ */ /* @@ -207,7 +207,7 @@ rip_output(m, va_alist) return (EINVAL); } if (ip->ip_id == 0) - ip->ip_id = htons(ip_id++); + ip->ip_id = htons(ip_randomid()); /* XXX prevent ip_output from overwriting header fields */ flags |= IP_RAWOUTPUT; ipstat.ips_rawout++; -- cgit v1.2.3