1 /* $OpenBSD: arc4random.c,v 1.19 2008/06/04 00:50:23 djm Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm (at) uun.org> 5 * Copyright (c) 2008, Damien Miller <djm (at) openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 /* 21 * Arc4 random number generator for OpenBSD. 22 * 23 * This code is derived from section 17.1 of Applied Cryptography, 24 * second edition, which describes a stream cipher allegedly 25 * compatible with RSA Labs "RC4" cipher (the actual description of 26 * which is a trade secret). The same algorithm is used as a stream 27 * cipher called "arcfour" in Tatu Ylonen's ssh package. 28 * 29 * Here the stream cipher has been modified always to include the time 30 * when initializing the state. That makes it impossible to 31 * regenerate the same random sequence twice, so this can't be used 32 * for encryption, but will generate good random numbers. 33 * 34 * RC4 is a registered trademark of RSA Laboratories. 35 */ 36 37 #include <fcntl.h> 38 #include <limits.h> 39 #include <stdlib.h> 40 #include <unistd.h> 41 #include <sys/types.h> 42 #include <sys/param.h> 43 #include <sys/time.h> 44 #include "thread_private.h" 45 46 /* BIONIC-BEGIN */ 47 /* this lock should protect the global variables in this file */ 48 static pthread_mutex_t _arc4_lock = PTHREAD_MUTEX_INITIALIZER; 49 #define _ARC4_LOCK() pthread_mutex_lock(&_arc4_lock) 50 #define _ARC4_UNLOCK() pthread_mutex_unlock(&_arc4_lock) 51 /* BIONIC-END */ 52 53 #ifdef __GNUC__ 54 #define inline __inline 55 #else /* !__GNUC__ */ 56 #define inline 57 #endif /* !__GNUC__ */ 58 59 struct arc4_stream { 60 u_int8_t i; 61 u_int8_t j; 62 u_int8_t s[256]; 63 }; 64 65 static int rs_initialized; 66 static struct arc4_stream rs; 67 static pid_t arc4_stir_pid; 68 static int arc4_count; 69 70 static inline u_int8_t arc4_getbyte(void); 71 72 static inline void 73 arc4_init(void) 74 { 75 int n; 76 77 for (n = 0; n < 256; n++) 78 rs.s[n] = n; 79 rs.i = 0; 80 rs.j = 0; 81 } 82 83 static inline void 84 arc4_addrandom(u_char *dat, int datlen) 85 { 86 int n; 87 u_int8_t si; 88 89 rs.i--; 90 for (n = 0; n < 256; n++) { 91 rs.i = (rs.i + 1); 92 si = rs.s[rs.i]; 93 rs.j = (rs.j + si + dat[n % datlen]); 94 rs.s[rs.i] = rs.s[rs.j]; 95 rs.s[rs.j] = si; 96 } 97 rs.j = rs.i; 98 } 99 100 static void 101 arc4_stir(void) 102 { 103 #if 1 /* BIONIC-BEGIN */ 104 int i, fd; 105 union { 106 struct timeval tv; 107 u_int rnd[128 / sizeof(u_int)]; 108 } rdat; 109 int n; 110 111 if (!rs_initialized) { 112 arc4_init(); 113 rs_initialized = 1; 114 } 115 116 fd = open("/dev/urandom", O_RDONLY); 117 if (fd != -1) { 118 read(fd, rdat.rnd, sizeof(rdat.rnd)); 119 close(fd); 120 } 121 else 122 { 123 /* fd < 0 ? Ah, what the heck. We'll just take 124 * whatever was on the stack. just add a little more 125 * time-based randomness though 126 */ 127 gettimeofday(&rdat.tv, NULL); 128 } 129 130 arc4_stir_pid = getpid(); 131 arc4_addrandom((void *) &rdat, sizeof(rdat)); 132 #else /* BIONIC-END */ 133 int i, mib[2]; 134 size_t len; 135 u_char rnd[128]; 136 137 if (!rs_initialized) { 138 arc4_init(); 139 rs_initialized = 1; 140 } 141 142 mib[0] = CTL_KERN; 143 mib[1] = KERN_ARND; 144 145 len = sizeof(rnd); 146 sysctl(mib, 2, rnd, &len, NULL, 0); 147 148 arc4_stir_pid = getpid(); 149 arc4_addrandom(rnd, sizeof(rnd)); 150 #endif 151 /* 152 * Discard early keystream, as per recommendations in: 153 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 154 */ 155 for (i = 0; i < 256; i++) 156 (void)arc4_getbyte(); 157 arc4_count = 1600000; 158 } 159 160 static inline u_int8_t 161 arc4_getbyte(void) 162 { 163 u_int8_t si, sj; 164 165 rs.i = (rs.i + 1); 166 si = rs.s[rs.i]; 167 rs.j = (rs.j + si); 168 sj = rs.s[rs.j]; 169 rs.s[rs.i] = sj; 170 rs.s[rs.j] = si; 171 return (rs.s[(si + sj) & 0xff]); 172 } 173 174 u_int8_t 175 __arc4_getbyte(void) 176 { 177 u_int8_t val; 178 179 _ARC4_LOCK(); 180 if (--arc4_count == 0 || !rs_initialized) 181 arc4_stir(); 182 val = arc4_getbyte(); 183 _ARC4_UNLOCK(); 184 return val; 185 } 186 187 static inline u_int32_t 188 arc4_getword(void) 189 { 190 u_int32_t val; 191 val = arc4_getbyte() << 24; 192 val |= arc4_getbyte() << 16; 193 val |= arc4_getbyte() << 8; 194 val |= arc4_getbyte(); 195 return val; 196 } 197 198 void 199 arc4random_stir(void) 200 { 201 _ARC4_LOCK(); 202 arc4_stir(); 203 _ARC4_UNLOCK(); 204 } 205 206 void 207 arc4random_addrandom(u_char *dat, int datlen) 208 { 209 _ARC4_LOCK(); 210 if (!rs_initialized) 211 arc4_stir(); 212 arc4_addrandom(dat, datlen); 213 _ARC4_UNLOCK(); 214 } 215 216 u_int32_t 217 arc4random(void) 218 { 219 u_int32_t val; 220 _ARC4_LOCK(); 221 arc4_count -= 4; 222 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != getpid()) 223 arc4_stir(); 224 val = arc4_getword(); 225 _ARC4_UNLOCK(); 226 return val; 227 } 228 229 void 230 arc4random_buf(void *_buf, size_t n) 231 { 232 u_char *buf = (u_char *)_buf; 233 _ARC4_LOCK(); 234 if (!rs_initialized || arc4_stir_pid != getpid()) 235 arc4_stir(); 236 while (n--) { 237 if (--arc4_count <= 0) 238 arc4_stir(); 239 buf[n] = arc4_getbyte(); 240 } 241 _ARC4_UNLOCK(); 242 } 243 244 /* 245 * Calculate a uniformly distributed random number less than upper_bound 246 * avoiding "modulo bias". 247 * 248 * Uniformity is achieved by generating new random numbers until the one 249 * returned is outside the range [0, 2**32 % upper_bound). This 250 * guarantees the selected random number will be inside 251 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 252 * after reduction modulo upper_bound. 253 */ 254 u_int32_t 255 arc4random_uniform(u_int32_t upper_bound) 256 { 257 u_int32_t r, min; 258 259 if (upper_bound < 2) 260 return 0; 261 262 #if (ULONG_MAX > 0xffffffffUL) 263 min = 0x100000000UL % upper_bound; 264 #else 265 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 266 if (upper_bound > 0x80000000) 267 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 268 else { 269 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 270 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 271 } 272 #endif 273 274 /* 275 * This could theoretically loop forever but each retry has 276 * p > 0.5 (worst case, usually far better) of selecting a 277 * number inside the range we need, so it should rarely need 278 * to re-roll. 279 */ 280 for (;;) { 281 r = arc4random(); 282 if (r >= min) 283 break; 284 } 285 286 return r % upper_bound; 287 } 288 289 #if 0 290 /*-------- Test code for i386 --------*/ 291 #include <stdio.h> 292 #include <machine/pctr.h> 293 int 294 main(int argc, char **argv) 295 { 296 const int iter = 1000000; 297 int i; 298 pctrval v; 299 300 v = rdtsc(); 301 for (i = 0; i < iter; i++) 302 arc4random(); 303 v = rdtsc() - v; 304 v /= iter; 305 306 printf("%qd cycles\n", v); 307 } 308 #endif 309
