1268962Spfg/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */ 2227519Sdas 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" 36227520Sdas#include <fcntl.h> 37227520Sdas#include <limits.h> 38227520Sdas#include <stdlib.h> 39227520Sdas#include <unistd.h> 4092986Sobrien#include <sys/types.h> 41227520Sdas#include <sys/param.h> 42238118Spjd#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 49227519Sdas#ifdef __GNUC__ 50227519Sdas#define inline __inline 51227519Sdas#else /* !__GNUC__ */ 52227519Sdas#define inline 53227519Sdas#endif /* !__GNUC__ */ 54227519Sdas 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" 64227519Sdas#define KEYSIZE 128 65227519Sdas#define _ARC4_LOCK() \ 66127373Sgreen do { \ 67127373Sgreen if (__isthreaded) \ 68127373Sgreen _pthread_mutex_lock(&arc4random_mtx); \ 69127373Sgreen } while (0) 70127373Sgreen 71227519Sdas#define _ARC4_UNLOCK() \ 72127373Sgreen do { \ 73127373Sgreen if (__isthreaded) \ 74127373Sgreen _pthread_mutex_unlock(&arc4random_mtx); \ 75127373Sgreen } while (0) 76127373Sgreen 77227520Sdasstatic int rs_initialized; 78127373Sgreenstatic struct arc4_stream rs; 79227520Sdasstatic pid_t arc4_stir_pid; 80162995Sachestatic int arc4_count; 8126628Sache 82238118Spjdextern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, 83238118Spjd void *newp, size_t newlen); 84238118Spjd 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 116238118Spjdstatic size_t 117238118Spjdarc4_sysctl(u_char *buf, size_t size) 118238118Spjd{ 119238118Spjd int mib[2]; 120238118Spjd size_t len, done; 121238118Spjd 122238118Spjd mib[0] = CTL_KERN; 123238118Spjd mib[1] = KERN_ARND; 124238118Spjd done = 0; 125238118Spjd 126238118Spjd do { 127238118Spjd len = size; 128238118Spjd if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) 129238118Spjd return (done); 130238118Spjd done += len; 131238118Spjd buf += len; 132238118Spjd size -= len; 133238118Spjd } while (size > 0); 134238118Spjd 135238118Spjd return (done); 136238118Spjd} 137238118Spjd 13826628Sachestatic void 139180672Sachearc4_stir(void) 14026628Sache{ 141227519Sdas int done, fd, i; 14226628Sache struct { 143181261Sache struct timeval tv; 144227519Sdas pid_t pid; 145227519Sdas u_char rnd[KEYSIZE]; 146181261Sache } rdat; 14726628Sache 148227520Sdas if (!rs_initialized) { 149227520Sdas arc4_init(); 150227520Sdas rs_initialized = 1; 151227520Sdas } 152181261Sache done = 0; 153238118Spjd if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE) 154238118Spjd done = 1; 155238118Spjd if (!done) { 156241046Sjilles fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0); 157238118Spjd if (fd >= 0) { 158238118Spjd if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) 159238118Spjd done = 1; 160238118Spjd (void)_close(fd); 161238118Spjd } 162227519Sdas } 163181261Sache 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 /* 172227519Sdas * Discard early keystream, as per recommendations in: 173227519Sdas * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 174124741Sdas */ 175227519Sdas for (i = 0; i < 1024; i++) 176227519Sdas (void)arc4_getbyte(); 177180655Sache arc4_count = 1600000; 17826628Sache} 17926628Sache 180227520Sdasstatic void 181227520Sdasarc4_stir_if_needed(void) 182227520Sdas{ 183227520Sdas pid_t pid = getpid(); 184227520Sdas 185268962Spfg if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) { 186227520Sdas arc4_stir_pid = pid; 187227520Sdas arc4_stir(); 188227520Sdas } 189227520Sdas} 190227520Sdas 19126628Sachestatic inline u_int8_t 192180672Sachearc4_getbyte(void) 19326628Sache{ 19426628Sache u_int8_t si, sj; 19526628Sache 196180672Sache rs.i = (rs.i + 1); 197180672Sache si = rs.s[rs.i]; 198180672Sache rs.j = (rs.j + si); 199180672Sache sj = rs.s[rs.j]; 200180672Sache rs.s[rs.i] = sj; 201180672Sache rs.s[rs.j] = si; 202180672Sache return (rs.s[(si + sj) & 0xff]); 20326628Sache} 20426628Sache 20526628Sachestatic inline u_int32_t 206180672Sachearc4_getword(void) 20726628Sache{ 20826628Sache u_int32_t val; 209180672Sache val = arc4_getbyte() << 24; 210180672Sache val |= arc4_getbyte() << 16; 211180672Sache val |= arc4_getbyte() << 8; 212180672Sache val |= arc4_getbyte(); 213227519Sdas return val; 21426628Sache} 21526628Sache 216127373Sgreenvoid 217169981Sdelphijarc4random_stir(void) 218127373Sgreen{ 219227519Sdas _ARC4_LOCK(); 220180672Sache arc4_stir(); 221227519Sdas _ARC4_UNLOCK(); 22226628Sache} 22326628Sache 22426628Sachevoid 225169981Sdelphijarc4random_addrandom(u_char *dat, int datlen) 22626628Sache{ 227227519Sdas _ARC4_LOCK(); 228227520Sdas if (!rs_initialized) 229227520Sdas arc4_stir(); 230180672Sache arc4_addrandom(dat, datlen); 231227519Sdas _ARC4_UNLOCK(); 23226628Sache} 23326628Sache 23426628Sacheu_int32_t 235169981Sdelphijarc4random(void) 23626628Sache{ 237227519Sdas u_int32_t val; 238227519Sdas _ARC4_LOCK(); 239227520Sdas arc4_count -= 4; 240227520Sdas arc4_stir_if_needed(); 241227519Sdas val = arc4_getword(); 242227519Sdas _ARC4_UNLOCK(); 243227519Sdas return val; 24426628Sache} 24526628Sache 246180657Sachevoid 247180657Sachearc4random_buf(void *_buf, size_t n) 248180657Sache{ 249180657Sache u_char *buf = (u_char *)_buf; 250227519Sdas _ARC4_LOCK(); 251227520Sdas arc4_stir_if_needed(); 252180657Sache while (n--) { 253227520Sdas if (--arc4_count <= 0) 254227520Sdas arc4_stir(); 255180672Sache buf[n] = arc4_getbyte(); 256180657Sache } 257227519Sdas _ARC4_UNLOCK(); 258180657Sache} 259180657Sache 260180688Sache/* 261180688Sache * Calculate a uniformly distributed random number less than upper_bound 262180688Sache * avoiding "modulo bias". 263180688Sache * 264180688Sache * Uniformity is achieved by generating new random numbers until the one 265180688Sache * returned is outside the range [0, 2**32 % upper_bound). This 266180688Sache * guarantees the selected random number will be inside 267180688Sache * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 268180688Sache * after reduction modulo upper_bound. 269180688Sache */ 270180688Sacheu_int32_t 271180688Sachearc4random_uniform(u_int32_t upper_bound) 272180688Sache{ 273180688Sache u_int32_t r, min; 274180688Sache 275180688Sache if (upper_bound < 2) 276227519Sdas return 0; 277180688Sache 278268962Spfg /* 2**32 % x == (2**32 - x) % x */ 279268962Spfg min = -upper_bound % upper_bound; 280180688Sache /* 281180688Sache * This could theoretically loop forever but each retry has 282180688Sache * p > 0.5 (worst case, usually far better) of selecting a 283180688Sache * number inside the range we need, so it should rarely need 284180688Sache * to re-roll. 285180688Sache */ 286180688Sache for (;;) { 287180688Sache r = arc4random(); 288180688Sache if (r >= min) 289180688Sache break; 290180688Sache } 291180688Sache 292227519Sdas return r % upper_bound; 293180688Sache} 294180688Sache 29526628Sache#if 0 29626628Sache/*-------- Test code for i386 --------*/ 29726628Sache#include <stdio.h> 29826628Sache#include <machine/pctr.h> 29926628Sacheint 30026628Sachemain(int argc, char **argv) 30126628Sache{ 30226628Sache const int iter = 1000000; 30326628Sache int i; 30426628Sache pctrval v; 30526628Sache 30626628Sache v = rdtsc(); 30726628Sache for (i = 0; i < iter; i++) 30826628Sache arc4random(); 30926628Sache v = rdtsc() - v; 31026628Sache v /= iter; 31126628Sache 31226628Sache printf("%qd cycles\n", v); 31326628Sache} 31426628Sache#endif 315