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