1 /* $OpenBSD: arc4random.c,v 1.23 2012/06/24 18:25:12 matthew Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm@uun.org> 5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 /* 21 * Arc4 random number generator for OpenBSD. 22 * 23 * This code is derived from section 17.1 of Applied Cryptography, 24 * second edition, which describes a stream cipher allegedly 25 * compatible with RSA Labs "RC4" cipher (the actual description of 26 * which is a trade secret). The same algorithm is used as a stream 27 * cipher called "arcfour" in Tatu Ylonen's ssh package. 28 * 29 * RC4 is a registered trademark of RSA Laboratories. 30 */ 31 32 #include <fcntl.h> 33 #include <limits.h> 34 #include <stdlib.h> 35 #include <unistd.h> 36 #include <sys/types.h> 37 #include <sys/param.h> 38 #include <sys/time.h> 39 #include <sys/sysctl.h> 40 #include "thread_private.h" 41 42 #ifdef __GNUC__ 43 #define inline __inline 44 #else /* !__GNUC__ */ 45 #define inline 46 #endif /* !__GNUC__ */ 47 48 struct arc4_stream { 49 u_int8_t i; 50 u_int8_t j; 51 u_int8_t s[256]; 52 }; 53 54 static int rs_initialized; 55 static struct arc4_stream rs; 56 static pid_t arc4_stir_pid; 57 static int arc4_count; 58 59 static inline u_int8_t arc4_getbyte(void); 60 61 static inline void 62 arc4_init(void) 63 { 64 int n; 65 66 for (n = 0; n < 256; n++) 67 rs.s[n] = n; 68 rs.i = 0; 69 rs.j = 0; 70 } 71 72 static inline void 73 arc4_addrandom(u_char *dat, int datlen) 74 { 75 int n; 76 u_int8_t si; 77 78 rs.i--; 79 for (n = 0; n < 256; n++) { 80 rs.i = (rs.i + 1); 81 si = rs.s[rs.i]; 82 rs.j = (rs.j + si + dat[n % datlen]); 83 rs.s[rs.i] = rs.s[rs.j]; 84 rs.s[rs.j] = si; 85 } 86 rs.j = rs.i; 87 } 88 89 static void 90 arc4_stir(void) 91 { 92 int i, mib[2]; 93 size_t len; 94 u_char rnd[128]; 95 96 if (!rs_initialized) { 97 arc4_init(); 98 rs_initialized = 1; 99 } 100 101 mib[0] = CTL_KERN; 102 mib[1] = KERN_ARND; 103 104 len = sizeof(rnd); 105 sysctl(mib, 2, rnd, &len, NULL, 0); 106 107 arc4_addrandom(rnd, sizeof(rnd)); 108 109 /* 110 * Discard early keystream, as per recommendations in: 111 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 112 */ 113 for (i = 0; i < 256; i++) 114 (void)arc4_getbyte(); 115 arc4_count = 1600000; 116 } 117 118 static void 119 arc4_stir_if_needed(void) 120 { 121 pid_t pid = getpid(); 122 123 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 124 { 125 arc4_stir_pid = pid; 126 arc4_stir(); 127 } 128 } 129 130 static inline u_int8_t 131 arc4_getbyte(void) 132 { 133 u_int8_t si, sj; 134 135 rs.i = (rs.i + 1); 136 si = rs.s[rs.i]; 137 rs.j = (rs.j + si); 138 sj = rs.s[rs.j]; 139 rs.s[rs.i] = sj; 140 rs.s[rs.j] = si; 141 return (rs.s[(si + sj) & 0xff]); 142 } 143 144 static inline u_int32_t 145 arc4_getword(void) 146 { 147 u_int32_t val; 148 val = arc4_getbyte() << 24; 149 val |= arc4_getbyte() << 16; 150 val |= arc4_getbyte() << 8; 151 val |= arc4_getbyte(); 152 return val; 153 } 154 155 void 156 arc4random_stir(void) 157 { 158 _ARC4_LOCK(); 159 arc4_stir(); 160 _ARC4_UNLOCK(); 161 } 162 163 void 164 arc4random_addrandom(u_char *dat, int datlen) 165 { 166 _ARC4_LOCK(); 167 if (!rs_initialized) 168 arc4_stir(); 169 arc4_addrandom(dat, datlen); 170 _ARC4_UNLOCK(); 171 } 172 173 u_int32_t 174 arc4random(void) 175 { 176 u_int32_t val; 177 _ARC4_LOCK(); 178 arc4_count -= 4; 179 arc4_stir_if_needed(); 180 val = arc4_getword(); 181 _ARC4_UNLOCK(); 182 return val; 183 } 184 185 void 186 arc4random_buf(void *_buf, size_t n) 187 { 188 u_char *buf = (u_char *)_buf; 189 _ARC4_LOCK(); 190 arc4_stir_if_needed(); 191 while (n--) { 192 if (--arc4_count <= 0) 193 arc4_stir(); 194 buf[n] = arc4_getbyte(); 195 } 196 _ARC4_UNLOCK(); 197 } 198 199 /* 200 * Calculate a uniformly distributed random number less than upper_bound 201 * avoiding "modulo bias". 202 * 203 * Uniformity is achieved by generating new random numbers until the one 204 * returned is outside the range [0, 2**32 % upper_bound). This 205 * guarantees the selected random number will be inside 206 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 207 * after reduction modulo upper_bound. 208 */ 209 u_int32_t 210 arc4random_uniform(u_int32_t upper_bound) 211 { 212 u_int32_t r, min; 213 214 if (upper_bound < 2) 215 return 0; 216 217 /* 2**32 % x == (2**32 - x) % x */ 218 min = -upper_bound % upper_bound; 219 220 /* 221 * This could theoretically loop forever but each retry has 222 * p > 0.5 (worst case, usually far better) of selecting a 223 * number inside the range we need, so it should rarely need 224 * to re-roll. 225 */ 226 for (;;) { 227 r = arc4random(); 228 if (r >= min) 229 break; 230 } 231 232 return r % upper_bound; 233 } 234 235 #if 0 236 /*-------- Test code for i386 --------*/ 237 #include <stdio.h> 238 #include <machine/pctr.h> 239 int 240 main(int argc, char **argv) 241 { 242 const int iter = 1000000; 243 int i; 244 pctrval v; 245 246 v = rdtsc(); 247 for (i = 0; i < iter; i++) 248 arc4random(); 249 v = rdtsc() - v; 250 v /= iter; 251 252 printf("%qd cycles\n", v); 253 } 254 #endif 255