lib/libcr/gen/arc4random.c

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