1 /* $NetBSD: arc4random.c,v 1.25 2014/07/19 14:53:22 roy Exp $ */ 2 /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */ 3 4 /* 5 * Arc4 random number generator for OpenBSD. 6 * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 7 * 8 * Modification and redistribution in source and binary forms is 9 * permitted provided that due credit is given to the author and the 10 * OpenBSD project by leaving this copyright notice intact. 11 */ 12 13 /* 14 * This code is derived from section 17.1 of Applied Cryptography, 15 * second edition, which describes a stream cipher allegedly 16 * compatible with RSA Labs "RC4" cipher (the actual description of 17 * which is a trade secret). The same algorithm is used as a stream 18 * cipher called "arcfour" in Tatu Ylonen's ssh package. 19 * 20 * Here the stream cipher has been modified always to include the time 21 * when initializing the state. That makes it impossible to 22 * regenerate the same random sequence twice, so this can't be used 23 * for encryption, but will generate good random numbers. 24 * 25 * RC4 is a registered trademark of RSA Laboratories. 26 */ 27 28 #include <sys/cdefs.h> 29 #if defined(LIBC_SCCS) && !defined(lint) 30 __RCSID("$NetBSD: arc4random.c,v 1.25 2014/07/19 14:53:22 roy Exp $"); 31 #endif /* LIBC_SCCS and not lint */ 32 33 #include "namespace.h" 34 #include "reentrant.h" 35 #include <fcntl.h> 36 #include <pthread.h> 37 #include <stdbool.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 <sys/sysctl.h> 44 45 #ifdef __weak_alias 46 __weak_alias(arc4random,_arc4random) 47 __weak_alias(arc4random_addrandom,_arc4random_addrandom) 48 __weak_alias(arc4random_buf,_arc4random_buf) 49 __weak_alias(arc4random_stir,_arc4random_stir) 50 __weak_alias(arc4random_uniform,_arc4random_uniform) 51 #endif 52 53 #define REKEY_BYTES 1600000 54 55 struct arc4_stream { 56 bool inited; 57 uint8_t i; 58 uint8_t j; 59 uint8_t s[(uint8_t)~0u + 1u]; /* 256 to you and me */ 60 size_t count; 61 mutex_t mtx; 62 }; 63 64 #ifdef _REENTRANT 65 #define LOCK(rs) do { \ 66 if (__isthreaded) mutex_lock(&(rs)->mtx); \ 67 } while (/*CONSTCOND*/ 0) 68 #define UNLOCK(rs) do { \ 69 if (__isthreaded) mutex_unlock(&(rs)->mtx); \ 70 } while (/*CONSTCOND*/ 0) 71 #else 72 #define LOCK(rs) 73 #define UNLOCK(rs) 74 #endif 75 76 #define S(n) (n) 77 #define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3) 78 #define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12) 79 #define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48) 80 #define S256 S64(0), S64(64), S64(128), S64(192) 81 82 static struct arc4_stream rs = { .inited = false, 83 .i = 0xff, .j = 0, .s = { S256 }, 84 .count = 0, .mtx = MUTEX_INITIALIZER }; 85 86 #undef S 87 #undef S4 88 #undef S16 89 #undef S64 90 #undef S256 91 92 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 93 static __noinline void arc4_stir(struct arc4_stream *); 94 static inline uint8_t arc4_getbyte(struct arc4_stream *); 95 static inline uint32_t arc4_getword(struct arc4_stream *); 96 97 #ifdef _REENTRANT 98 static void 99 arc4_fork_prepare(void) 100 { 101 102 LOCK(&rs); 103 } 104 105 static void 106 arc4_fork_parent(void) 107 { 108 109 UNLOCK(&rs); 110 } 111 #else 112 #define arc4_fork_prepare NULL 113 #define arc4_fork_parent NULL 114 #endif 115 116 static void 117 arc4_fork_child(void) 118 { 119 120 /* Reset the counter to a force new stir after forking */ 121 rs.count = 0; 122 UNLOCK(&rs); 123 } 124 125 static inline void 126 arc4_check_init(struct arc4_stream *as) 127 { 128 /* 129 * pthread_atfork(3) only allows async-signal-safe functions in 130 * the child handler. 131 * NetBSD's mutex_unlock is async-signal safe, other implementations 132 * may not be. 133 */ 134 135 if (__predict_false(!as->inited)) { 136 as->inited = true; 137 pthread_atfork(arc4_fork_prepare, 138 arc4_fork_parent, arc4_fork_child); 139 } 140 } 141 142 static inline void 143 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 144 { 145 uint8_t si; 146 size_t n; 147 148 for (n = 0; n < __arraycount(as->s); n++) { 149 as->i = (as->i + 1); 150 si = as->s[as->i]; 151 as->j = (as->j + si + dat[n % datlen]); 152 as->s[as->i] = as->s[as->j]; 153 as->s[as->j] = si; 154 } 155 } 156 157 static __noinline void 158 arc4_stir(struct arc4_stream *as) 159 { 160 int rdat[32]; 161 int mib[] = { CTL_KERN, KERN_URND }; 162 size_t len; 163 size_t i, j; 164 165 arc4_check_init(as); 166 167 /* 168 * This code once opened and read /dev/urandom on each 169 * call. That causes repeated rekeying of the kernel stream 170 * generator, which is very wasteful. Because of application 171 * behavior, caching the fd doesn't really help. So we just 172 * fill up the tank from sysctl, which is a tiny bit slower 173 * for us but much friendlier to other entropy consumers. 174 */ 175 176 for (i = 0; i < __arraycount(rdat); i++) { 177 len = sizeof(rdat[i]); 178 if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) 179 abort(); 180 } 181 182 arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat)); 183 184 /* 185 * Throw away the first N words of output, as suggested in the 186 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 187 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 188 */ 189 for (j = 0; j < __arraycount(as->s) * sizeof(uint32_t); j++) 190 arc4_getbyte(as); 191 192 /* Stir again after REKEY_BYTES bytes, or if the pid changes */ 193 as->count = REKEY_BYTES; 194 } 195 196 static inline void 197 arc4_stir_if_needed(struct arc4_stream *as, size_t len) 198 { 199 200 if (__predict_false(as->count <= len)) 201 arc4_stir(as); 202 else 203 as->count -= len; 204 } 205 206 static __inline uint8_t 207 arc4_getbyte_ij(struct arc4_stream *as, uint8_t *i, uint8_t *j) 208 { 209 uint8_t si, sj; 210 211 *i = *i + 1; 212 si = as->s[*i]; 213 *j = *j + si; 214 sj = as->s[*j]; 215 as->s[*i] = sj; 216 as->s[*j] = si; 217 return (as->s[(si + sj) & 0xff]); 218 } 219 220 static inline uint8_t 221 arc4_getbyte(struct arc4_stream *as) 222 { 223 224 return arc4_getbyte_ij(as, &as->i, &as->j); 225 } 226 227 static inline uint32_t 228 arc4_getword(struct arc4_stream *as) 229 { 230 uint32_t val; 231 232 val = arc4_getbyte(as) << 24; 233 val |= arc4_getbyte(as) << 16; 234 val |= arc4_getbyte(as) << 8; 235 val |= arc4_getbyte(as); 236 return val; 237 } 238 239 void 240 arc4random_stir(void) 241 { 242 243 LOCK(&rs); 244 arc4_stir(&rs); 245 UNLOCK(&rs); 246 } 247 248 void 249 arc4random_addrandom(u_char *dat, int datlen) 250 { 251 252 LOCK(&rs); 253 arc4_stir_if_needed(&rs, datlen); 254 arc4_addrandom(&rs, dat, datlen); 255 UNLOCK(&rs); 256 } 257 258 uint32_t 259 arc4random(void) 260 { 261 uint32_t v; 262 263 LOCK(&rs); 264 arc4_stir_if_needed(&rs, sizeof(v)); 265 v = arc4_getword(&rs); 266 UNLOCK(&rs); 267 return v; 268 } 269 270 void 271 arc4random_buf(void *buf, size_t len) 272 { 273 uint8_t *bp = buf; 274 uint8_t *ep = bp + len; 275 uint8_t i, j; 276 277 LOCK(&rs); 278 arc4_stir_if_needed(&rs, len); 279 280 /* cache i and j - compiler can't know 'buf' doesn't alias them */ 281 i = rs.i; 282 j = rs.j; 283 284 while (bp < ep) 285 *bp++ = arc4_getbyte_ij(&rs, &i, &j); 286 rs.i = i; 287 rs.j = j; 288 289 UNLOCK(&rs); 290 } 291 292 /*- 293 * Written by Damien Miller. 294 * With simplifications by Jinmei Tatuya. 295 */ 296 297 /* 298 * Calculate a uniformly distributed random number less than 299 * upper_bound avoiding "modulo bias". 300 * 301 * Uniformity is achieved by generating new random numbers 302 * until the one returned is outside the range 303 * [0, 2^32 % upper_bound[. This guarantees the selected 304 * random number will be inside the range 305 * [2^32 % upper_bound, 2^32[ which maps back to 306 * [0, upper_bound[ after reduction modulo upper_bound. 307 */ 308 uint32_t 309 arc4random_uniform(uint32_t upper_bound) 310 { 311 uint32_t r, min; 312 313 if (upper_bound < 2) 314 return 0; 315 316 /* calculate (2^32 % upper_bound) avoiding 64-bit math */ 317 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ 318 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; 319 320 LOCK(&rs); 321 arc4_stir_if_needed(&rs, sizeof(r)); 322 323 /* 324 * This could theoretically loop forever but each retry has 325 * p > 0.5 (worst case, usually far better) of selecting a 326 * number inside the range we need, so it should rarely need 327 * to re-roll (at all). 328 */ 329 do 330 r = arc4_getword(&rs); 331 while (r < min); 332 UNLOCK(&rs); 333 334 return r % upper_bound; 335 } 336