1 /* $NetBSD: arc4random.c,v 1.7 2005/02/09 21:35:46 kleink 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 "namespace.h" 29 #include <fcntl.h> 30 #include <stdlib.h> 31 #include <unistd.h> 32 #include <sys/types.h> 33 #include <sys/param.h> 34 #include <sys/time.h> 35 #include <sys/sysctl.h> 36 37 #ifdef __weak_alias 38 __weak_alias(arc4random,_arc4random) 39 #endif 40 41 #ifdef __GNUC__ 42 #define inline __inline 43 #else /* !__GNUC__ */ 44 #define inline 45 #endif /* !__GNUC__ */ 46 47 struct arc4_stream { 48 u_int8_t i; 49 u_int8_t j; 50 u_int8_t s[256]; 51 }; 52 53 static int rs_initialized; 54 static struct arc4_stream rs; 55 56 static inline void arc4_init(struct arc4_stream *); 57 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 58 static void arc4_stir(struct arc4_stream *); 59 static inline u_int8_t arc4_getbyte(struct arc4_stream *); 60 static inline u_int32_t arc4_getword(struct arc4_stream *); 61 62 static inline void 63 arc4_init(as) 64 struct arc4_stream *as; 65 { 66 int n; 67 68 for (n = 0; n < 256; n++) 69 as->s[n] = n; 70 as->i = 0; 71 as->j = 0; 72 } 73 74 static inline void 75 arc4_addrandom(as, dat, datlen) 76 struct arc4_stream *as; 77 u_char *dat; 78 int datlen; 79 { 80 int n; 81 u_int8_t si; 82 83 as->i--; 84 for (n = 0; n < 256; n++) { 85 as->i = (as->i + 1); 86 si = as->s[as->i]; 87 as->j = (as->j + si + dat[n % datlen]); 88 as->s[as->i] = as->s[as->j]; 89 as->s[as->j] = si; 90 } 91 as->j = as->i; 92 } 93 94 static void 95 arc4_stir(as) 96 struct arc4_stream *as; 97 { 98 int fd; 99 struct { 100 struct timeval tv; 101 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 102 } rdat; 103 int n; 104 105 gettimeofday(&rdat.tv, NULL); 106 fd = open("/dev/urandom", O_RDONLY); 107 if (fd != -1) { 108 read(fd, rdat.rnd, sizeof(rdat.rnd)); 109 close(fd); 110 } 111 #ifdef KERN_URND 112 else { 113 int mib[2]; 114 u_int i; 115 size_t len; 116 117 /* Device could not be opened, we might be chrooted, take 118 * randomness from sysctl. */ 119 120 mib[0] = CTL_KERN; 121 mib[1] = KERN_URND; 122 123 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i++) { 124 len = sizeof(u_int); 125 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 126 break; 127 } 128 } 129 #endif 130 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 131 * whatever was on the stack... */ 132 133 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 134 135 /* 136 * Throw away the first N words of output, as suggested in the 137 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 138 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 139 */ 140 for (n = 0; n < 256 * 4; n++) 141 arc4_getbyte(as); 142 } 143 144 static inline u_int8_t 145 arc4_getbyte(as) 146 struct arc4_stream *as; 147 { 148 u_int8_t si, sj; 149 150 as->i = (as->i + 1); 151 si = as->s[as->i]; 152 as->j = (as->j + si); 153 sj = as->s[as->j]; 154 as->s[as->i] = sj; 155 as->s[as->j] = si; 156 return (as->s[(si + sj) & 0xff]); 157 } 158 159 static inline u_int32_t 160 arc4_getword(as) 161 struct arc4_stream *as; 162 { 163 u_int32_t val; 164 val = arc4_getbyte(as) << 24; 165 val |= arc4_getbyte(as) << 16; 166 val |= arc4_getbyte(as) << 8; 167 val |= arc4_getbyte(as); 168 return val; 169 } 170 171 void 172 arc4random_stir() 173 { 174 if (!rs_initialized) { 175 arc4_init(&rs); 176 rs_initialized = 1; 177 } 178 arc4_stir(&rs); 179 } 180 181 void 182 arc4random_addrandom(dat, datlen) 183 u_char *dat; 184 int datlen; 185 { 186 if (!rs_initialized) 187 arc4random_stir(); 188 arc4_addrandom(&rs, dat, datlen); 189 } 190 191 u_int32_t 192 arc4random() 193 { 194 if (!rs_initialized) 195 arc4random_stir(); 196 return arc4_getword(&rs); 197 } 198 199 #if 0 200 /*-------- Test code for i386 --------*/ 201 #include <stdio.h> 202 #include <machine/pctr.h> 203 int 204 main(int argc, char **argv) 205 { 206 const int iter = 1000000; 207 int i; 208 pctrval v; 209 210 v = rdtsc(); 211 for (i = 0; i < iter; i++) 212 arc4random(); 213 v = rdtsc() - v; 214 v /= iter; 215 216 printf("%qd cycles\n", v); 217 } 218 #endif 219