Line data    Source code

       1             : /*      $OpenBSD: ip_id.c,v 1.24 2014/11/18 02:37:31 tedu 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 <sys/systm.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           0 : ip_randomid(void)
      45             : {
      46             :         static int ipid_initialized;
      47           0 :         u_int16_t si, r;
      48             :         int i, i2;
      49             : 
      50           0 :         if (!ipid_initialized) {
      51           0 :                 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           0 :                 for (i = 0; i < nitems(ip_shuffle); ++i) {
      63           0 :                         i2 = arc4random_uniform(i + 1);
      64           0 :                         ip_shuffle[i] = ip_shuffle[i2];
      65           0 :                         ip_shuffle[i2] = i;
      66             :                 }
      67             :         }
      68             : 
      69           0 :         do {
      70           0 :                 arc4random_buf(&si, sizeof(si));
      71           0 :                 i = isindex & 0xFFFF;
      72           0 :                 i2 = (isindex - (si & 0x7FFF)) & 0xFFFF;
      73           0 :                 r = ip_shuffle[i];
      74           0 :                 ip_shuffle[i] = ip_shuffle[i2];
      75           0 :                 ip_shuffle[i2] = r;
      76           0 :                 isindex++;
      77           0 :         } while (r == 0);
      78             : 
      79           0 :         return (r);
      80           0 : }