arc4random.c revision 181261
126628Sache/* 2180672Sache * Copyright (c) 1996, David Mazieres <dm@uun.org> 3180672Sache * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 426628Sache * 5180672Sache * Permission to use, copy, modify, and distribute this software for any 6180672Sache * purpose with or without fee is hereby granted, provided that the above 7180672Sache * copyright notice and this permission notice appear in all copies. 8180672Sache * 9180672Sache * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10180672Sache * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11180672Sache * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12180672Sache * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13180672Sache * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14180672Sache * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15180672Sache * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 1626628Sache */ 1726628Sache 1826628Sache/* 19180672Sache * Arc4 random number generator for OpenBSD. 20180672Sache * 2126628Sache * This code is derived from section 17.1 of Applied Cryptography, 2226628Sache * second edition, which describes a stream cipher allegedly 2326628Sache * compatible with RSA Labs "RC4" cipher (the actual description of 2426628Sache * which is a trade secret). The same algorithm is used as a stream 2526628Sache * cipher called "arcfour" in Tatu Ylonen's ssh package. 2626628Sache * 2726628Sache * Here the stream cipher has been modified always to include the time 2826628Sache * when initializing the state. That makes it impossible to 2926628Sache * regenerate the same random sequence twice, so this can't be used 3026628Sache * for encryption, but will generate good random numbers. 3126628Sache * 3226628Sache * RC4 is a registered trademark of RSA Laboratories. 3326628Sache */ 3426628Sache 3592986Sobrien#include <sys/cdefs.h> 3692986Sobrien__FBSDID("$FreeBSD: head/lib/libc/gen/arc4random.c 181261 2008-08-03 20:15:22Z ache $"); 3792986Sobrien 3871579Sdeischen#include "namespace.h" 3992986Sobrien#include <sys/types.h> 4092986Sobrien#include <sys/time.h> 4126628Sache#include <stdlib.h> 4226628Sache#include <fcntl.h> 4326628Sache#include <unistd.h> 44127373Sgreen#include <pthread.h> 45127373Sgreen 46127373Sgreen#include "libc_private.h" 4771579Sdeischen#include "un-namespace.h" 4826628Sache 4926628Sachestruct arc4_stream { 5026628Sache u_int8_t i; 5126628Sache u_int8_t j; 5226628Sache u_int8_t s[256]; 5326628Sache}; 5426628Sache 55127373Sgreenstatic pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; 56127373Sgreen 57180804Sache#define RANDOMDEV "/dev/urandom" 58181261Sache#define KEYSIZE 128 59127373Sgreen#define THREAD_LOCK() \ 60127373Sgreen do { \ 61127373Sgreen if (__isthreaded) \ 62127373Sgreen _pthread_mutex_lock(&arc4random_mtx); \ 63127373Sgreen } while (0) 64127373Sgreen 65127373Sgreen#define THREAD_UNLOCK() \ 66127373Sgreen do { \ 67127373Sgreen if (__isthreaded) \ 68127373Sgreen _pthread_mutex_unlock(&arc4random_mtx); \ 69127373Sgreen } while (0) 70127373Sgreen 71127373Sgreenstatic struct arc4_stream rs; 7226628Sachestatic int rs_initialized; 73127373Sgreenstatic int rs_stired; 74162995Sachestatic int arc4_count; 7526628Sache 76180672Sachestatic inline u_int8_t arc4_getbyte(void); 77180672Sachestatic void arc4_stir(void); 78124741Sdas 7926628Sachestatic inline void 80180672Sachearc4_init(void) 8126628Sache{ 8226628Sache int n; 8326628Sache 8426628Sache for (n = 0; n < 256; n++) 85180672Sache rs.s[n] = n; 86180672Sache rs.i = 0; 87180672Sache rs.j = 0; 8826628Sache} 8926628Sache 9026628Sachestatic inline void 91180672Sachearc4_addrandom(u_char *dat, int datlen) 9226628Sache{ 9326628Sache int n; 9426628Sache u_int8_t si; 9526628Sache 96180672Sache rs.i--; 9726628Sache for (n = 0; n < 256; n++) { 98180672Sache rs.i = (rs.i + 1); 99180672Sache si = rs.s[rs.i]; 100180672Sache rs.j = (rs.j + si + dat[n % datlen]); 101180672Sache rs.s[rs.i] = rs.s[rs.j]; 102180672Sache rs.s[rs.j] = si; 10326628Sache } 104180672Sache rs.j = rs.i; 10526628Sache} 10626628Sache 10726628Sachestatic void 108180672Sachearc4_stir(void) 10926628Sache{ 110181261Sache int done, fd, n; 11126628Sache struct { 112181261Sache struct timeval tv; 113181261Sache pid_t pid; 114181261Sache u_int8_t rnd[KEYSIZE]; 115181261Sache } rdat; 11626628Sache 117127373Sgreen fd = _open(RANDOMDEV, O_RDONLY, 0); 118181261Sache done = 0; 11926628Sache if (fd >= 0) { 120181261Sache if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) 121181261Sache done = 1; 122181261Sache (void)_close(fd); 123127373Sgreen } 124181261Sache if (!done) { 125181261Sache (void)gettimeofday(&rdat.tv, NULL); 126181261Sache rdat.pid = getpid(); 127181261Sache /* We'll just take whatever was on the stack too... */ 128181261Sache } 12926628Sache 130181261Sache arc4_addrandom((u_char *)&rdat, KEYSIZE); 131124741Sdas 132124741Sdas /* 133124741Sdas * Throw away the first N bytes of output, as suggested in the 134124741Sdas * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 135180804Sache * by Fluher, Mantin, and Shamir. N=1024 is based on 136124741Sdas * suggestions in the paper "(Not So) Random Shuffles of RC4" 137124741Sdas * by Ilya Mironov. 138124741Sdas */ 139180804Sache for (n = 0; n < 1024; n++) 140180804Sache (void) arc4_getbyte(); 141180655Sache arc4_count = 1600000; 14226628Sache} 14326628Sache 14426628Sachestatic inline u_int8_t 145180672Sachearc4_getbyte(void) 14626628Sache{ 14726628Sache u_int8_t si, sj; 14826628Sache 149180672Sache rs.i = (rs.i + 1); 150180672Sache si = rs.s[rs.i]; 151180672Sache rs.j = (rs.j + si); 152180672Sache sj = rs.s[rs.j]; 153180672Sache rs.s[rs.i] = sj; 154180672Sache rs.s[rs.j] = si; 155126180Sgreen 156180672Sache return (rs.s[(si + sj) & 0xff]); 15726628Sache} 15826628Sache 15926628Sachestatic inline u_int32_t 160180672Sachearc4_getword(void) 16126628Sache{ 16226628Sache u_int32_t val; 163126180Sgreen 164180672Sache val = arc4_getbyte() << 24; 165180672Sache val |= arc4_getbyte() << 16; 166180672Sache val |= arc4_getbyte() << 8; 167180672Sache val |= arc4_getbyte(); 168126180Sgreen 169126180Sgreen return (val); 17026628Sache} 17126628Sache 172127373Sgreenstatic void 173127373Sgreenarc4_check_init(void) 17426628Sache{ 17526628Sache if (!rs_initialized) { 176180672Sache arc4_init(); 177180804Sache rs_initialized = 1; 17826628Sache } 179127373Sgreen} 180127373Sgreen 181180657Sachestatic inline void 182127373Sgreenarc4_check_stir(void) 183127373Sgreen{ 184180656Sache if (!rs_stired || arc4_count <= 0) { 185180672Sache arc4_stir(); 186127373Sgreen rs_stired = 1; 187127373Sgreen } 188127373Sgreen} 189127373Sgreen 190127373Sgreenvoid 191169981Sdelphijarc4random_stir(void) 192127373Sgreen{ 193127373Sgreen THREAD_LOCK(); 194127373Sgreen arc4_check_init(); 195180672Sache arc4_stir(); 196127373Sgreen THREAD_UNLOCK(); 19726628Sache} 19826628Sache 19926628Sachevoid 200169981Sdelphijarc4random_addrandom(u_char *dat, int datlen) 20126628Sache{ 202127373Sgreen THREAD_LOCK(); 203127373Sgreen arc4_check_init(); 204127373Sgreen arc4_check_stir(); 205180672Sache arc4_addrandom(dat, datlen); 206127373Sgreen THREAD_UNLOCK(); 20726628Sache} 20826628Sache 20926628Sacheu_int32_t 210169981Sdelphijarc4random(void) 21126628Sache{ 212127373Sgreen u_int32_t rnd; 213126180Sgreen 214127373Sgreen THREAD_LOCK(); 215127373Sgreen arc4_check_init(); 216127373Sgreen arc4_check_stir(); 217180672Sache rnd = arc4_getword(); 218180656Sache arc4_count -= 4; 219127373Sgreen THREAD_UNLOCK(); 220127373Sgreen 221127373Sgreen return (rnd); 22226628Sache} 22326628Sache 224180657Sachevoid 225180657Sachearc4random_buf(void *_buf, size_t n) 226180657Sache{ 227180657Sache u_char *buf = (u_char *)_buf; 228180657Sache 229180657Sache THREAD_LOCK(); 230180657Sache arc4_check_init(); 231180657Sache while (n--) { 232180657Sache arc4_check_stir(); 233180672Sache buf[n] = arc4_getbyte(); 234180657Sache arc4_count--; 235180657Sache } 236180657Sache THREAD_UNLOCK(); 237180657Sache} 238180657Sache 239180688Sache/* 240180688Sache * Calculate a uniformly distributed random number less than upper_bound 241180688Sache * avoiding "modulo bias". 242180688Sache * 243180688Sache * Uniformity is achieved by generating new random numbers until the one 244180688Sache * returned is outside the range [0, 2**32 % upper_bound). This 245180688Sache * guarantees the selected random number will be inside 246180688Sache * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 247180688Sache * after reduction modulo upper_bound. 248180688Sache */ 249180688Sacheu_int32_t 250180688Sachearc4random_uniform(u_int32_t upper_bound) 251180688Sache{ 252180688Sache u_int32_t r, min; 253180688Sache 254180688Sache if (upper_bound < 2) 255180690Sache return (0); 256180688Sache 257180688Sache#if (ULONG_MAX > 0xffffffffUL) 258180688Sache min = 0x100000000UL % upper_bound; 259180688Sache#else 260180688Sache /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 261180688Sache if (upper_bound > 0x80000000) 262180688Sache min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 263180688Sache else { 264180688Sache /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 265180688Sache min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 266180688Sache } 267180688Sache#endif 268180688Sache 269180688Sache /* 270180688Sache * This could theoretically loop forever but each retry has 271180688Sache * p > 0.5 (worst case, usually far better) of selecting a 272180688Sache * number inside the range we need, so it should rarely need 273180688Sache * to re-roll. 274180688Sache */ 275180688Sache for (;;) { 276180688Sache r = arc4random(); 277180688Sache if (r >= min) 278180688Sache break; 279180688Sache } 280180688Sache 281180688Sache return (r % upper_bound); 282180688Sache} 283180688Sache 28426628Sache#if 0 28526628Sache/*-------- Test code for i386 --------*/ 28626628Sache#include <stdio.h> 28726628Sache#include <machine/pctr.h> 28826628Sacheint 28926628Sachemain(int argc, char **argv) 29026628Sache{ 29126628Sache const int iter = 1000000; 29226628Sache int i; 29326628Sache pctrval v; 29426628Sache 29526628Sache v = rdtsc(); 29626628Sache for (i = 0; i < iter; i++) 29726628Sache arc4random(); 29826628Sache v = rdtsc() - v; 29926628Sache v /= iter; 30026628Sache 30126628Sache printf("%qd cycles\n", v); 30226628Sache} 30326628Sache#endif 304