1 /* $OpenBSD: arc4random.c,v 1.22 2010/12/22 08:23:42 otto Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm@uun.org> 5 * Copyright (c) 2008, Damien Miller <djm@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 * RC4 is a registered trademark of RSA Laboratories. 30 */ 31 32 #include <sys/cdefs.h> 33 __FBSDID("$FreeBSD$"); 34 35 #include "namespace.h" 36 #include <fcntl.h> 37 #include <limits.h> 38 #include <stdlib.h> 39 #include <unistd.h> 40 #include <sys/types.h> 41 #include <sys/param.h> 42 #include <sys/time.h> 43 #include <pthread.h> 44 45 #include "libc_private.h" 46 #include "un-namespace.h" 47 48 #ifdef __GNUC__ 49 #define inline __inline 50 #else /* !__GNUC__ */ 51 #define inline 52 #endif /* !__GNUC__ */ 53 54 struct arc4_stream { 55 u_int8_t i; 56 u_int8_t j; 57 u_int8_t s[256]; 58 }; 59 60 static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; 61 62 #define RANDOMDEV "/dev/random" 63 #define KEYSIZE 128 64 #define _ARC4_LOCK() \ 65 do { \ 66 if (__isthreaded) \ 67 _pthread_mutex_lock(&arc4random_mtx); \ 68 } while (0) 69 70 #define _ARC4_UNLOCK() \ 71 do { \ 72 if (__isthreaded) \ 73 _pthread_mutex_unlock(&arc4random_mtx); \ 74 } while (0) 75 76 static int rs_initialized; 77 static struct arc4_stream rs; 78 static pid_t arc4_stir_pid; 79 static int arc4_count; 80 81 static inline 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 < 256; 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, int datlen) 97 { 98 int n; 99 u_int8_t si; 100 101 rs.i--; 102 for (n = 0; n < 256; 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 static void 113 arc4_stir(void) 114 { 115 int done, fd, i; 116 struct { 117 struct timeval tv; 118 pid_t pid; 119 u_char rnd[KEYSIZE]; 120 } rdat; 121 122 if (!rs_initialized) { 123 arc4_init(); 124 rs_initialized = 1; 125 } 126 fd = _open(RANDOMDEV, O_RDONLY, 0); 127 done = 0; 128 if (fd >= 0) { 129 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) 130 done = 1; 131 (void)_close(fd); 132 } 133 if (!done) { 134 (void)gettimeofday(&rdat.tv, NULL); 135 rdat.pid = getpid(); 136 /* We'll just take whatever was on the stack too... */ 137 } 138 139 arc4_addrandom((u_char *)&rdat, KEYSIZE); 140 141 /* 142 * Discard early keystream, as per recommendations in: 143 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 144 */ 145 for (i = 0; i < 1024; i++) 146 (void)arc4_getbyte(); 147 arc4_count = 1600000; 148 } 149 150 static void 151 arc4_stir_if_needed(void) 152 { 153 pid_t pid = getpid(); 154 155 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 156 { 157 arc4_stir_pid = pid; 158 arc4_stir(); 159 } 160 } 161 162 static inline u_int8_t 163 arc4_getbyte(void) 164 { 165 u_int8_t si, sj; 166 167 rs.i = (rs.i + 1); 168 si = rs.s[rs.i]; 169 rs.j = (rs.j + si); 170 sj = rs.s[rs.j]; 171 rs.s[rs.i] = sj; 172 rs.s[rs.j] = si; 173 return (rs.s[(si + sj) & 0xff]); 174 } 175 176 static inline u_int32_t 177 arc4_getword(void) 178 { 179 u_int32_t val; 180 val = arc4_getbyte() << 24; 181 val |= arc4_getbyte() << 16; 182 val |= arc4_getbyte() << 8; 183 val |= arc4_getbyte(); 184 return val; 185 } 186 187 void 188 arc4random_stir(void) 189 { 190 _ARC4_LOCK(); 191 arc4_stir(); 192 _ARC4_UNLOCK(); 193 } 194 195 void 196 arc4random_addrandom(u_char *dat, int datlen) 197 { 198 _ARC4_LOCK(); 199 if (!rs_initialized) 200 arc4_stir(); 201 arc4_addrandom(dat, datlen); 202 _ARC4_UNLOCK(); 203 } 204 205 u_int32_t 206 arc4random(void) 207 { 208 u_int32_t val; 209 _ARC4_LOCK(); 210 arc4_count -= 4; 211 arc4_stir_if_needed(); 212 val = arc4_getword(); 213 _ARC4_UNLOCK(); 214 return val; 215 } 216 217 void 218 arc4random_buf(void *_buf, size_t n) 219 { 220 u_char *buf = (u_char *)_buf; 221 _ARC4_LOCK(); 222 arc4_stir_if_needed(); 223 while (n--) { 224 if (--arc4_count <= 0) 225 arc4_stir(); 226 buf[n] = arc4_getbyte(); 227 } 228 _ARC4_UNLOCK(); 229 } 230 231 /* 232 * Calculate a uniformly distributed random number less than upper_bound 233 * avoiding "modulo bias". 234 * 235 * Uniformity is achieved by generating new random numbers until the one 236 * returned is outside the range [0, 2**32 % upper_bound). This 237 * guarantees the selected random number will be inside 238 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 239 * after reduction modulo upper_bound. 240 */ 241 u_int32_t 242 arc4random_uniform(u_int32_t upper_bound) 243 { 244 u_int32_t r, min; 245 246 if (upper_bound < 2) 247 return 0; 248 249 #if (ULONG_MAX > 0xffffffffUL) 250 min = 0x100000000UL % upper_bound; 251 #else 252 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 253 if (upper_bound > 0x80000000) 254 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 255 else { 256 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 257 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 258 } 259 #endif 260 261 /* 262 * This could theoretically loop forever but each retry has 263 * p > 0.5 (worst case, usually far better) of selecting a 264 * number inside the range we need, so it should rarely need 265 * to re-roll. 266 */ 267 for (;;) { 268 r = arc4random(); 269 if (r >= min) 270 break; 271 } 272 273 return r % upper_bound; 274 } 275 276 #if 0 277 /*-------- Test code for i386 --------*/ 278 #include <stdio.h> 279 #include <machine/pctr.h> 280 int 281 main(int argc, char **argv) 282 { 283 const int iter = 1000000; 284 int i; 285 pctrval v; 286 287 v = rdtsc(); 288 for (i = 0; i < iter; i++) 289 arc4random(); 290 v = rdtsc() - v; 291 v /= iter; 292 293 printf("%qd cycles\n", v); 294 } 295 #endif 296