1261287Sdes/* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */ 2261287Sdes 3261287Sdes/* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */ 4261287Sdes 5261287Sdes/* 6261287Sdes * Copyright (c) 1996, David Mazieres <dm@uun.org> 7261287Sdes * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 8261287Sdes * Copyright (c) 2013, Markus Friedl <markus@openbsd.org> 9261287Sdes * 10261287Sdes * Permission to use, copy, modify, and distribute this software for any 11261287Sdes * purpose with or without fee is hereby granted, provided that the above 12261287Sdes * copyright notice and this permission notice appear in all copies. 13261287Sdes * 14261287Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 15261287Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 16261287Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 17261287Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 18261287Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 19261287Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 20261287Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 21261287Sdes */ 22261287Sdes 23261287Sdes/* 24261287Sdes * ChaCha based random number generator for OpenBSD. 25261287Sdes */ 26261287Sdes 27261287Sdes#include "includes.h" 28261287Sdes 29295367Sdes#include <sys/types.h> 30295367Sdes 31295367Sdes#include <fcntl.h> 32261287Sdes#include <stdlib.h> 33261287Sdes#include <string.h> 34261287Sdes#include <unistd.h> 35261287Sdes 36261287Sdes#ifndef HAVE_ARC4RANDOM 37261287Sdes 38295367Sdes#ifdef WITH_OPENSSL 39261287Sdes#include <openssl/rand.h> 40261287Sdes#include <openssl/err.h> 41295367Sdes#endif 42261287Sdes 43261287Sdes#include "log.h" 44261287Sdes 45261287Sdes#define KEYSTREAM_ONLY 46261287Sdes#include "chacha_private.h" 47261287Sdes 48261287Sdes#ifdef __GNUC__ 49261287Sdes#define inline __inline 50261287Sdes#else /* !__GNUC__ */ 51261287Sdes#define inline 52261287Sdes#endif /* !__GNUC__ */ 53261287Sdes 54261287Sdes/* OpenSSH isn't multithreaded */ 55261287Sdes#define _ARC4_LOCK() 56261287Sdes#define _ARC4_UNLOCK() 57261287Sdes 58261287Sdes#define KEYSZ 32 59261287Sdes#define IVSZ 8 60261287Sdes#define BLOCKSZ 64 61261287Sdes#define RSBUFSZ (16*BLOCKSZ) 62261287Sdesstatic int rs_initialized; 63261287Sdesstatic pid_t rs_stir_pid; 64261287Sdesstatic chacha_ctx rs; /* chacha context for random keystream */ 65261287Sdesstatic u_char rs_buf[RSBUFSZ]; /* keystream blocks */ 66261287Sdesstatic size_t rs_have; /* valid bytes at end of rs_buf */ 67261287Sdesstatic size_t rs_count; /* bytes till reseed */ 68261287Sdes 69261287Sdesstatic inline void _rs_rekey(u_char *dat, size_t datlen); 70261287Sdes 71261287Sdesstatic inline void 72261287Sdes_rs_init(u_char *buf, size_t n) 73261287Sdes{ 74261287Sdes if (n < KEYSZ + IVSZ) 75261287Sdes return; 76261287Sdes chacha_keysetup(&rs, buf, KEYSZ * 8, 0); 77261287Sdes chacha_ivsetup(&rs, buf + KEYSZ); 78261287Sdes} 79261287Sdes 80295367Sdes#ifndef WITH_OPENSSL 81295367Sdes#define SSH_RANDOM_DEV "/dev/urandom" 82295367Sdes/* XXX use getrandom() if supported on Linux */ 83261287Sdesstatic void 84295367Sdesgetrnd(u_char *s, size_t len) 85295367Sdes{ 86295367Sdes int fd; 87295367Sdes ssize_t r; 88295367Sdes size_t o = 0; 89295367Sdes 90295367Sdes if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1) 91295367Sdes fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno)); 92295367Sdes while (o < len) { 93295367Sdes r = read(fd, s + o, len - o); 94295367Sdes if (r < 0) { 95295367Sdes if (errno == EAGAIN || errno == EINTR || 96295367Sdes errno == EWOULDBLOCK) 97295367Sdes continue; 98295367Sdes fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno)); 99295367Sdes } 100295367Sdes o += r; 101295367Sdes } 102295367Sdes close(fd); 103295367Sdes} 104295367Sdes#endif 105295367Sdes 106295367Sdesstatic void 107261287Sdes_rs_stir(void) 108261287Sdes{ 109261287Sdes u_char rnd[KEYSZ + IVSZ]; 110261287Sdes 111295367Sdes#ifdef WITH_OPENSSL 112261287Sdes if (RAND_bytes(rnd, sizeof(rnd)) <= 0) 113323124Sdes fatal("Couldn't obtain random bytes (error 0x%lx)", 114323124Sdes (unsigned long)ERR_get_error()); 115295367Sdes#else 116295367Sdes getrnd(rnd, sizeof(rnd)); 117295367Sdes#endif 118261287Sdes 119261287Sdes if (!rs_initialized) { 120261287Sdes rs_initialized = 1; 121261287Sdes _rs_init(rnd, sizeof(rnd)); 122261287Sdes } else 123261287Sdes _rs_rekey(rnd, sizeof(rnd)); 124295367Sdes explicit_bzero(rnd, sizeof(rnd)); 125261287Sdes 126261287Sdes /* invalidate rs_buf */ 127261287Sdes rs_have = 0; 128261287Sdes memset(rs_buf, 0, RSBUFSZ); 129261287Sdes 130261287Sdes rs_count = 1600000; 131261287Sdes} 132261287Sdes 133261287Sdesstatic inline void 134261287Sdes_rs_stir_if_needed(size_t len) 135261287Sdes{ 136261287Sdes pid_t pid = getpid(); 137261287Sdes 138261287Sdes if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) { 139261287Sdes rs_stir_pid = pid; 140261287Sdes _rs_stir(); 141261287Sdes } else 142261287Sdes rs_count -= len; 143261287Sdes} 144261287Sdes 145261287Sdesstatic inline void 146261287Sdes_rs_rekey(u_char *dat, size_t datlen) 147261287Sdes{ 148261287Sdes#ifndef KEYSTREAM_ONLY 149261287Sdes memset(rs_buf, 0,RSBUFSZ); 150261287Sdes#endif 151261287Sdes /* fill rs_buf with the keystream */ 152261287Sdes chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ); 153261287Sdes /* mix in optional user provided data */ 154261287Sdes if (dat) { 155261287Sdes size_t i, m; 156261287Sdes 157261287Sdes m = MIN(datlen, KEYSZ + IVSZ); 158261287Sdes for (i = 0; i < m; i++) 159261287Sdes rs_buf[i] ^= dat[i]; 160261287Sdes } 161261287Sdes /* immediately reinit for backtracking resistance */ 162261287Sdes _rs_init(rs_buf, KEYSZ + IVSZ); 163261287Sdes memset(rs_buf, 0, KEYSZ + IVSZ); 164261287Sdes rs_have = RSBUFSZ - KEYSZ - IVSZ; 165261287Sdes} 166261287Sdes 167261287Sdesstatic inline void 168261287Sdes_rs_random_buf(void *_buf, size_t n) 169261287Sdes{ 170261287Sdes u_char *buf = (u_char *)_buf; 171261287Sdes size_t m; 172261287Sdes 173261287Sdes _rs_stir_if_needed(n); 174261287Sdes while (n > 0) { 175261287Sdes if (rs_have > 0) { 176261287Sdes m = MIN(n, rs_have); 177261287Sdes memcpy(buf, rs_buf + RSBUFSZ - rs_have, m); 178261287Sdes memset(rs_buf + RSBUFSZ - rs_have, 0, m); 179261287Sdes buf += m; 180261287Sdes n -= m; 181261287Sdes rs_have -= m; 182261287Sdes } 183261287Sdes if (rs_have == 0) 184261287Sdes _rs_rekey(NULL, 0); 185261287Sdes } 186261287Sdes} 187261287Sdes 188261287Sdesstatic inline void 189261287Sdes_rs_random_u32(u_int32_t *val) 190261287Sdes{ 191261287Sdes _rs_stir_if_needed(sizeof(*val)); 192261287Sdes if (rs_have < sizeof(*val)) 193261287Sdes _rs_rekey(NULL, 0); 194261287Sdes memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val)); 195261287Sdes memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val)); 196261287Sdes rs_have -= sizeof(*val); 197261287Sdes return; 198261287Sdes} 199261287Sdes 200261287Sdesvoid 201261287Sdesarc4random_stir(void) 202261287Sdes{ 203261287Sdes _ARC4_LOCK(); 204261287Sdes _rs_stir(); 205261287Sdes _ARC4_UNLOCK(); 206261287Sdes} 207261287Sdes 208261287Sdesvoid 209261287Sdesarc4random_addrandom(u_char *dat, int datlen) 210261287Sdes{ 211261287Sdes int m; 212261287Sdes 213261287Sdes _ARC4_LOCK(); 214261287Sdes if (!rs_initialized) 215261287Sdes _rs_stir(); 216261287Sdes while (datlen > 0) { 217261287Sdes m = MIN(datlen, KEYSZ + IVSZ); 218261287Sdes _rs_rekey(dat, m); 219261287Sdes dat += m; 220261287Sdes datlen -= m; 221261287Sdes } 222261287Sdes _ARC4_UNLOCK(); 223261287Sdes} 224261287Sdes 225261287Sdesu_int32_t 226261287Sdesarc4random(void) 227261287Sdes{ 228261287Sdes u_int32_t val; 229261287Sdes 230261287Sdes _ARC4_LOCK(); 231261287Sdes _rs_random_u32(&val); 232261287Sdes _ARC4_UNLOCK(); 233261287Sdes return val; 234261287Sdes} 235261287Sdes 236261287Sdes/* 237261287Sdes * If we are providing arc4random, then we can provide a more efficient 238261287Sdes * arc4random_buf(). 239261287Sdes */ 240261287Sdes# ifndef HAVE_ARC4RANDOM_BUF 241261287Sdesvoid 242261287Sdesarc4random_buf(void *buf, size_t n) 243261287Sdes{ 244261287Sdes _ARC4_LOCK(); 245261287Sdes _rs_random_buf(buf, n); 246261287Sdes _ARC4_UNLOCK(); 247261287Sdes} 248261287Sdes# endif /* !HAVE_ARC4RANDOM_BUF */ 249261287Sdes#endif /* !HAVE_ARC4RANDOM */ 250261287Sdes 251261287Sdes/* arc4random_buf() that uses platform arc4random() */ 252261287Sdes#if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) 253261287Sdesvoid 254261287Sdesarc4random_buf(void *_buf, size_t n) 255261287Sdes{ 256261287Sdes size_t i; 257261287Sdes u_int32_t r = 0; 258261287Sdes char *buf = (char *)_buf; 259261287Sdes 260261287Sdes for (i = 0; i < n; i++) { 261261287Sdes if (i % 4 == 0) 262261287Sdes r = arc4random(); 263261287Sdes buf[i] = r & 0xff; 264261287Sdes r >>= 8; 265261287Sdes } 266295367Sdes explicit_bzero(&r, sizeof(r)); 267261287Sdes} 268261287Sdes#endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */ 269261287Sdes 270261287Sdes#ifndef HAVE_ARC4RANDOM_UNIFORM 271261287Sdes/* 272261287Sdes * Calculate a uniformly distributed random number less than upper_bound 273261287Sdes * avoiding "modulo bias". 274261287Sdes * 275261287Sdes * Uniformity is achieved by generating new random numbers until the one 276261287Sdes * returned is outside the range [0, 2**32 % upper_bound). This 277261287Sdes * guarantees the selected random number will be inside 278261287Sdes * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 279261287Sdes * after reduction modulo upper_bound. 280261287Sdes */ 281261287Sdesu_int32_t 282261287Sdesarc4random_uniform(u_int32_t upper_bound) 283261287Sdes{ 284261287Sdes u_int32_t r, min; 285261287Sdes 286261287Sdes if (upper_bound < 2) 287261287Sdes return 0; 288261287Sdes 289261287Sdes /* 2**32 % x == (2**32 - x) % x */ 290261287Sdes min = -upper_bound % upper_bound; 291261287Sdes 292261287Sdes /* 293261287Sdes * This could theoretically loop forever but each retry has 294261287Sdes * p > 0.5 (worst case, usually far better) of selecting a 295261287Sdes * number inside the range we need, so it should rarely need 296261287Sdes * to re-roll. 297261287Sdes */ 298261287Sdes for (;;) { 299261287Sdes r = arc4random(); 300261287Sdes if (r >= min) 301261287Sdes break; 302261287Sdes } 303261287Sdes 304261287Sdes return r % upper_bound; 305261287Sdes} 306261287Sdes#endif /* !HAVE_ARC4RANDOM_UNIFORM */ 307261287Sdes 308261287Sdes#if 0 309261287Sdes/*-------- Test code for i386 --------*/ 310261287Sdes#include <stdio.h> 311261287Sdes#include <machine/pctr.h> 312261287Sdesint 313261287Sdesmain(int argc, char **argv) 314261287Sdes{ 315261287Sdes const int iter = 1000000; 316261287Sdes int i; 317261287Sdes pctrval v; 318261287Sdes 319261287Sdes v = rdtsc(); 320261287Sdes for (i = 0; i < iter; i++) 321261287Sdes arc4random(); 322261287Sdes v = rdtsc() - v; 323261287Sdes v /= iter; 324261287Sdes 325261287Sdes printf("%qd cycles\n", v); 326261287Sdes exit(0); 327261287Sdes} 328261287Sdes#endif 329