gen/arc4random.c

   1 /* $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.4 2000/01/27 23:06:13 jasone Exp $ */
   2
   3 /*
   4  * Arc4 random number generator for OpenBSD.
   5  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
   6  *
   7  * Modification and redistribution in source and binary forms is
   8  * permitted provided that due credit is given to the author and the
   9  * OpenBSD project (for instance by leaving this copyright notice
  10  * intact).
  11  */
  12
  13 /*
  14  * This code is derived from section 17.1 of Applied Cryptography,
  15  * second edition, which describes a stream cipher allegedly
  16  * compatible with RSA Labs "RC4" cipher (the actual description of
  17  * which is a trade secret).  The same algorithm is used as a stream
  18  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  19  *
  20  * Here the stream cipher has been modified always to include the time
  21  * when initializing the state.  That makes it impossible to
  22  * regenerate the same random sequence twice, so this can't be used
  23  * for encryption, but will generate good random numbers.
  24  *
  25  * RC4 is a registered trademark of RSA Laboratories.
  26  */
  27
  28 #include <stdlib.h>
  29 #include <fcntl.h>
  30 #include <unistd.h>
  31 #include <sys/types.h>
  32 #include <sys/time.h>
  33
  34 struct arc4_stream {
  35         u_int8_t i;
  36         u_int8_t j;
  37         u_int8_t s[256];
  38 };
  39
  40 static int rs_initialized;
  41 static struct arc4_stream *rs = NULL;
  42
  43 static inline void
  44 arc4_init(as)
  45         struct arc4_stream *as;
  46 {
  47         int     n;
  48
  49         for (n = 0; n < 256; n++)
  50                 as->s[n] = n;
  51         as->i = 0;
  52         as->j = 0;
  53 }
  54
  55 static inline void
  56 arc4_addrandom(as, dat, datlen)
  57         struct arc4_stream *as;
  58         u_char *dat;
  59         int     datlen;
  60 {
  61         int     n;
  62         u_int8_t si;
  63
  64         as->i--;
  65         for (n = 0; n < 256; n++) {
  66                 as->i = (as->i + 1);
  67                 si = as->s[as->i];
  68                 as->j = (as->j + si + dat[n % datlen]);
  69                 as->s[as->i] = as->s[as->j];
  70                 as->s[as->j] = si;
  71         }
  72 }
  73
  74 static void
  75 arc4_stir(as)
  76         struct arc4_stream *as;
  77 {
  78         int     fd;
  79         struct {
  80                 struct timeval tv;
  81                 pid_t pid;
  82                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
  83         }       rdat;
  84
  85         gettimeofday(&rdat.tv, NULL);
  86         rdat.pid = getpid();
  87         fd = open("/dev/urandom", O_RDONLY, 0);
  88         if (fd >= 0) {
  89                 (void) read(fd, rdat.rnd, sizeof(rdat.rnd));
  90                 close(fd);
  91         }
  92         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
  93          * stack... */
  94
  95         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
  96 }
  97
  98 static inline u_int8_t
  99 arc4_getbyte(as)
 100         struct arc4_stream *as;
 101 {
 102         u_int8_t si, sj;
 103
 104         as->i = (as->i + 1);
 105         si = as->s[as->i];
 106         as->j = (as->j + si);
 107         sj = as->s[as->j];
 108         as->s[as->i] = sj;
 109         as->s[as->j] = si;
 110         return (as->s[(si + sj) & 0xff]);
 111 }
 112
 113 static inline u_int32_t
 114 arc4_getword(as)
 115         struct arc4_stream *as;
 116 {
 117         u_int32_t val;
 118         val = arc4_getbyte(as) << 24;
 119         val |= arc4_getbyte(as) << 16;
 120         val |= arc4_getbyte(as) << 8;
 121         val |= arc4_getbyte(as);
 122         return val;
 123 }
 124
 125 void
 126 arc4random_stir()
 127 {
 128         if ( rs == NULL ) {
 129                 rs = malloc( sizeof(struct arc4_stream) );
 130                 if( rs == NULL )
 131                         return ; /* Hmmm. */
 132         }
 133         if (!rs_initialized) {
 134                 arc4_init(rs);
 135                 rs_initialized = 1;
 136         }
 137         arc4_stir(rs);
 138 }
 139
 140 void
 141 arc4random_addrandom(dat, datlen)
 142         u_char *dat;
 143         int     datlen;
 144 {
 145         if (!rs_initialized)
 146                 arc4random_stir();
 147         arc4_addrandom(rs, dat, datlen);
 148 }
 149
 150 u_int32_t
 151 arc4random()
 152 {
 153         if (!rs_initialized)
 154                 arc4random_stir();
 155         return arc4_getword(rs);
 156 }
 157
 158 #if 0
 159 /*-------- Test code for i386 --------*/
 160 #include <stdio.h>
 161 #include <machine/pctr.h>
 162 int
 163 main(int argc, char **argv)
 164 {
 165         const int iter = 1000000;
 166         int     i;
 167         pctrval v;
 168
 169         v = rdtsc();
 170         for (i = 0; i < iter; i++)
 171                 arc4random();
 172         v = rdtsc() - v;
 173         v /= iter;
 174
 175         printf("%qd cycles\n", v);
 176 }
 177 #endif