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
  73         /* Reset for next reseed cycle. */
  74         arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
  75         arc4_numruns = 0;
  76
  77         /*
  78          * Throw away the first N words of output, as suggested in the
  79          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
  80          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
  81          */
  82         for (n = 0; n < 256*4; n++)
  83                 arc4_randbyte();
  84         mtx_unlock(&arc4_mtx);
  85 }
  86
  87 /*
  88  * Initialize our S-box to its beginning defaults.
  89  */
  90 static void
  91 arc4_init(void)
  92 {
  93         int n;
  94
  95         mtx_init(&arc4_mtx, "arc4_mtx", NULL, MTX_DEF);
  96         arc4_i = arc4_j = 0;
  97         for (n = 0; n < 256; n++)
  98                 arc4_sbox[n] = (u_int8_t) n;
  99
 100         arc4_t_reseed = 0;
 101 }
 102
 103 SYSINIT(arc4_init, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
 104
 105 /*
 106  * Generate a random byte.
 107  */
 108 static u_int8_t
 109 arc4_randbyte(void)
 110 {
 111         u_int8_t arc4_t;
 112
 113         arc4_i = (arc4_i + 1) % 256;
 114         arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
 115
 116         arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
 117
 118         arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
 119         return arc4_sbox[arc4_t];
 120 }
 121
 122 /*
 123  * MPSAFE
 124  */
 125 void
 126 arc4rand(void *ptr, u_int len, int reseed)
 127 {
 128         u_char *p;
 129         struct timeval tv;
 130
 131         getmicrouptime(&tv);
 132         if (reseed ||
 133            (arc4_numruns > ARC4_RESEED_BYTES) ||
 134            (tv.tv_sec > arc4_t_reseed))
 135                 arc4_randomstir();
 136
 137         mtx_lock(&arc4_mtx);
 138         arc4_numruns += len;
 139         p = ptr;
 140         while (len--)
 141                 *p++ = arc4_randbyte();
 142         mtx_unlock(&arc4_mtx);
 143 }
 144
 145 uint32_t
 146 arc4random(void)
 147 {
 148         uint32_t ret;
 149
 150         arc4rand(&ret, sizeof ret, 0);
 151         return ret;
 152 }