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