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