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 #include <sys/smp.h>
  23 #include <sys/malloc.h>
  24
  25 #define ARC4_RESEED_BYTES 65536
  26 #define ARC4_RESEED_SECONDS 300
  27 #define ARC4_KEYBYTES 256
  28
  29 int arc4rand_iniseed_state = ARC4_ENTR_NONE;
  30
  31 MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures");
  32
  33 struct arc4_s {
  34         struct mtx mtx;
  35         u_int8_t i, j;
  36         int numruns;
  37         u_int8_t sbox[256];
  38         time_t t_reseed;
  39
  40 } __aligned(CACHE_LINE_SIZE);
  41
  42 static struct arc4_s *arc4inst = NULL;
  43
  44 #define ARC4_FOREACH(_arc4) \
  45         for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++)
  46
  47 static u_int8_t arc4_randbyte(struct arc4_s *arc4);
  48
  49 static __inline void
  50 arc4_swap(u_int8_t *a, u_int8_t *b)
  51 {
  52         u_int8_t c;
  53
  54         c = *a;
  55         *a = *b;
  56         *b = c;
  57 }
  58
  59 /*
  60  * Stir our S-box.
  61  */
  62 static void
  63 arc4_randomstir(struct arc4_s* arc4)
  64 {
  65         u_int8_t key[ARC4_KEYBYTES];
  66         int n;
  67         struct timeval tv_now;
  68
  69         /*
  70          * XXX: FIX!! This isn't brilliant. Need more confidence.
  71          * This returns zero entropy before random(4) is seeded.
  72          */
  73         (void)read_random(key, ARC4_KEYBYTES);
  74         getmicrouptime(&tv_now);
  75         mtx_lock(&arc4->mtx);
  76         for (n = 0; n < 256; n++) {
  77                 arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256;
  78                 arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]);
  79         }
  80         arc4->i = arc4->j = 0;
  81         /* Reset for next reseed cycle. */
  82         arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
  83         arc4->numruns = 0;
  84         /*
  85          * Throw away the first N words of output, as suggested in the
  86          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
  87          * by Fluher, Mantin, and Shamir.  (N = 768 in our case.)
  88          *
  89          * http://dl.acm.org/citation.cfm?id=646557.694759
  90          */
  91         for (n = 0; n < 768*4; n++)
  92                 arc4_randbyte(arc4);
  93
  94         mtx_unlock(&arc4->mtx);
  95 }
  96
  97 /*
  98  * Initialize our S-box to its beginning defaults.
  99  */
 100 static void
 101 arc4_init(void)
 102 {
 103         struct arc4_s *arc4;
 104         int n;
 105
 106         arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s),
 107                         M_ARC4RANDOM, M_NOWAIT | M_ZERO);
 108         KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error"));
 109
 110         ARC4_FOREACH(arc4) {
 111                 mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF);
 112
 113                 arc4->i = arc4->j = 0;
 114                 for (n = 0; n < 256; n++)
 115                         arc4->sbox[n] = (u_int8_t) n;
 116
 117                 arc4->t_reseed = -1;
 118                 arc4->numruns = 0;
 119         }
 120 }
 121 SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
 122
 123
 124 static void
 125 arc4_uninit(void)
 126 {
 127         struct arc4_s *arc4;
 128
 129         ARC4_FOREACH(arc4) {
 130                 mtx_destroy(&arc4->mtx);
 131         }
 132
 133         free(arc4inst, M_ARC4RANDOM);
 134 }
 135
 136 SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL);
 137
 138
 139 /*
 140  * Generate a random byte.
 141  */
 142 static u_int8_t
 143 arc4_randbyte(struct arc4_s *arc4)
 144 {
 145         u_int8_t arc4_t;
 146
 147         arc4->i = (arc4->i + 1) % 256;
 148         arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256;
 149
 150         arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]);
 151
 152         arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256;
 153         return arc4->sbox[arc4_t];
 154 }
 155
 156 /*
 157  * MPSAFE
 158  */
 159 void
 160 arc4rand(void *ptr, u_int len, int reseed)
 161 {
 162         u_char *p;
 163         struct timeval tv;
 164         struct arc4_s *arc4;
 165
 166         if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state,
 167                         ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) {
 168                 ARC4_FOREACH(arc4)
 169                         arc4_randomstir(arc4);
 170         }
 171
 172         arc4 = &arc4inst[curcpu];
 173         getmicrouptime(&tv);
 174         if ((arc4->numruns > ARC4_RESEED_BYTES) ||
 175                 (tv.tv_sec > arc4->t_reseed))
 176                 arc4_randomstir(arc4);
 177
 178         mtx_lock(&arc4->mtx);
 179         arc4->numruns += len;
 180         p = ptr;
 181         while (len--)
 182                 *p++ = arc4_randbyte(arc4);
 183         mtx_unlock(&arc4->mtx);
 184 }
 185
 186 uint32_t
 187 arc4random(void)
 188 {
 189         uint32_t ret;
 190
 191         arc4rand(&ret, sizeof ret, 0);
 192         return ret;
 193 }