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