1 /* $NetBSD: arc4random.c,v 1.20 2012/08/20 21:38:09 dsl 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.20 2012/08/20 21:38:09 dsl 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 mutex_t mtx; 58 }; 59 60 #ifdef _REENTRANT 61 #define LOCK(rs) { \ 62 int isthreaded = __isthreaded; \ 63 if (isthreaded) \ 64 mutex_lock(&(rs)->mtx); 65 #define UNLOCK(rs) \ 66 if (isthreaded) \ 67 mutex_unlock(&(rs)->mtx); \ 68 } 69 #else 70 #define LOCK(rs) 71 #define UNLOCK(rs) 72 #endif 73 74 #define S(n) (n) 75 #define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3) 76 #define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12) 77 #define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48) 78 #define S256 S64(0), S64(64), S64(128), S64(192) 79 80 static struct arc4_stream rs = { .i = 0xff, .j = 0, .s = { S256 }, 81 .stirred = 0, .mtx = MUTEX_INITIALIZER }; 82 83 #undef S 84 #undef S4 85 #undef S16 86 #undef S64 87 #undef S256 88 89 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 90 static __noinline void arc4_stir(struct arc4_stream *); 91 static inline uint8_t arc4_getbyte(struct arc4_stream *); 92 static inline uint32_t arc4_getword(struct arc4_stream *); 93 94 static inline int 95 arc4_check_init(struct arc4_stream *as) 96 { 97 if (__predict_true(rs.stirred)) 98 return 0; 99 100 arc4_stir(as); 101 return 1; 102 } 103 104 static inline void 105 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 106 { 107 uint8_t si; 108 size_t n; 109 110 for (n = 0; n < __arraycount(as->s); n++) { 111 as->i = (as->i + 1); 112 si = as->s[as->i]; 113 as->j = (as->j + si + dat[n % datlen]); 114 as->s[as->i] = as->s[as->j]; 115 as->s[as->j] = si; 116 } 117 } 118 119 static __noinline void 120 arc4_stir(struct arc4_stream *as) 121 { 122 int rdat[32]; 123 int mib[] = { CTL_KERN, KERN_URND }; 124 size_t len; 125 size_t i, j; 126 127 /* 128 * This code once opened and read /dev/urandom on each 129 * call. That causes repeated rekeying of the kernel stream 130 * generator, which is very wasteful. Because of application 131 * behavior, caching the fd doesn't really help. So we just 132 * fill up the tank from sysctl, which is a tiny bit slower 133 * for us but much friendlier to other entropy consumers. 134 */ 135 136 for (i = 0; i < __arraycount(rdat); i++) { 137 len = sizeof(rdat[i]); 138 if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1) 139 abort(); 140 } 141 142 arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat)); 143 144 /* 145 * Throw away the first N words of output, as suggested in the 146 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 147 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 148 */ 149 for (j = 0; j < __arraycount(as->s) * 4; j++) 150 arc4_getbyte(as); 151 152 as->stirred = 1; 153 } 154 155 static __always_inline uint8_t 156 arc4_getbyte_ij(struct arc4_stream *as, uint8_t *i, uint8_t *j) 157 { 158 uint8_t si, sj; 159 160 *i = *i + 1; 161 si = as->s[*i]; 162 *j = *j + si; 163 sj = as->s[*j]; 164 as->s[*i] = sj; 165 as->s[*j] = si; 166 return (as->s[(si + sj) & 0xff]); 167 } 168 169 static inline uint8_t 170 arc4_getbyte(struct arc4_stream *as) 171 { 172 return arc4_getbyte_ij(as, &as->i, &as->j); 173 } 174 175 static inline uint32_t 176 arc4_getword(struct arc4_stream *as) 177 { 178 uint32_t val; 179 val = arc4_getbyte(as) << 24; 180 val |= arc4_getbyte(as) << 16; 181 val |= arc4_getbyte(as) << 8; 182 val |= arc4_getbyte(as); 183 return val; 184 } 185 186 void 187 arc4random_stir(void) 188 { 189 LOCK(&rs); 190 arc4_stir(&rs); 191 UNLOCK(&rs); 192 } 193 194 void 195 arc4random_addrandom(u_char *dat, int datlen) 196 { 197 LOCK(&rs); 198 arc4_check_init(&rs); 199 arc4_addrandom(&rs, dat, datlen); 200 UNLOCK(&rs); 201 } 202 203 uint32_t 204 arc4random(void) 205 { 206 uint32_t v; 207 208 LOCK(&rs); 209 arc4_check_init(&rs); 210 v = arc4_getword(&rs); 211 UNLOCK(&rs); 212 return v; 213 } 214 215 void 216 arc4random_buf(void *buf, size_t len) 217 { 218 uint8_t *bp = buf; 219 uint8_t *ep = bp + len; 220 uint8_t i, j; 221 222 LOCK(&rs); 223 arc4_check_init(&rs); 224 225 /* cache i and j - compiler can't know 'buf' doesn't alias them */ 226 i = rs.i; 227 j = rs.j; 228 229 while (bp < ep) 230 *bp++ = arc4_getbyte_ij(&rs, &i, &j); 231 rs.i = i; 232 rs.j = j; 233 234 UNLOCK(&rs); 235 } 236 237 /*- 238 * Written by Damien Miller. 239 * With simplifications by Jinmei Tatuya. 240 */ 241 242 /* 243 * Calculate a uniformly distributed random number less than 244 * upper_bound avoiding "modulo bias". 245 * 246 * Uniformity is achieved by generating new random numbers 247 * until the one returned is outside the range 248 * [0, 2^32 % upper_bound[. This guarantees the selected 249 * random number will be inside the range 250 * [2^32 % upper_bound, 2^32[ which maps back to 251 * [0, upper_bound[ after reduction modulo upper_bound. 252 */ 253 uint32_t 254 arc4random_uniform(uint32_t upper_bound) 255 { 256 uint32_t r, min; 257 258 if (upper_bound < 2) 259 return 0; 260 261 /* calculate (2^32 % upper_bound) avoiding 64-bit math */ 262 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ 263 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; 264 265 LOCK(&rs); 266 arc4_check_init(&rs); 267 268 /* 269 * This could theoretically loop forever but each retry has 270 * p > 0.5 (worst case, usually far better) of selecting a 271 * number inside the range we need, so it should rarely need 272 * to re-roll (at all). 273 */ 274 do 275 r = arc4_getword(&rs); 276 while (r < min); 277 UNLOCK(&rs); 278 279 return r % upper_bound; 280 } 281