1 /* $NetBSD: arc4random.c,v 1.21 2013/10/17 23:56:17 christos 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.21 2013/10/17 23:56:17 christos Exp $"); 31 #endif /* LIBC_SCCS and not lint */ 32 33 #include "namespace.h" 34 #include "reentrant.h" 35 #include <fcntl.h> 36 #include <stdlib.h> 37 #include <unistd.h> 38 #include <sys/types.h> 39 #include <sys/param.h> 40 #include <sys/time.h> 41 #include <sys/sysctl.h> 42 43 #ifdef __weak_alias 44 __weak_alias(arc4random,_arc4random) 45 __weak_alias(arc4random_addrandom,_arc4random_addrandom) 46 __weak_alias(arc4random_buf,_arc4random_buf) 47 __weak_alias(arc4random_stir,_arc4random_stir) 48 __weak_alias(arc4random_uniform,_arc4random_uniform) 49 #endif 50 51 struct arc4_stream { 52 uint8_t stirred; 53 uint8_t pad; 54 uint8_t i; 55 uint8_t j; 56 uint8_t s[(uint8_t)~0u + 1u]; /* 256 to you and me */ 57 #ifdef _REENTRANT 58 mutex_t mtx; 59 #endif 60 }; 61 62 #ifdef _REENTRANT 63 #define LOCK(rs) { \ 64 int isthreaded = __isthreaded; \ 65 if (isthreaded) \ 66 mutex_lock(&(rs)->mtx); 67 #define UNLOCK(rs) \ 68 if (isthreaded) \ 69 mutex_unlock(&(rs)->mtx); \ 70 } 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 = { .i = 0xff, .j = 0, .s = { S256 }, 83 #ifdef _REENTRANT 84 .stirred = 0, .mtx = MUTEX_INITIALIZER }; 85 #else 86 .stirred = 0 }; 87 #endif 88 89 #undef S 90 #undef S4 91 #undef S16 92 #undef S64 93 #undef S256 94 95 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 96 static __noinline void arc4_stir(struct arc4_stream *); 97 static inline uint8_t arc4_getbyte(struct arc4_stream *); 98 static inline uint32_t arc4_getword(struct arc4_stream *); 99 100 static inline int 101 arc4_check_init(struct arc4_stream *as) 102 { 103 if (__predict_true(rs.stirred)) 104 return 0; 105 106 arc4_stir(as); 107 return 1; 108 } 109 110 static inline void 111 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 112 { 113 uint8_t si; 114 size_t n; 115 116 for (n = 0; n < __arraycount(as->s); n++) { 117 as->i = (as->i + 1); 118 si = as->s[as->i]; 119 as->j = (as->j + si + dat[n % datlen]); 120 as->s[as->i] = as->s[as->j]; 121 as->s[as->j] = si; 122 } 123 } 124 125 static __noinline void 126 arc4_stir(struct arc4_stream *as) 127 { 128 #if defined(__minix) 129 /* LSC: We do not have a compatibility layer for the 130 * KERN_URND call, so use the old way... */ 131 int fd; 132 size_t j; 133 struct { 134 struct timeval tv; 135 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 136 } rdat; 137 138 gettimeofday(&rdat.tv, NULL); 139 fd = open("/dev/urandom", O_RDONLY); 140 if (fd != -1) { 141 read(fd, rdat.rnd, sizeof(rdat.rnd)); 142 close(fd); 143 } 144 145 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 146 * whatever was on the stack... */ 147 #else 148 int rdat[32]; 149 int mib[] = { CTL_KERN, KERN_URND }; 150 size_t len; 151 size_t i, j; 152 153 /* 154 * This code once opened and read /dev/urandom on each 155 * call. That causes repeated rekeying of the kernel stream 156 * generator, which is very wasteful. Because of application 157 * behavior, caching the fd doesn't really help. So we just 158 * fill up the tank from sysctl, which is a tiny bit slower 159 * for us but much friendlier to other entropy consumers. 160 */ 161 162 for (i = 0; i < __arraycount(rdat); i++) { 163 len = sizeof(rdat[i]); 164 if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) 165 abort(); 166 } 167 #endif /* !defined(__minix) */ 168 169 arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat)); 170 171 /* 172 * Throw away the first N words of output, as suggested in the 173 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 174 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 175 */ 176 for (j = 0; j < __arraycount(as->s) * 4; j++) 177 arc4_getbyte(as); 178 179 as->stirred = 1; 180 } 181 182 static __inline uint8_t 183 arc4_getbyte_ij(struct arc4_stream *as, uint8_t *i, uint8_t *j) 184 { 185 uint8_t si, sj; 186 187 *i = *i + 1; 188 si = as->s[*i]; 189 *j = *j + si; 190 sj = as->s[*j]; 191 as->s[*i] = sj; 192 as->s[*j] = si; 193 return (as->s[(si + sj) & 0xff]); 194 } 195 196 static inline uint8_t 197 arc4_getbyte(struct arc4_stream *as) 198 { 199 return arc4_getbyte_ij(as, &as->i, &as->j); 200 } 201 202 static inline uint32_t 203 arc4_getword(struct arc4_stream *as) 204 { 205 uint32_t val; 206 val = arc4_getbyte(as) << 24; 207 val |= arc4_getbyte(as) << 16; 208 val |= arc4_getbyte(as) << 8; 209 val |= arc4_getbyte(as); 210 return val; 211 } 212 213 void 214 arc4random_stir(void) 215 { 216 LOCK(&rs); 217 arc4_stir(&rs); 218 UNLOCK(&rs); 219 } 220 221 void 222 arc4random_addrandom(u_char *dat, int datlen) 223 { 224 LOCK(&rs); 225 arc4_check_init(&rs); 226 arc4_addrandom(&rs, dat, datlen); 227 UNLOCK(&rs); 228 } 229 230 uint32_t 231 arc4random(void) 232 { 233 uint32_t v; 234 235 LOCK(&rs); 236 arc4_check_init(&rs); 237 v = arc4_getword(&rs); 238 UNLOCK(&rs); 239 return v; 240 } 241 242 void 243 arc4random_buf(void *buf, size_t len) 244 { 245 uint8_t *bp = buf; 246 uint8_t *ep = bp + len; 247 uint8_t i, j; 248 249 LOCK(&rs); 250 arc4_check_init(&rs); 251 252 /* cache i and j - compiler can't know 'buf' doesn't alias them */ 253 i = rs.i; 254 j = rs.j; 255 256 while (bp < ep) 257 *bp++ = arc4_getbyte_ij(&rs, &i, &j); 258 rs.i = i; 259 rs.j = j; 260 261 UNLOCK(&rs); 262 } 263 264 /*- 265 * Written by Damien Miller. 266 * With simplifications by Jinmei Tatuya. 267 */ 268 269 /* 270 * Calculate a uniformly distributed random number less than 271 * upper_bound avoiding "modulo bias". 272 * 273 * Uniformity is achieved by generating new random numbers 274 * until the one returned is outside the range 275 * [0, 2^32 % upper_bound[. This guarantees the selected 276 * random number will be inside the range 277 * [2^32 % upper_bound, 2^32[ which maps back to 278 * [0, upper_bound[ after reduction modulo upper_bound. 279 */ 280 uint32_t 281 arc4random_uniform(uint32_t upper_bound) 282 { 283 uint32_t r, min; 284 285 if (upper_bound < 2) 286 return 0; 287 288 /* calculate (2^32 % upper_bound) avoiding 64-bit math */ 289 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ 290 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; 291 292 LOCK(&rs); 293 arc4_check_init(&rs); 294 295 /* 296 * This could theoretically loop forever but each retry has 297 * p > 0.5 (worst case, usually far better) of selecting a 298 * number inside the range we need, so it should rarely need 299 * to re-roll (at all). 300 */ 301 do 302 r = arc4_getword(&rs); 303 while (r < min); 304 UNLOCK(&rs); 305 306 return r % upper_bound; 307 } 308