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