[openssh.git] / openbsd-compat / bsd-arc4random.c

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

#include "includes.h"

#include <sys/types.h>

#include <string.h>
#include <stdlib.h>
#include <stdarg.h>

#include "log.h"

#ifndef HAVE_ARC4RANDOM

#include <openssl/rand.h>
#include <openssl/rc4.h>
#include <openssl/err.h>

/* Size of key to use */
#define SEED_SIZE 20

/* Number of bytes to reseed after */
#define REKEY_BYTES	(1 << 24)

static int rc4_ready = 0;
static RC4_KEY rc4;

unsigned int
arc4random(void)
{
	unsigned int r = 0;
	static int first_time = 1;

	if (rc4_ready <= 0) {
		if (first_time)
			seed_rng();
		first_time = 0;
		arc4random_stir();
	}

	RC4(&rc4, sizeof(r), (unsigned char *)&r, (unsigned char *)&r);

	rc4_ready -= sizeof(r);
	
	return(r);
}

void
arc4random_stir(void)
{
	unsigned char rand_buf[SEED_SIZE];
	int i;

	memset(&rc4, 0, sizeof(rc4));
	if (RAND_bytes(rand_buf, sizeof(rand_buf)) <= 0)
		fatal("Couldn't obtain random bytes (error %ld)",
		    ERR_get_error());
	RC4_set_key(&rc4, sizeof(rand_buf), rand_buf);

	/*
	 * Discard early keystream, as per recommendations in:
	 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
	 */
	for(i = 0; i <= 256; i += sizeof(rand_buf))
		RC4(&rc4, sizeof(rand_buf), rand_buf, rand_buf);

	memset(rand_buf, 0, sizeof(rand_buf));

	rc4_ready = REKEY_BYTES;
}
#endif /* !HAVE_ARC4RANDOM */

#ifndef ARC4RANDOM_BUF
void
arc4random_buf(void *_buf, size_t n)
{
	size_t i;
	u_int32_t r = 0;
	char *buf = (char *)_buf;

	for (i = 0; i < n; i++) {
		if (i % 4 == 0)
			r = arc4random();
		buf[i] = r & 0xff;
		r >>= 8;
	}
	i = r = 0;
}
#endif /* !HAVE_ARC4RANDOM_BUF */

#ifndef ARC4RANDOM_UNIFORM
/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
	u_int32_t r, min;

	if (upper_bound < 2)
		return 0;

#if (ULONG_MAX > 0xffffffffUL)
	min = 0x100000000UL % upper_bound;
#else
	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
	if (upper_bound > 0x80000000)
		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
	else {
		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
	}
#endif

	/*
	 * This could theoretically loop forever but each retry has
	 * p > 0.5 (worst case, usually far better) of selecting a
	 * number inside the range we need, so it should rarely need
	 * to re-roll.
	 */
	for (;;) {
		r = arc4random();
		if (r >= min)
			break;
	}

	return r % upper_bound;
}
#endif /* !HAVE_ARC4RANDOM_UNIFORM */
Commit	Line	Data
416ed5a7	1	/*
9cd11896	2	* Copyright (c) 1999,2000,2004 Damien Miller <djm@mindrot.org>
416ed5a7	3	*
9cd11896	4	* Permission to use, copy, modify, and distribute this software for any
	5	* purpose with or without fee is hereby granted, provided that the above
	6	* copyright notice and this permission notice appear in all copies.
416ed5a7	7	*
9cd11896	8	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	9	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	10	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	11	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	12	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	13	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	14	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
416ed5a7	15	*/
	16
	17	#include "includes.h"
28cb0a43	18
28cb0a43	19	#include <sys/types.h>
f2265d5d	20
28cb0a43	21	#include <string.h>
936e7c8c	22	#include <stdlib.h>
f2265d5d	23	#include <stdarg.h>
28cb0a43	24
a701a70b	25	#include "log.h"
416ed5a7	26
	27	#ifndef HAVE_ARC4RANDOM
	28
2f125ca1	29	#include <openssl/rand.h>
2f125ca1	30	#include <openssl/rc4.h>
a701a70b	31	#include <openssl/err.h>
2f125ca1	32
10fa00c8	33	/* Size of key to use */
	34	#define SEED_SIZE 20
	35
	36	/* Number of bytes to reseed after */
