172071196SDamien Miller /* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */
272071196SDamien Miller 
391593100SDamien Miller /*	$OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $	*/
491593100SDamien Miller 
591593100SDamien Miller /*
691593100SDamien Miller  * Copyright (c) 1996, David Mazieres <dm@uun.org>
791593100SDamien Miller  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
891593100SDamien Miller  * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
991593100SDamien Miller  *
1091593100SDamien Miller  * Permission to use, copy, modify, and distribute this software for any
1191593100SDamien Miller  * purpose with or without fee is hereby granted, provided that the above
1291593100SDamien Miller  * copyright notice and this permission notice appear in all copies.
1391593100SDamien Miller  *
1491593100SDamien Miller  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
1591593100SDamien Miller  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
1691593100SDamien Miller  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
1791593100SDamien Miller  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
1891593100SDamien Miller  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
1991593100SDamien Miller  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
2091593100SDamien Miller  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
2191593100SDamien Miller  */
2291593100SDamien Miller 
2391593100SDamien Miller /*
2491593100SDamien Miller  * ChaCha based random number generator for OpenBSD.
2591593100SDamien Miller  */
2691593100SDamien Miller 
2772071196SDamien Miller #include "includes.h"
2872071196SDamien Miller 
2972ef7c14SDamien Miller #include <sys/types.h>
3072ef7c14SDamien Miller 
3172ef7c14SDamien Miller #include <fcntl.h>
3291593100SDamien Miller #include <stdlib.h>
3391593100SDamien Miller #include <string.h>
3491593100SDamien Miller #include <unistd.h>
3572071196SDamien Miller 
36*afa6e79bSDamien Miller #ifdef HAVE_SYS_RANDOM_H
37*afa6e79bSDamien Miller # include <sys/random.h>
38*afa6e79bSDamien Miller #endif
39*afa6e79bSDamien Miller 
4072071196SDamien Miller #ifndef HAVE_ARC4RANDOM
4172071196SDamien Miller 
4272ef7c14SDamien Miller #ifdef WITH_OPENSSL
4372071196SDamien Miller #include <openssl/rand.h>
4472071196SDamien Miller #include <openssl/err.h>
4572ef7c14SDamien Miller #endif
4672071196SDamien Miller 
4772071196SDamien Miller #include "log.h"
4891593100SDamien Miller 
4991593100SDamien Miller #define KEYSTREAM_ONLY
5091593100SDamien Miller #include "chacha_private.h"
5191593100SDamien Miller 
5291593100SDamien Miller #ifdef __GNUC__
5391593100SDamien Miller #define inline __inline
5491593100SDamien Miller #else				/* !__GNUC__ */
5591593100SDamien Miller #define inline
5691593100SDamien Miller #endif				/* !__GNUC__ */
5791593100SDamien Miller 
5872071196SDamien Miller /* OpenSSH isn't multithreaded */
5972071196SDamien Miller #define _ARC4_LOCK()
6072071196SDamien Miller #define _ARC4_UNLOCK()
6172071196SDamien Miller 
6291593100SDamien Miller #define KEYSZ	32
6391593100SDamien Miller #define IVSZ	8
6491593100SDamien Miller #define BLOCKSZ	64
6591593100SDamien Miller #define RSBUFSZ	(16*BLOCKSZ)
6691593100SDamien Miller static int rs_initialized;
6791593100SDamien Miller static pid_t rs_stir_pid;
6891593100SDamien Miller static chacha_ctx rs;		/* chacha context for random keystream */
6991593100SDamien Miller static u_char rs_buf[RSBUFSZ];	/* keystream blocks */
7091593100SDamien Miller static size_t rs_have;		/* valid bytes at end of rs_buf */
7191593100SDamien Miller static size_t rs_count;		/* bytes till reseed */
7291593100SDamien Miller 
7391593100SDamien Miller static inline void _rs_rekey(u_char *dat, size_t datlen);
7491593100SDamien Miller 
7591593100SDamien Miller static inline void
_rs_init(u_char * buf,size_t n)7691593100SDamien Miller _rs_init(u_char *buf, size_t n)
7791593100SDamien Miller {
7891593100SDamien Miller 	if (n < KEYSZ + IVSZ)
7991593100SDamien Miller 		return;
8091593100SDamien Miller 	chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
8191593100SDamien Miller 	chacha_ivsetup(&rs, buf + KEYSZ);
8291593100SDamien Miller }
8391593100SDamien Miller 
8472ef7c14SDamien Miller #ifndef WITH_OPENSSL
85*afa6e79bSDamien Miller # ifndef SSH_RANDOM_DEV
8672ef7c14SDamien Miller #  define SSH_RANDOM_DEV "/dev/urandom"
87*afa6e79bSDamien Miller # endif /* SSH_RANDOM_DEV */
8872ef7c14SDamien Miller static void
getrnd(u_char * s,size_t len)8972ef7c14SDamien Miller getrnd(u_char *s, size_t len)
9072ef7c14SDamien Miller {
9172ef7c14SDamien Miller 	int fd;
9272ef7c14SDamien Miller 	ssize_t r;
9372ef7c14SDamien Miller 	size_t o = 0;
9472ef7c14SDamien Miller 
95*afa6e79bSDamien Miller #ifdef HAVE_GETRANDOM
96*afa6e79bSDamien Miller 	if ((r = getrandom(s, len, 0)) > 0 && (size_t)r == len)
97*afa6e79bSDamien Miller 		return;
98*afa6e79bSDamien Miller #endif /* HAVE_GETRANDOM */
99*afa6e79bSDamien Miller 
10072ef7c14SDamien Miller 	if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
10172ef7c14SDamien Miller 		fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
10272ef7c14SDamien Miller 	while (o < len) {
10372ef7c14SDamien Miller 		r = read(fd, s + o, len - o);
10472ef7c14SDamien Miller 		if (r < 0) {
10572ef7c14SDamien Miller 			if (errno == EAGAIN || errno == EINTR ||
10672ef7c14SDamien Miller 			    errno == EWOULDBLOCK)
10772ef7c14SDamien Miller 				continue;
10872ef7c14SDamien Miller 			fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
10972ef7c14SDamien Miller 		}
11072ef7c14SDamien Miller 		o += r;
11172ef7c14SDamien Miller 	}
11272ef7c14SDamien Miller 	close(fd);
11372ef7c14SDamien Miller }
114*afa6e79bSDamien Miller #endif /* WITH_OPENSSL */
11572ef7c14SDamien Miller 
11691593100SDamien Miller static void
_rs_stir(void)11791593100SDamien Miller _rs_stir(void)
11891593100SDamien Miller {
11991593100SDamien Miller 	u_char rnd[KEYSZ + IVSZ];
12091593100SDamien Miller 
12172ef7c14SDamien Miller #ifdef WITH_OPENSSL
12272071196SDamien Miller 	if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
1234a984fd3SDamien Miller 		fatal("Couldn't obtain random bytes (error 0x%lx)",
1244a984fd3SDamien Miller 		    (unsigned long)ERR_get_error());
12572ef7c14SDamien Miller #else
12672ef7c14SDamien Miller 	getrnd(rnd, sizeof(rnd));
12772ef7c14SDamien Miller #endif
12891593100SDamien Miller 
12991593100SDamien Miller 	if (!rs_initialized) {
13091593100SDamien Miller 		rs_initialized = 1;
13191593100SDamien Miller 		_rs_init(rnd, sizeof(rnd));
13291593100SDamien Miller 	} else
13391593100SDamien Miller 		_rs_rekey(rnd, sizeof(rnd));
1342a8699f3SDamien Miller 	explicit_bzero(rnd, sizeof(rnd));
13591593100SDamien Miller 
13691593100SDamien Miller 	/* invalidate rs_buf */
13791593100SDamien Miller 	rs_have = 0;
13891593100SDamien Miller 	memset(rs_buf, 0, RSBUFSZ);
13991593100SDamien Miller 
14091593100SDamien Miller 	rs_count = 1600000;
14191593100SDamien Miller }
14291593100SDamien Miller 
14391593100SDamien Miller static inline void
_rs_stir_if_needed(size_t len)14491593100SDamien Miller _rs_stir_if_needed(size_t len)
14591593100SDamien Miller {
14691593100SDamien Miller 	pid_t pid = getpid();
14791593100SDamien Miller 
14891593100SDamien Miller 	if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
14991593100SDamien Miller 		rs_stir_pid = pid;
15091593100SDamien Miller 		_rs_stir();
15191593100SDamien Miller 	} else
15291593100SDamien Miller 		rs_count -= len;
15391593100SDamien Miller }
15491593100SDamien Miller 
15591593100SDamien Miller static inline void
_rs_rekey(u_char * dat,size_t datlen)15691593100SDamien Miller _rs_rekey(u_char *dat, size_t datlen)
15791593100SDamien Miller {
15891593100SDamien Miller #ifndef KEYSTREAM_ONLY
15991593100SDamien Miller 	memset(rs_buf, 0,RSBUFSZ);
16091593100SDamien Miller #endif
16191593100SDamien Miller 	/* fill rs_buf with the keystream */
16291593100SDamien Miller 	chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
16391593100SDamien Miller 	/* mix in optional user provided data */
16491593100SDamien Miller 	if (dat) {
16591593100SDamien Miller 		size_t i, m;
16691593100SDamien Miller 
16791593100SDamien Miller 		m = MIN(datlen, KEYSZ + IVSZ);
16891593100SDamien Miller 		for (i = 0; i < m; i++)
16991593100SDamien Miller 			rs_buf[i] ^= dat[i];
17091593100SDamien Miller 	}
17191593100SDamien Miller 	/* immediately reinit for backtracking resistance */
17291593100SDamien Miller 	_rs_init(rs_buf, KEYSZ + IVSZ);
17391593100SDamien Miller 	memset(rs_buf, 0, KEYSZ + IVSZ);
17491593100SDamien Miller 	rs_have = RSBUFSZ - KEYSZ - IVSZ;
17591593100SDamien Miller }
17691593100SDamien Miller 
17791593100SDamien Miller static inline void
_rs_random_buf(void * _buf,size_t n)17891593100SDamien Miller _rs_random_buf(void *_buf, size_t n)
17991593100SDamien Miller {
18091593100SDamien Miller 	u_char *buf = (u_char *)_buf;
18191593100SDamien Miller 	size_t m;
18291593100SDamien Miller 
18391593100SDamien Miller 	_rs_stir_if_needed(n);
18491593100SDamien Miller 	while (n > 0) {
18591593100SDamien Miller 		if (rs_have > 0) {
18691593100SDamien Miller 			m = MIN(n, rs_have);
18791593100SDamien Miller 			memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
18891593100SDamien Miller 			memset(rs_buf + RSBUFSZ - rs_have, 0, m);
18991593100SDamien Miller 			buf += m;
19091593100SDamien Miller 			n -= m;
19191593100SDamien Miller 			rs_have -= m;
19291593100SDamien Miller 		}
19391593100SDamien Miller 		if (rs_have == 0)
19491593100SDamien Miller 			_rs_rekey(NULL, 0);
19591593100SDamien Miller 	}
19691593100SDamien Miller }
19791593100SDamien Miller 
19891593100SDamien Miller static inline void
_rs_random_u32(u_int32_t * val)19991593100SDamien Miller _rs_random_u32(u_int32_t *val)
20091593100SDamien Miller {
20191593100SDamien Miller 	_rs_stir_if_needed(sizeof(*val));
20291593100SDamien Miller 	if (rs_have < sizeof(*val))
20391593100SDamien Miller 		_rs_rekey(NULL, 0);
20491593100SDamien Miller 	memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
20591593100SDamien Miller 	memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
20691593100SDamien Miller 	rs_have -= sizeof(*val);
20791593100SDamien Miller 	return;
20891593100SDamien Miller }
20991593100SDamien Miller 
21091593100SDamien Miller void
arc4random_stir(void)21191593100SDamien Miller arc4random_stir(void)
21291593100SDamien Miller {
21391593100SDamien Miller 	_ARC4_LOCK();
21491593100SDamien Miller 	_rs_stir();
21591593100SDamien Miller 	_ARC4_UNLOCK();
21691593100SDamien Miller }
21791593100SDamien Miller 
21891593100SDamien Miller void
arc4random_addrandom(u_char * dat,int datlen)21991593100SDamien Miller arc4random_addrandom(u_char *dat, int datlen)
22091593100SDamien Miller {
22191593100SDamien Miller 	int m;
22291593100SDamien Miller 
22391593100SDamien Miller 	_ARC4_LOCK();
22491593100SDamien Miller 	if (!rs_initialized)
22591593100SDamien Miller 		_rs_stir();
22691593100SDamien Miller 	while (datlen > 0) {
22791593100SDamien Miller 		m = MIN(datlen, KEYSZ + IVSZ);
22891593100SDamien Miller 		_rs_rekey(dat, m);
22991593100SDamien Miller 		dat += m;
23091593100SDamien Miller 		datlen -= m;
23191593100SDamien Miller 	}
23291593100SDamien Miller 	_ARC4_UNLOCK();
23391593100SDamien Miller }
23491593100SDamien Miller 
23591593100SDamien Miller u_int32_t
arc4random(void)23691593100SDamien Miller arc4random(void)
23791593100SDamien Miller {
23891593100SDamien Miller 	u_int32_t val;
23991593100SDamien Miller 
24091593100SDamien Miller 	_ARC4_LOCK();
24191593100SDamien Miller 	_rs_random_u32(&val);
24291593100SDamien Miller 	_ARC4_UNLOCK();
24391593100SDamien Miller 	return val;
24491593100SDamien Miller }
24591593100SDamien Miller 
24672071196SDamien Miller /*
24772071196SDamien Miller  * If we are providing arc4random, then we can provide a more efficient
24872071196SDamien Miller  * arc4random_buf().
24972071196SDamien Miller  */
25072071196SDamien Miller # ifndef HAVE_ARC4RANDOM_BUF
25191593100SDamien Miller void
arc4random_buf(void * buf,size_t n)25291593100SDamien Miller arc4random_buf(void *buf, size_t n)
25391593100SDamien Miller {
25491593100SDamien Miller 	_ARC4_LOCK();
25591593100SDamien Miller 	_rs_random_buf(buf, n);
25691593100SDamien Miller 	_ARC4_UNLOCK();
25791593100SDamien Miller }
25872071196SDamien Miller # endif /* !HAVE_ARC4RANDOM_BUF */
25972071196SDamien Miller #endif /* !HAVE_ARC4RANDOM */
26091593100SDamien Miller 
26172071196SDamien Miller /* arc4random_buf() that uses platform arc4random() */
26272071196SDamien Miller #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
26372071196SDamien Miller void
arc4random_buf(void * _buf,size_t n)26472071196SDamien Miller arc4random_buf(void *_buf, size_t n)
26572071196SDamien Miller {
26672071196SDamien Miller 	size_t i;
26772071196SDamien Miller 	u_int32_t r = 0;
26872071196SDamien Miller 	char *buf = (char *)_buf;
26972071196SDamien Miller 
27072071196SDamien Miller 	for (i = 0; i < n; i++) {
27172071196SDamien Miller 		if (i % 4 == 0)
27272071196SDamien Miller 			r = arc4random();
27372071196SDamien Miller 		buf[i] = r & 0xff;
27472071196SDamien Miller 		r >>= 8;
27572071196SDamien Miller 	}
276eb012ac5SDarren Tucker 	explicit_bzero(&r, sizeof(r));
27772071196SDamien Miller }
27872071196SDamien Miller #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
27972071196SDamien Miller 
28072071196SDamien Miller #ifndef HAVE_ARC4RANDOM_UNIFORM
28191593100SDamien Miller /*
28291593100SDamien Miller  * Calculate a uniformly distributed random number less than upper_bound
28391593100SDamien Miller  * avoiding "modulo bias".
28491593100SDamien Miller  *
28591593100SDamien Miller  * Uniformity is achieved by generating new random numbers until the one
28691593100SDamien Miller  * returned is outside the range [0, 2**32 % upper_bound).  This
28791593100SDamien Miller  * guarantees the selected random number will be inside
28891593100SDamien Miller  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
28991593100SDamien Miller  * after reduction modulo upper_bound.
29091593100SDamien Miller  */
29191593100SDamien Miller u_int32_t
arc4random_uniform(u_int32_t upper_bound)29291593100SDamien Miller arc4random_uniform(u_int32_t upper_bound)
29391593100SDamien Miller {
29491593100SDamien Miller 	u_int32_t r, min;
29591593100SDamien Miller 
29691593100SDamien Miller 	if (upper_bound < 2)
29791593100SDamien Miller 		return 0;
29891593100SDamien Miller 
29991593100SDamien Miller 	/* 2**32 % x == (2**32 - x) % x */
30091593100SDamien Miller 	min = -upper_bound % upper_bound;
30191593100SDamien Miller 
30291593100SDamien Miller 	/*
30391593100SDamien Miller 	 * This could theoretically loop forever but each retry has
30491593100SDamien Miller 	 * p > 0.5 (worst case, usually far better) of selecting a
30591593100SDamien Miller 	 * number inside the range we need, so it should rarely need
30691593100SDamien Miller 	 * to re-roll.
30791593100SDamien Miller 	 */
30891593100SDamien Miller 	for (;;) {
30991593100SDamien Miller 		r = arc4random();
31091593100SDamien Miller 		if (r >= min)
31191593100SDamien Miller 			break;
31291593100SDamien Miller 	}
31391593100SDamien Miller 
31491593100SDamien Miller 	return r % upper_bound;
31591593100SDamien Miller }
31672071196SDamien Miller #endif /* !HAVE_ARC4RANDOM_UNIFORM */
31791593100SDamien Miller 
31891593100SDamien Miller #if 0
31991593100SDamien Miller /*-------- Test code for i386 --------*/
32091593100SDamien Miller #include <stdio.h>
32191593100SDamien Miller #include <machine/pctr.h>
32291593100SDamien Miller int
32391593100SDamien Miller main(int argc, char **argv)
32491593100SDamien Miller {
32591593100SDamien Miller 	const int iter = 1000000;
32691593100SDamien Miller 	int     i;
32791593100SDamien Miller 	pctrval v;
32891593100SDamien Miller 
32991593100SDamien Miller 	v = rdtsc();
33091593100SDamien Miller 	for (i = 0; i < iter; i++)
33191593100SDamien Miller 		arc4random();
33291593100SDamien Miller 	v = rdtsc() - v;
33391593100SDamien Miller 	v /= iter;
33491593100SDamien Miller 
33591593100SDamien Miller 	printf("%qd cycles\n", v);
33691593100SDamien Miller 	exit(0);
33791593100SDamien Miller }
33891593100SDamien Miller #endif
339