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