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