1 /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev 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 int rs_initialized; 48 static struct arc4_stream rs; 49 50 static inline void 51 arc4_init(as) 52 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(as, dat, datlen) 64 struct arc4_stream *as; 65 u_char *dat; 66 int datlen; 67 { 68 int n; 69 u_int8_t si; 70 71 as->i--; 72 for (n = 0; n < 256; n++) { 73 as->i = (as->i + 1); 74 si = as->s[as->i]; 75 as->j = (as->j + si + dat[n % datlen]); 76 as->s[as->i] = as->s[as->j]; 77 as->s[as->j] = si; 78 } 79 as->j = as->i; 80 } 81 82 static void 83 arc4_stir(as) 84 struct arc4_stream *as; 85 { 86 int fd; 87 struct { 88 struct timeval tv; 89 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 90 } rdat; 91 92 gettimeofday(&rdat.tv, NULL); 93 fd = open("/dev/arandom", O_RDONLY); 94 if (fd != -1) { 95 read(fd, rdat.rnd, sizeof(rdat.rnd)); 96 close(fd); 97 } else { 98 int i, mib[2]; 99 size_t len; 100 101 /* Device could not be opened, we might be chrooted, take 102 * randomness from sysctl. */ 103 104 mib[0] = CTL_KERN; 105 mib[1] = KERN_ARND; 106 107 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i ++) { 108 len = sizeof(u_int); 109 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 110 break; 111 } 112 } 113 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 114 * whatever was on the stack... */ 115 116 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 117 } 118 119 static inline u_int8_t 120 arc4_getbyte(as) 121 struct arc4_stream *as; 122 { 123 u_int8_t si, sj; 124 125 as->i = (as->i + 1); 126 si = as->s[as->i]; 127 as->j = (as->j + si); 128 sj = as->s[as->j]; 129 as->s[as->i] = sj; 130 as->s[as->j] = si; 131 return (as->s[(si + sj) & 0xff]); 132 } 133 134 static inline u_int32_t 135 arc4_getword(as) 136 struct arc4_stream *as; 137 { 138 u_int32_t val; 139 val = arc4_getbyte(as) << 24; 140 val |= arc4_getbyte(as) << 16; 141 val |= arc4_getbyte(as) << 8; 142 val |= arc4_getbyte(as); 143 return val; 144 } 145 146 void 147 arc4random_stir() 148 { 149 if (!rs_initialized) { 150 arc4_init(&rs); 151 rs_initialized = 1; 152 } 153 arc4_stir(&rs); 154 } 155 156 void 157 arc4random_addrandom(dat, datlen) 158 u_char *dat; 159 int datlen; 160 { 161 if (!rs_initialized) 162 arc4random_stir(); 163 arc4_addrandom(&rs, dat, datlen); 164 } 165 166 u_int32_t 167 arc4random() 168 { 169 if (!rs_initialized) 170 arc4random_stir(); 171 return arc4_getword(&rs); 172 } 173 174 #if 0 175 /*-------- Test code for i386 --------*/ 176 #include <stdio.h> 177 #include <machine/pctr.h> 178 int 179 main(int argc, char **argv) 180 { 181 const int iter = 1000000; 182 int i; 183 pctrval v; 184 185 v = rdtsc(); 186 for (i = 0; i < iter; i++) 187 arc4random(); 188 v = rdtsc() - v; 189 v /= iter; 190 191 printf("%qd cycles\n", v); 192 } 193 #endif 194