1 /* $OpenBSD: ip_id.c,v 1.23 2011/03/31 10:36:42 jasper Exp $ */ 2 3 /* 4 * Copyright (c) 2008 Theo de Raadt, Ryan McBride 5 * 6 * Slightly different algorithm from the one designed by 7 * Matthew Dillon <dillon@backplane.com> for The DragonFly Project 8 * 9 * Permission to use, copy, modify, and distribute this software for any 10 * purpose with or without fee is hereby granted, provided that the above 11 * copyright notice and this permission notice appear in all copies. 12 * 13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 20 */ 21 22 /* 23 * Random ip sequence number generator. Use the system PRNG to shuffle 24 * the 65536 entry ID space. We reshuffle the ID we pick out of the array 25 * into the previous 32767 cells, providing an guarantee that an ID will not 26 * be reused for at least 32768 calls. 27 */ 28 #include <sys/param.h> 29 #include <dev/rndvar.h> 30 31 static u_int16_t ip_shuffle[65536]; 32 static int isindex = 0; 33 34 u_int16_t ip_randomid(void); 35 36 /* 37 * Return a random IP id. Shuffle the new value we get into the previous half 38 * of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates 39 * occuring too quickly but also still be random. 40 * 41 * 0 is a special IP ID -- don't return it. 42 */ 43 u_int16_t 44 ip_randomid(void) 45 { 46 static int ipid_initialized; 47 u_int16_t si, r; 48 int i, i2; 49 50 if (!ipid_initialized) { 51 ipid_initialized = 1; 52 53 /* 54 * Initialize with a random permutation. Do so using Knuth 55 * which avoids the exchange in the Durstenfeld shuffle. 56 * (See "The Art of Computer Programming, Vol 2" 3rd ed, pg. 145). 57 * 58 * Even if our PRNG is imperfect at boot time, we have deferred 59 * doing this until the first packet being sent and now must 60 * generate an ID. 61 */ 62 for (i = 0; i < nitems(ip_shuffle); ++i) { 63 i2 = arc4random_uniform(i + 1); 64 ip_shuffle[i] = ip_shuffle[i2]; 65 ip_shuffle[i2] = i; 66 } 67 } 68 69 do { 70 arc4random_buf(&si, sizeof(si)); 71 i = isindex & 0xFFFF; 72 i2 = (isindex - (si & 0x7FFF)) & 0xFFFF; 73 r = ip_shuffle[i]; 74 ip_shuffle[i] = ip_shuffle[i2]; 75 ip_shuffle[i2] = r; 76 isindex++; 77 } while (r == 0); 78 79 return (r); 80 } 81