1227519Sdas/* $OpenBSD: arc4random.c,v 1.22 2010/12/22 08:23:42 otto 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 185227520Sdas if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 186227520Sdas { 187227520Sdas arc4_stir_pid = pid; 188227520Sdas arc4_stir(); 189227520Sdas } 190227520Sdas} 191227520Sdas 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(); 214227519Sdas return val; 21526628Sache} 21626628Sache 217127373Sgreenvoid 218169981Sdelphijarc4random_stir(void) 219127373Sgreen{ 220227519Sdas _ARC4_LOCK(); 221180672Sache arc4_stir(); 222227519Sdas _ARC4_UNLOCK(); 22326628Sache} 22426628Sache 22526628Sachevoid 226169981Sdelphijarc4random_addrandom(u_char *dat, int datlen) 22726628Sache{ 228227519Sdas _ARC4_LOCK(); 229227520Sdas if (!rs_initialized) 230227520Sdas arc4_stir(); 231180672Sache arc4_addrandom(dat, datlen); 232227519Sdas _ARC4_UNLOCK(); 23326628Sache} 23426628Sache 23526628Sacheu_int32_t 236169981Sdelphijarc4random(void) 23726628Sache{ 238227519Sdas u_int32_t val; 239227519Sdas _ARC4_LOCK(); 240227520Sdas arc4_count -= 4; 241227520Sdas arc4_stir_if_needed(); 242227519Sdas val = arc4_getword(); 243227519Sdas _ARC4_UNLOCK(); 244227519Sdas return val; 24526628Sache} 24626628Sache 247180657Sachevoid 248180657Sachearc4random_buf(void *_buf, size_t n) 249180657Sache{ 250180657Sache u_char *buf = (u_char *)_buf; 251227519Sdas _ARC4_LOCK(); 252227520Sdas arc4_stir_if_needed(); 253180657Sache while (n--) { 254227520Sdas if (--arc4_count <= 0) 255227520Sdas arc4_stir(); 256180672Sache buf[n] = arc4_getbyte(); 257180657Sache } 258227519Sdas _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) 277227519Sdas 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 303227519Sdas 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