arc4random.c revision 71579
150476Speter/* $FreeBSD: head/lib/libc/gen/arc4random.c 71579 2001-01-24 13:01:12Z deischen $ */ 226628Sache 326628Sache/* 426628Sache * Arc4 random number generator for OpenBSD. 526628Sache * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 626628Sache * 726628Sache * Modification and redistribution in source and binary forms is 826628Sache * permitted provided that due credit is given to the author and the 926628Sache * OpenBSD project (for instance by leaving this copyright notice 1026628Sache * intact). 1126628Sache */ 1226628Sache 1326628Sache/* 1426628Sache * This code is derived from section 17.1 of Applied Cryptography, 1526628Sache * second edition, which describes a stream cipher allegedly 1626628Sache * compatible with RSA Labs "RC4" cipher (the actual description of 1726628Sache * which is a trade secret). The same algorithm is used as a stream 1826628Sache * cipher called "arcfour" in Tatu Ylonen's ssh package. 1926628Sache * 2026628Sache * Here the stream cipher has been modified always to include the time 2126628Sache * when initializing the state. That makes it impossible to 2226628Sache * regenerate the same random sequence twice, so this can't be used 2326628Sache * for encryption, but will generate good random numbers. 2426628Sache * 2526628Sache * RC4 is a registered trademark of RSA Laboratories. 2626628Sache */ 2726628Sache 2871579Sdeischen#include "namespace.h" 2926628Sache#include <stdlib.h> 3026628Sache#include <fcntl.h> 3126628Sache#include <unistd.h> 3226628Sache#include <sys/types.h> 3326628Sache#include <sys/time.h> 3471579Sdeischen#include "un-namespace.h" 3526628Sache 3626628Sachestruct arc4_stream { 3726628Sache u_int8_t i; 3826628Sache u_int8_t j; 3926628Sache u_int8_t s[256]; 4026628Sache}; 4126628Sache 4226628Sachestatic int rs_initialized; 4326628Sachestatic struct arc4_stream rs; 4426628Sache 4526628Sachestatic inline void 4626628Sachearc4_init(as) 4726628Sache struct arc4_stream *as; 4826628Sache{ 4926628Sache int n; 5026628Sache 5126628Sache for (n = 0; n < 256; n++) 5226628Sache as->s[n] = n; 5326628Sache as->i = 0; 5426628Sache as->j = 0; 5526628Sache} 5626628Sache 5726628Sachestatic inline void 5826628Sachearc4_addrandom(as, dat, datlen) 5926628Sache struct arc4_stream *as; 6026628Sache u_char *dat; 6126628Sache int datlen; 6226628Sache{ 6326628Sache int n; 6426628Sache u_int8_t si; 6526628Sache 6626628Sache as->i--; 6726628Sache for (n = 0; n < 256; n++) { 6826628Sache as->i = (as->i + 1); 6926628Sache si = as->s[as->i]; 7026628Sache as->j = (as->j + si + dat[n % datlen]); 7126628Sache as->s[as->i] = as->s[as->j]; 7226628Sache as->s[as->j] = si; 7326628Sache } 7426628Sache} 7526628Sache 7626628Sachestatic void 7726628Sachearc4_stir(as) 7826628Sache struct arc4_stream *as; 7926628Sache{ 8026628Sache int fd; 8126628Sache struct { 8226628Sache struct timeval tv; 8326628Sache pid_t pid; 8426628Sache u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)]; 8526628Sache } rdat; 8626628Sache 8726628Sache gettimeofday(&rdat.tv, NULL); 8826628Sache rdat.pid = getpid(); 8956698Sjasone fd = _open("/dev/urandom", O_RDONLY, 0); 9026628Sache if (fd >= 0) { 9156698Sjasone (void) _read(fd, rdat.rnd, sizeof(rdat.rnd)); 9256698Sjasone _close(fd); 9326628Sache } 9426628Sache /* fd < 0? Ah, what the heck. We'll just take whatever was on the 9526628Sache * stack... */ 9626628Sache 9726628Sache arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 9826628Sache} 9926628Sache 10026628Sachestatic inline u_int8_t 10126628Sachearc4_getbyte(as) 10226628Sache struct arc4_stream *as; 10326628Sache{ 10426628Sache u_int8_t si, sj; 10526628Sache 10626628Sache as->i = (as->i + 1); 10726628Sache si = as->s[as->i]; 10826628Sache as->j = (as->j + si); 10926628Sache sj = as->s[as->j]; 11026628Sache as->s[as->i] = sj; 11126628Sache as->s[as->j] = si; 11226628Sache return (as->s[(si + sj) & 0xff]); 11326628Sache} 11426628Sache 11526628Sachestatic inline u_int32_t 11626628Sachearc4_getword(as) 11726628Sache struct arc4_stream *as; 11826628Sache{ 11926628Sache u_int32_t val; 12026628Sache val = arc4_getbyte(as) << 24; 12126628Sache val |= arc4_getbyte(as) << 16; 12226628Sache val |= arc4_getbyte(as) << 8; 12326628Sache val |= arc4_getbyte(as); 12426628Sache return val; 12526628Sache} 12626628Sache 12726628Sachevoid 12826628Sachearc4random_stir() 12926628Sache{ 13026628Sache if (!rs_initialized) { 13126628Sache arc4_init(&rs); 13226628Sache rs_initialized = 1; 13326628Sache } 13426628Sache arc4_stir(&rs); 13526628Sache} 13626628Sache 13726628Sachevoid 13826628Sachearc4random_addrandom(dat, datlen) 13926628Sache u_char *dat; 14026628Sache int datlen; 14126628Sache{ 14226628Sache if (!rs_initialized) 14326628Sache arc4random_stir(); 14426628Sache arc4_addrandom(&rs, dat, datlen); 14526628Sache} 14626628Sache 14726628Sacheu_int32_t 14826628Sachearc4random() 14926628Sache{ 15026628Sache if (!rs_initialized) 15126628Sache arc4random_stir(); 15226628Sache return arc4_getword(&rs); 15326628Sache} 15426628Sache 15526628Sache#if 0 15626628Sache/*-------- Test code for i386 --------*/ 15726628Sache#include <stdio.h> 15826628Sache#include <machine/pctr.h> 15926628Sacheint 16026628Sachemain(int argc, char **argv) 16126628Sache{ 16226628Sache const int iter = 1000000; 16326628Sache int i; 16426628Sache pctrval v; 16526628Sache 16626628Sache v = rdtsc(); 16726628Sache for (i = 0; i < iter; i++) 16826628Sache arc4random(); 16926628Sache v = rdtsc() - v; 17026628Sache v /= iter; 17126628Sache 17226628Sache printf("%qd cycles\n", v); 17326628Sache} 17426628Sache#endif 175