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
  26
  27 int arc4rand_iniseed_state = ARC4_ENTR_NONE;
  28
  29 static u_int8_t arc4_i, arc4_j;
  30 static int arc4_numruns = 0;
  31 static u_int8_t arc4_sbox[256];
  32 static time_t arc4_t_reseed;
  33 static struct mtx arc4_mtx;
  34
  35 static u_int8_t arc4_randbyte(void);
  36
  37 static __inline void
  38 arc4_swap(u_int8_t *a, u_int8_t *b)
  39 {
  40         u_int8_t c;
  41
  42         c = *a;
  43         *a = *b;
  44         *b = c;
  45 }
  46
  47 /*
  48  * Stir our S-box.
  49  */
  50 static void
  51 arc4_randomstir(void)
  52 {
  53         u_int8_t key[ARC4_KEYBYTES];
  54         int n;
  55         struct timeval tv_now;
  56
  57         /*
  58          * XXX: FIX!! This isn't brilliant. Need more confidence.
  59          * This returns zero entropy before random(4) is seeded.
  60          */
  61         (void)read_random(key, ARC4_KEYBYTES);
  62         getmicrouptime(&tv_now);
  63         mtx_lock(&arc4_mtx);
  64         for (n = 0; n < 256; n++) {
  65                 arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
  66                 arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
  67         }
  68         arc4_i = arc4_j = 0;
  69         /* Reset for next reseed cycle. */
  70         arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
  71         arc4_numruns = 0;
  72         /*
  73          * Throw away the first N words of output, as suggested in the
  74          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
  75          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
  76          *
  77          * http://dl.acm.org/citation.cfm?id=646557.694759
  78          */
  79         for (n = 0; n < 256*4; n++)
  80                 arc4_randbyte();
  81         mtx_unlock(&arc4_mtx);
  82 }
  83
  84 /*
  85  * Initialize our S-box to its beginning defaults.
  86  */
  87 static void
  88 arc4_init(void)
  89 {
  90         int n;
  91
  92         mtx_init(&arc4_mtx, "arc4_mtx", NULL, MTX_DEF);
  93         arc4_i = arc4_j = 0;
  94         for (n = 0; n < 256; n++)
  95                 arc4_sbox[n] = (u_int8_t) n;
  96
  97         arc4_t_reseed = 0;
  98 }
  99
 100 SYSINIT(arc4_init, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
 101
 102 /*
 103  * Generate a random byte.
 104  */
 105 static u_int8_t
 106 arc4_randbyte(void)
 107 {
 108         u_int8_t arc4_t;
 109
 110         arc4_i = (arc4_i + 1) % 256;
 111         arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
 112
 113         arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
 114
 115         arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
 116         return arc4_sbox[arc4_t];
 117 }
 118
 119 /*
 120  * MPSAFE
 121  */
 122 void
 123 arc4rand(void *ptr, u_int len, int reseed)
 124 {
 125         u_char *p;
 126         struct timeval tv;
 127
 128         getmicrouptime(&tv);
 129         if (atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_HAVE,
 130             ARC4_ENTR_SEED) || reseed ||
 131            (arc4_numruns > ARC4_RESEED_BYTES) ||
 132            (tv.tv_sec > arc4_t_reseed))
 133                 arc4_randomstir();
 134
 135         mtx_lock(&arc4_mtx);
 136         arc4_numruns += len;
 137         p = ptr;
 138         while (len--)
 139                 *p++ = arc4_randbyte();
 140         mtx_unlock(&arc4_mtx);
 141 }
 142
 143 uint32_t
 144 arc4random(void)
 145 {
 146         uint32_t ret;
 147
 148         arc4rand(&ret, sizeof ret, 0);
 149         return ret;
 150 }