1 /* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm@uun.org> 5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 6 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org> 7 * 8 * Permission to use, copy, modify, and distribute this software for any 9 * purpose with or without fee is hereby granted, provided that the above 10 * copyright notice and this permission notice appear in all copies. 11 * 12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 19 */ 20 21 /* 22 * ChaCha based random number generator for OpenBSD. 23 */ 24 25 #include <fcntl.h> 26 #include <limits.h> 27 #include <stdlib.h> 28 #include <string.h> 29 #include <unistd.h> 30 #include <sys/types.h> 31 #include <sys/param.h> 32 #include <sys/time.h> 33 #include <sys/sysctl.h> 34 #include "thread_private.h" 35 36 #define KEYSTREAM_ONLY 37 #include "chacha_private.h" 38 39 #ifdef __GNUC__ 40 #define inline __inline 41 #else /* !__GNUC__ */ 42 #define inline 43 #endif /* !__GNUC__ */ 44 45 #define KEYSZ 32 46 #define IVSZ 8 47 #define BLOCKSZ 64 48 #define RSBUFSZ (16*BLOCKSZ) 49 static int rs_initialized; 50 static pid_t rs_stir_pid; 51 static chacha_ctx rs; /* chacha context for random keystream */ 52 static u_char rs_buf[RSBUFSZ]; /* keystream blocks */ 53 static size_t rs_have; /* valid bytes at end of rs_buf */ 54 static size_t rs_count; /* bytes till reseed */ 55 56 static inline void _rs_rekey(u_char *dat, size_t datlen); 57 58 static inline void 59 _rs_init(u_char *buf, size_t n) 60 { 61 if (n < KEYSZ + IVSZ) 62 return; 63 chacha_keysetup(&rs, buf, KEYSZ * 8, 0); 64 chacha_ivsetup(&rs, buf + KEYSZ); 65 } 66 67 static void 68 _rs_stir(void) 69 { 70 int mib[2]; 71 size_t len; 72 u_char rnd[KEYSZ + IVSZ]; 73 74 mib[0] = CTL_KERN; 75 mib[1] = KERN_ARND; 76 77 len = sizeof(rnd); 78 sysctl(mib, 2, rnd, &len, NULL, 0); 79 80 if (!rs_initialized) { 81 rs_initialized = 1; 82 _rs_init(rnd, sizeof(rnd)); 83 } else 84 _rs_rekey(rnd, sizeof(rnd)); 85 memset(rnd, 0, sizeof(rnd)); 86 87 /* invalidate rs_buf */ 88 rs_have = 0; 89 memset(rs_buf, 0, RSBUFSZ); 90 91 rs_count = 1600000; 92 } 93 94 static inline void 95 _rs_stir_if_needed(size_t len) 96 { 97 pid_t pid = getpid(); 98 99 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) { 100 rs_stir_pid = pid; 101 _rs_stir(); 102 } else 103 rs_count -= len; 104 } 105 106 static inline void 107 _rs_rekey(u_char *dat, size_t datlen) 108 { 109 #ifndef KEYSTREAM_ONLY 110 memset(rs_buf, 0,RSBUFSZ); 111 #endif 112 /* fill rs_buf with the keystream */ 113 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 114 /* mix in optional user provided data */ 115 if (dat) { 116 size_t i, m; 117 118 m = MIN(datlen, KEYSZ + IVSZ); 119 for (i = 0; i < m; i++) 120 rs_buf[i] ^= dat[i]; 121 } 122 /* immediately reinit for backtracking resistance */ 123 _rs_init(rs_buf, KEYSZ + IVSZ); 124 memset(rs_buf, 0, KEYSZ + IVSZ); 125 rs_have = RSBUFSZ - KEYSZ - IVSZ; 126 } 127 128 static inline void 129 _rs_random_buf(void *_buf, size_t n) 130 { 131 u_char *buf = (u_char *)_buf; 132 size_t m; 133 134 _rs_stir_if_needed(n); 135 while (n > 0) { 136 if (rs_have > 0) { 137 m = MIN(n, rs_have); 138 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 139 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 140 buf += m; 141 n -= m; 142 rs_have -= m; 143 } 144 if (rs_have == 0) 145 _rs_rekey(NULL, 0); 146 } 147 } 148 149 static inline void 150 _rs_random_u32(u_int32_t *val) 151 { 152 _rs_stir_if_needed(sizeof(*val)); 153 if (rs_have < sizeof(*val)) 154 _rs_rekey(NULL, 0); 155 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 156 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 157 rs_have -= sizeof(*val); 158 return; 159 } 160 161 void 162 arc4random_stir(void) 163 { 164 _ARC4_LOCK(); 165 _rs_stir(); 166 _ARC4_UNLOCK(); 167 } 168 169 void 170 arc4random_addrandom(u_char *dat, int datlen) 171 { 172 int m; 173 174 _ARC4_LOCK(); 175 if (!rs_initialized) 176 _rs_stir(); 177 while (datlen > 0) { 178 m = MIN(datlen, KEYSZ + IVSZ); 179 _rs_rekey(dat, m); 180 dat += m; 181 datlen -= m; 182 } 183 _ARC4_UNLOCK(); 184 } 185 186 u_int32_t 187 arc4random(void) 188 { 189 u_int32_t val; 190 191 _ARC4_LOCK(); 192 _rs_random_u32(&val); 193 _ARC4_UNLOCK(); 194 return val; 195 } 196 197 void 198 arc4random_buf(void *buf, size_t n) 199 { 200 _ARC4_LOCK(); 201 _rs_random_buf(buf, n); 202 _ARC4_UNLOCK(); 203 } 204 205 /* 206 * Calculate a uniformly distributed random number less than upper_bound 207 * avoiding "modulo bias". 208 * 209 * Uniformity is achieved by generating new random numbers until the one 210 * returned is outside the range [0, 2**32 % upper_bound). This 211 * guarantees the selected random number will be inside 212 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 213 * after reduction modulo upper_bound. 214 */ 215 u_int32_t 216 arc4random_uniform(u_int32_t upper_bound) 217 { 218 u_int32_t r, min; 219 220 if (upper_bound < 2) 221 return 0; 222 223 /* 2**32 % x == (2**32 - x) % x */ 224 min = -upper_bound % upper_bound; 225 226 /* 227 * This could theoretically loop forever but each retry has 228 * p > 0.5 (worst case, usually far better) of selecting a 229 * number inside the range we need, so it should rarely need 230 * to re-roll. 231 */ 232 for (;;) { 233 r = arc4random(); 234 if (r >= min) 235 break; 236 } 237 238 return r % upper_bound; 239 } 240 241 #if 0 242 /*-------- Test code for i386 --------*/ 243 #include <stdio.h> 244 #include <machine/pctr.h> 245 int 246 main(int argc, char **argv) 247 { 248 const int iter = 1000000; 249 int i; 250 pctrval v; 251 252 v = rdtsc(); 253 for (i = 0; i < iter; i++) 254 arc4random(); 255 v = rdtsc() - v; 256 v /= iter; 257 258 printf("%qd cycles\n", v); 259 exit(0); 260 } 261 #endif 262