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 <stdlib.h>
  42 #include <fcntl.h>
  43 #include <unistd.h>
  44 #include <pthread.h>
  45
  46 #include "libc_private.h"
  47 #include "un-namespace.h"
  48
  49 struct arc4_stream {
  50         u_int8_t i;
  51         u_int8_t j;
  52         u_int8_t s[256];
  53 };
  54
  55 static pthread_mutex_t  arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
  56
  57 #define RANDOMDEV       "/dev/random"
  58 #define KEYSIZE         128
  59 #define THREAD_LOCK()                                           \
  60         do {                                                    \
  61                 if (__isthreaded)                               \
  62                         _pthread_mutex_lock(&arc4random_mtx);   \
  63         } while (0)
  64
  65 #define THREAD_UNLOCK()                                         \
  66         do {                                                    \
  67                 if (__isthreaded)                               \
  68                         _pthread_mutex_unlock(&arc4random_mtx); \
  69         } while (0)
  70
  71 static struct arc4_stream rs;
  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 < 256; 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 < 256; 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 static void
 108 arc4_stir(void)
 109 {
 110         int done, fd, n;
 111         struct {
 112                 struct timeval  tv;
 113                 pid_t           pid;
 114                 u_int8_t        rnd[KEYSIZE];
 115         } rdat;
 116
 117         fd = _open(RANDOMDEV, O_RDONLY, 0);
 118         done = 0;
 119         if (fd >= 0) {
 120                 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
 121                         done = 1;
 122                 _close(fd);
 123         }
 124         if (!done) {
 125                 gettimeofday(&rdat.tv, NULL);
 126                 rdat.pid = getpid();
 127                 /* We'll just take whatever was on the stack too... */
 128         }
 129
 130         arc4_addrandom((u_char *)&rdat, KEYSIZE);
 131
 132         /*
 133          * Throw away the first N bytes of output, as suggested in the
 134          * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
 135          * by Fluher, Mantin, and Shamir.  N=1024 is based on
 136          * suggestions in the paper "(Not So) Random Shuffles of RC4"
 137          * by Ilya Mironov.
 138          */
 139         for (n = 0; n < 1024; n++)
 140                 arc4_getbyte();
 141         arc4_count = 1600000;
 142 }
 143
 144 static u_int8_t
 145 arc4_getbyte(void)
 146 {
 147         u_int8_t si, sj;
 148
 149         rs.i = (rs.i + 1);
 150         si = rs.s[rs.i];
 151         rs.j = (rs.j + si);
 152         sj = rs.s[rs.j];
 153         rs.s[rs.i] = sj;
 154         rs.s[rs.j] = si;
 155
 156         return (rs.s[(si + sj) & 0xff]);
 157 }
 158
 159 static u_int32_t
 160 arc4_getword(void)
 161 {
 162         u_int32_t val;
 163
 164         val = arc4_getbyte() << 24;
 165         val |= arc4_getbyte() << 16;
 166         val |= arc4_getbyte() << 8;
 167         val |= arc4_getbyte();
 168
 169         return (val);
 170 }
 171
 172 static void
 173 arc4_check_init(void)
 174 {
 175         if (!rs_initialized) {
 176                 arc4_init();
 177                 rs_initialized = 1;
 178         }
 179 }
 180
 181 static inline void
 182 arc4_check_stir(void)
 183 {
 184         if (!rs_stired || arc4_count <= 0) {
 185                 arc4_stir();
 186                 rs_stired = 1;
 187         }
 188 }
 189
 190 void
 191 arc4random_stir(void)
 192 {
 193         THREAD_LOCK();
 194         arc4_check_init();
 195         arc4_stir();
 196         rs_stired = 1;
 197         THREAD_UNLOCK();
 198 }
 199
 200 void
 201 arc4random_addrandom(uint8_t *dat, size_t datlen)
 202 {
 203         THREAD_LOCK();
 204         arc4_check_init();
 205         arc4_check_stir();
 206         arc4_addrandom(dat, datlen);
 207         THREAD_UNLOCK();
 208 }
 209
 210 u_int32_t
 211 arc4random(void)
 212 {
 213         u_int32_t rnd;
 214
 215         THREAD_LOCK();
 216         arc4_check_init();
 217         arc4_check_stir();
 218         rnd = arc4_getword();
 219         arc4_count -= 4;
 220         THREAD_UNLOCK();
 221
 222         return (rnd);
 223 }
 224
 225 void
 226 arc4random_buf(void *_buf, size_t n)
 227 {
 228         u_char *buf = (u_char *)_buf;
 229
 230         THREAD_LOCK();
 231         arc4_check_init();
 232         while (n--) {
 233                 arc4_check_stir();
 234                 buf[n] = arc4_getbyte();
 235                 arc4_count--;
 236         }
 237         THREAD_UNLOCK();
 238 }
 239
 240 /*
 241  * Calculate a uniformly distributed random number less than upper_bound
 242  * avoiding "modulo bias".
 243  *
 244  * Uniformity is achieved by generating new random numbers until the one
 245  * returned is outside the range [0, 2**32 % upper_bound).  This
 246  * guarantees the selected random number will be inside
 247  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 248  * after reduction modulo upper_bound.
 249  */
 250 u_int32_t
 251 arc4random_uniform(u_int32_t upper_bound)
 252 {
 253         u_int32_t r, min;
 254
 255         if (upper_bound < 2)
 256                 return (0);
 257
 258 #if (ULONG_MAX > 0xffffffffUL)
 259         min = 0x100000000UL % upper_bound;
 260 #else
 261         /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
 262         if (upper_bound > 0x80000000)
 263                 min = 1 + ~upper_bound;         /* 2**32 - upper_bound */
 264         else {
 265                 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
 266                 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
 267         }
 268 #endif
 269
 270         /*
 271          * This could theoretically loop forever but each retry has
 272          * p > 0.5 (worst case, usually far better) of selecting a
 273          * number inside the range we need, so it should rarely need
 274          * to re-roll.
 275          */
 276         for (;;) {
 277                 r = arc4random();
 278                 if (r >= min)
 279                         break;
 280         }
 281
 282         return (r % upper_bound);
 283 }
 284
 285 #if 0
 286 /*-------- Test code for i386 --------*/
 287 #include <stdio.h>
 288 #include <machine/pctr.h>
 289 int
 290 main(int argc, char **argv)
 291 {
 292         const int iter = 1000000;
 293         int     i;
 294         pctrval v;
 295
 296         v = rdtsc();
 297         for (i = 0; i < iter; i++)
 298                 arc4random();
 299         v = rdtsc() - v;
 300         v /= iter;
 301
 302         printf("%qd cycles\n", v);
 303 }
 304 #endif