lib/libc/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;
  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_initialized) {
 129                 arc4_init(&rs);
 130                 rs_initialized = 1;
 131         }
 132         arc4_stir(&rs);
 133 }
 134
 135 void
 136 arc4random_addrandom(dat, datlen)
 137         u_char *dat;
 138         int     datlen;
 139 {
 140         if (!rs_initialized)
 141                 arc4random_stir();
 142         arc4_addrandom(&rs, dat, datlen);
 143 }
 144
 145 u_int32_t
 146 arc4random()
 147 {
 148         if (!rs_initialized)
 149                 arc4random_stir();
 150         return arc4_getword(&rs);
 151 }
 152
 153 #if 0
 154 /*-------- Test code for i386 --------*/
 155 #include <stdio.h>
 156 #include <machine/pctr.h>
 157 int
 158 main(int argc, char **argv)
 159 {
 160         const int iter = 1000000;
 161         int     i;
 162         pctrval v;
 163
 164         v = rdtsc();
 165         for (i = 0; i < iter; i++)
 166                 arc4random();
 167         v = rdtsc() - v;
 168         v /= iter;
 169
 170         printf("%qd cycles\n", v);
 171 }
 172 #endif