sys/libkern/arc4random.c

   1 /*-
   2  * THE BEER-WARE LICENSE
   3  *
   4  * <dan@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
   5  * can do whatever you want with this stuff.  If we meet some day, and you
   6  * think this stuff is worth it, you can buy me a beer in return.
   7  *
   8  * Dan Moschuk
   9  */
  10
  11 #include <sys/cdefs.h>
  12 __FBSDID("$FreeBSD$");
  13
  14 #include <sys/types.h>
  15 #include <sys/param.h>
  16 #include <sys/kernel.h>
  17 #include <sys/random.h>
  18 #include <sys/libkern.h>
  19 #include <sys/lock.h>
  20 #include <sys/mutex.h>
  21 #include <sys/time.h>
  22
  23 #define ARC4_RESEED_BYTES 65536
  24 #define ARC4_RESEED_SECONDS 300
  25 #define ARC4_KEYBYTES (256 / 8)
  26
  27 static u_int8_t arc4_i, arc4_j;
  28 static int arc4_numruns = 0;
  29 static u_int8_t arc4_sbox[256];
  30 static time_t arc4_t_reseed;
  31 static struct mtx arc4_mtx;
  32
  33 static u_int8_t arc4_randbyte(void);
  34
  35 static __inline void
  36 arc4_swap(u_int8_t *a, u_int8_t *b)
  37 {
  38         u_int8_t c;
  39
  40         c = *a;
  41         *a = *b;
  42         *b = c;
  43 }
  44
  45 /*
  46  * Stir our S-box.
  47  */
  48 static void
  49 arc4_randomstir (void)
  50 {
  51         u_int8_t key[256];
  52         int r, n;
  53         struct timeval tv_now;
  54
  55         /*
  56          * XXX read_random() returns unsafe numbers if the entropy
  57          * device is not loaded -- MarkM.
  58          */
  59         r = read_random(key, ARC4_KEYBYTES);
  60         getmicrouptime(&tv_now);
  61         mtx_lock(&arc4_mtx);
  62         /* If r == 0 || -1, just use what was on the stack. */
  63         if (r > 0) {
  64                 for (n = r; n < sizeof(key); n++)
  65                         key[n] = key[n % r];
  66         }
  67
  68         for (n = 0; n < 256; n++) {
  69                 arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
  70                 arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
  71         }
  72         arc4_i = arc4_j = 0;
  73
  74         /* Reset for next reseed cycle. */
  75         arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
  76         arc4_numruns = 0;
  77
  78         /*
  79          * Throw away the first N words of output, as suggested in the
  80          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
  81          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
  82          */
  83         for (n = 0; n < 256*4; n++)
  84                 arc4_randbyte();
  85         mtx_unlock(&arc4_mtx);
  86 }
  87
  88 /*
  89  * Initialize our S-box to its beginning defaults.
  90  */
  91 static void
  92 arc4_init(void)
  93 {
  94         int n;
  95
  96         mtx_init(&arc4_mtx, "arc4_mtx", NULL, MTX_DEF);
  97         arc4_i = arc4_j = 0;
  98         for (n = 0; n < 256; n++)
  99                 arc4_sbox[n] = (u_int8_t) n;
 100
 101         arc4_t_reseed = 0;
 102 }
 103
 104 SYSINIT(arc4_init, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
 105
 106 /*
 107  * Generate a random byte.
 108  */
 109 static u_int8_t
 110 arc4_randbyte(void)
 111 {
 112         u_int8_t arc4_t;
 113
 114         arc4_i = (arc4_i + 1) % 256;
 115         arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
 116
 117         arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
 118
 119         arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
 120         return arc4_sbox[arc4_t];
 121 }
 122
 123 /*
 124  * MPSAFE
 125  */
 126 void
 127 arc4rand(void *ptr, u_int len, int reseed)
 128 {
 129         u_char *p;
 130         struct timeval tv;
 131
 132         getmicrouptime(&tv);
 133         if (reseed ||
 134            (arc4_numruns > ARC4_RESEED_BYTES) ||
 135            (tv.tv_sec > arc4_t_reseed))
 136                 arc4_randomstir();
 137
 138         mtx_lock(&arc4_mtx);
 139         arc4_numruns += len;
 140         p = ptr;
 141         while (len--)
 142                 *p++ = arc4_randbyte();
 143         mtx_unlock(&arc4_mtx);
 144 }
 145
 146 uint32_t
 147 arc4random(void)
 148 {
 149         uint32_t ret;
 150
 151         arc4rand(&ret, sizeof ret, 0);
 152         return ret;
 153 }