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