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 KEYSIZE 128 63 #define _ARC4_LOCK() \ 64 do { \ 65 if (__isthreaded) \ 66 _pthread_mutex_lock(&arc4random_mtx); \ 67 } while (0) 68 69 #define _ARC4_UNLOCK() \ 70 do { \ 71 if (__isthreaded) \ 72 _pthread_mutex_unlock(&arc4random_mtx); \ 73 } while (0) 74 75 static int rs_initialized; 76 static struct arc4_stream rs; 77 static pid_t arc4_stir_pid; 78 static int arc4_count; 79 80 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, 81 void *newp, size_t newlen); 82 83 static inline u_int8_t arc4_getbyte(void); 84 static void arc4_stir(void); 85 86 static inline void 87 arc4_init(void) 88 { 89 int n; 90 91 for (n = 0; n < 256; n++) 92 rs.s[n] = n; 93 rs.i = 0; 94 rs.j = 0; 95 } 96 97 static inline void 98 arc4_addrandom(u_char *dat, int datlen) 99 { 100 int n; 101 u_int8_t si; 102 103 rs.i--; 104 for (n = 0; n < 256; n++) { 105 rs.i = (rs.i + 1); 106 si = rs.s[rs.i]; 107 rs.j = (rs.j + si + dat[n % datlen]); 108 rs.s[rs.i] = rs.s[rs.j]; 109 rs.s[rs.j] = si; 110 } 111 rs.j = rs.i; 112 } 113 114 size_t 115 __arc4_sysctl(u_char *buf, size_t size) 116 { 117 int mib[2]; 118 size_t len, done; 119 120 mib[0] = CTL_KERN; 121 mib[1] = KERN_ARND; 122 done = 0; 123 124 do { 125 len = size; 126 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) 127 return (done); 128 done += len; 129 buf += len; 130 size -= len; 131 } while (size > 0); 132 133 return (done); 134 } 135 136 static void 137 arc4_stir(void) 138 { 139 u_char rdat[KEYSIZE]; 140 int i; 141 142 if (!rs_initialized) { 143 arc4_init(); 144 rs_initialized = 1; 145 } 146 if (__arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) { 147 /* 148 * The sysctl cannot fail. If it does fail on some FreeBSD 149 * derivative or after some future change, just abort so that 150 * the problem will be found and fixed. abort is not normally 151 * suitable for a library but makes sense here. 152 */ 153 abort(); 154 } 155 156 arc4_addrandom(rdat, KEYSIZE); 157 158 /* 159 * Discard early keystream, as per recommendations in: 160 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 161 */ 162 for (i = 0; i < 3072; i++) 163 (void)arc4_getbyte(); 164 arc4_count = 1600000; 165 } 166 167 static void 168 arc4_stir_if_needed(void) 169 { 170 pid_t pid = getpid(); 171 172 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) { 173 arc4_stir_pid = pid; 174 arc4_stir(); 175 } 176 } 177 178 static inline 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 return (rs.s[(si + sj) & 0xff]); 190 } 191 192 static inline u_int32_t 193 arc4_getword(void) 194 { 195 u_int32_t val; 196 val = arc4_getbyte() << 24; 197 val |= arc4_getbyte() << 16; 198 val |= arc4_getbyte() << 8; 199 val |= arc4_getbyte(); 200 return val; 201 } 202 203 void 204 arc4random_stir(void) 205 { 206 _ARC4_LOCK(); 207 arc4_stir(); 208 _ARC4_UNLOCK(); 209 } 210 211 void 212 arc4random_addrandom(u_char *dat, int datlen) 213 { 214 _ARC4_LOCK(); 215 if (!rs_initialized) 216 arc4_stir(); 217 arc4_addrandom(dat, datlen); 218 _ARC4_UNLOCK(); 219 } 220 221 u_int32_t 222 arc4random(void) 223 { 224 u_int32_t val; 225 _ARC4_LOCK(); 226 arc4_count -= 4; 227 arc4_stir_if_needed(); 228 val = arc4_getword(); 229 _ARC4_UNLOCK(); 230 return val; 231 } 232 233 void 234 arc4random_buf(void *_buf, size_t n) 235 { 236 u_char *buf = (u_char *)_buf; 237 _ARC4_LOCK(); 238 arc4_stir_if_needed(); 239 while (n--) { 240 if (--arc4_count <= 0) 241 arc4_stir(); 242 buf[n] = arc4_getbyte(); 243 } 244 _ARC4_UNLOCK(); 245 } 246 247 /* 248 * Calculate a uniformly distributed random number less than upper_bound 249 * avoiding "modulo bias". 250 * 251 * Uniformity is achieved by generating new random numbers until the one 252 * returned is outside the range [0, 2**32 % upper_bound). This 253 * guarantees the selected random number will be inside 254 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 255 * after reduction modulo upper_bound. 256 */ 257 u_int32_t 258 arc4random_uniform(u_int32_t upper_bound) 259 { 260 u_int32_t r, min; 261 262 if (upper_bound < 2) 263 return 0; 264 265 /* 2**32 % x == (2**32 - x) % x */ 266 min = -upper_bound % upper_bound; 267 /* 268 * This could theoretically loop forever but each retry has 269 * p > 0.5 (worst case, usually far better) of selecting a 270 * number inside the range we need, so it should rarely need 271 * to re-roll. 272 */ 273 for (;;) { 274 r = arc4random(); 275 if (r >= min) 276 break; 277 } 278 279 return r % upper_bound; 280 } 281 282 #if 0 283 /*-------- Test code for i386 --------*/ 284 #include <stdio.h> 285 #include <machine/pctr.h> 286 int 287 main(int argc, char **argv) 288 { 289 const int iter = 1000000; 290 int i; 291 pctrval v; 292 293 v = rdtsc(); 294 for (i = 0; i < iter; i++) 295 arc4random(); 296 v = rdtsc() - v; 297 v /= iter; 298 299 printf("%qd cycles\n", v); 300 } 301 #endif 302