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  * $FreeBSD: src/sys/libkern/arc4random.c,v 1.3.2.2 2001/09/17 07:06:50 silby Exp $
  11  * $DragonFly: src/sys/libkern/arc4random.c,v 1.3 2006/09/03 17:31:55 dillon Exp $
  12  */
  13
  14 #include <sys/types.h>
  15 #include <sys/systm.h>
  16 #include <sys/random.h>
  17 #include <sys/libkern.h>
  18 #include <sys/time.h>
  19
  20 #include <vm/vm_extern.h>
  21
  22 #define ARC4_MAXRUNS            16384
  23 #define ARC4_RESEED_SECONDS     300
  24 #define ARC4_KEYBYTES           32      /* 256 bit key */
  25
  26 struct arc4_data {
  27         uint8_t                 arc4_i;
  28         uint8_t                 arc4_j;
  29         int                     arc4_numruns;
  30         time_t                  arc4_nextreseed;
  31         uint8_t                 arc4_sbox[256];
  32 };
  33
  34 static struct arc4_data         *arc4_data_pcpu[MAXCPU];
  35
  36 static uint8_t                  arc4_randbyte(struct arc4_data *);
  37
  38 static __inline void
  39 arc4_swap(uint8_t *a, uint8_t *b)
  40 {
  41         uint8_t c;
  42
  43         c = *a;
  44         *a = *b;
  45         *b = c;
  46 }
  47
  48 /*
  49  * Stir our S-box.
  50  */
  51 static void
  52 arc4_randomstir(struct arc4_data *d)
  53 {
  54         uint8_t key[256];
  55         int r, n;
  56
  57         /*
  58          * XXX read_random() returns unsafe numbers if the entropy
  59          * device is not loaded -- MarkM.
  60          */
  61         r = read_random(key, ARC4_KEYBYTES, 1);
  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                 d->arc4_j = (d->arc4_j + d->arc4_sbox[n] + key[n]) % 256;
  70                 arc4_swap(&d->arc4_sbox[n], &d->arc4_sbox[d->arc4_j]);
  71         }
  72
  73         /*
  74          * Discard early keystream, as per recommendations in:
  75          * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
  76          */
  77         for (n = 0; n < 768 * 4; n++)
  78                 arc4_randbyte(d);
  79
  80         /* Reset for next reseed cycle. */
  81         d->arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
  82         d->arc4_numruns = 0;
  83 }
  84
  85 /*
  86  * Generate a random byte.
  87  */
  88 static uint8_t
  89 arc4_randbyte(struct arc4_data *d)
  90 {
  91         uint8_t arc4_t;
  92
  93         d->arc4_i = (d->arc4_i + 1) % 256;
  94         d->arc4_j = (d->arc4_j + d->arc4_sbox[d->arc4_i]) % 256;
  95
  96         arc4_swap(&d->arc4_sbox[d->arc4_i], &d->arc4_sbox[d->arc4_j]);
  97
  98         arc4_t = (d->arc4_sbox[d->arc4_i] + d->arc4_sbox[d->arc4_j]) % 256;
  99         return d->arc4_sbox[arc4_t];
 100 }
 101
 102 uint32_t
 103 karc4random(void)
 104 {
 105         struct arc4_data *d = arc4_data_pcpu[mycpuid];
 106         uint32_t ret;
 107
 108         if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
 109             time_uptime > d->arc4_nextreseed)
 110                 arc4_randomstir(d);
 111
 112         ret = arc4_randbyte(d);
 113         ret |= arc4_randbyte(d) << 8;
 114         ret |= arc4_randbyte(d) << 16;
 115         ret |= arc4_randbyte(d) << 24;
 116
 117         return ret;
 118 }
 119
 120 uint64_t
 121 karc4random64(void)
 122 {
 123         struct arc4_data *d = arc4_data_pcpu[mycpuid];
 124         uint64_t ret;
 125
 126         if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
 127             time_uptime > d->arc4_nextreseed)
 128                 arc4_randomstir(d);
 129
 130         ret = arc4_randbyte(d);
 131         ret |= arc4_randbyte(d) << 8;
 132         ret |= arc4_randbyte(d) << 16;
 133         ret |= arc4_randbyte(d) << 24;
 134         ret |= (uint64_t)arc4_randbyte(d) << 32;
 135         ret |= (uint64_t)arc4_randbyte(d) << 40;
 136         ret |= (uint64_t)arc4_randbyte(d) << 48;
 137         ret |= (uint64_t)arc4_randbyte(d) << 56;
 138
 139         return ret;
 140 }
 141
 142 void
 143 karc4rand(void *ptr, size_t len)
 144 {
 145         struct arc4_data *d = arc4_data_pcpu[mycpuid];
 146         uint8_t *p = ptr;
 147
 148 #if 0
 149         /* No one call this function in ISR/ithread. */
 150         crit_enter();
 151 #endif
 152
 153         if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
 154             time_uptime > d->arc4_nextreseed)
 155                 arc4_randomstir(d);
 156
 157         while (len--)
 158                 *p++ = arc4_randbyte(d);
 159
 160 #if 0
 161         crit_exit();
 162 #endif
 163 }
 164
 165 /*
 166  * Initialize our S-box to its beginning defaults.
 167  */
 168 void
 169 arc4_init_pcpu(int cpuid)
 170 {
 171         struct arc4_data *d;
 172         int n;
 173
 174         KASSERT(arc4_data_pcpu[cpuid] == NULL,
 175             ("arc4 was initialized on cpu%d", cpuid));
 176
 177         d = (void *)kmem_alloc3(kernel_map, sizeof(*d), VM_SUBSYS_GD,
 178             KM_CPU(cpuid));
 179         memset(d, 0, sizeof(*d));
 180
 181         for (n = 0; n < 256; n++)
 182                 d->arc4_sbox[n] = (uint8_t)n;
 183
 184         arc4_randomstir(d);
 185
 186         /*
 187          * Discard early keystream, as per recommendations in:
 188          * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
 189          */
 190         for (n = 0; n < 768 * 4; n++)
 191                 arc4_randbyte(d);
 192
 193         arc4_data_pcpu[cpuid] = d;
 194 }