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/sysctl.h> 43 #include <sys/time.h> 44 #include <pthread.h> 45 46 #include "libc_private.h" 47 #include "un-namespace.h" 48 49 #ifdef __GNUC__ 50 #define inline __inline 51 #else /* !__GNUC__ */ 52 #define inline 53 #endif /* !__GNUC__ */ 54 55 struct arc4_stream { 56 u_int8_t i; 57 u_int8_t j; 58 u_int8_t s[256]; 59 }; 60 61 static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; 62 63 #define RANDOMDEV "/dev/random" 64 #define KEYSIZE 128 65 #define _ARC4_LOCK() \ 66 do { \ 67 if (__isthreaded) \ 68 _pthread_mutex_lock(&arc4random_mtx); \ 69 } while (0) 70 71 #define _ARC4_UNLOCK() \ 72 do { \ 73 if (__isthreaded) \ 74 _pthread_mutex_unlock(&arc4random_mtx); \ 75 } while (0) 76 77 static int rs_initialized; 78 static struct arc4_stream rs; 79 static pid_t arc4_stir_pid; 80 static int arc4_count; 81 82 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, 83 void *newp, size_t newlen); 84 85 static inline u_int8_t arc4_getbyte(void); 86 static void arc4_stir(void); 87 88 static inline void 89 arc4_init(void) 90 { 91 int n; 92 93 for (n = 0; n < 256; n++) 94 rs.s[n] = n; 95 rs.i = 0; 96 rs.j = 0; 97 } 98 99 static inline void 100 arc4_addrandom(u_char *dat, int datlen) 101 { 102 int n; 103 u_int8_t si; 104 105 rs.i--; 106 for (n = 0; n < 256; n++) { 107 rs.i = (rs.i + 1); 108 si = rs.s[rs.i]; 109 rs.j = (rs.j + si + dat[n % datlen]); 110 rs.s[rs.i] = rs.s[rs.j]; 111 rs.s[rs.j] = si; 112 } 113 rs.j = rs.i; 114 } 115 116 static size_t 117 arc4_sysctl(u_char *buf, size_t size) 118 { 119 int mib[2]; 120 size_t len, done; 121 122 mib[0] = CTL_KERN; 123 mib[1] = KERN_ARND; 124 done = 0; 125 126 do { 127 len = size; 128 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) 129 return (done); 130 done += len; 131 buf += len; 132 size -= len; 133 } while (size > 0); 134 135 return (done); 136 } 137 138 static void 139 arc4_stir(void) 140 { 141 int done, fd, i; 142 struct { 143 struct timeval tv; 144 pid_t pid; 145 u_char rnd[KEYSIZE]; 146 } rdat; 147 148 if (!rs_initialized) { 149 arc4_init(); 150 rs_initialized = 1; 151 } 152 done = 0; 153 if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE) 154 done = 1; 155 if (!done) { 156 fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0); 157 if (fd >= 0) { 158 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) 159 done = 1; 160 (void)_close(fd); 161 } 162 } 163 if (!done) { 164 (void)gettimeofday(&rdat.tv, NULL); 165 rdat.pid = getpid(); 166 /* We'll just take whatever was on the stack too... */ 167 } 168 169 arc4_addrandom((u_char *)&rdat, KEYSIZE); 170 171 /* 172 * Discard early keystream, as per recommendations in: 173 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 174 */ 175 for (i = 0; i < 1024; i++) 176 (void)arc4_getbyte(); 177 arc4_count = 1600000; 178 } 179 180 static void 181 arc4_stir_if_needed(void) 182 { 183 pid_t pid = getpid(); 184 185 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 186 { 187 arc4_stir_pid = pid; 188 arc4_stir(); 189 } 190 } 191 192 static inline u_int8_t 193 arc4_getbyte(void) 194 { 195 u_int8_t si, sj; 196 197 rs.i = (rs.i + 1); 198 si = rs.s[rs.i]; 199 rs.j = (rs.j + si); 200 sj = rs.s[rs.j]; 201 rs.s[rs.i] = sj; 202 rs.s[rs.j] = si; 203 return (rs.s[(si + sj) & 0xff]); 204 } 205 206 static inline u_int32_t 207 arc4_getword(void) 208 { 209 u_int32_t val; 210 val = arc4_getbyte() << 24; 211 val |= arc4_getbyte() << 16; 212 val |= arc4_getbyte() << 8; 213 val |= arc4_getbyte(); 214 return val; 215 } 216 217 void 218 arc4random_stir(void) 219 { 220 _ARC4_LOCK(); 221 arc4_stir(); 222 _ARC4_UNLOCK(); 223 } 224 225 void 226 arc4random_addrandom(u_char *dat, int datlen) 227 { 228 _ARC4_LOCK(); 229 if (!rs_initialized) 230 arc4_stir(); 231 arc4_addrandom(dat, datlen); 232 _ARC4_UNLOCK(); 233 } 234 235 u_int32_t 236 arc4random(void) 237 { 238 u_int32_t val; 239 _ARC4_LOCK(); 240 arc4_count -= 4; 241 arc4_stir_if_needed(); 242 val = arc4_getword(); 243 _ARC4_UNLOCK(); 244 return val; 245 } 246 247 void 248 arc4random_buf(void *_buf, size_t n) 249 { 250 u_char *buf = (u_char *)_buf; 251 _ARC4_LOCK(); 252 arc4_stir_if_needed(); 253 while (n--) { 254 if (--arc4_count <= 0) 255 arc4_stir(); 256 buf[n] = arc4_getbyte(); 257 } 258 _ARC4_UNLOCK(); 259 } 260 261 /* 262 * Calculate a uniformly distributed random number less than upper_bound 263 * avoiding "modulo bias". 264 * 265 * Uniformity is achieved by generating new random numbers until the one 266 * returned is outside the range [0, 2**32 % upper_bound). This 267 * guarantees the selected random number will be inside 268 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 269 * after reduction modulo upper_bound. 270 */ 271 u_int32_t 272 arc4random_uniform(u_int32_t upper_bound) 273 { 274 u_int32_t r, min; 275 276 if (upper_bound < 2) 277 return 0; 278 279 #if (ULONG_MAX > 0xffffffffUL) 280 min = 0x100000000UL % upper_bound; 281 #else 282 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 283 if (upper_bound > 0x80000000) 284 min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 285 else { 286 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 287 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 288 } 289 #endif 290 291 /* 292 * This could theoretically loop forever but each retry has 293 * p > 0.5 (worst case, usually far better) of selecting a 294 * number inside the range we need, so it should rarely need 295 * to re-roll. 296 */ 297 for (;;) { 298 r = arc4random(); 299 if (r >= min) 300 break; 301 } 302 303 return r % upper_bound; 304 } 305 306 #if 0 307 /*-------- Test code for i386 --------*/ 308 #include <stdio.h> 309 #include <machine/pctr.h> 310 int 311 main(int argc, char **argv) 312 { 313 const int iter = 1000000; 314 int i; 315 pctrval v; 316 317 v = rdtsc(); 318 for (i = 0; i < iter; i++) 319 arc4random(); 320 v = rdtsc() - v; 321 v /= iter; 322 323 printf("%qd cycles\n", v); 324 } 325 #endif 326