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 #ifdef HAVE_SYS_RANDOM_H 37 # include <sys/random.h> 38 #endif 39 40 #ifndef HAVE_ARC4RANDOM 41 42 #ifdef WITH_OPENSSL 43 #include <openssl/rand.h> 44 #include <openssl/err.h> 45 #endif 46 47 #include "log.h" 48 49 #define KEYSTREAM_ONLY 50 #include "chacha_private.h" 51 52 #ifdef __GNUC__ 53 #define inline __inline 54 #else /* !__GNUC__ */ 55 #define inline 56 #endif /* !__GNUC__ */ 57 58 /* OpenSSH isn't multithreaded */ 59 #define _ARC4_LOCK() 60 #define _ARC4_UNLOCK() 61 62 #define KEYSZ 32 63 #define IVSZ 8 64 #define BLOCKSZ 64 65 #define RSBUFSZ (16*BLOCKSZ) 66 static int rs_initialized; 67 static pid_t rs_stir_pid; 68 static chacha_ctx rs; /* chacha context for random keystream */ 69 static u_char rs_buf[RSBUFSZ]; /* keystream blocks */ 70 static size_t rs_have; /* valid bytes at end of rs_buf */ 71 static size_t rs_count; /* bytes till reseed */ 72 73 static inline void _rs_rekey(u_char *dat, size_t datlen); 74 75 static inline void 76 _rs_init(u_char *buf, size_t n) 77 { 78 if (n < KEYSZ + IVSZ) 79 return; 80 chacha_keysetup(&rs, buf, KEYSZ * 8, 0); 81 chacha_ivsetup(&rs, buf + KEYSZ); 82 } 83 84 #ifndef WITH_OPENSSL 85 # ifndef SSH_RANDOM_DEV 86 # define SSH_RANDOM_DEV "/dev/urandom" 87 # endif /* SSH_RANDOM_DEV */ 88 static void 89 getrnd(u_char *s, size_t len) 90 { 91 int fd, save_errno; 92 ssize_t r; 93 size_t o = 0; 94 95 #ifdef HAVE_GETRANDOM 96 if ((r = getrandom(s, len, 0)) > 0 && (size_t)r == len) 97 return; 98 #endif /* HAVE_GETRANDOM */ 99 100 if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1) { 101 save_errno = errno; 102 /* Try egd/prngd before giving up. */ 103 if (seed_from_prngd(s, len) == 0) 104 return; 105 fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, 106 strerror(save_errno)); 107 } 108 while (o < len) { 109 r = read(fd, s + o, len - o); 110 if (r < 0) { 111 if (errno == EAGAIN || errno == EINTR || 112 errno == EWOULDBLOCK) 113 continue; 114 fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno)); 115 } 116 o += r; 117 } 118 close(fd); 119 } 120 #endif /* WITH_OPENSSL */ 121 122 static void 123 _rs_stir(void) 124 { 125 u_char rnd[KEYSZ + IVSZ]; 126 127 #ifdef WITH_OPENSSL 128 if (RAND_bytes(rnd, sizeof(rnd)) <= 0) 129 fatal("Couldn't obtain random bytes (error 0x%lx)", 130 (unsigned long)ERR_get_error()); 131 #else 132 getrnd(rnd, sizeof(rnd)); 133 #endif 134 135 if (!rs_initialized) { 136 rs_initialized = 1; 137 _rs_init(rnd, sizeof(rnd)); 138 } else 139 _rs_rekey(rnd, sizeof(rnd)); 140 explicit_bzero(rnd, sizeof(rnd)); 141 142 /* invalidate rs_buf */ 143 rs_have = 0; 144 memset(rs_buf, 0, RSBUFSZ); 145 146 rs_count = 1600000; 147 } 148 149 static inline void 150 _rs_stir_if_needed(size_t len) 151 { 152 pid_t pid = getpid(); 153 154 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) { 155 rs_stir_pid = pid; 156 _rs_stir(); 157 } else 158 rs_count -= len; 159 } 160 161 static inline void 162 _rs_rekey(u_char *dat, size_t datlen) 163 { 164 #ifndef KEYSTREAM_ONLY 165 memset(rs_buf, 0,RSBUFSZ); 166 #endif 167 /* fill rs_buf with the keystream */ 168 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 169 /* mix in optional user provided data */ 170 if (dat) { 171 size_t i, m; 172 173 m = MIN(datlen, KEYSZ + IVSZ); 174 for (i = 0; i < m; i++) 175 rs_buf[i] ^= dat[i]; 176 } 177 /* immediately reinit for backtracking resistance */ 178 _rs_init(rs_buf, KEYSZ + IVSZ); 179 memset(rs_buf, 0, KEYSZ + IVSZ); 180 rs_have = RSBUFSZ - KEYSZ - IVSZ; 181 } 182 183 static inline void 184 _rs_random_buf(void *_buf, size_t n) 185 { 186 u_char *buf = (u_char *)_buf; 187 size_t m; 188 189 _rs_stir_if_needed(n); 190 while (n > 0) { 191 if (rs_have > 0) { 192 m = MIN(n, rs_have); 193 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 194 memset(rs_buf + RSBUFSZ - rs_have, 0, m); 195 buf += m; 196 n -= m; 197 rs_have -= m; 198 } 199 if (rs_have == 0) 200 _rs_rekey(NULL, 0); 201 } 202 } 203 204 static inline void 205 _rs_random_u32(u_int32_t *val) 206 { 207 _rs_stir_if_needed(sizeof(*val)); 208 if (rs_have < sizeof(*val)) 209 _rs_rekey(NULL, 0); 210 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 211 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 212 rs_have -= sizeof(*val); 213 return; 214 } 215 216 void 217 arc4random_stir(void) 218 { 219 _ARC4_LOCK(); 220 _rs_stir(); 221 _ARC4_UNLOCK(); 222 } 223 224 void 225 arc4random_addrandom(u_char *dat, int datlen) 226 { 227 int m; 228 229 _ARC4_LOCK(); 230 if (!rs_initialized) 231 _rs_stir(); 232 while (datlen > 0) { 233 m = MIN(datlen, KEYSZ + IVSZ); 234 _rs_rekey(dat, m); 235 dat += m; 236 datlen -= m; 237 } 238 _ARC4_UNLOCK(); 239 } 240 241 u_int32_t 242 arc4random(void) 243 { 244 u_int32_t val; 245 246 _ARC4_LOCK(); 247 _rs_random_u32(&val); 248 _ARC4_UNLOCK(); 249 return val; 250 } 251 252 /* 253 * If we are providing arc4random, then we can provide a more efficient 254 * arc4random_buf(). 255 */ 256 # ifndef HAVE_ARC4RANDOM_BUF 257 void 258 arc4random_buf(void *buf, size_t n) 259 { 260 _ARC4_LOCK(); 261 _rs_random_buf(buf, n); 262 _ARC4_UNLOCK(); 263 } 264 # endif /* !HAVE_ARC4RANDOM_BUF */ 265 #endif /* !HAVE_ARC4RANDOM */ 266 267 /* arc4random_buf() that uses platform arc4random() */ 268 #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) 269 void 270 arc4random_buf(void *_buf, size_t n) 271 { 272 size_t i; 273 u_int32_t r = 0; 274 char *buf = (char *)_buf; 275 276 for (i = 0; i < n; i++) { 277 if (i % 4 == 0) 278 r = arc4random(); 279 buf[i] = r & 0xff; 280 r >>= 8; 281 } 282 explicit_bzero(&r, sizeof(r)); 283 } 284 #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */ 285 286 #ifndef HAVE_ARC4RANDOM_UNIFORM 287 /* 288 * Calculate a uniformly distributed random number less than upper_bound 289 * avoiding "modulo bias". 290 * 291 * Uniformity is achieved by generating new random numbers until the one 292 * returned is outside the range [0, 2**32 % upper_bound). This 293 * guarantees the selected random number will be inside 294 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 295 * after reduction modulo upper_bound. 296 */ 297 u_int32_t 298 arc4random_uniform(u_int32_t upper_bound) 299 { 300 u_int32_t r, min; 301 302 if (upper_bound < 2) 303 return 0; 304 305 /* 2**32 % x == (2**32 - x) % x */ 306 min = -upper_bound % upper_bound; 307 308 /* 309 * This could theoretically loop forever but each retry has 310 * p > 0.5 (worst case, usually far better) of selecting a 311 * number inside the range we need, so it should rarely need 312 * to re-roll. 313 */ 314 for (;;) { 315 r = arc4random(); 316 if (r >= min) 317 break; 318 } 319 320 return r % upper_bound; 321 } 322 #endif /* !HAVE_ARC4RANDOM_UNIFORM */ 323 324 #if 0 325 /*-------- Test code for i386 --------*/ 326 #include <stdio.h> 327 #include <machine/pctr.h> 328 int 329 main(int argc, char **argv) 330 { 331 const int iter = 1000000; 332 int i; 333 pctrval v; 334 335 v = rdtsc(); 336 for (i = 0; i < iter; i++) 337 arc4random(); 338 v = rdtsc() - v; 339 v /= iter; 340 341 printf("%qd cycles\n", v); 342 exit(0); 343 } 344 #endif 345