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