xref: /freebsd/lib/libc/gen/arc4random.c (revision 5295209eff8469c31d77af18b5cb8e72ad1e1801)
183a03b38SAndrey A. Chernov /*
283a03b38SAndrey A. Chernov  * Arc4 random number generator for OpenBSD.
383a03b38SAndrey A. Chernov  * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
483a03b38SAndrey A. Chernov  *
583a03b38SAndrey A. Chernov  * Modification and redistribution in source and binary forms is
683a03b38SAndrey A. Chernov  * permitted provided that due credit is given to the author and the
783a03b38SAndrey A. Chernov  * OpenBSD project (for instance by leaving this copyright notice
883a03b38SAndrey A. Chernov  * intact).
983a03b38SAndrey A. Chernov  */
1083a03b38SAndrey A. Chernov 
1183a03b38SAndrey A. Chernov /*
1283a03b38SAndrey A. Chernov  * This code is derived from section 17.1 of Applied Cryptography,
1383a03b38SAndrey A. Chernov  * second edition, which describes a stream cipher allegedly
1483a03b38SAndrey A. Chernov  * compatible with RSA Labs "RC4" cipher (the actual description of
1583a03b38SAndrey A. Chernov  * which is a trade secret).  The same algorithm is used as a stream
1683a03b38SAndrey A. Chernov  * cipher called "arcfour" in Tatu Ylonen's ssh package.
1783a03b38SAndrey A. Chernov  *
1883a03b38SAndrey A. Chernov  * Here the stream cipher has been modified always to include the time
1983a03b38SAndrey A. Chernov  * when initializing the state.  That makes it impossible to
2083a03b38SAndrey A. Chernov  * regenerate the same random sequence twice, so this can't be used
2183a03b38SAndrey A. Chernov  * for encryption, but will generate good random numbers.
2283a03b38SAndrey A. Chernov  *
2383a03b38SAndrey A. Chernov  * RC4 is a registered trademark of RSA Laboratories.
2483a03b38SAndrey A. Chernov  */
2583a03b38SAndrey A. Chernov 
26333fc21eSDavid E. O'Brien #include <sys/cdefs.h>
27333fc21eSDavid E. O'Brien __FBSDID("$FreeBSD$");
28333fc21eSDavid E. O'Brien 
29d201fe46SDaniel Eischen #include "namespace.h"
30333fc21eSDavid E. O'Brien #include <sys/types.h>
31333fc21eSDavid E. O'Brien #include <sys/time.h>
3283a03b38SAndrey A. Chernov #include <stdlib.h>
3383a03b38SAndrey A. Chernov #include <fcntl.h>
3483a03b38SAndrey A. Chernov #include <unistd.h>
355295209eSBrian Feldman #include <pthread.h>
365295209eSBrian Feldman 
375295209eSBrian Feldman #include "libc_private.h"
38d201fe46SDaniel Eischen #include "un-namespace.h"
3983a03b38SAndrey A. Chernov 
4083a03b38SAndrey A. Chernov struct arc4_stream {
4183a03b38SAndrey A. Chernov 	u_int8_t i;
4283a03b38SAndrey A. Chernov 	u_int8_t j;
4383a03b38SAndrey A. Chernov 	u_int8_t s[256];
4483a03b38SAndrey A. Chernov };
4583a03b38SAndrey A. Chernov 
465295209eSBrian Feldman static pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
475295209eSBrian Feldman 
485295209eSBrian Feldman #define	RANDOMDEV	"/dev/urandom"
495295209eSBrian Feldman #define	THREAD_LOCK()						\
505295209eSBrian Feldman 	do {							\
515295209eSBrian Feldman 		if (__isthreaded)				\
525295209eSBrian Feldman 			_pthread_mutex_lock(&arc4random_mtx);	\
535295209eSBrian Feldman 	} while (0)
545295209eSBrian Feldman 
555295209eSBrian Feldman #define	THREAD_UNLOCK()						\
565295209eSBrian Feldman 	do {							\
575295209eSBrian Feldman 		if (__isthreaded)				\
585295209eSBrian Feldman 			_pthread_mutex_unlock(&arc4random_mtx);	\
595295209eSBrian Feldman 	} while (0)
605295209eSBrian Feldman 
6183a03b38SAndrey A. Chernov static struct arc4_stream rs;
625295209eSBrian Feldman static int rs_initialized;
635295209eSBrian Feldman static int rs_stired;
6483a03b38SAndrey A. Chernov 
6560ce8b0eSDavid Schultz static inline u_int8_t arc4_getbyte(struct arc4_stream *);
665295209eSBrian Feldman static void arc4_stir(struct arc4_stream *);
6760ce8b0eSDavid Schultz 
6883a03b38SAndrey A. Chernov static inline void
6983a03b38SAndrey A. Chernov arc4_init(as)
7083a03b38SAndrey A. Chernov 	struct arc4_stream *as;
7183a03b38SAndrey A. Chernov {
7283a03b38SAndrey A. Chernov 	int     n;
7383a03b38SAndrey A. Chernov 
7483a03b38SAndrey A. Chernov 	for (n = 0; n < 256; n++)
7583a03b38SAndrey A. Chernov 		as->s[n] = n;
7683a03b38SAndrey A. Chernov 	as->i = 0;
7783a03b38SAndrey A. Chernov 	as->j = 0;
7883a03b38SAndrey A. Chernov }
7983a03b38SAndrey A. Chernov 
8083a03b38SAndrey A. Chernov static inline void
8183a03b38SAndrey A. Chernov arc4_addrandom(as, dat, datlen)
8283a03b38SAndrey A. Chernov 	struct arc4_stream *as;
8383a03b38SAndrey A. Chernov 	u_char *dat;
8483a03b38SAndrey A. Chernov 	int     datlen;
8583a03b38SAndrey A. Chernov {
8683a03b38SAndrey A. Chernov 	int     n;
8783a03b38SAndrey A. Chernov 	u_int8_t si;
8883a03b38SAndrey A. Chernov 
8983a03b38SAndrey A. Chernov 	as->i--;
9083a03b38SAndrey A. Chernov 	for (n = 0; n < 256; n++) {
9183a03b38SAndrey A. Chernov 		as->i = (as->i + 1);
9283a03b38SAndrey A. Chernov 		si = as->s[as->i];
9383a03b38SAndrey A. Chernov 		as->j = (as->j + si + dat[n % datlen]);
9483a03b38SAndrey A. Chernov 		as->s[as->i] = as->s[as->j];
9583a03b38SAndrey A. Chernov 		as->s[as->j] = si;
9683a03b38SAndrey A. Chernov 	}
9783a03b38SAndrey A. Chernov }
9883a03b38SAndrey A. Chernov 
9983a03b38SAndrey A. Chernov static void
10083a03b38SAndrey A. Chernov arc4_stir(as)
10183a03b38SAndrey A. Chernov 	struct arc4_stream *as;
10283a03b38SAndrey A. Chernov {
10360ce8b0eSDavid Schultz 	int     fd, n;
10483a03b38SAndrey A. Chernov 	struct {
10583a03b38SAndrey A. Chernov 		struct timeval tv;
10683a03b38SAndrey A. Chernov 		pid_t pid;
10783a03b38SAndrey A. Chernov 		u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
10883a03b38SAndrey A. Chernov 	}       rdat;
10983a03b38SAndrey A. Chernov 
11083a03b38SAndrey A. Chernov 	gettimeofday(&rdat.tv, NULL);
11183a03b38SAndrey A. Chernov 	rdat.pid = getpid();
1125295209eSBrian Feldman 	fd = _open(RANDOMDEV, O_RDONLY, 0);
11383a03b38SAndrey A. Chernov 	if (fd >= 0) {
1149233c4d9SJason Evans 		(void) _read(fd, rdat.rnd, sizeof(rdat.rnd));
1159233c4d9SJason Evans 		_close(fd);
11683a03b38SAndrey A. Chernov 	}
11783a03b38SAndrey A. Chernov 	/* fd < 0?  Ah, what the heck. We'll just take whatever was on the
11883a03b38SAndrey A. Chernov 	 * stack... */
11983a03b38SAndrey A. Chernov 
12083a03b38SAndrey A. Chernov 	arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
12160ce8b0eSDavid Schultz 
12260ce8b0eSDavid Schultz 	/*
12360ce8b0eSDavid Schultz 	 * Throw away the first N bytes of output, as suggested in the
12460ce8b0eSDavid Schultz 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
12560ce8b0eSDavid Schultz 	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
12660ce8b0eSDavid Schultz 	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
12760ce8b0eSDavid Schultz 	 * by Ilya Mironov.
12860ce8b0eSDavid Schultz 	 */
12960ce8b0eSDavid Schultz 	for (n = 0; n < 1024; n++)
13060ce8b0eSDavid Schultz 		arc4_getbyte(as);
13183a03b38SAndrey A. Chernov }
13283a03b38SAndrey A. Chernov 
13383a03b38SAndrey A. Chernov static inline u_int8_t
13483a03b38SAndrey A. Chernov arc4_getbyte(as)
13583a03b38SAndrey A. Chernov 	struct arc4_stream *as;
13683a03b38SAndrey A. Chernov {
13783a03b38SAndrey A. Chernov 	u_int8_t si, sj;
13883a03b38SAndrey A. Chernov 
13983a03b38SAndrey A. Chernov 	as->i = (as->i + 1);
14083a03b38SAndrey A. Chernov 	si = as->s[as->i];
14183a03b38SAndrey A. Chernov 	as->j = (as->j + si);
14283a03b38SAndrey A. Chernov 	sj = as->s[as->j];
14383a03b38SAndrey A. Chernov 	as->s[as->i] = sj;
14483a03b38SAndrey A. Chernov 	as->s[as->j] = si;
1457ce21b20SBrian Feldman 
14683a03b38SAndrey A. Chernov 	return (as->s[(si + sj) & 0xff]);
14783a03b38SAndrey A. Chernov }
14883a03b38SAndrey A. Chernov 
14983a03b38SAndrey A. Chernov static inline u_int32_t
15083a03b38SAndrey A. Chernov arc4_getword(as)
15183a03b38SAndrey A. Chernov 	struct arc4_stream *as;
15283a03b38SAndrey A. Chernov {
15383a03b38SAndrey A. Chernov 	u_int32_t val;
1547ce21b20SBrian Feldman 
15583a03b38SAndrey A. Chernov 	val = arc4_getbyte(as) << 24;
15683a03b38SAndrey A. Chernov 	val |= arc4_getbyte(as) << 16;
15783a03b38SAndrey A. Chernov 	val |= arc4_getbyte(as) << 8;
15883a03b38SAndrey A. Chernov 	val |= arc4_getbyte(as);
1597ce21b20SBrian Feldman 
1607ce21b20SBrian Feldman 	return (val);
16183a03b38SAndrey A. Chernov }
16283a03b38SAndrey A. Chernov 
1635295209eSBrian Feldman static void
1645295209eSBrian Feldman arc4_check_init(void)
16583a03b38SAndrey A. Chernov {
16683a03b38SAndrey A. Chernov 	if (!rs_initialized) {
16783a03b38SAndrey A. Chernov 		arc4_init(&rs);
16883a03b38SAndrey A. Chernov 		rs_initialized = 1;
16983a03b38SAndrey A. Chernov 	}
1705295209eSBrian Feldman }
1715295209eSBrian Feldman 
1725295209eSBrian Feldman static void
1735295209eSBrian Feldman arc4_check_stir(void)
1745295209eSBrian Feldman {
1755295209eSBrian Feldman 	if (!rs_stired) {
17683a03b38SAndrey A. Chernov 		arc4_stir(&rs);
1775295209eSBrian Feldman 		rs_stired = 1;
1785295209eSBrian Feldman 	}
1795295209eSBrian Feldman }
1805295209eSBrian Feldman 
1815295209eSBrian Feldman void
1825295209eSBrian Feldman arc4random_stir()
1835295209eSBrian Feldman {
1845295209eSBrian Feldman 	THREAD_LOCK();
1855295209eSBrian Feldman 	arc4_check_init();
1865295209eSBrian Feldman 	arc4_stir(&rs);
1875295209eSBrian Feldman 	THREAD_UNLOCK();
18883a03b38SAndrey A. Chernov }
18983a03b38SAndrey A. Chernov 
19083a03b38SAndrey A. Chernov void
19183a03b38SAndrey A. Chernov arc4random_addrandom(dat, datlen)
19283a03b38SAndrey A. Chernov 	u_char *dat;
19383a03b38SAndrey A. Chernov 	int     datlen;
19483a03b38SAndrey A. Chernov {
1955295209eSBrian Feldman 	THREAD_LOCK();
1965295209eSBrian Feldman 	arc4_check_init();
1975295209eSBrian Feldman 	arc4_check_stir();
19883a03b38SAndrey A. Chernov 	arc4_addrandom(&rs, dat, datlen);
1995295209eSBrian Feldman 	THREAD_UNLOCK();
20083a03b38SAndrey A. Chernov }
20183a03b38SAndrey A. Chernov 
20283a03b38SAndrey A. Chernov u_int32_t
20383a03b38SAndrey A. Chernov arc4random()
20483a03b38SAndrey A. Chernov {
2055295209eSBrian Feldman 	u_int32_t rnd;
2067ce21b20SBrian Feldman 
2075295209eSBrian Feldman 	THREAD_LOCK();
2085295209eSBrian Feldman 	arc4_check_init();
2095295209eSBrian Feldman 	arc4_check_stir();
2105295209eSBrian Feldman 	rnd = arc4_getword(&rs);
2115295209eSBrian Feldman 	THREAD_UNLOCK();
2125295209eSBrian Feldman 
2135295209eSBrian Feldman 	return (rnd);
21483a03b38SAndrey A. Chernov }
21583a03b38SAndrey A. Chernov 
21683a03b38SAndrey A. Chernov #if 0
21783a03b38SAndrey A. Chernov /*-------- Test code for i386 --------*/
21883a03b38SAndrey A. Chernov #include <stdio.h>
21983a03b38SAndrey A. Chernov #include <machine/pctr.h>
22083a03b38SAndrey A. Chernov int
22183a03b38SAndrey A. Chernov main(int argc, char **argv)
22283a03b38SAndrey A. Chernov {
22383a03b38SAndrey A. Chernov 	const int iter = 1000000;
22483a03b38SAndrey A. Chernov 	int     i;
22583a03b38SAndrey A. Chernov 	pctrval v;
22683a03b38SAndrey A. Chernov 
22783a03b38SAndrey A. Chernov 	v = rdtsc();
22883a03b38SAndrey A. Chernov 	for (i = 0; i < iter; i++)
22983a03b38SAndrey A. Chernov 		arc4random();
23083a03b38SAndrey A. Chernov 	v = rdtsc() - v;
23183a03b38SAndrey A. Chernov 	v /= iter;
23283a03b38SAndrey A. Chernov 
23383a03b38SAndrey A. Chernov 	printf("%qd cycles\n", v);
23483a03b38SAndrey A. Chernov }
23583a03b38SAndrey A. Chernov #endif
236