1 /* $OpenBSD: arc4random.c,v 1.28 2014/05/06 02:31:45 tedu 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 <sys/mman.h> 35 36 #include "thread_private.h" 37 38 #define KEYSTREAM_ONLY 39 #include "chacha_private.h" 40 41 #ifdef __GNUC__ 42 #define inline __inline 43 #else /* !__GNUC__ */ 44 #define inline 45 #endif /* !__GNUC__ */ 46 47 #define KEYSZ 32 48 #define IVSZ 8 49 #define BLOCKSZ 64 50 #define RSBUFSZ (16*BLOCKSZ) 51 static int rs_initialized; 52 static pid_t rs_stir_pid; 53 static chacha_ctx *rs; /* chacha context for random keystream */ 54 static u_char *rs_buf; /* keystream blocks */ 55 static size_t rs_have; /* valid bytes at end of rs_buf */ 56 static size_t rs_count; /* bytes till reseed */ 57 58 static inline void _rs_rekey(u_char *dat, size_t datlen); 59 60 static inline void 61 _rs_init(u_char *buf, size_t n) 62 { 63 if (n < KEYSZ + IVSZ) 64 return; 65 66 if ((rs = mmap(NULL, sizeof(*rs), PROT_READ|PROT_WRITE, 67 MAP_ANON, -1, 0)) == MAP_FAILED) 68 abort(); 69 if ((rs_buf = mmap(NULL, RSBUFSZ, PROT_READ|PROT_WRITE, 70 MAP_ANON, -1, 0)) == MAP_FAILED) 71 abort(); 72 73 chacha_keysetup(rs, buf, KEYSZ * 8, 0); 74 chacha_ivsetup(rs, buf + KEYSZ); 75 } 76 77 static void 78 _rs_stir(void) 79 { 80 int mib[2]; 81 size_t len; 82 u_char rnd[KEYSZ + IVSZ]; 83 84 mib[0] = CTL_KERN; 85 mib[1] = KERN_ARND; 86 87 len = sizeof(rnd); 88 sysctl(mib, 2, rnd, &len, NULL, 0); 89 90 if (!rs_initialized) { 91 rs_initialized = 1; 92 _rs_init(rnd, sizeof(rnd)); 93 } else 94 _rs_rekey(rnd, sizeof(rnd)); 95 memset(rnd, 0, sizeof(rnd)); 96 97 /* invalidate rs_buf */ 98 rs_have = 0; 99 memset(rs_buf, 0, RSBUFSZ); 100 101 rs_count = 1600000; 102 } 103 104 static inline void 105 _rs_stir_if_needed(size_t len) 106 { 107 pid_t pid = getpid(); 108 109 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) { 110 rs_stir_pid = pid; 111 _rs_stir(); 112 } else 113 rs_count -= len; 114 } 115 116 static inline void 117 _rs_rekey(u_char *dat, size_t datlen) 118 { 119 #ifndef KEYSTREAM_ONLY 120 memset(rs_buf, 0,RSBUFSZ); 121 #endif 122 /* fill rs_buf with the keystream */ 123 chacha_encrypt_bytes(rs, rs_buf, rs_buf, RSBUFSZ); 124 /* mix in optional user provided data */ 125 if (dat) { 126 size_t i, m; 127 128 m = MIN(datlen, KEYSZ + IVSZ); 129 for (i = 0; i < m; i++) 130 rs_buf[i] ^= dat[i]; 131 } 132 /* immediately reinit for backtracking resistance */ 133 _rs_init(rs_buf, KEYSZ + IVSZ); 134 memset(rs_buf, 0, KEYSZ + IVSZ); 135 rs_have = RSBUFSZ - KEYSZ - IVSZ; 136 } 137 138 static inline void 139 _rs_random_buf(void *_buf, size_t n) 140 { 141 u_char *buf = (u_char *)_buf; 142 size_t m; 143 144 _rs_stir_if_needed(n); 145 while (n > 0) { 146 if (rs_have > 0) { 147 m = MIN(n, rs_have); 148 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 149 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 150 buf += m; 151 n -= m; 152 rs_have -= m; 153 } 154 if (rs_have == 0) 155 _rs_rekey(NULL, 0); 156 } 157 } 158 159 static inline void 160 _rs_random_u32(u_int32_t *val) 161 { 162 _rs_stir_if_needed(sizeof(*val)); 163 if (rs_have < sizeof(*val)) 164 _rs_rekey(NULL, 0); 165 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 166 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 167 rs_have -= sizeof(*val); 168 return; 169 } 170 171 u_int32_t 172 arc4random(void) 173 { 174 u_int32_t val; 175 176 _ARC4_LOCK(); 177 _rs_random_u32(&val); 178 _ARC4_UNLOCK(); 179 return val; 180 } 181 182 void 183 arc4random_buf(void *buf, size_t n) 184 { 185 _ARC4_LOCK(); 186 _rs_random_buf(buf, n); 187 _ARC4_UNLOCK(); 188 } 189 190 /* 191 * Calculate a uniformly distributed random number less than upper_bound 192 * avoiding "modulo bias". 193 * 194 * Uniformity is achieved by generating new random numbers until the one 195 * returned is outside the range [0, 2**32 % upper_bound). This 196 * guarantees the selected random number will be inside 197 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 198 * after reduction modulo upper_bound. 199 */ 200 u_int32_t 201 arc4random_uniform(u_int32_t upper_bound) 202 { 203 u_int32_t r, min; 204 205 if (upper_bound < 2) 206 return 0; 207 208 /* 2**32 % x == (2**32 - x) % x */ 209 min = -upper_bound % upper_bound; 210 211 /* 212 * This could theoretically loop forever but each retry has 213 * p > 0.5 (worst case, usually far better) of selecting a 214 * number inside the range we need, so it should rarely need 215 * to re-roll. 216 */ 217 for (;;) { 218 r = arc4random(); 219 if (r >= min) 220 break; 221 } 222 223 return r % upper_bound; 224 } 225