[BACK]Return to ip_id.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / sys / netinet

File: [cvs.NetBSD.org] / src / sys / netinet / ip_id.c (download)

Revision 1.12, Wed Feb 6 03:20:51 2008 UTC (6 years, 10 months ago) by matt
Branch: MAIN
CVS Tags: yamt-pf42-baseX, yamt-pf42-base4, yamt-pf42-base3, yamt-pf42-base2, yamt-pf42-base, yamt-pf42, yamt-nfs-mp-base9, yamt-nfs-mp-base8, yamt-nfs-mp-base7, yamt-nfs-mp-base6, yamt-nfs-mp-base5, yamt-nfs-mp-base4, yamt-nfs-mp-base3, yamt-nfs-mp-base2, yamt-nfs-mp-base11, yamt-nfs-mp-base10, yamt-nfs-mp-base, yamt-nfs-mp, yamt-lazymbuf-base15, yamt-lazymbuf-base14, wrstuden-revivesa-base-4, wrstuden-revivesa-base-3, wrstuden-revivesa-base-2, wrstuden-revivesa-base-1, wrstuden-revivesa-base, wrstuden-revivesa, uebayasi-xip-base3, uebayasi-xip-base2, uebayasi-xip-base1, uebayasi-xip-base, simonb-wapbl-nbase, simonb-wapbl-base, simonb-wapbl, nick-net80211-sync-base, nick-net80211-sync, nick-hppapmap-base4, nick-hppapmap-base3, nick-hppapmap-base2, nick-hppapmap-base, nick-hppapmap, netbsd-5-base, netbsd-5-2-RELEASE, netbsd-5-2-RC1, netbsd-5-2-3-RELEASE, netbsd-5-2-2-RELEASE, netbsd-5-2-1-RELEASE, netbsd-5-2, netbsd-5-1-RELEASE, netbsd-5-1-RC4, netbsd-5-1-RC3, netbsd-5-1-RC2, netbsd-5-1-RC1, netbsd-5-1-5-RELEASE, netbsd-5-1-4-RELEASE, netbsd-5-1-3-RELEASE, netbsd-5-1-2-RELEASE, netbsd-5-1-1-RELEASE, netbsd-5-1, netbsd-5-0-RELEASE, netbsd-5-0-RC4, netbsd-5-0-RC3, netbsd-5-0-RC2, netbsd-5-0-RC1, netbsd-5-0-2-RELEASE, netbsd-5-0-1-RELEASE, netbsd-5-0, netbsd-5, mjf-devfs2-base, mjf-devfs2, mjf-devfs-base, matt-premerge-20091211, matt-nb5-pq3-base, matt-nb5-pq3, matt-nb5-mips64-u2-k2-k4-k7-k8-k9, matt-nb5-mips64-u1-k1-k5, matt-nb5-mips64-premerge-20101231, matt-nb5-mips64-premerge-20091211, matt-nb5-mips64-k15, matt-nb5-mips64, matt-nb4-mips64-k7-u2a-k9b, matt-mips64-base2, matt-armv6-nbase, keiichi-mipv6-nbase, keiichi-mipv6-base, keiichi-mipv6, jymxensuspend-base, jym-xensuspend-nbase, jym-xensuspend-base, jym-xensuspend, hpcarm-cleanup-nbase, hpcarm-cleanup-base, haad-nbase2, haad-dm-base2, haad-dm-base1, haad-dm-base, haad-dm, ad-socklock-base1, ad-audiomp2-base, ad-audiomp2
Branch point for: uebayasi-xip, rmind-uvmplock
Changes since 1.11: +63 -107 lines

Add a new ip_id generation scheme based on a Fisher-Yates shuffle over a
sliding window.  XXX replace use of arc4random RSN.

/*	$NetBSD: ip_id.c,v 1.12 2008/02/06 03:20:51 matt Exp $	*/
/*	$OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $	*/

/*
 * 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.
 *
 * 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)
 *
 * Effectively 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 <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: ip_id.c,v 1.12 2008/02/06 03:20:51 matt Exp $");

#include "opt_inet.h"

#include <sys/param.h>
#include <lib/libkern/libkern.h>

#include <net/if.h>
#include <netinet/in.h>
#include <netinet/in_var.h>

#define	IPID_MAXID	65535
#define	IPID_NUMIDS	32768

static struct ipid_state {
	uint16_t ids_start_slot;
	uint16_t ids_slots[IPID_MAXID];
} idstate;

static inline uint32_t
ipid_random(void)
{
	return arc4random();
}

/*
 * Initalizes the  
 * 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.
 */
void
ip_initid(void)
{
	size_t i;

	idstate.ids_start_slot = ipid_random();
	for (i = 0; i < __arraycount(idstate.ids_slots); i++)
		idstate.ids_slots[i] = i;

	/*
	 * Shuffle the array.
	 */
	for (i = __arraycount(idstate.ids_slots); --i > 0;) {
		size_t k = ipid_random() % (i + 1);
		uint16_t t = idstate.ids_slots[i];
		idstate.ids_slots[i] = idstate.ids_slots[k];
		idstate.ids_slots[k] = t;
	}
}

uint16_t
ip_randomid(uint16_t salt)
{
	uint32_t r, k, id;

	/*
	 * We need a random number 
	 */
	r = ipid_random();

	/*
	 * We do a modified Fisher-Yates shuffle but only one position at a
	 * time. Instead of the last entry, we swap with the first entry and
	 * then advance the start of the window by 1.  The next time that 
	 * swapped-out entry can be used is at least 32768 iterations in the
	 * future.
 	 *
	 * The easiest way to visual this is to imagine a card deck with 52
	 * cards.  First thing we do is split that into two sets, each with
	 * half of the cards; call them deck A and deck B.  Pick a card
	 * randomly from deck A and remember it, then place it at the
	 * bottom of deck B.  Then take the top card from deck B and add it
	 * to deck A.  Pick another card randomly from deck A and ...
	 */
	k = (r & (IPID_NUMIDS-1)) + idstate.ids_start_slot;
	if (k >= IPID_MAXID)
		k -= IPID_MAXID;

	id = idstate.ids_slots[k];
	if (k != idstate.ids_start_slot) {
		idstate.ids_slots[k] = idstate.ids_slots[idstate.ids_start_slot];
		idstate.ids_slots[idstate.ids_start_slot] = id;
	}
	if (++idstate.ids_start_slot == IPID_MAXID)
		idstate.ids_start_slot = 0;
	/*
	 * Add an optional salt to the id to further obscure it.
	 */
	id += salt;
	if (id >= IPID_MAXID)
		id -= IPID_MAXID;

	return (uint16_t) htons(id + 1);
}