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