libc/stdlib/arc4random.c

   1 /*      $$$: arc4random.c 2005/02/08 robert */
   2 /*      $NetBSD: arc4random.c,v 1.5.2.1 2004/03/26 22:52:50 jmc Exp $   */
   3 /*      $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */
   4
   5 /*
   6  * Arc4 random number generator for OpenBSD.
   7  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
   8  *
   9  * Modification and redistribution in source and binary forms is
  10  * permitted provided that due credit is given to the author and the
  11  * OpenBSD project by leaving this copyright notice 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 <features.h>
  30 #include <fcntl.h>
  31 #include <stdlib.h>
  32 #include <unistd.h>
  33 #include <sys/types.h>
  34 #include <sys/param.h>
  35 #include <sys/time.h>
  36 #ifdef __ARC4RANDOM_USE_ERANDOM__
  37 #include <sys/sysctl.h>
  38 #endif
  39
  40
  41 struct arc4_stream {
  42         uint8_t i;
  43         uint8_t j;
  44         uint8_t s[256];
  45 };
  46
  47 static int    rs_initialized;
  48 static struct arc4_stream rs;
  49
  50 static __inline__ void arc4_init(struct arc4_stream *);
  51 static __inline__ void arc4_addrandom(struct arc4_stream *, u_char *, int);
  52 static void arc4_stir(struct arc4_stream *);
  53 static __inline__ uint8_t arc4_getbyte(struct arc4_stream *);
  54 static __inline__ uint32_t arc4_getword(struct arc4_stream *);
  55
  56 static __inline__ void
  57 arc4_init(as)
  58         struct arc4_stream *as;
  59 {
  60         int     n;
  61
  62         for (n = 0; n < 256; n++)
  63                 as->s[n] = n;
  64         as->i = 0;
  65         as->j = 0;
  66 }
  67
  68 static __inline__ void
  69 arc4_addrandom(as, dat, datlen)
  70         struct arc4_stream *as;
  71         u_char *dat;
  72         int     datlen;
  73 {
  74         int     n;
  75         uint8_t si;
  76
  77         as->i--;
  78         for (n = 0; n < 256; n++) {
  79                 as->i = (as->i + 1);
  80                 si = as->s[as->i];
  81                 as->j = (as->j + si + dat[n % datlen]);
  82                 as->s[as->i] = as->s[as->j];
  83                 as->s[as->j] = si;
  84         }
  85         as->j = as->i;
  86 }
  87
  88 static void
  89 arc4_stir(as)
  90         struct arc4_stream *as;
  91 {
  92         int     fd;
  93         struct {
  94                 struct timeval tv;
  95                 uint rnd[(128 - sizeof(struct timeval)) / sizeof(uint)];
  96         }       rdat;
  97         int     n;
  98
  99         gettimeofday(&rdat.tv, NULL);
 100         fd = open("/dev/urandom", O_RDONLY);
 101         if (fd != -1) {
 102                 read(fd, rdat.rnd, sizeof(rdat.rnd));
 103                 close(fd);
 104         }
 105 #ifdef __ARC4RANDOM_USE_ERANDOM__
 106         else {
 107                 int mib[3];
 108                 uint i;
 109                 size_t len;
 110
 111                 /* Device could not be opened, we might be chrooted, take
 112                  * randomness from sysctl. */
 113
 114                 mib[0] = CTL_KERN;
 115                 mib[1] = KERN_RANDOM;
 116                 mib[2] = RANDOM_ERANDOM;
 117
 118                 for (i = 0; i < sizeof(rdat.rnd) / sizeof(uint); i++) {
 119                         len = sizeof(uint);
 120                         if (sysctl(mib, 3, &rdat.rnd[i], &len, NULL, 0) == -1)
 121                                 break;
 122                 }
 123         }
 124 #endif
 125
 126         arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
 127
 128         /*
 129          * Throw away the first N words of output, as suggested in the
 130          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 131          * by Fluher, Mantin, and Shamir.
 132          * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
 133          * N = 256 in our case.
 134          */
 135         for (n = 0; n < 256 * 4; n++)
 136                 arc4_getbyte(as);
 137 }
 138
 139 static __inline__ uint8_t
 140 arc4_getbyte(as)
 141         struct arc4_stream *as;
 142 {
 143         uint8_t si, sj;
 144
 145         as->i = (as->i + 1);
 146         si = as->s[as->i];
 147         as->j = (as->j + si);
 148         sj = as->s[as->j];
 149         as->s[as->i] = sj;
 150         as->s[as->j] = si;
 151         return (as->s[(si + sj) & 0xff]);
 152 }
 153
 154 static __inline__ uint32_t
 155 arc4_getword(as)
 156         struct arc4_stream *as;
 157 {
 158         uint32_t val;
 159         val = arc4_getbyte(as) << 24;
 160         val |= arc4_getbyte(as) << 16;
 161         val |= arc4_getbyte(as) << 8;
 162         val |= arc4_getbyte(as);
 163         return val;
 164 }
 165
 166 void
 167 arc4random_stir(void)
 168 {
 169         if (!rs_initialized) {
 170                 arc4_init(&rs);
 171                 rs_initialized = 1;
 172         }
 173         arc4_stir(&rs);
 174 }
 175 libc_hidden_def(arc4random_stir)
 176
 177 void
 178 arc4random_addrandom(u_char *dat, int datlen)
 179 {
 180         if (!rs_initialized)
 181                 arc4random_stir();
 182         arc4_addrandom(&rs, dat, datlen);
 183 }
 184
 185 uint32_t
 186 arc4random(void)
 187 {
 188         if (!rs_initialized)
 189                 arc4random_stir();
 190         return arc4_getword(&rs);
 191 }
 192
 193 #if 0
 194 /*-------- Test code --------*/
 195 #include <stdlib.h>
 196 #include <stdio.h>
 197
 198 int main(void) {
 199     int random_number;
 200     random_number = arc4random() % 65536;
 201     printf("%d\n", random_number);
 202     return 0;
 203 }
 204 #endif