arc4random.c revision 50476
1274955Ssvnmir/* $FreeBSD: head/lib/libc/gen/arc4random.c 50476 1999-08-28 00:22:10Z peter $ */ 2274955Ssvnmir 3353358Sdim/* 4353358Sdim * Arc4 random number generator for OpenBSD. 5353358Sdim * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 6274955Ssvnmir * 7274955Ssvnmir * Modification and redistribution in source and binary forms is 8274955Ssvnmir * permitted provided that due credit is given to the author and the 9274955Ssvnmir * OpenBSD project (for instance by leaving this copyright notice 10327952Sdim * intact). 11327952Sdim */ 12327952Sdim 13341825Sdim/* 14280031Sdim * This code is derived from section 17.1 of Applied Cryptography, 15274955Ssvnmir * second edition, which describes a stream cipher allegedly 16274955Ssvnmir * compatible with RSA Labs "RC4" cipher (the actual description of 17274955Ssvnmir * which is a trade secret). The same algorithm is used as a stream 18274955Ssvnmir * cipher called "arcfour" in Tatu Ylonen's ssh package. 19274955Ssvnmir * 20274955Ssvnmir * Here the stream cipher has been modified always to include the time 21280031Sdim * when initializing the state. That makes it impossible to 22274955Ssvnmir * regenerate the same random sequence twice, so this can't be used 23327952Sdim * for encryption, but will generate good random numbers. 24341825Sdim * 25341825Sdim * RC4 is a registered trademark of RSA Laboratories. 26341825Sdim */ 27274955Ssvnmir 28327952Sdim#include <stdlib.h> 29280031Sdim#include <fcntl.h> 30327952Sdim#include <unistd.h> 31274955Ssvnmir#include <sys/types.h> 32274955Ssvnmir#include <sys/time.h> 33274955Ssvnmir 34327952Sdimstruct arc4_stream { 35327952Sdim u_int8_t i; 36274955Ssvnmir u_int8_t j; 37274955Ssvnmir u_int8_t s[256]; 38274955Ssvnmir}; 39280031Sdim 40274955Ssvnmirstatic int rs_initialized; 41274955Ssvnmirstatic struct arc4_stream rs; 42280031Sdim 43280031Sdimstatic inline void 44280031Sdimarc4_init(as) 45280031Sdim struct arc4_stream *as; 46280031Sdim{ 47280031Sdim int n; 48327952Sdim 49327952Sdim for (n = 0; n < 256; n++) 50327952Sdim as->s[n] = n; 51327952Sdim as->i = 0; 52327952Sdim as->j = 0; 53327952Sdim} 54274955Ssvnmir 55274955Ssvnmirstatic inline void 56274955Ssvnmirarc4_addrandom(as, dat, datlen) 57274955Ssvnmir struct arc4_stream *as; 58274955Ssvnmir u_char *dat; 59274955Ssvnmir int datlen; 60274955Ssvnmir{ 61274955Ssvnmir int n; 62327952Sdim u_int8_t si; 63327952Sdim 64341825Sdim as->i--; 65327952Sdim for (n = 0; n < 256; n++) { 66327952Sdim as->i = (as->i + 1); 67296417Sdim si = as->s[as->i]; 68327952Sdim as->j = (as->j + si + dat[n % datlen]); 69341825Sdim as->s[as->i] = as->s[as->j]; 70274955Ssvnmir as->s[as->j] = si; 71296417Sdim } 72274955Ssvnmir} 73274955Ssvnmir 74274955Ssvnmirstatic void 75arc4_stir(as) 76 struct arc4_stream *as; 77{ 78 int fd; 79 struct { 80 struct timeval tv; 81 pid_t pid; 82 u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)]; 83 } rdat; 84 85 gettimeofday(&rdat.tv, NULL); 86 rdat.pid = getpid(); 87 fd = open("/dev/urandom", O_RDONLY, 0); 88 if (fd >= 0) { 89 (void) read(fd, rdat.rnd, sizeof(rdat.rnd)); 90 close(fd); 91 } 92 /* fd < 0? Ah, what the heck. We'll just take whatever was on the 93 * stack... */ 94 95 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 96} 97 98static inline u_int8_t 99arc4_getbyte(as) 100 struct arc4_stream *as; 101{ 102 u_int8_t si, sj; 103 104 as->i = (as->i + 1); 105 si = as->s[as->i]; 106 as->j = (as->j + si); 107 sj = as->s[as->j]; 108 as->s[as->i] = sj; 109 as->s[as->j] = si; 110 return (as->s[(si + sj) & 0xff]); 111} 112 113static inline u_int32_t 114arc4_getword(as) 115 struct arc4_stream *as; 116{ 117 u_int32_t val; 118 val = arc4_getbyte(as) << 24; 119 val |= arc4_getbyte(as) << 16; 120 val |= arc4_getbyte(as) << 8; 121 val |= arc4_getbyte(as); 122 return val; 123} 124 125void 126arc4random_stir() 127{ 128 if (!rs_initialized) { 129 arc4_init(&rs); 130 rs_initialized = 1; 131 } 132 arc4_stir(&rs); 133} 134 135void 136arc4random_addrandom(dat, datlen) 137 u_char *dat; 138 int datlen; 139{ 140 if (!rs_initialized) 141 arc4random_stir(); 142 arc4_addrandom(&rs, dat, datlen); 143} 144 145u_int32_t 146arc4random() 147{ 148 if (!rs_initialized) 149 arc4random_stir(); 150 return arc4_getword(&rs); 151} 152 153#if 0 154/*-------- Test code for i386 --------*/ 155#include <stdio.h> 156#include <machine/pctr.h> 157int 158main(int argc, char **argv) 159{ 160 const int iter = 1000000; 161 int i; 162 pctrval v; 163 164 v = rdtsc(); 165 for (i = 0; i < iter; i++) 166 arc4random(); 167 v = rdtsc() - v; 168 v /= iter; 169 170 printf("%qd cycles\n", v); 171} 172#endif 173