Differential D16760 Diff 46919 lib/libc/gen/arc4random.c

Changeset View

Standalone View

lib/libc/gen/arc4random.c

Property	Old Value	New Value
svn:mime-type	null	text/plain \ No newline at end of property

	/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */			/* $OpenBSD: arc4random.c,v 1.54 2015/09/13 08:31:47 guenther Exp $ */

	/*			/*
	* Copyright (c) 1996, David Mazieres <dm@uun.org>			* Copyright (c) 1996, David Mazieres <dm@uun.org>
	* Copyright (c) 2008, Damien Miller <djm@openbsd.org>			* Copyright (c) 2008, Damien Miller <djm@openbsd.org>
				* Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
				* Copyright (c) 2014, Theo de Raadt <deraadt@openbsd.org>
	*			*
	* Permission to use, copy, modify, and distribute this software for any			* Permission to use, copy, modify, and distribute this software for any
	* purpose with or without fee is hereby granted, provided that the above			* purpose with or without fee is hereby granted, provided that the above
	* copyright notice and this permission notice appear in all copies.			* copyright notice and this permission notice appear in all copies.
	*			*
	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES			* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF			* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR			* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES			* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN			* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF			* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.			* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	*/			*/

	/*			/*
	* Arc4 random number generator for OpenBSD.			* ChaCha based random number generator for OpenBSD.
	*
	* This code is derived from section 17.1 of Applied Cryptography,
	* second edition, which describes a stream cipher allegedly
	* compatible with RSA Labs "RC4" cipher (the actual description of
	* which is a trade secret). The same algorithm is used as a stream
	* cipher called "arcfour" in Tatu Ylonen's ssh package.
	*
	* RC4 is a registered trademark of RSA Laboratories.
	*/			*/

	#include <sys/cdefs.h>			#include <sys/cdefs.h>
	__FBSDID("$FreeBSD$");			__FBSDID("$FreeBSD$");

	#include "namespace.h"			#include "namespace.h"
	#include <fcntl.h>			#include <fcntl.h>
	#include <limits.h>			#include <limits.h>
				#include <pthread.h>
				#include <signal.h>
				#include <stdint.h>
	#include <stdlib.h>			#include <stdlib.h>
				#include <string.h>
	#include <unistd.h>			#include <unistd.h>
	#include <sys/param.h>			#include <sys/types.h>
	#include <sys/sysctl.h>
	#include <sys/time.h>			#include <sys/time.h>
	#include <pthread.h>

	#include "libc_private.h"			#include "libc_private.h"
	#include "un-namespace.h"			#include "un-namespace.h"

	#ifdef __GNUC__			#define KEYSTREAM_ONLY
				#include "chacha.c"

				#define minimum(a, b) ((a) < (b) ? (a) : (b))
				cemUnsubmitted Done Inline Actions `MIN()`? cem: `MIN()`?
				delphijAuthorUnsubmitted Done Inline Actions The goal is to minimize changes to this file and not diverge from OpenBSD. Their reasoning was at https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random.c?rev=1.53&content-type=text/x-cvsweb-markup . delphij: The goal is to minimize changes to this file and not diverge from OpenBSD. Their reasoning was…
				cemUnsubmitted Done Inline Actions MIN() is a different name than min(), and regardless we don't build FreeBSD with MSVC. cem: MIN() is a different name than min(), and regardless we don't build FreeBSD with MSVC.

				#if defined(__GNUC__) \|\| defined(_MSC_VER)
	#define inline __inline			#define inline __inline
	#else /* !__GNUC__ */			#else /* __GNUC__ \|\| _MSC_VER */
	#define inline			#define inline
	#endif /* !__GNUC__ */			#endif /* !__GNUC__ && !_MSC_VER */
				cemUnsubmitted Done Inline Actions What is this trying to accomplish? cem: What is this trying to accomplish?
				cemUnsubmitted Not Done Inline Actions Hm, I'm still not sure what the inline ifdefs are for. cem: Hm, I'm still not sure what the inline ifdefs are for.

	struct arc4_stream {			#define KEYSZ 32
	u_int8_t i;			#define IVSZ 8
	u_int8_t j;			#define BLOCKSZ 64
	u_int8_t s[256];			#define RSBUFSZ (16*BLOCKSZ)
	};

	static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;			/* Marked INHERIT_ZERO, so zero'd out in fork children. */
				static struct _rs {
				size_t rs_have; /* valid bytes at end of rs_buf */
				size_t rs_count; /* bytes till reseed */
				} *rs;
				devnexen_gmail.comUnsubmitted Done Inline Actions INHERIT_ZERO devnexen_gmail.com: INHERIT_ZERO

	#define KEYSIZE 128			/* Maybe be preserved in fork children, if _rs_allocate() decides. */
	#define _ARC4_LOCK() \			static struct _rsx {
	do { \			chacha_ctx rs_chacha; /* chacha context for random keystream */
	if (__isthreaded) \			u_char rs_buf[RSBUFSZ]; /* keystream blocks */
	_pthread_mutex_lock(&arc4random_mtx); \			} *rsx;
	} while (0)

	#define _ARC4_UNLOCK() \			static inline int _rs_allocate(struct _rs , struct _rsx );
	do { \			static inline void _rs_forkdetect(void);
	if (__isthreaded) \			#include "arc4random.h"
				cemUnsubmitted Done Inline Actions This is a very odd pattern. Why is any of the contents of arc4random.h in a header instead of in this file? cem: This is a very odd pattern. Why is any of the contents of arc4random.h in a header instead of…
	_pthread_mutex_unlock(&arc4random_mtx); \
	} while (0)

	static int rs_initialized;			static inline void _rs_rekey(u_char *dat, size_t datlen);
	static struct arc4_stream rs;
	static pid_t arc4_stir_pid;
	static int arc4_count;

	extern int __sysctl(int name, u_int namelen, void oldp, size_t *oldlenp,
	void *newp, size_t newlen);

	static inline u_int8_t arc4_getbyte(void);
	static void arc4_stir(void);

	static inline void			static inline void
	arc4_init(void)			_rs_init(u_char *buf, size_t n)
	{			{
	int n;			if (n < KEYSZ + IVSZ)
				return;

	for (n = 0; n < 256; n++)			if (rs == NULL) {
	rs.s[n] = n;			if (_rs_allocate(&rs, &rsx) == -1)
	rs.i = 0;			abort();
	rs.j = 0;
	}			}

	static inline void			chacha_keysetup(&rsx->rs_chacha, buf, KEYSZ * 8);
	arc4_addrandom(u_char *dat, int datlen)			chacha_ivsetup(&rsx->rs_chacha, buf + KEYSZ, NULL);
	{
	int n;
	u_int8_t si;

	rs.i--;
	for (n = 0; n < 256; n++) {
	rs.i = (rs.i + 1);
	si = rs.s[rs.i];
	rs.j = (rs.j + si + dat[n % datlen]);
	rs.s[rs.i] = rs.s[rs.j];
	rs.s[rs.j] = si;
	}			}
	rs.j = rs.i;
	}

	size_t			static void
	__arc4_sysctl(u_char *buf, size_t size)			_rs_stir(void)
	{			{
	int mib[2];			u_char rnd[KEYSZ + IVSZ];
	size_t len, done;

	mib[0] = CTL_KERN;			if (getentropy(rnd, sizeof rnd) == -1)
	mib[1] = KERN_ARND;			_getentropy_fail();
	done = 0;

	do {			if (!rs)
	len = size;			_rs_init(rnd, sizeof(rnd));
	if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)			else
	return (done);			_rs_rekey(rnd, sizeof(rnd));
	done += len;			explicit_bzero(rnd, sizeof(rnd)); /* discard source seed */
	buf += len;
	size -= len;
	} while (size > 0);

	return (done);			/* invalidate rs_buf */
				rs->rs_have = 0;
				memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));

				rs->rs_count = 1600000;
	}			}

	static void			static inline void
	arc4_stir(void)			_rs_stir_if_needed(size_t len)
	{			{
	u_char rdat[KEYSIZE];			_rs_forkdetect();
	int i;			if (!rs \|\| rs->rs_count <= len)
				_rs_stir();
	if (!rs_initialized) {			if (rs->rs_count <= len)
	arc4_init();			rs->rs_count = 0;
	rs_initialized = 1;			else
				rs->rs_count -= len;
	}			}
	if (__arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) {
	/*
	* The sysctl cannot fail. If it does fail on some FreeBSD
	* derivative or after some future change, just abort so that
	* the problem will be found and fixed. abort is not normally
	* suitable for a library but makes sense here.
	*/
	abort();
	}

	arc4_addrandom(rdat, KEYSIZE);			static inline void
				_rs_rekey(u_char *dat, size_t datlen)
	/*
	* Discard early keystream, as per recommendations in:
	* "(Not So) Random Shuffles of RC4" by Ilya Mironov.
	*/
	for (i = 0; i < 3072; i++)
	(void)arc4_getbyte();
	arc4_count = 1600000;
	}

	static void
	arc4_stir_if_needed(void)
	{			{
	pid_t pid = getpid();			#ifndef KEYSTREAM_ONLY
				memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf));
				#endif
				/* fill rs_buf with the keystream */
				chacha_encrypt_bytes(&rsx->rs_chacha, rsx->rs_buf,
				rsx->rs_buf, sizeof(rsx->rs_buf));
				/* mix in optional user provided data */
				if (dat) {
				size_t i, m;

	if (arc4_count <= 0 \|\| !rs_initialized \|\| arc4_stir_pid != pid) {			m = minimum(datlen, KEYSZ + IVSZ);
	arc4_stir_pid = pid;			for (i = 0; i < m; i++)
	arc4_stir();			rsx->rs_buf[i] ^= dat[i];
	}			}
				/* immediately reinit for backtracking resistance */
				_rs_init(rsx->rs_buf, KEYSZ + IVSZ);
				memset(rsx->rs_buf, 0, KEYSZ + IVSZ);
				rs->rs_have = sizeof(rsx->rs_buf) - KEYSZ - IVSZ;
	}			}

	static inline u_int8_t			static inline void
	arc4_getbyte(void)			_rs_random_buf(void *_buf, size_t n)
	{			{
	u_int8_t si, sj;			u_char buf = (u_char )_buf;
				u_char *keystream;
				size_t m;

	rs.i = (rs.i + 1);			_rs_stir_if_needed(n);
	si = rs.s[rs.i];			while (n > 0) {
	rs.j = (rs.j + si);			if (rs->rs_have > 0) {
	sj = rs.s[rs.j];			m = minimum(n, rs->rs_have);
	rs.s[rs.i] = sj;			keystream = rsx->rs_buf + sizeof(rsx->rs_buf)
	rs.s[rs.j] = si;			- rs->rs_have;
	return (rs.s[(si + sj) & 0xff]);			memcpy(buf, keystream, m);
				memset(keystream, 0, m);
				buf += m;
				n -= m;
				rs->rs_have -= m;
	}			}
				if (rs->rs_have == 0)
	static inline u_int32_t			_rs_rekey(NULL, 0);
	arc4_getword(void)
	{
	u_int32_t val;
	val = arc4_getbyte() << 24;
	val \|= arc4_getbyte() << 16;
	val \|= arc4_getbyte() << 8;
	val \|= arc4_getbyte();
	return val;
	}			}

	void
	arc4random_stir(void)
	{
	_ARC4_LOCK();
	arc4_stir();
	_ARC4_UNLOCK();
	}			}

	void			static inline void
	arc4random_addrandom(u_char *dat, int datlen)			_rs_random_u32(uint32_t *val)
	{			{
	_ARC4_LOCK();			u_char *keystream;
	if (!rs_initialized)
	arc4_stir();			_rs_stir_if_needed(sizeof(*val));
	arc4_addrandom(dat, datlen);			if (rs->rs_have < sizeof(*val))
	_ARC4_UNLOCK();			_rs_rekey(NULL, 0);
				keystream = rsx->rs_buf + sizeof(rsx->rs_buf) - rs->rs_have;
				memcpy(val, keystream, sizeof(*val));
				memset(keystream, 0, sizeof(*val));
				rs->rs_have -= sizeof(*val);
	}			}

	u_int32_t			uint32_t
	arc4random(void)			arc4random(void)
	{			{
	u_int32_t val;			uint32_t val;

	_ARC4_LOCK();			_ARC4_LOCK();
	arc4_count -= 4;			_rs_random_u32(&val);
	arc4_stir_if_needed();
	val = arc4_getword();
	_ARC4_UNLOCK();			_ARC4_UNLOCK();
	return val;			return val;
	}			}

	void			void
	arc4random_buf(void *_buf, size_t n)			arc4random_buf(void *buf, size_t n)
	{			{
	u_char buf = (u_char )_buf;
	_ARC4_LOCK();			_ARC4_LOCK();
	arc4_stir_if_needed();			_rs_random_buf(buf, n);
	while (n--) {
	if (--arc4_count <= 0)
	arc4_stir();
	buf[n] = arc4_getbyte();
	}
	_ARC4_UNLOCK();			_ARC4_UNLOCK();
	}			}

	#if 0
	/-------- Test code for i386 --------/
	#include <stdio.h>
	#include <machine/pctr.h>
	int
	main(int argc, char **argv)
	{
	const int iter = 1000000;
	int i;
	pctrval v;

	v = rdtsc();
	for (i = 0; i < iter; i++)
	arc4random();
	v = rdtsc() - v;
	v /= iter;

	printf("%qd cycles\n", v);
	}
	#endif