1 /* $OpenBSD: arc4random.c,v 1.8 2003/06/11 21:03:10 deraadt Exp $ */ 2 3 /* 4 * Arc4 random number generator for OpenBSD. 5 * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 6 * 7 * Modification and redistribution in source and binary forms is 8 * permitted provided that due credit is given to the author and the 9 * OpenBSD project by leaving this copyright notice intact. 10 */ 11 12 /* 13 * This code is derived from section 17.1 of Applied Cryptography, 14 * second edition, which describes a stream cipher allegedly 15 * compatible with RSA Labs "RC4" cipher (the actual description of 16 * which is a trade secret). The same algorithm is used as a stream 17 * cipher called "arcfour" in Tatu Ylonen's ssh package. 18 * 19 * Here the stream cipher has been modified always to include the time 20 * when initializing the state. That makes it impossible to 21 * regenerate the same random sequence twice, so this can't be used 22 * for encryption, but will generate good random numbers. 23 * 24 * RC4 is a registered trademark of RSA Laboratories. 25 */ 26 27 #include <fcntl.h> 28 #include <stdlib.h> 29 #include <unistd.h> 30 #include <sys/types.h> 31 #include <sys/param.h> 32 #include <sys/time.h> 33 #include <sys/sysctl.h> 34 35 #ifdef __GNUC__ 36 #define inline __inline 37 #else /* !__GNUC__ */ 38 #define inline 39 #endif /* !__GNUC__ */ 40 41 struct arc4_stream { 42 u_int8_t i; 43 u_int8_t j; 44 u_int8_t s[256]; 45 }; 46 47 static int rs_initialized; 48 static struct arc4_stream rs; 49 static pid_t arc4_stir_pid; 50 51 static inline void 52 arc4_init(struct arc4_stream *as) 53 { 54 int n; 55 56 for (n = 0; n < 256; n++) 57 as->s[n] = n; 58 as->i = 0; 59 as->j = 0; 60 } 61 62 static inline void 63 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 64 { 65 int n; 66 u_int8_t si; 67 68 as->i--; 69 for (n = 0; n < 256; n++) { 70 as->i = (as->i + 1); 71 si = as->s[as->i]; 72 as->j = (as->j + si + dat[n % datlen]); 73 as->s[as->i] = as->s[as->j]; 74 as->s[as->j] = si; 75 } 76 as->j = as->i; 77 } 78 79 static void 80 arc4_stir(struct arc4_stream *as) 81 { 82 int fd; 83 struct { 84 struct timeval tv; 85 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 86 } rdat; 87 88 gettimeofday(&rdat.tv, NULL); 89 fd = open("/dev/arandom", O_RDONLY); 90 if (fd != -1) { 91 read(fd, rdat.rnd, sizeof(rdat.rnd)); 92 close(fd); 93 } else { 94 int i, mib[2]; 95 size_t len; 96 97 /* Device could not be opened, we might be chrooted, take 98 * randomness from sysctl. */ 99 100 mib[0] = CTL_KERN; 101 mib[1] = KERN_ARND; 102 103 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i ++) { 104 len = sizeof(u_int); 105 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 106 break; 107 } 108 } 109 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 110 * whatever was on the stack... */ 111 112 arc4_stir_pid = getpid(); 113 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 114 } 115 116 static inline u_int8_t 117 arc4_getbyte(struct arc4_stream *as) 118 { 119 u_int8_t si, sj; 120 121 as->i = (as->i + 1); 122 si = as->s[as->i]; 123 as->j = (as->j + si); 124 sj = as->s[as->j]; 125 as->s[as->i] = sj; 126 as->s[as->j] = si; 127 return (as->s[(si + sj) & 0xff]); 128 } 129 130 static inline u_int32_t 131 arc4_getword(struct arc4_stream *as) 132 { 133 u_int32_t val; 134 val = arc4_getbyte(as) << 24; 135 val |= arc4_getbyte(as) << 16; 136 val |= arc4_getbyte(as) << 8; 137 val |= arc4_getbyte(as); 138 return val; 139 } 140 141 void 142 arc4random_stir(void) 143 { 144 if (!rs_initialized) { 145 arc4_init(&rs); 146 rs_initialized = 1; 147 } 148 arc4_stir(&rs); 149 } 150 151 void 152 arc4random_addrandom(u_char *dat, int datlen) 153 { 154 if (!rs_initialized) 155 arc4random_stir(); 156 arc4_addrandom(&rs, dat, datlen); 157 } 158 159 u_int32_t 160 arc4random(void) 161 { 162 if (!rs_initialized || arc4_stir_pid != getpid()) 163 arc4random_stir(); 164 return arc4_getword(&rs); 165 } 166 167 #if 0 168 /*-------- Test code for i386 --------*/ 169 #include <stdio.h> 170 #include <machine/pctr.h> 171 int 172 main(int argc, char **argv) 173 { 174 const int iter = 1000000; 175 int i; 176 pctrval v; 177 178 v = rdtsc(); 179 for (i = 0; i < iter; i++) 180 arc4random(); 181 v = rdtsc() - v; 182 v /= iter; 183 184 printf("%qd cycles\n", v); 185 } 186 #endif 187