1 /* $NetBSD: arc4random.c,v 1.24 2014/06/12 19:12:19 apb 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.24 2014/06/12 19:12:19 apb 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 if (__predict_false(!as->inited)) { 130 as->inited = true; 131 pthread_atfork(arc4_fork_prepare, 132 arc4_fork_parent, arc4_fork_child); 133 } 134 } 135 136 static inline void 137 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 138 { 139 uint8_t si; 140 size_t n; 141 142 for (n = 0; n < __arraycount(as->s); n++) { 143 as->i = (as->i + 1); 144 si = as->s[as->i]; 145 as->j = (as->j + si + dat[n % datlen]); 146 as->s[as->i] = as->s[as->j]; 147 as->s[as->j] = si; 148 } 149 } 150 151 static __noinline void 152 arc4_stir(struct arc4_stream *as) 153 { 154 int rdat[32]; 155 int mib[] = { CTL_KERN, KERN_URND }; 156 size_t len; 157 size_t i, j; 158 159 arc4_check_init(as); 160 161 /* 162 * This code once opened and read /dev/urandom on each 163 * call. That causes repeated rekeying of the kernel stream 164 * generator, which is very wasteful. Because of application 165 * behavior, caching the fd doesn't really help. So we just 166 * fill up the tank from sysctl, which is a tiny bit slower 167 * for us but much friendlier to other entropy consumers. 168 */ 169 170 for (i = 0; i < __arraycount(rdat); i++) { 171 len = sizeof(rdat[i]); 172 if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) 173 abort(); 174 } 175 176 arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat)); 177 178 /* 179 * Throw away the first N words of output, as suggested in the 180 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 181 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 182 */ 183 for (j = 0; j < __arraycount(as->s) * sizeof(uint32_t); j++) 184 arc4_getbyte(as); 185 186 /* Stir again after REKEY_BYTES bytes, or if the pid changes */ 187 as->count = REKEY_BYTES; 188 } 189 190 static inline void 191 arc4_stir_if_needed(struct arc4_stream *as, size_t len) 192 { 193 194 if (__predict_false(as->count <= len)) 195 arc4_stir(as); 196 else 197 as->count -= len; 198 } 199 200 static __inline uint8_t 201 arc4_getbyte_ij(struct arc4_stream *as, uint8_t *i, uint8_t *j) 202 { 203 uint8_t si, sj; 204 205 *i = *i + 1; 206 si = as->s[*i]; 207 *j = *j + si; 208 sj = as->s[*j]; 209 as->s[*i] = sj; 210 as->s[*j] = si; 211 return (as->s[(si + sj) & 0xff]); 212 } 213 214 static inline uint8_t 215 arc4_getbyte(struct arc4_stream *as) 216 { 217 218 return arc4_getbyte_ij(as, &as->i, &as->j); 219 } 220 221 static inline uint32_t 222 arc4_getword(struct arc4_stream *as) 223 { 224 uint32_t val; 225 226 val = arc4_getbyte(as) << 24; 227 val |= arc4_getbyte(as) << 16; 228 val |= arc4_getbyte(as) << 8; 229 val |= arc4_getbyte(as); 230 return val; 231 } 232 233 void 234 arc4random_stir(void) 235 { 236 237 LOCK(&rs); 238 arc4_stir(&rs); 239 UNLOCK(&rs); 240 } 241 242 void 243 arc4random_addrandom(u_char *dat, int datlen) 244 { 245 246 LOCK(&rs); 247 arc4_stir_if_needed(&rs, datlen); 248 arc4_addrandom(&rs, dat, datlen); 249 UNLOCK(&rs); 250 } 251 252 uint32_t 253 arc4random(void) 254 { 255 uint32_t v; 256 257 LOCK(&rs); 258 arc4_stir_if_needed(&rs, sizeof(v)); 259 v = arc4_getword(&rs); 260 UNLOCK(&rs); 261 return v; 262 } 263 264 void 265 arc4random_buf(void *buf, size_t len) 266 { 267 uint8_t *bp = buf; 268 uint8_t *ep = bp + len; 269 uint8_t i, j; 270 271 LOCK(&rs); 272 arc4_stir_if_needed(&rs, len); 273 274 /* cache i and j - compiler can't know 'buf' doesn't alias them */ 275 i = rs.i; 276 j = rs.j; 277 278 while (bp < ep) 279 *bp++ = arc4_getbyte_ij(&rs, &i, &j); 280 rs.i = i; 281 rs.j = j; 282 283 UNLOCK(&rs); 284 } 285 286 /*- 287 * Written by Damien Miller. 288 * With simplifications by Jinmei Tatuya. 289 */ 290 291 /* 292 * Calculate a uniformly distributed random number less than 293 * upper_bound avoiding "modulo bias". 294 * 295 * Uniformity is achieved by generating new random numbers 296 * until the one returned is outside the range 297 * [0, 2^32 % upper_bound[. This guarantees the selected 298 * random number will be inside the range 299 * [2^32 % upper_bound, 2^32[ which maps back to 300 * [0, upper_bound[ after reduction modulo upper_bound. 301 */ 302 uint32_t 303 arc4random_uniform(uint32_t upper_bound) 304 { 305 uint32_t r, min; 306 307 if (upper_bound < 2) 308 return 0; 309 310 /* calculate (2^32 % upper_bound) avoiding 64-bit math */ 311 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ 312 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; 313 314 LOCK(&rs); 315 arc4_stir_if_needed(&rs, sizeof(r)); 316 317 /* 318 * This could theoretically loop forever but each retry has 319 * p > 0.5 (worst case, usually far better) of selecting a 320 * number inside the range we need, so it should rarely need 321 * to re-roll (at all). 322 */ 323 do 324 r = arc4_getword(&rs); 325 while (r < min); 326 UNLOCK(&rs); 327 328 return r % upper_bound; 329 } 330