ddc49b5c	37	#define REKEY_BYTES (1 << 24)
10fa00c8	38
416ed5a7	39	static int rc4_ready = 0;
	40	static RC4_KEY rc4;
	41
15606882	42	unsigned int
15606882	43	arc4random(void)
416ed5a7	44	{
416ed5a7	45	unsigned int r = 0;
e339aa53	46	static int first_time = 1;
416ed5a7	47
e339aa53	48	if (rc4_ready <= 0) {
af5ee4e4	49	if (first_time)
e339aa53	50	seed_rng();
e339aa53	51	first_time = 0;
416ed5a7	52	arc4random_stir();
e339aa53	53	}
e339aa53	54
416ed5a7	55	RC4(&rc4, sizeof(r), (unsigned char )&r, (unsigned char )&r);
10fa00c8	56
10fa00c8	57	rc4_ready -= sizeof(r);
416ed5a7	58
	59	return(r);
	60	}
	61
15606882	62	void
15606882	63	arc4random_stir(void)
416ed5a7	64	{
10fa00c8	65	unsigned char rand_buf[SEED_SIZE];
75d1f941	66	int i;
10fa00c8	67
e339aa53	68	memset(&rc4, 0, sizeof(rc4));
d8eb5247	69	if (RAND_bytes(rand_buf, sizeof(rand_buf)) <= 0)
e339aa53	70	fatal("Couldn't obtain random bytes (error %ld)",
e339aa53	71	ERR_get_error());
416ed5a7	72	RC4_set_key(&rc4, sizeof(rand_buf), rand_buf);
75d1f941	73
	74	/*
	75	* Discard early keystream, as per recommendations in:
	76	* http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
	77	*/
	78	for(i = 0; i <= 256; i += sizeof(rand_buf))
	79	RC4(&rc4, sizeof(rand_buf), rand_buf, rand_buf);
	80
416ed5a7	81	memset(rand_buf, 0, sizeof(rand_buf));
e339aa53	82
10fa00c8	83	rc4_ready = REKEY_BYTES;
416ed5a7	84	}
416ed5a7	85	#endif /* !HAVE_ARC4RANDOM */
185adaf8	86
	87	#ifndef ARC4RANDOM_BUF
	88	void
	89	arc4random_buf(void *_buf, size_t n)
	90	{
	91	size_t i;
936e7c8c	92	u_int32_t r = 0;
185adaf8	93	char buf = (char )_buf;
	94
	95	for (i = 0; i < n; i++) {
	96	if (i % 4 == 0)
	97	r = arc4random();
	98	buf[i] = r & 0xff;
	99	r >>= 8;
	100	}
	101	i = r = 0;
	102	}
	103	#endif /* !HAVE_ARC4RANDOM_BUF */
	104
	105	#ifndef ARC4RANDOM_UNIFORM
	106	/*
	107	* Calculate a uniformly distributed random number less than upper_bound
	108	* avoiding "modulo bias".
	109	*
	110	* Uniformity is achieved by generating new random numbers until the one
	111	* returned is outside the range [0, 2**32 % upper_bound). This
	112	* guarantees the selected random number will be inside
	113	* [232 % upper_bound, 232) which maps back to [0, upper_bound)
	114	* after reduction modulo upper_bound.
	115	*/
	116	u_int32_t
	117	arc4random_uniform(u_int32_t upper_bound)
	118	{
	119	u_int32_t r, min;
	120
	121	if (upper_bound < 2)
	122	return 0;
	123
	124	#if (ULONG_MAX > 0xffffffffUL)
	125	min = 0x100000000UL % upper_bound;
	126	#else
	127	/* Calculate (2*32 % upper_bound) avoiding 64-bit math /
	128	if (upper_bound > 0x80000000)
	129	min = 1 + ~upper_bound; /* 2*32 - upper_bound /
	130	else {
	131	/* (2*32 - (x 2)) % x == 232 % x when x <= 231 */
07e61b8a	132	min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
185adaf8	133	}
	134	#endif
	135
	136	/*
	137	* This could theoretically loop forever but each retry has
	138	* p > 0.5 (worst case, usually far better) of selecting a
	139	* number inside the range we need, so it should rarely need
	140	* to re-roll.
	141	*/
	142	for (;;) {
	143	r = arc4random();
	144	if (r >= min)
	145	break;
	146	}
	147
	148	return r % upper_bound;
	149	}
	150	#endif /* !HAVE_ARC4RANDOM_UNIFORM */