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