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_unlimited(key, ARC4_KEYBYTES);
  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 0
 109         /* No one call this function in ISR/ithread. */
 110         crit_enter();
 111 #endif
 112
 113         if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
 114             time_uptime > d->arc4_nextreseed)
 115                 arc4_randomstir(d);
 116
 117         ret = arc4_randbyte(d);
 118         ret |= arc4_randbyte(d) << 8;
 119         ret |= arc4_randbyte(d) << 16;
 120         ret |= arc4_randbyte(d) << 24;
 121
 122 #if 0
 123         crit_exit();
 124 #endif
 125
 126         return ret;
 127 }
 128
 129 void
 130 karc4rand(void *ptr, size_t len)
 131 {
 132         struct arc4_data *d = arc4_data_pcpu[mycpuid];
 133         uint8_t *p = ptr;
 134
 135 #if 0
 136         /* No one call this function in ISR/ithread. */
 137         crit_enter();
 138 #endif
 139
 140         if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
 141             time_uptime > d->arc4_nextreseed)
 142                 arc4_randomstir(d);
 143
 144         while (len--)
 145                 *p++ = arc4_randbyte(d);
 146
 147 #if 0
 148         crit_exit();
 149 #endif
 150 }
 151
 152 /*
 153  * Initialize our S-box to its beginning defaults.
 154  */
 155 void
 156 arc4_init_pcpu(int cpuid)
 157 {
 158         struct arc4_data *d;
 159         int n;
 160
 161         KASSERT(arc4_data_pcpu[cpuid] == NULL,
 162             ("arc4 was initialized on cpu%d", cpuid));
 163
 164         d = (void *)kmem_alloc3(&kernel_map, sizeof(*d), VM_SUBSYS_GD,
 165             KM_CPU(cpuid));
 166         memset(d, 0, sizeof(*d));
 167
 168         for (n = 0; n < 256; n++)
 169                 d->arc4_sbox[n] = (uint8_t)n;
 170
 171         arc4_randomstir(d);
 172
 173         /*
 174          * Discard early keystream, as per recommendations in:
 175          * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
 176          */
 177         for (n = 0; n < 768 * 4; n++)
 178                 arc4_randbyte(d);
 179
 180         arc4_data_pcpu[cpuid] = d;
 181 }