1267379Sdelphij/* $OpenBSD: arc4random.c,v 1.22 2010/12/22 08:23:42 otto Exp $ */ 2267379Sdelphij 326628Sache/* 4180672Sache * Copyright (c) 1996, David Mazieres <dm@uun.org> 5180672Sache * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 626628Sache * 7180672Sache * Permission to use, copy, modify, and distribute this software for any 8180672Sache * purpose with or without fee is hereby granted, provided that the above 9180672Sache * copyright notice and this permission notice appear in all copies. 10180672Sache * 11180672Sache * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12180672Sache * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13180672Sache * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14180672Sache * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15180672Sache * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16180672Sache * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17180672Sache * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 1826628Sache */ 1926628Sache 2026628Sache/* 21180672Sache * Arc4 random number generator for OpenBSD. 22180672Sache * 2326628Sache * This code is derived from section 17.1 of Applied Cryptography, 2426628Sache * second edition, which describes a stream cipher allegedly 2526628Sache * compatible with RSA Labs "RC4" cipher (the actual description of 2626628Sache * which is a trade secret). The same algorithm is used as a stream 2726628Sache * cipher called "arcfour" in Tatu Ylonen's ssh package. 2826628Sache * 2926628Sache * RC4 is a registered trademark of RSA Laboratories. 3026628Sache */ 3126628Sache 3292986Sobrien#include <sys/cdefs.h> 3392986Sobrien__FBSDID("$FreeBSD$"); 3492986Sobrien 3571579Sdeischen#include "namespace.h" 36267379Sdelphij#include <fcntl.h> 37267379Sdelphij#include <limits.h> 38267379Sdelphij#include <stdlib.h> 39267379Sdelphij#include <unistd.h> 4092986Sobrien#include <sys/types.h> 41267379Sdelphij#include <sys/param.h> 42267379Sdelphij#include <sys/sysctl.h> 4392986Sobrien#include <sys/time.h> 44127373Sgreen#include <pthread.h> 45127373Sgreen 46127373Sgreen#include "libc_private.h" 4771579Sdeischen#include "un-namespace.h" 4826628Sache 49267379Sdelphij#ifdef __GNUC__ 50267379Sdelphij#define inline __inline 51267379Sdelphij#else /* !__GNUC__ */ 52267379Sdelphij#define inline 53267379Sdelphij#endif /* !__GNUC__ */ 54267379Sdelphij 5526628Sachestruct arc4_stream { 5626628Sache u_int8_t i; 5726628Sache u_int8_t j; 5826628Sache u_int8_t s[256]; 5926628Sache}; 6026628Sache 61127373Sgreenstatic pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; 62127373Sgreen 63182886Sache#define RANDOMDEV "/dev/random" 64267379Sdelphij#define KEYSIZE 128 65267379Sdelphij#define _ARC4_LOCK() \ 66127373Sgreen do { \ 67127373Sgreen if (__isthreaded) \ 68127373Sgreen _pthread_mutex_lock(&arc4random_mtx); \ 69127373Sgreen } while (0) 70127373Sgreen 71267379Sdelphij#define _ARC4_UNLOCK() \ 72127373Sgreen do { \ 73127373Sgreen if (__isthreaded) \ 74127373Sgreen _pthread_mutex_unlock(&arc4random_mtx); \ 75127373Sgreen } while (0) 76127373Sgreen 77267379Sdelphijstatic int rs_initialized; 78127373Sgreenstatic struct arc4_stream rs; 79267379Sdelphijstatic pid_t arc4_stir_pid; 80162995Sachestatic int arc4_count; 8126628Sache 82267379Sdelphijextern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, 83267379Sdelphij void *newp, size_t newlen); 84267379Sdelphij 85180672Sachestatic inline u_int8_t arc4_getbyte(void); 86180672Sachestatic void arc4_stir(void); 87124741Sdas 8826628Sachestatic inline void 89180672Sachearc4_init(void) 9026628Sache{ 9126628Sache int n; 9226628Sache 9326628Sache for (n = 0; n < 256; n++) 94180672Sache rs.s[n] = n; 95180672Sache rs.i = 0; 96180672Sache rs.j = 0; 9726628Sache} 9826628Sache 9926628Sachestatic inline void 100180672Sachearc4_addrandom(u_char *dat, int datlen) 10126628Sache{ 10226628Sache int n; 10326628Sache u_int8_t si; 10426628Sache 105180672Sache rs.i--; 10626628Sache for (n = 0; n < 256; n++) { 107180672Sache rs.i = (rs.i + 1); 108180672Sache si = rs.s[rs.i]; 109180672Sache rs.j = (rs.j + si + dat[n % datlen]); 110180672Sache rs.s[rs.i] = rs.s[rs.j]; 111180672Sache rs.s[rs.j] = si; 11226628Sache } 113180672Sache rs.j = rs.i; 11426628Sache} 11526628Sache 116267379Sdelphijstatic size_t 117267379Sdelphijarc4_sysctl(u_char *buf, size_t size) 118267379Sdelphij{ 119267379Sdelphij int mib[2]; 120267379Sdelphij size_t len, done; 121267379Sdelphij 122267379Sdelphij mib[0] = CTL_KERN; 123267379Sdelphij mib[1] = KERN_ARND; 124267379Sdelphij done = 0; 125267379Sdelphij 126267379Sdelphij do { 127267379Sdelphij len = size; 128267379Sdelphij if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) 129267379Sdelphij return (done); 130267379Sdelphij done += len; 131267379Sdelphij buf += len; 132267379Sdelphij size -= len; 133267379Sdelphij } while (size > 0); 134267379Sdelphij 135267379Sdelphij return (done); 136267379Sdelphij} 137267379Sdelphij 13826628Sachestatic void 139180672Sachearc4_stir(void) 14026628Sache{ 141267379Sdelphij int done, fd, i; 14226628Sache struct { 143181261Sache struct timeval tv; 144267379Sdelphij pid_t pid; 145267379Sdelphij u_char rnd[KEYSIZE]; 146181261Sache } rdat; 14726628Sache 148267379Sdelphij if (!rs_initialized) { 149267379Sdelphij arc4_init(); 150267379Sdelphij rs_initialized = 1; 151267379Sdelphij } 152181261Sache done = 0; 153267379Sdelphij if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE) 154267379Sdelphij done = 1; 155181261Sache if (!done) { 156267379Sdelphij fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0); 157267379Sdelphij if (fd >= 0) { 158267379Sdelphij if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) 159267379Sdelphij done = 1; 160267379Sdelphij (void)_close(fd); 161267379Sdelphij } 162267379Sdelphij } 163267379Sdelphij if (!done) { 164181261Sache (void)gettimeofday(&rdat.tv, NULL); 165181261Sache rdat.pid = getpid(); 166181261Sache /* We'll just take whatever was on the stack too... */ 167181261Sache } 16826628Sache 169181261Sache arc4_addrandom((u_char *)&rdat, KEYSIZE); 170124741Sdas 171124741Sdas /* 172267379Sdelphij * Discard early keystream, as per recommendations in: 173267379Sdelphij * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 174124741Sdas */ 175267379Sdelphij for (i = 0; i < 1024; i++) 176267379Sdelphij (void)arc4_getbyte(); 177180655Sache arc4_count = 1600000; 17826628Sache} 17926628Sache 180267379Sdelphijstatic void 181267379Sdelphijarc4_stir_if_needed(void) 182267379Sdelphij{ 183267379Sdelphij pid_t pid = getpid(); 184267379Sdelphij 185267379Sdelphij if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 186267379Sdelphij { 187267379Sdelphij arc4_stir_pid = pid; 188267379Sdelphij arc4_stir(); 189267379Sdelphij } 190267379Sdelphij} 191267379Sdelphij 19226628Sachestatic inline u_int8_t 193180672Sachearc4_getbyte(void) 19426628Sache{ 19526628Sache u_int8_t si, sj; 19626628Sache 197180672Sache rs.i = (rs.i + 1); 198180672Sache si = rs.s[rs.i]; 199180672Sache rs.j = (rs.j + si); 200180672Sache sj = rs.s[rs.j]; 201180672Sache rs.s[rs.i] = sj; 202180672Sache rs.s[rs.j] = si; 203180672Sache return (rs.s[(si + sj) & 0xff]); 20426628Sache} 20526628Sache 20626628Sachestatic inline u_int32_t 207180672Sachearc4_getword(void) 20826628Sache{ 20926628Sache u_int32_t val; 210180672Sache val = arc4_getbyte() << 24; 211180672Sache val |= arc4_getbyte() << 16; 212180672Sache val |= arc4_getbyte() << 8; 213180672Sache val |= arc4_getbyte(); 214267379Sdelphij return val; 21526628Sache} 21626628Sache 217127373Sgreenvoid 218169981Sdelphijarc4random_stir(void) 219127373Sgreen{ 220267379Sdelphij _ARC4_LOCK(); 221180672Sache arc4_stir(); 222267379Sdelphij _ARC4_UNLOCK(); 22326628Sache} 22426628Sache 22526628Sachevoid 226169981Sdelphijarc4random_addrandom(u_char *dat, int datlen) 22726628Sache{ 228267379Sdelphij _ARC4_LOCK(); 229267379Sdelphij if (!rs_initialized) 230267379Sdelphij arc4_stir(); 231180672Sache arc4_addrandom(dat, datlen); 232267379Sdelphij _ARC4_UNLOCK(); 23326628Sache} 23426628Sache 23526628Sacheu_int32_t 236169981Sdelphijarc4random(void) 23726628Sache{ 238267379Sdelphij u_int32_t val; 239267379Sdelphij _ARC4_LOCK(); 240180656Sache arc4_count -= 4; 241267379Sdelphij arc4_stir_if_needed(); 242267379Sdelphij val = arc4_getword(); 243267379Sdelphij _ARC4_UNLOCK(); 244267379Sdelphij return val; 24526628Sache} 24626628Sache 247180657Sachevoid 248180657Sachearc4random_buf(void *_buf, size_t n) 249180657Sache{ 250180657Sache u_char *buf = (u_char *)_buf; 251267379Sdelphij _ARC4_LOCK(); 252267379Sdelphij arc4_stir_if_needed(); 253180657Sache while (n--) { 254267379Sdelphij if (--arc4_count <= 0) 255267379Sdelphij arc4_stir(); 256180672Sache buf[n] = arc4_getbyte(); 257180657Sache } 258267379Sdelphij _ARC4_UNLOCK(); 259180657Sache} 260180657Sache 261180688Sache/* 262180688Sache * Calculate a uniformly distributed random number less than upper_bound 263180688Sache * avoiding "modulo bias". 264180688Sache * 265180688Sache * Uniformity is achieved by generating new random numbers until the one 266180688Sache * returned is outside the range [0, 2**32 % upper_bound). This 267180688Sache * guarantees the selected random number will be inside 268180688Sache * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 269180688Sache * after reduction modulo upper_bound. 270180688Sache */ 271180688Sacheu_int32_t 272180688Sachearc4random_uniform(u_int32_t upper_bound) 273180688Sache{ 274180688Sache u_int32_t r, min; 275180688Sache 276180688Sache if (upper_bound < 2) 277267379Sdelphij return 0; 278180688Sache 279180688Sache#if (ULONG_MAX > 0xffffffffUL) 280180688Sache min = 0x100000000UL % upper_bound; 281180688Sache#else 282180688Sache /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 283180688Sache if (upper_bound > 0x80000000) 284180688Sache min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 285180688Sache else { 286180688Sache /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 287180688Sache min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 288180688Sache } 289180688Sache#endif 290180688Sache 291180688Sache /* 292180688Sache * This could theoretically loop forever but each retry has 293180688Sache * p > 0.5 (worst case, usually far better) of selecting a 294180688Sache * number inside the range we need, so it should rarely need 295180688Sache * to re-roll. 296180688Sache */ 297180688Sache for (;;) { 298180688Sache r = arc4random(); 299180688Sache if (r >= min) 300180688Sache break; 301180688Sache } 302180688Sache 303267379Sdelphij return r % upper_bound; 304180688Sache} 305180688Sache 30626628Sache#if 0 30726628Sache/*-------- Test code for i386 --------*/ 30826628Sache#include <stdio.h> 30926628Sache#include <machine/pctr.h> 31026628Sacheint 31126628Sachemain(int argc, char **argv) 31226628Sache{ 31326628Sache const int iter = 1000000; 31426628Sache int i; 31526628Sache pctrval v; 31626628Sache 31726628Sache v = rdtsc(); 31826628Sache for (i = 0; i < iter; i++) 31926628Sache arc4random(); 32026628Sache v = rdtsc() - v; 32126628Sache v /= iter; 32226628Sache 32326628Sache printf("%qd cycles\n", v); 32426628Sache} 32526628Sache#endif 326