lib/libc/gen/arc4random.c

   1 /*      $NetBSD: arc4random.c,v 1.8 2005/06/12 05:21:27 lukem Exp $     */
   2 /*      $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev 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 by leaving this copyright notice 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 <sys/cdefs.h>
  29 #if defined(LIBC_SCCS) && !defined(lint)
  30 __RCSID("$NetBSD: arc4random.c,v 1.8 2005/06/12 05:21:27 lukem Exp $");
  31 #endif /* LIBC_SCCS and not lint */
  32
  33 #include "namespace.h"
  34 #include <fcntl.h>
  35 #include <stdlib.h>
  36 #include <unistd.h>
  37 #include <sys/types.h>
  38 #include <sys/param.h>
  39 #include <sys/time.h>
  40 #include <sys/sysctl.h>
  41
  42 #ifdef __weak_alias
  43 __weak_alias(arc4random,_arc4random)
  44 #endif
  45
  46 struct arc4_stream {
  47         u_int8_t i;
  48         u_int8_t j;
  49         u_int8_t s[256];
  50 };
  51
  52 static int rs_initialized;
  53 static struct arc4_stream rs;
  54
  55 static inline void arc4_init(struct arc4_stream *);
  56 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int);
  57 static void arc4_stir(struct arc4_stream *);
  58 static inline u_int8_t arc4_getbyte(struct arc4_stream *);
  59 static inline u_int32_t arc4_getword(struct arc4_stream *);
  60
  61 static inline void
  62 arc4_init(as)
  63         struct arc4_stream *as;
  64 {
  65         int     n;
  66
  67         for (n = 0; n < 256; n++)
  68                 as->s[n] = n;
  69         as->i = 0;
  70         as->j = 0;
  71 }
  72
  73 static inline void
  74 arc4_addrandom(as, dat, datlen)
  75         struct arc4_stream *as;
  76         u_char *dat;
  77         int     datlen;
  78 {
  79         int     n;
  80         u_int8_t si;
  81
  82         as->i--;
  83         for (n = 0; n < 256; n++) {
  84                 as->i = (as->i + 1);
  85                 si = as->s[as->i];
  86                 as->j = (as->j + si + dat[n % datlen]);
  87                 as->s[as->i] = as->s[as->j];
  88                 as->s[as->j] = si;
  89         }
  90         as->j = as->i;
  91 }
  92
  93 static void
  94 arc4_stir(as)
  95         struct arc4_stream *as;
  96 {
  97         int     fd;
  98         struct {
  99                 struct timeval tv;
 100                 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)];
 101         }       rdat;
 102         int     n;
 103
 104         gettimeofday(&rdat.tv, NULL);
 105         fd = open("/dev/urandom", O_RDONLY);
 106         if (fd != -1) {
 107                 read(fd, rdat.rnd, sizeof(rdat.rnd));
 108                 close(fd);
 109         }
 110 #ifdef KERN_URND
 111         else {
 112                 int mib[2];
 113                 u_int i;
 114                 size_t len;
 115
 116                 /* Device could not be opened, we might be chrooted, take
 117                  * randomness from sysctl. */
 118
 119                 mib[0] = CTL_KERN;
 120                 mib[1] = KERN_URND;
 121
 122                 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i++) {
 123                         len = sizeof(u_int);
 124                         if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1)
 125                                 break;
 126                 }
 127         }
 128 #endif
 129         /* fd < 0 or failed sysctl ?  Ah, what the heck. We'll just take
 130          * whatever was on the stack... */
 131
 132         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 133
 134         /*
 135          * Throw away the first N words of output, as suggested in the
 136          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 137          * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
 138          */
 139         for (n = 0; n < 256 * 4; n++)
 140                 arc4_getbyte(as);
 141 }
 142
 143 static inline u_int8_t
 144 arc4_getbyte(as)
 145         struct arc4_stream *as;
 146 {
 147         u_int8_t si, sj;
 148
 149         as->i = (as->i + 1);
 150         si = as->s[as->i];
 151         as->j = (as->j + si);
 152         sj = as->s[as->j];
 153         as->s[as->i] = sj;
 154         as->s[as->j] = si;
 155         return (as->s[(si + sj) & 0xff]);
 156 }
 157
 158 static inline u_int32_t
 159 arc4_getword(as)
 160         struct arc4_stream *as;
 161 {
 162         u_int32_t val;
 163         val = arc4_getbyte(as) << 24;
 164         val |= arc4_getbyte(as) << 16;
 165         val |= arc4_getbyte(as) << 8;
 166         val |= arc4_getbyte(as);
 167         return val;
 168 }
 169
 170 void
 171 arc4random_stir()
 172 {
 173         if (!rs_initialized) {
 174                 arc4_init(&rs);
 175                 rs_initialized = 1;
 176         }
 177         arc4_stir(&rs);
 178 }
 179
 180 void
 181 arc4random_addrandom(dat, datlen)
 182         u_char *dat;
 183         int     datlen;
 184 {
 185         if (!rs_initialized)
 186                 arc4random_stir();
 187         arc4_addrandom(&rs, dat, datlen);
 188 }
 189
 190 u_int32_t
 191 arc4random()
 192 {
 193         if (!rs_initialized)
 194                 arc4random_stir();
 195         return arc4_getword(&rs);
 196 }
 197
 198 #if 0
 199 /*-------- Test code for i386 --------*/
 200 #include <stdio.h>
 201 #include <machine/pctr.h>
 202 int
 203 main(int argc, char **argv)
 204 {
 205         const int iter = 1000000;
 206         int     i;
 207         pctrval v;
 208
 209         v = rdtsc();
 210         for (i = 0; i < iter; i++)
 211                 arc4random();
 212         v = rdtsc() - v;
 213         v /= iter;
 214
 215         printf("%qd cycles\n", v);
 216 }
 217 #endif