lib/libc/gen/arc4random.c

   1 /*
   2  * Copyright (c) 1996, David Mazieres <dm@uun.org>
   3  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /*
  19  * Arc4 random number generator for OpenBSD.
  20  *
  21  * This code is derived from section 17.1 of Applied Cryptography,
  22  * second edition, which describes a stream cipher allegedly
  23  * compatible with RSA Labs "RC4" cipher (the actual description of
  24  * which is a trade secret).  The same algorithm is used as a stream
  25  * cipher called "arcfour" in Tatu Ylonen's ssh package.
  26  *
  27  * RC4 is a registered trademark of RSA Laboratories.
  28  *
  29  * $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $
  30  * $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $
  31  */
  32
  33 #include "namespace.h"
  34 #include <sys/types.h>
  35 #include <sys/time.h>
  36 #include <sys/sysctl.h>
  37 #include <stdlib.h>
  38 #include <fcntl.h>
  39 #include <unistd.h>
  40 #include <pthread.h>
  41
  42 #include "libc_private.h"
  43 #include "un-namespace.h"
  44
  45 /*
  46  * Misc constants
  47  */
  48 #define RANDOMDEV       "/dev/random"
  49 #define KEYSIZE         128
  50 #define _ARC4_LOCK()                                            \
  51         do {                                                    \
  52                 if (__isthreaded)                               \
  53                         _pthread_mutex_lock(&arc4random_mtx);   \
  54         } while (0)
  55
  56 #define _ARC4_UNLOCK()                                          \
  57         do {                                                    \
  58                 if (__isthreaded)                               \
  59                         _pthread_mutex_unlock(&arc4random_mtx); \
  60         } while (0)
  61
  62 struct arc4_stream {
  63         u_int8_t i;
  64         u_int8_t j;
  65         u_int8_t s[KEYSIZE * 2];
  66 };
  67
  68 static pthread_mutex_t  arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
  69
  70 static struct arc4_stream rs;
  71 static pid_t arc4_stir_pid;
  72 static int rs_initialized;
  73 static int rs_stired;
  74 static int arc4_count;
  75
  76 static u_int8_t arc4_getbyte(void);
  77 static void arc4_stir(void);
  78
  79 static inline void
  80 arc4_init(void)
  81 {
  82         int     n;
  83
  84         for (n = 0; n < KEYSIZE * 2; n++)
  85                 rs.s[n] = n;
  86         rs.i = 0;
  87         rs.j = 0;
  88 }
  89
  90 static inline void
  91 arc4_addrandom(u_char *dat, size_t datlen)
  92 {
  93         size_t n;
  94         u_int8_t si;
  95
  96         rs.i--;
  97         for (n = 0; n < KEYSIZE * 2; n++) {
  98                 rs.i = (rs.i + 1);
  99                 si = rs.s[rs.i];
 100                 rs.j = (rs.j + si + dat[n % datlen]);
 101                 rs.s[rs.i] = rs.s[rs.j];
 102                 rs.s[rs.j] = si;
 103         }
 104         rs.j = rs.i;
 105 }
 106
 107 struct pray {
 108         struct timeval  tv;
 109         pid_t           pid;
 110 };
 111
 112 static void
 113 arc4_stir(void)
 114 {
 115         u_int8_t rnd[KEYSIZE*2];
 116         size_t n;
 117         int fd;
 118
 119         /*
 120          * NOTE: Don't assume that the garbage on the stack is actually
 121          *       random.
 122          */
 123         n = 0;
 124         fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
 125         if (fd >= 0) {
 126                 n = _read(fd, rnd, sizeof(rnd));
 127                 _close(fd);
 128                 if ((ssize_t)n < 0)
 129                         n = 0;
 130         }
 131
 132         /*
 133          * Align for added entropy, sysctl back-off for chroots that might
 134          * not have access to /dev/random.
 135          */
 136         n = n & ~15;    /* align for added entropy */
 137         if (n < sizeof(rnd)) {
 138                 size_t r = sizeof(rnd) - n;
 139                 if (sysctlbyname("kern.random", rnd + n, &r, NULL, 0) == 0)
 140                         n += r;
 141         }
 142
 143         /*
 144          * Pray if this code ever gets triggered.
 145          */
 146         n = n & ~15;
 147         if (n <= sizeof(rnd) - sizeof(struct pray)) {
 148                 struct pray *pray = (void *)(rnd + n);
 149                 gettimeofday(&pray->tv, NULL);
 150                 pray->pid = getpid();
 151                 n += sizeof(struct pray);
 152         }
 153         arc4_addrandom((u_char *)rnd, n);
 154
 155         /*
 156          * Discard early keystream, as per recommendations in:
 157          * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
 158          */
 159         for (n = 0; n < 3072; n++)
 160                 arc4_getbyte();
 161
 162         /*
 163          * Theoretically we can set arc4_count to 1600000.  Realistically,
 164          * it makes no sense to use a number that high.  Use something
 165          * reasonable.
 166          */
 167         arc4_count = 65539;
 168 }
 169
 170 static u_int8_t
 171 arc4_getbyte(void)
 172 {
 173         u_int8_t si, sj;
 174
 175         rs.i = (rs.i + 1);
 176         si = rs.s[rs.i];
 177         rs.j = (rs.j + si);
 178         sj = rs.s[rs.j];
 179         rs.s[rs.i] = sj;
 180         rs.s[rs.j] = si;
 181
 182         return (rs.s[(si + sj) & 0xff]);
 183 }
 184
 185 static u_int32_t
 186 arc4_getword(void)
 187 {
 188         u_int32_t val;
 189
 190         val = arc4_getbyte() << 24;
 191         val |= arc4_getbyte() << 16;
 192         val |= arc4_getbyte() << 8;
 193         val |= arc4_getbyte();
 194
 195         return (val);
 196 }
 197
 198 static void
 199 arc4_check_init(void)
 200 {
 201         if (!rs_initialized) {
 202                 arc4_init();
 203                 rs_initialized = 1;
 204         }
 205 }
 206
 207 static inline void
 208 arc4_check_stir(void)
 209 {
 210         pid_t pid = getpid();   /* optimized by upmap */
 211
 212         if (!rs_stired || arc4_count <= 0 || arc4_stir_pid != pid) {
 213                 arc4_stir_pid = pid;
 214                 arc4_stir();
 215                 rs_stired = 1;
 216         }
 217 }
 218
 219 void
 220 arc4random_stir(void)
 221 {
 222         _ARC4_LOCK();
 223         arc4_check_init();
 224         arc4_stir();
 225         rs_stired = 1;
 226         _ARC4_UNLOCK();
 227 }
 228
 229 void
 230 arc4random_addrandom(uint8_t *dat, size_t datlen)
 231 {
 232         _ARC4_LOCK();
 233         arc4_check_init();
 234         arc4_check_stir();
 235         arc4_addrandom(dat, datlen);
 236         _ARC4_UNLOCK();
 237 }
 238
 239 u_int32_t
 240 arc4random(void)
 241 {
 242         u_int32_t rnd;
 243
 244         _ARC4_LOCK();
 245         arc4_check_init();
 246         arc4_check_stir();
 247         rnd = arc4_getword();
 248         arc4_count -= 4;
 249         _ARC4_UNLOCK();
 250
 251         return (rnd);
 252 }
 253
 254 void
 255 arc4random_buf(void *_buf, size_t n)
 256 {
 257         u_char *buf = (u_char *)_buf;
 258
 259         _ARC4_LOCK();
 260         arc4_check_init();
 261         while (n--) {
 262                 arc4_check_stir();
 263                 buf[n] = arc4_getbyte();
 264                 arc4_count--;
 265         }
 266         _ARC4_UNLOCK();
 267 }
 268
 269 /*
 270  * Calculate a uniformly distributed random number less than upper_bound
 271  * avoiding "modulo bias".
 272  *
 273  * Uniformity is achieved by generating new random numbers until the one
 274  * returned is outside the range [0, 2**32 % upper_bound).  This
 275  * guarantees the selected random number will be inside
 276  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 277  * after reduction modulo upper_bound.
 278  */
 279 u_int32_t
 280 arc4random_uniform(u_int32_t upper_bound)
 281 {
 282         u_int32_t r, min;
 283
 284         if (upper_bound < 2)
 285                 return 0;
 286
 287         /* 2**32 % x == (2**32 - x) % x */
 288         min = -upper_bound % upper_bound;
 289         /*
 290          * This could theoretically loop forever but each retry has
 291          * p > 0.5 (worst case, usually far better) of selecting a
 292          * number inside the range we need, so it should rarely need
 293          * to re-roll.
 294          */
 295         for (;;) {
 296                 r = arc4random();
 297                 if (r >= min)
 298                         break;
 299         }
 300
 301         return (r % upper_bound);
 302 }
 303
 304 #if 0
 305 /*-------- Test code for i386 --------*/
 306 #include <stdio.h>
 307 #include <machine/pctr.h>
 308 int
 309 main(int argc, char **argv)
 310 {
 311         const int iter = 1000000;
 312         int     i;
 313         pctrval v;
 314
 315         v = rdtsc();
 316         for (i = 0; i < iter; i++)
 317                 arc4random();
 318         v = rdtsc() - v;
 319         v /= iter;
 320
 321         printf("%qd cycles\n", v);
 322 }
 323 #endif