1 /* $NetBSD: arc4random.c,v 1.10 2011/02/04 22:07:07 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.10 2011/02/04 22:07:07 christos Exp $"); 31 #endif /* LIBC_SCCS and not lint */ 32 33 #include "namespace.h" 34 #include <fcntl.h> 35 #include <stdlib.h> 36 #include <unistd.h> 37 #include <sys/types.h> 38 #include <sys/param.h> 39 #include <sys/time.h> 40 #include <sys/sysctl.h> 41 42 #ifdef __weak_alias 43 __weak_alias(arc4random,_arc4random) 44 #endif 45 46 struct arc4_stream { 47 uint8_t i; 48 uint8_t j; 49 uint8_t s[256]; 50 }; 51 52 static int rs_initialized; 53 static struct arc4_stream rs; 54 55 static inline void arc4_init(struct arc4_stream *); 56 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 57 static void arc4_stir(struct arc4_stream *); 58 static inline uint8_t arc4_getbyte(struct arc4_stream *); 59 static inline uint32_t arc4_getword(struct arc4_stream *); 60 61 static inline void 62 arc4_init(struct arc4_stream *as) 63 { 64 int n; 65 66 for (n = 0; n < 256; n++) 67 as->s[n] = n; 68 as->i = 0; 69 as->j = 0; 70 } 71 72 static inline void 73 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 74 { 75 int n; 76 uint8_t si; 77 78 as->i--; 79 for (n = 0; n < 256; n++) { 80 as->i = (as->i + 1); 81 si = as->s[as->i]; 82 as->j = (as->j + si + dat[n % datlen]); 83 as->s[as->i] = as->s[as->j]; 84 as->s[as->j] = si; 85 } 86 as->j = as->i; 87 } 88 89 static void 90 arc4_stir(struct arc4_stream *as) 91 { 92 int fd; 93 struct { 94 struct timeval tv; 95 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 96 } rdat; 97 int n; 98 99 gettimeofday(&rdat.tv, NULL); 100 fd = open("/dev/urandom", O_RDONLY); 101 if (fd != -1) { 102 read(fd, rdat.rnd, sizeof(rdat.rnd)); 103 close(fd); 104 } 105 #ifdef KERN_URND 106 else { 107 int mib[2]; 108 u_int i; 109 size_t len; 110 111 /* Device could not be opened, we might be chrooted, take 112 * randomness from sysctl. */ 113 114 mib[0] = CTL_KERN; 115 mib[1] = KERN_URND; 116 117 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i++) { 118 len = sizeof(u_int); 119 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 120 break; 121 } 122 } 123 #endif 124 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 125 * whatever was on the stack... */ 126 127 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 128 129 /* 130 * Throw away the first N words of output, as suggested in the 131 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 132 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 133 */ 134 for (n = 0; n < 256 * 4; n++) 135 arc4_getbyte(as); 136 } 137 138 static inline uint8_t 139 arc4_getbyte(struct arc4_stream *as) 140 { 141 uint8_t si, sj; 142 143 as->i = (as->i + 1); 144 si = as->s[as->i]; 145 as->j = (as->j + si); 146 sj = as->s[as->j]; 147 as->s[as->i] = sj; 148 as->s[as->j] = si; 149 return (as->s[(si + sj) & 0xff]); 150 } 151 152 static inline uint32_t 153 arc4_getword(struct arc4_stream *as) 154 { 155 uint32_t val; 156 val = arc4_getbyte(as) << 24; 157 val |= arc4_getbyte(as) << 16; 158 val |= arc4_getbyte(as) << 8; 159 val |= arc4_getbyte(as); 160 return val; 161 } 162 163 void 164 arc4random_stir(void) 165 { 166 if (!rs_initialized) { 167 arc4_init(&rs); 168 rs_initialized = 1; 169 } 170 arc4_stir(&rs); 171 } 172 173 void 174 arc4random_addrandom(u_char *dat, int datlen) 175 { 176 if (!rs_initialized) 177 arc4random_stir(); 178 arc4_addrandom(&rs, dat, datlen); 179 } 180 181 uint32_t 182 arc4random(void) 183 { 184 if (!rs_initialized) 185 arc4random_stir(); 186 return arc4_getword(&rs); 187 } 188 189 void 190 arc4random_buf(void *buf, size_t len) 191 { 192 uint8_t *bp = buf; 193 uint8_t *ep = bp + len; 194 195 bp[0] = arc4_getbyte(&rs) % 3; 196 while (bp[0]--) 197 (void)arc4_getbyte(&rs); 198 199 while (bp < ep) 200 *bp++ = arc4_getbyte(&rs); 201 } 202 203 /*- 204 * Written by Damien Miller. 205 * With simplifications by Jinmei Tatuya. 206 */ 207 208 /* 209 * Calculate a uniformly distributed random number less than 210 * upper_bound avoiding "modulo bias". 211 * 212 * Uniformity is achieved by generating new random numbers 213 * until the one returned is outside the range 214 * [0, 2^32 % upper_bound[. This guarantees the selected 215 * random number will be inside the range 216 * [2^32 % upper_bound, 2^32[ which maps back to 217 * [0, upper_bound[ after reduction modulo upper_bound. 218 */ 219 uint32_t 220 arc4random_uniform(uint32_t upper_bound) 221 { 222 uint32_t r, min; 223 224 if (upper_bound < 2) 225 return 0; 226 227 #if defined(ULONG_MAX) && (ULONG_MAX > 0xFFFFFFFFUL) 228 min = 0x100000000UL % upper_bound; 229 #else 230 /* calculate (2^32 % upper_bound) avoiding 64-bit math */ 231 if (upper_bound > 0x80000000U) 232 /* 2^32 - upper_bound (only one "value area") */ 233 min = 1 + ~upper_bound; 234 else 235 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */ 236 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound; 237 #endif 238 239 /* 240 * This could theoretically loop forever but each retry has 241 * p > 0.5 (worst case, usually far better) of selecting a 242 * number inside the range we need, so it should rarely need 243 * to re-roll (at all). 244 */ 245 if (!rs_initialized) 246 arc4random_stir(); 247 if (arc4_getbyte(&rs) & 1) 248 (void)arc4_getbyte(&rs); 249 do 250 r = arc4_getword(&rs); 251 while (r < min); 252 253 return r % upper_bound; 254 } 255 256 257 #if 0 258 /*-------- Test code for i386 --------*/ 259 #include <stdio.h> 260 #include <machine/pctr.h> 261 int 262 main(int argc, char **argv) 263 { 264 const int iter = 1000000; 265 int i; 266 pctrval v; 267 268 v = rdtsc(); 269 for (i = 0; i < iter; i++) 270 arc4random(); 271 v = rdtsc() - v; 272 v /= iter; 273 274 printf("%qd cycles\n", v); 275 } 276 #endif 277