libc/stdlib/arc4random.c

   1 /*
   2  * Copyright (c) 1996, David Mazieres <dm@uun.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /*
  18  * Arc4 random number generator for OpenBSD.
  19  *
  20  * This code is derived from section 17.1 of Applied Cryptography,
  21  * second edition, which describes a stream cipher allegedly
  22  * compatible with RSA Labs "RC4" cipher (the actual description of
  23  * which is a trade secret).  The same algorithm is used as a stream
  24  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  25  *
  26  * Here the stream cipher has been modified always to include entropy
  27  * when initializing the state.  That makes it impossible to
  28  * regenerate the same random sequence twice, so this can't be used
  29  * for encryption, but will generate good random numbers.
  30  *
  31  * RC4 is a registered trademark of RSA Laboratories.
  32  */
  33
  34 /*      $OpenBSD: arc4random.c,v 1.16 2007/02/12 19:58:47 otto Exp $    */
  35
  36 #include <features.h>
  37
  38 #include <fcntl.h>
  39 #include <stdlib.h>
  40 #include <unistd.h>
  41 #include <sys/types.h>
  42 #include <sys/time.h>
  43
  44 struct arc4_stream {
  45         u_int8_t i;
  46         u_int8_t j;
  47         u_int8_t s[256];
  48 };
  49
  50 static smallint rs_initialized;
  51 static struct arc4_stream rs;
  52 static pid_t arc4_stir_pid;
  53 static int arc4_count;
  54
  55 static __inline__ void
  56 arc4_init(struct arc4_stream *as)
  57 {
  58         int     n;
  59
  60         for (n = 0; n < 256; n++)
  61                 as->s[n] = n;
  62         as->i = 0;
  63         as->j = 0;
  64 }
  65
  66 static __inline__ u_int8_t
  67 arc4_getbyte(struct arc4_stream *as)
  68 {
  69         u_int8_t si, sj;
  70
  71         as->i = (as->i + 1);
  72         si = as->s[as->i];
  73         as->j = (as->j + si);
  74         sj = as->s[as->j];
  75         as->s[as->i] = sj;
  76         as->s[as->j] = si;
  77         return (as->s[(si + sj) & 0xff]);
  78 }
  79
  80 static __inline__ void
  81 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen)
  82 {
  83         int     n;
  84         u_int8_t si;
  85
  86         as->i--;
  87         for (n = 0; n < 256; n++) {
  88                 as->i = (as->i + 1);
  89                 si = as->s[as->i];
  90                 as->j = (as->j + si + dat[n % datlen]);
  91                 as->s[as->i] = as->s[as->j];
  92                 as->s[as->j] = si;
  93         }
  94         as->j = as->i;
  95 }
  96
  97 static void
  98 arc4_stir(struct arc4_stream *as)
  99 {
 100         int     n;
 101         u_char  rnd[128];
 102         struct timeval tv;
 103
 104 #ifndef __ARC4RANDOM_USES_NODEV__
 105         int     fd;
 106
 107         fd = open("/dev/urandom", O_RDONLY);
 108         if (fd != -1) {
 109                 read(fd, rnd, sizeof(rnd));
 110                 close(fd);
 111         }
 112         /* Did the pseudo-random device fail? Use gettimeofday(). */
 113         else
 114 #endif
 115         if (gettimeofday(&tv, NULL) != (-1)) {
 116
 117                 /* Initialize the first element so it's hopefully not '0',
 118                  * to help out the next loop. Tossing in some prime numbers
 119                  * probably can't hurt. */
 120                 rnd[0] = (tv.tv_sec % 10000) * 3 + tv.tv_usec * 7 + \
 121                         (getpid() % 1000) * 13;
 122
 123                 for (n = 1; n < 127 ; n++) {
 124
 125                 /* Take advantage of the stack space. Only initialize
 126                  * elements equal to '0'. This will make the rnd[]
 127                  * array much less vulnerable to timing attacks. Here
 128                  * we'll stir getpid() into the value of the previous
 129                  * element. Approximately 1 in 128 elements will still
 130                  * become '0'. */
 131
 132                         if (rnd[n] == 0) {
 133                                 rnd[n] = ((rnd[n - 1] + n) ^ \
 134                                         ((getpid() % 1000) * 17));
 135                         }
 136                 }
 137         }
 138         else {
 139         /* gettimeofday() failed? Do the same thing as above, but only
 140          * with getpid(). */
 141
 142                 rnd[0] = (getpid() % 1000) * 19;
 143                 for (n = 1; n < 127 ; n++) {
 144                         if (rnd[n] == 0) {
 145                                 rnd[n] = ((rnd[n - 1] + n) ^ \
 146                                         ((getpid() % 1000) * 23));
 147                         }
 148                 }
 149         }
 150
 151         arc4_stir_pid = getpid();
 152         arc4_addrandom(as, rnd, sizeof(rnd));
 153
 154         /*
 155          * Discard early keystream, as per recommendations.
 156          * Network Operations Division Cryptographic requirements
 157          * published on wikileaks on march 2017
 158          */
 159         for (n = 0; n < 3072; n++)
 160                 (void)arc4_getbyte(as);
 161         arc4_count = 1600000;
 162 }
 163
 164 #if 0
 165 static void __arc4random_stir(void);
 166 /*
 167  * __arc4_getbyte() is a libc private function intended for use
 168  * with malloc.
 169  */
 170 u_int8_t
 171 __arc4_getbyte(void)
 172 {
 173         if (--arc4_count == 0 || !rs_initialized)
 174                 __arc4random_stir();
 175         return arc4_getbyte(&rs);
 176 }
 177 #endif
 178
 179 static __inline__ u_int32_t
 180 arc4_getword(struct arc4_stream *as)
 181 {
 182         u_int32_t val;
 183         val = arc4_getbyte(as) << 24;
 184         val |= arc4_getbyte(as) << 16;
 185         val |= arc4_getbyte(as) << 8;
 186         val |= arc4_getbyte(as);
 187         return val;
 188 }
 189
 190 static void
 191 __arc4random_stir(void)
 192 {
 193         if (!rs_initialized) {
 194                 arc4_init(&rs);
 195                 rs_initialized = 1;
 196         }
 197         arc4_stir(&rs);
 198 }
 199 strong_alias(__arc4random_stir,arc4random_stir)
 200
 201 void
 202 arc4random_addrandom(u_char *dat, int datlen)
 203 {
 204         if (!rs_initialized)
 205                 __arc4random_stir();
 206         arc4_addrandom(&rs, dat, datlen);
 207 }
 208
 209 u_int32_t
 210 arc4random(void)
 211 {
 212         arc4_count -= 4;
 213         if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid())
 214                 __arc4random_stir();
 215         return arc4_getword(&rs);
 216 }