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