lib/libc/gen/arc4random.c

   1 /*
   2  * Arc4 random number generator for OpenBSD.
   3  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
   4  *
   5  * Modification and redistribution in source and binary forms is
   6  * permitted provided that due credit is given to the author and the
   7  * OpenBSD project (for instance by leaving this copyright notice
   8  * intact).
   9  */
  10
  11 /*
  12  * This code is derived from section 17.1 of Applied Cryptography,
  13  * second edition, which describes a stream cipher allegedly
  14  * compatible with RSA Labs "RC4" cipher (the actual description of
  15  * which is a trade secret).  The same algorithm is used as a stream
  16  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  17  *
  18  * Here the stream cipher has been modified always to include the time
  19  * when initializing the state.  That makes it impossible to
  20  * regenerate the same random sequence twice, so this can't be used
  21  * for encryption, but will generate good random numbers.
  22  *
  23  * RC4 is a registered trademark of RSA Laboratories.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD$");
  28
  29 #include "namespace.h"
  30 #include <sys/types.h>
  31 #include <sys/time.h>
  32 #include <stdlib.h>
  33 #include <fcntl.h>
  34 #include <unistd.h>
  35 #include <pthread.h>
  36
  37 #include "libc_private.h"
  38 #include "un-namespace.h"
  39
  40 struct arc4_stream {
  41         u_int8_t i;
  42         u_int8_t j;
  43         u_int8_t s[256];
  44 };
  45
  46 static pthread_mutex_t  arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
  47
  48 #define RANDOMDEV       "/dev/urandom"
  49 #define THREAD_LOCK()                                           \
  50         do {                                                    \
  51                 if (__isthreaded)                               \
  52                         _pthread_mutex_lock(&arc4random_mtx);   \
  53         } while (0)
  54
  55 #define THREAD_UNLOCK()                                         \
  56         do {                                                    \
  57                 if (__isthreaded)                               \
  58                         _pthread_mutex_unlock(&arc4random_mtx); \
  59         } while (0)
  60
  61 static struct arc4_stream rs;
  62 static int rs_initialized;
  63 static int rs_stired;
  64 static int arc4_count;
  65
  66 static inline u_int8_t arc4_getbyte(struct arc4_stream *);
  67 static void arc4_stir(struct arc4_stream *);
  68
  69 static inline void
  70 arc4_init(as)
  71         struct arc4_stream *as;
  72 {
  73         int     n;
  74
  75         for (n = 0; n < 256; n++)
  76                 as->s[n] = n;
  77         as->i = 0;
  78         as->j = 0;
  79 }
  80
  81 static inline void
  82 arc4_addrandom(as, dat, datlen)
  83         struct arc4_stream *as;
  84         u_char *dat;
  85         int     datlen;
  86 {
  87         int     n;
  88         u_int8_t si;
  89
  90         as->i--;
  91         for (n = 0; n < 256; n++) {
  92                 as->i = (as->i + 1);
  93                 si = as->s[as->i];
  94                 as->j = (as->j + si + dat[n % datlen]);
  95                 as->s[as->i] = as->s[as->j];
  96                 as->s[as->j] = si;
  97         }
  98 }
  99
 100 static void
 101 arc4_stir(as)
 102         struct arc4_stream *as;
 103 {
 104         int     fd, n;
 105         struct {
 106                 struct timeval tv;
 107                 pid_t pid;
 108                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
 109         }       rdat;
 110
 111         gettimeofday(&rdat.tv, NULL);
 112         rdat.pid = getpid();
 113         fd = _open(RANDOMDEV, O_RDONLY, 0);
 114         if (fd >= 0) {
 115                 (void) _read(fd, rdat.rnd, sizeof(rdat.rnd));
 116                 _close(fd);
 117         }
 118         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
 119          * stack... */
 120
 121         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 122
 123         /*
 124          * Throw away the first N bytes of output, as suggested in the
 125          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 126          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 127          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 128          * by Ilya Mironov.
 129          */
 130         for (n = 0; n < 1024; n++)
 131                 (void) arc4_getbyte(as);
 132         arc4_count = 400000;
 133 }
 134
 135 static inline u_int8_t
 136 arc4_getbyte(as)
 137         struct arc4_stream *as;
 138 {
 139         u_int8_t si, sj;
 140
 141         as->i = (as->i + 1);
 142         si = as->s[as->i];
 143         as->j = (as->j + si);
 144         sj = as->s[as->j];
 145         as->s[as->i] = sj;
 146         as->s[as->j] = si;
 147
 148         return (as->s[(si + sj) & 0xff]);
 149 }
 150
 151 static inline u_int32_t
 152 arc4_getword(as)
 153         struct arc4_stream *as;
 154 {
 155         u_int32_t val;
 156
 157         val = arc4_getbyte(as) << 24;
 158         val |= arc4_getbyte(as) << 16;
 159         val |= arc4_getbyte(as) << 8;
 160         val |= arc4_getbyte(as);
 161
 162         return (val);
 163 }
 164
 165 static void
 166 arc4_check_init(void)
 167 {
 168         if (!rs_initialized) {
 169                 arc4_init(&rs);
 170                 rs_initialized = 1;
 171         }
 172 }
 173
 174 static void
 175 arc4_check_stir(void)
 176 {
 177         if (!rs_stired || --arc4_count == 0) {
 178                 arc4_stir(&rs);
 179                 rs_stired = 1;
 180         }
 181 }
 182
 183 void
 184 arc4random_stir()
 185 {
 186         THREAD_LOCK();
 187         arc4_check_init();
 188         arc4_stir(&rs);
 189         THREAD_UNLOCK();
 190 }
 191
 192 void
 193 arc4random_addrandom(dat, datlen)
 194         u_char *dat;
 195         int     datlen;
 196 {
 197         THREAD_LOCK();
 198         arc4_check_init();
 199         arc4_check_stir();
 200         arc4_addrandom(&rs, dat, datlen);
 201         THREAD_UNLOCK();
 202 }
 203
 204 u_int32_t
 205 arc4random()
 206 {
 207         u_int32_t rnd;
 208
 209         THREAD_LOCK();
 210         arc4_check_init();
 211         arc4_check_stir();
 212         rnd = arc4_getword(&rs);
 213         THREAD_UNLOCK();
 214
 215         return (rnd);
 216 }
 217
 218 #if 0
 219 /*-------- Test code for i386 --------*/
 220 #include <stdio.h>
 221 #include <machine/pctr.h>
 222 int
 223 main(int argc, char **argv)
 224 {
 225         const int iter = 1000000;
 226         int     i;
 227         pctrval v;
 228
 229         v = rdtsc();
 230         for (i = 0; i < iter; i++)
 231                 arc4random();
 232         v = rdtsc() - v;
 233         v /= iter;
 234
 235         printf("%qd cycles\n", v);
 236 }
 237 #endif