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  * Here the stream cipher has been modified always to include the time
  28  * when initializing the state.  That makes it impossible to
  29  * regenerate the same random sequence twice, so this can't be used
  30  * for encryption, but will generate good random numbers.
  31  *
  32  * RC4 is a registered trademark of RSA Laboratories.
  33  *
  34  * $FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $
  35  * $DragonFly: src/lib/libc/gen/arc4random.c,v 1.7 2005/11/13 00:07:42 swildner Exp $
  36  */
  37
  38 #include "namespace.h"
  39 #include <sys/types.h>
  40 #include <sys/time.h>
  41 #include <sys/sysctl.h>
  42 #include <stdlib.h>
  43 #include <fcntl.h>
  44 #include <unistd.h>
  45 #include <pthread.h>
  46
  47 #include "libc_private.h"
  48 #include "un-namespace.h"
  49
  50 /*
  51  * Misc constants
  52  */
  53 #define RANDOMDEV       "/dev/random"
  54 #define KEYSIZE         128
  55 #define THREAD_LOCK()                                           \
  56         do {                                                    \
  57                 if (__isthreaded)                               \
  58                         _pthread_mutex_lock(&arc4random_mtx);   \
  59         } while (0)
  60
  61 #define THREAD_UNLOCK()                                         \
  62         do {                                                    \
  63                 if (__isthreaded)                               \
  64                         _pthread_mutex_unlock(&arc4random_mtx); \
  65         } while (0)
  66
  67
  68 struct arc4_stream {
  69         u_int8_t i;
  70         u_int8_t j;
  71         u_int8_t s[KEYSIZE * 2];
  72 };
  73
  74 static pthread_mutex_t  arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
  75
  76 static struct arc4_stream rs;
  77 static int rs_initialized;
  78 static int rs_stired;
  79 static int arc4_count;
  80
  81 static u_int8_t arc4_getbyte(void);
  82 static void arc4_stir(void);
  83
  84 static inline void
  85 arc4_init(void)
  86 {
  87         int     n;
  88
  89         for (n = 0; n < KEYSIZE * 2; n++)
  90                 rs.s[n] = n;
  91         rs.i = 0;
  92         rs.j = 0;
  93 }
  94
  95 static inline void
  96 arc4_addrandom(u_char *dat, size_t datlen)
  97 {
  98         size_t n;
  99         u_int8_t si;
 100
 101         rs.i--;
 102         for (n = 0; n < KEYSIZE * 2; n++) {
 103                 rs.i = (rs.i + 1);
 104                 si = rs.s[rs.i];
 105                 rs.j = (rs.j + si + dat[n % datlen]);
 106                 rs.s[rs.i] = rs.s[rs.j];
 107                 rs.s[rs.j] = si;
 108         }
 109         rs.j = rs.i;
 110 }
 111
 112 struct pray {
 113         struct timeval  tv;
 114         pid_t           pid;
 115 };
 116
 117 static void
 118 arc4_stir(void)
 119 {
 120         u_int8_t rnd[KEYSIZE*2];
 121         size_t n;
 122         int fd;
 123
 124         /*
 125          * NOTE: Don't assume that the garbage on the stack is actually
 126          *       random.
 127          */
 128         n = 0;
 129         fd = _open(RANDOMDEV, O_RDONLY, 0);
 130         if (fd >= 0) {
 131                 n = _read(fd, rnd, sizeof(rnd));
 132                 _close(fd);
 133                 if ((ssize_t)n < 0)
 134                         n = 0;
 135         }
 136
 137         /*
 138          * Align for added entropy, sysctl back-off for chroots that might
 139          * not have access to /dev/random.
 140          */
 141         n = n & ~15;    /* align for added entropy */
 142         if (n < sizeof(rnd)) {
 143                 size_t r = sizeof(rnd) - n;
 144                 if (sysctlbyname("kern.random", rnd + n, &r, NULL, 0) == 0)
 145                         n += r;
 146         }
 147
 148         /*
 149          * Pray if this code ever gets triggered.
 150          */
 151         n = n & ~15;
 152         if (n <= sizeof(rnd) - sizeof(struct pray)) {
 153                 struct pray *pray = (void *)(rnd + n);
 154                 gettimeofday(&pray->tv, NULL);
 155                 pray->pid = getpid();
 156                 n += sizeof(struct pray);
 157         }
 158         arc4_addrandom((u_char *)rnd, n);
 159
 160         /*
 161          * Throw away the first N bytes of output, as suggested in the
 162          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 163          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 164          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 165          * by Ilya Mironov.
 166          */
 167         for (n = 0; n < 1024; n++)
 168                 arc4_getbyte();
 169
 170         /*
 171          * Theoretically we can set arc4_count to 1600000.  Realistically,
 172          * it makes no sense to use a number that high.  Use something
 173          * reasonable.
 174          */
 175         arc4_count = 65539;
 176 }
 177
 178 static u_int8_t
 179 arc4_getbyte(void)
 180 {
 181         u_int8_t si, sj;
 182
 183         rs.i = (rs.i + 1);
 184         si = rs.s[rs.i];
 185         rs.j = (rs.j + si);
 186         sj = rs.s[rs.j];
 187         rs.s[rs.i] = sj;
 188         rs.s[rs.j] = si;
 189
 190         return (rs.s[(si + sj) & 0xff]);
 191 }
 192
 193 static u_int32_t
 194 arc4_getword(void)
 195 {
 196         u_int32_t val;
 197
 198         val = arc4_getbyte() << 24;
 199         val |= arc4_getbyte() << 16;
 200         val |= arc4_getbyte() << 8;
 201         val |= arc4_getbyte();
 202
 203         return (val);
 204 }
 205
 206 static void
 207 arc4_check_init(void)
 208 {
 209         if (!rs_initialized) {
 210                 arc4_init();
 211                 rs_initialized = 1;
 212         }
 213 }
 214
 215 static inline void
 216 arc4_check_stir(void)
 217 {
 218         if (!rs_stired || arc4_count <= 0) {
 219                 arc4_stir();
 220                 rs_stired = 1;
 221         }
 222 }
 223
 224 void
 225 arc4random_stir(void)
 226 {
 227         THREAD_LOCK();
 228         arc4_check_init();
 229         arc4_stir();
 230         rs_stired = 1;
 231         THREAD_UNLOCK();
 232 }
 233
 234 void
 235 arc4random_addrandom(uint8_t *dat, size_t datlen)
 236 {
 237         THREAD_LOCK();
 238         arc4_check_init();
 239         arc4_check_stir();
 240         arc4_addrandom(dat, datlen);
 241         THREAD_UNLOCK();
 242 }
 243
 244 u_int32_t
 245 arc4random(void)
 246 {
 247         u_int32_t rnd;
 248
 249         THREAD_LOCK();
 250         arc4_check_init();
 251         arc4_check_stir();
 252         rnd = arc4_getword();
 253         arc4_count -= 4;
 254         THREAD_UNLOCK();
 255
 256         return (rnd);
 257 }
 258
 259 void
 260 arc4random_buf(void *_buf, size_t n)
 261 {
 262         u_char *buf = (u_char *)_buf;
 263
 264         THREAD_LOCK();
 265         arc4_check_init();
 266         while (n--) {
 267                 arc4_check_stir();
 268                 buf[n] = arc4_getbyte();
 269                 arc4_count--;
 270         }
 271         THREAD_UNLOCK();
 272 }
 273
 274 /*
 275  * Calculate a uniformly distributed random number less than upper_bound
 276  * avoiding "modulo bias".
 277  *
 278  * Uniformity is achieved by generating new random numbers until the one
 279  * returned is outside the range [0, 2**32 % upper_bound).  This
 280  * guarantees the selected random number will be inside
 281  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 282  * after reduction modulo upper_bound.
 283  */
 284 u_int32_t
 285 arc4random_uniform(u_int32_t upper_bound)
 286 {
 287         u_int32_t r, min;
 288
 289         if (upper_bound < 2)
 290                 return (0);
 291
 292 #if (ULONG_MAX > 0xffffffffUL)
 293         min = 0x100000000UL % upper_bound;
 294 #else
 295         /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
 296         if (upper_bound > 0x80000000)
 297                 min = 1 + ~upper_bound;         /* 2**32 - upper_bound */
 298         else {
 299                 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
 300                 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
 301         }
 302 #endif
 303
 304         /*
 305          * This could theoretically loop forever but each retry has
 306          * p > 0.5 (worst case, usually far better) of selecting a
 307          * number inside the range we need, so it should rarely need
 308          * to re-roll.
 309          */
 310         for (;;) {
 311                 r = arc4random();
 312                 if (r >= min)
 313                         break;
 314         }
 315
 316         return (r % upper_bound);
 317 }
 318
 319 #if 0
 320 /*-------- Test code for i386 --------*/
 321 #include <stdio.h>
 322 #include <machine/pctr.h>
 323 int
 324 main(int argc, char **argv)
 325 {
 326         const int iter = 1000000;
 327         int     i;
 328         pctrval v;
 329
 330         v = rdtsc();
 331         for (i = 0; i < iter; i++)
 332                 arc4random();
 333         v = rdtsc() - v;
 334         v /= iter;
 335
 336         printf("%qd cycles\n", v);
 337 }
 338 #endif