gen/FreeBSD/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
  35 #include <sys/cdefs.h>
  36 __FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $");
  37
  38 #include <sys/types.h>
  39 #include <sys/time.h>
  40 #include <sys/param.h>
  41 #include <sys/random.h>
  42 #include <fcntl.h>
  43 #include <unistd.h>
  44 #include <pthread.h>
  45
  46 #include <TargetConditionals.h>
  47 #if !TARGET_OS_DRIVERKIT
  48 #define OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE 1
  49 #endif
  50 #include <os/assumes.h>
  51 #include <os/lock.h>
  52
  53 #include "string.h"
  54 #include "libc_private.h"
  55
  56 #if defined(__APPLE__) && !defined(VARIANT_STATIC)
  57 #include <corecrypto/ccrng.h>
  58
  59 static struct ccrng_state *rng;
  60
  61 static void
  62 arc4_init(void)
  63 {
  64         int err;
  65
  66         if (rng != NULL) return;
  67
  68         rng = ccrng(&err);
  69         if (rng == NULL) {
  70 #if OS_CRASH_ENABLE_EXPERIMENTAL_LIBTRACE
  71                 os_crash("arc4random: unable to get ccrng() handle (%d)", err);
  72 #else
  73                 os_crash("arc4random: unable to get ccrng() handle");
  74 #endif
  75         }
  76 }
  77
  78 void
  79 arc4random_addrandom(__unused u_char *dat, __unused int datlen)
  80 {
  81         /* NOP - deprecated */
  82 }
  83
  84 uint32_t
  85 arc4random(void)
  86 {
  87         uint32_t rand;
  88
  89         arc4random_buf(&rand, sizeof(rand));
  90
  91         return rand;
  92 }
  93
  94 void
  95 arc4random_buf(void *buf, size_t buf_size)
  96 {
  97         arc4_init();
  98         ccrng_generate(rng, buf_size, buf);
  99 }
 100
 101 void
 102 arc4random_stir(void)
 103 {
 104         /* NOP */
 105 }
 106
 107 uint32_t
 108 arc4random_uniform(uint32_t upper_bound)
 109 {
 110         uint64_t rand;
 111
 112         arc4_init();
 113         ccrng_uniform(rng, upper_bound, &rand);
 114
 115         return (uint32_t)rand;
 116 }
 117
 118 __private_extern__ void
 119 _arc4_fork_child(void)
 120 {
 121         /* NOP */
 122 }
 123
 124 #else /* __APPLE__ && !VARIANT_STATIC */
 125
 126 #define RANDOMDEV       "/dev/random"
 127
 128 static void
 129 _my_getentropy(uint8_t *buf, size_t size){
 130     int fd;
 131         ssize_t ret;
 132         if (getentropy(buf, size) == 0) {
 133                 return;
 134         }
 135
 136         // The above should never fail, but we'll try /dev/random anyway
 137         fd = open(RANDOMDEV, O_RDONLY, 0);
 138         if (fd == -1) {
 139 #if !defined(VARIANT_STATIC)
 140                 os_crash("arc4random: unable to open /dev/random");
 141 #else
 142                 abort();
 143 #endif
 144         }
 145 shortread:
 146         ret = read(fd, buf, size);
 147         if (ret == -1) {
 148 #if !defined(VARIANT_STATIC)
 149                 os_crash("arc4random: unable to read from /dev/random");
 150 #else
 151                 abort();
 152 #endif
 153         } else if ((size_t)ret < size) {
 154                 size -= (size_t)ret;
 155                 buf += ret;
 156                 goto shortread;
 157         }
 158         (void)close(fd);
 159 }
 160
 161 struct arc4_stream {
 162         u_int8_t i;
 163         u_int8_t j;
 164         u_int8_t s[256];
 165 };
 166
 167 #define KEYSIZE         128
 168
 169 static struct arc4_stream rs = {
 170         .i = 0,
 171         .j = 0,
 172         .s = {
 173                   0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
 174                  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
 175                  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
 176                  48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
 177                  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,
 178                  80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,
 179                  96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
 180                 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
 181                 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
 182                 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
 183                 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
 184                 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
 185                 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
 186                 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
 187                 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
 188                 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
 189         }
 190 };
 191 static int rs_stired;
 192
 193 static inline u_int8_t arc4_getbyte(void);
 194 static void arc4_stir(void);
 195
 196 static struct {
 197         struct timeval  tv;
 198         pid_t           pid;
 199         u_int8_t        rnd[KEYSIZE];
 200 } rdat;
 201 static volatile int rs_data_available = 0;
 202
 203 static inline void
 204 arc4_addrandom(u_char *dat, int datlen)
 205 {
 206         int     n;
 207         u_int8_t si;
 208
 209         rs.i--;
 210         for (n = 0; n < 256; n++) {
 211                 rs.i = (rs.i + 1);
 212                 si = rs.s[rs.i];
 213                 rs.j = (rs.j + si + dat[n % datlen]);
 214                 rs.s[rs.i] = rs.s[rs.j];
 215                 rs.s[rs.j] = si;
 216         }
 217         rs.j = rs.i;
 218 }
 219
 220 static void
 221 arc4_fetch(void)
 222 {
 223         _my_getentropy((uint8_t*)&rdat, KEYSIZE);
 224 }
 225
 226 static os_unfair_lock arc4_lock = OS_UNFAIR_LOCK_INIT;
 227 static int arc4_count;
 228
 229 static void
 230 arc4_stir(void)
 231 {
 232         int n;
 233         /*
 234          * If we don't have data, we need some now before we can integrate
 235          * it into the static buffers
 236          */
 237         if (!rs_data_available)
 238         {
 239                 arc4_fetch();
 240         }
 241         rs_data_available = 0;
 242         __sync_synchronize();
 243
 244         arc4_addrandom((u_char *)&rdat, KEYSIZE);
 245
 246         /*
 247          * Throw away the first N bytes of output, as suggested in the
 248          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 249          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 250          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 251          * by Ilya Mironov.
 252          */
 253         for (n = 0; n < 1024; n++)
 254                 (void) arc4_getbyte();
 255         arc4_count = 1600000;
 256         rs_stired = 1;
 257 }
 258
 259 static inline u_int8_t
 260 arc4_getbyte(void)
 261 {
 262         u_int8_t si, sj;
 263
 264         rs.i = (rs.i + 1);
 265         si = rs.s[rs.i];
 266         rs.j = (rs.j + si);
 267         sj = rs.s[rs.j];
 268         rs.s[rs.i] = sj;
 269         rs.s[rs.j] = si;
 270
 271         return (rs.s[(si + sj) & 0xff]);
 272 }
 273
 274 static inline u_int32_t
 275 arc4_getword(void)
 276 {
 277         u_int32_t val;
 278
 279         val = arc4_getbyte() << 24;
 280         val |= arc4_getbyte() << 16;
 281         val |= arc4_getbyte() << 8;
 282         val |= arc4_getbyte();
 283
 284         return (val);
 285 }
 286
 287 /* 7944700: force restir in child */
 288 __private_extern__ void
 289 _arc4_fork_child(void)
 290 {
 291         arc4_lock = OS_UNFAIR_LOCK_INIT;
 292         rs_stired = 0;
 293         rs_data_available = 0;
 294 }
 295
 296 static inline int
 297 arc4_check_stir(void)
 298 {
 299         if (!rs_stired || arc4_count <= 0) {
 300                 arc4_stir();
 301                 return 1;
 302         }
 303         return 0;
 304 }
 305
 306 void
 307 arc4random_addrandom(u_char *dat, int datlen)
 308 {
 309         os_unfair_lock_lock(&arc4_lock);
 310         arc4_check_stir();
 311         arc4_addrandom(dat, datlen);
 312         os_unfair_lock_unlock(&arc4_lock);
 313 }
 314
 315 u_int32_t
 316 arc4random(void)
 317 {
 318         u_int32_t rnd;
 319
 320         os_unfair_lock_lock(&arc4_lock);
 321
 322         int did_stir = arc4_check_stir();
 323         rnd = arc4_getword();
 324         arc4_count -= 4;
 325
 326         os_unfair_lock_unlock(&arc4_lock);
 327         if (did_stir)
 328         {
 329                 /* stirring used up our data pool, we need to read in new data outside of the lock */
 330                 arc4_fetch();
 331                 rs_data_available = 1;
 332                 __sync_synchronize();
 333         }
 334
 335         return (rnd);
 336 }
 337
 338 void
 339 arc4random_buf(void *_buf, size_t n)
 340 {
 341         u_char *buf = (u_char *)_buf;
 342         int did_stir = 0;
 343
 344         os_unfair_lock_lock(&arc4_lock);
 345
 346         while (n--) {
 347                 if (arc4_check_stir())
 348                 {
 349                         did_stir = 1;
 350                 }
 351                 buf[n] = arc4_getbyte();
 352                 arc4_count--;
 353         }
 354
 355         os_unfair_lock_unlock(&arc4_lock);
 356         if (did_stir)
 357         {
 358                 /* stirring used up our data pool, we need to read in new data outside of the lock */
 359                 arc4_fetch();
 360                 rs_data_available = 1;
 361                 __sync_synchronize();
 362         }
 363 }
 364
 365 void
 366 arc4random_stir(void)
 367 {
 368         os_unfair_lock_lock(&arc4_lock);
 369         arc4_stir();
 370         os_unfair_lock_unlock(&arc4_lock);
 371 }
 372
 373 /*
 374  * Calculate a uniformly distributed random number less than upper_bound
 375  * avoiding "modulo bias".
 376  *
 377  * Uniformity is achieved by trying successive ranges of bits from the random
 378  * value, each large enough to hold the desired upper bound, until a range
 379  * holding a value less than the bound is found.
 380  */
 381 uint32_t
 382 arc4random_uniform(uint32_t upper_bound)
 383 {
 384         if (upper_bound < 2)
 385                 return 0;
 386
 387         // find smallest 2**n -1 >= upper_bound
 388         int zeros = __builtin_clz(upper_bound);
 389         int bits = CHAR_BIT * sizeof(uint32_t) - zeros;
 390         uint32_t mask = 0xFFFFFFFFU >> zeros;
 391
 392         do {
 393                 uint32_t value = arc4random();
 394
 395                 // If low 2**n-1 bits satisfy the requested condition, return result
 396                 uint32_t result = value & mask;
 397                 if (result < upper_bound) {
 398                         return result;
 399                 }
 400
 401                 // otherwise consume remaining bits of randomness looking for a satisfactory result.
 402                 int bits_left = zeros;
 403                 while (bits_left >= bits) {
 404                         value >>= bits;
 405                         result = value & mask;
 406                         if (result < upper_bound) {
 407                                 return result;
 408                         }
 409                         bits_left -= bits;
 410                 }
 411         } while (1);
 412 }
 413
 414 #endif /* __APPLE__ */