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 /* $DragonFly: src/lib/libc/gen/arc4random.c,v 1.5 2005/01/31 22:29:15 dillon 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 "namespace.h"
  30 #include <stdlib.h>
  31 #include <fcntl.h>
  32 #include <unistd.h>
  33 #include <sys/types.h>
  34 #include <sys/time.h>
  35 #include "un-namespace.h"
  36
  37 struct arc4_stream {
  38         u_int8_t i;
  39         u_int8_t j;
  40         u_int8_t s[256];
  41 };
  42
  43 static int rs_initialized;
  44 static struct arc4_stream rs;
  45
  46 static inline u_int8_t  arc4_getbyte(struct arc4_stream *);
  47
  48 static inline void
  49 arc4_init(as)
  50         struct arc4_stream *as;
  51 {
  52         int     n;
  53
  54         for (n = 0; n < 256; n++)
  55                 as->s[n] = n;
  56         as->i = 0;
  57         as->j = 0;
  58 }
  59
  60 static inline void
  61 arc4_addrandom(as, dat, datlen)
  62         struct arc4_stream *as;
  63         u_char *dat;
  64         int     datlen;
  65 {
  66         int     n;
  67         u_int8_t si;
  68
  69         as->i--;
  70         for (n = 0; n < 256; n++) {
  71                 as->i = (as->i + 1);
  72                 si = as->s[as->i];
  73                 as->j = (as->j + si + dat[n % datlen]);
  74                 as->s[as->i] = as->s[as->j];
  75                 as->s[as->j] = si;
  76         }
  77 }
  78
  79 static void
  80 arc4_stir(as)
  81         struct arc4_stream *as;
  82 {
  83         int     fd, n;
  84         struct {
  85                 struct timeval tv;
  86                 pid_t pid;
  87                 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
  88         }       rdat;
  89
  90         gettimeofday(&rdat.tv, NULL);
  91         rdat.pid = getpid();
  92         fd = _open("/dev/urandom", O_RDONLY, 0);
  93         if (fd >= 0) {
  94                 (void) _read(fd, rdat.rnd, sizeof(rdat.rnd));
  95                 _close(fd);
  96         }
  97         /* fd < 0?  Ah, what the heck. We'll just take whatever was on the
  98          * stack... */
  99
 100         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 101
 102         /*
 103          * Throw away the first N bytes of output, as suggested in the
 104          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 105          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 106          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 107          * by Ilya Mironov.
 108          */
 109         for (n = 0; n < 1024; n++)
 110                 arc4_getbyte(as);
 111 }
 112
 113 static inline u_int8_t
 114 arc4_getbyte(struct arc4_stream *as)
 115 {
 116         u_int8_t si, sj;
 117
 118         as->i = (as->i + 1);
 119         si = as->s[as->i];
 120         as->j = (as->j + si);
 121         sj = as->s[as->j];
 122         as->s[as->i] = sj;
 123         as->s[as->j] = si;
 124         return (as->s[(si + sj) & 0xff]);
 125 }
 126
 127 static inline u_int32_t
 128 arc4_getword(as)
 129         struct arc4_stream *as;
 130 {
 131         u_int32_t val;
 132         val = arc4_getbyte(as) << 24;
 133         val |= arc4_getbyte(as) << 16;
 134         val |= arc4_getbyte(as) << 8;
 135         val |= arc4_getbyte(as);
 136         return val;
 137 }
 138
 139 void
 140 arc4random_stir()
 141 {
 142         if (!rs_initialized) {
 143                 arc4_init(&rs);
 144                 rs_initialized = 1;
 145         }
 146         arc4_stir(&rs);
 147 }
 148
 149 void
 150 arc4random_addrandom(dat, datlen)
 151         u_char *dat;
 152         int     datlen;
 153 {
 154         if (!rs_initialized)
 155                 arc4random_stir();
 156         arc4_addrandom(&rs, dat, datlen);
 157 }
 158
 159 u_int32_t
 160 arc4random()
 161 {
 162         if (!rs_initialized)
 163                 arc4random_stir();
 164         return arc4_getword(&rs);
 165 }
 166
 167 #if 0
 168 /*-------- Test code for i386 --------*/
 169 #include <stdio.h>
 170 #include <machine/pctr.h>
 171 int
 172 main(int argc, char **argv)
 173 {
 174         const int iter = 1000000;
 175         int     i;
 176         pctrval v;
 177
 178         v = rdtsc();
 179         for (i = 0; i < iter; i++)
 180                 arc4random();
 181         v = rdtsc() - v;
 182         v /= iter;
 183
 184         printf("%qd cycles\n", v);
 185 }
 186 #endif