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
  65 static inline u_int8_t arc4_getbyte(struct arc4_stream *);
  66 static void arc4_stir(struct arc4_stream *);
  67
  68 static inline void
  69 arc4_init(as)
  70         struct arc4_stream *as;
  71 {
  72         int     n;
  73
  74         for (n = 0; n < 256; n++)
  75                 as->s[n] = n;
  76         as->i = 0;
  77         as->j = 0;
  78 }
  79
  80 static inline void
  81 arc4_addrandom(as, dat, datlen)
  82         struct arc4_stream *as;
  83         u_char *dat;
  84         int     datlen;
  85 {
  86         int     n;
  87         u_int8_t si;
  88
  89         as->i--;
  90         for (n = 0; n < 256; n++) {
  91                 as->i = (as->i + 1);
  92                 si = as->s[as->i];
  93                 as->j = (as->j + si + dat[n % datlen]);
  94                 as->s[as->i] = as->s[as->j];
  95                 as->s[as->j] = si;
  96         }
  97 }
  98
  99 static void
 100 arc4_stir(as)
 101         struct arc4_stream *as;
 102 {
 103         int     fd, n;
 104         struct {
 105                 struct timeval tv;
 106                 pid_t pid;
 107                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
 108         }       rdat;
 109
 110         gettimeofday(&rdat.tv, NULL);
 111         rdat.pid = getpid();
 112         fd = _open(RANDOMDEV, O_RDONLY, 0);
 113         if (fd >= 0) {
 114                 (void) _read(fd, rdat.rnd, sizeof(rdat.rnd));
 115                 _close(fd);
 116         }
 117         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
 118          * stack... */
 119
 120         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 121
 122         /*
 123          * Throw away the first N bytes of output, as suggested in the
 124          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 125          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 126          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 127          * by Ilya Mironov.
 128          */
 129         for (n = 0; n < 1024; n++)
 130                 arc4_getbyte(as);
 131 }
 132
 133 static inline u_int8_t
 134 arc4_getbyte(as)
 135         struct arc4_stream *as;
 136 {
 137         u_int8_t si, sj;
 138
 139         as->i = (as->i + 1);
 140         si = as->s[as->i];
 141         as->j = (as->j + si);
 142         sj = as->s[as->j];
 143         as->s[as->i] = sj;
 144         as->s[as->j] = si;
 145
 146         return (as->s[(si + sj) & 0xff]);
 147 }
 148
 149 static inline u_int32_t
 150 arc4_getword(as)
 151         struct arc4_stream *as;
 152 {
 153         u_int32_t val;
 154
 155         val = arc4_getbyte(as) << 24;
 156         val |= arc4_getbyte(as) << 16;
 157         val |= arc4_getbyte(as) << 8;
 158         val |= arc4_getbyte(as);
 159
 160         return (val);
 161 }
 162
 163 static void
 164 arc4_check_init(void)
 165 {
 166         if (!rs_initialized) {
 167                 arc4_init(&rs);
 168                 rs_initialized = 1;
 169         }
 170 }
 171
 172 static void
 173 arc4_check_stir(void)
 174 {
 175         if (!rs_stired) {
 176                 arc4_stir(&rs);
 177                 rs_stired = 1;
 178         }
 179 }
 180
 181 void
 182 arc4random_stir()
 183 {
 184         THREAD_LOCK();
 185         arc4_check_init();
 186         arc4_stir(&rs);
 187         THREAD_UNLOCK();
 188 }
 189
 190 void
 191 arc4random_addrandom(dat, datlen)
 192         u_char *dat;
 193         int     datlen;
 194 {
 195         THREAD_LOCK();
 196         arc4_check_init();
 197         arc4_check_stir();
 198         arc4_addrandom(&rs, dat, datlen);
 199         THREAD_UNLOCK();
 200 }
 201
 202 u_int32_t
 203 arc4random()
 204 {
 205         u_int32_t rnd;
 206
 207         THREAD_LOCK();
 208         arc4_check_init();
 209         arc4_check_stir();
 210         rnd = arc4_getword(&rs);
 211         THREAD_UNLOCK();
 212
 213         return (rnd);
 214 }
 215
 216 #if 0
 217 /*-------- Test code for i386 --------*/
 218 #include <stdio.h>
 219 #include <machine/pctr.h>
 220 int
 221 main(int argc, char **argv)
 222 {
 223         const int iter = 1000000;
 224         int     i;
 225         pctrval v;
 226
 227         v = rdtsc();
 228         for (i = 0; i < iter; i++)
 229                 arc4random();
 230         v = rdtsc() - v;
 231         v /= iter;
 232
 233         printf("%qd cycles\n", v);
 234 }
 235 #endif