1 /* $OpenBSD: arc4random.c,v 1.10 2003/11/26 21:40:08 djm 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 u_int8_t arc4_getbyte(struct arc4_stream *); 52 53 static inline void 54 arc4_init(struct arc4_stream *as) 55 { 56 int n; 57 58 for (n = 0; n < 256; n++) 59 as->s[n] = n; 60 as->i = 0; 61 as->j = 0; 62 } 63 64 static inline void 65 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) 66 { 67 int n; 68 u_int8_t si; 69 70 as->i--; 71 for (n = 0; n < 256; n++) { 72 as->i = (as->i + 1); 73 si = as->s[as->i]; 74 as->j = (as->j + si + dat[n % datlen]); 75 as->s[as->i] = as->s[as->j]; 76 as->s[as->j] = si; 77 } 78 as->j = as->i; 79 } 80 81 static void 82 arc4_stir(struct arc4_stream *as) 83 { 84 int i, mib[2]; 85 size_t len; 86 struct { 87 struct timeval tv; 88 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 89 } rdat; 90 91 gettimeofday(&rdat.tv, NULL); 92 mib[0] = CTL_KERN; 93 mib[1] = KERN_ARND; 94 95 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i ++) { 96 len = sizeof(u_int); 97 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 98 break; 99 } 100 101 arc4_stir_pid = getpid(); 102 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 103 104 /* 105 * Discard early keystream, as per recommendations in: 106 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 107 */ 108 for (i = 0; i < 256; i++) 109 (void) arc4_getbyte(as); 110 } 111 112 static inline u_int8_t 113 arc4_getbyte(struct arc4_stream *as) 114 { 115 u_int8_t si, sj; 116 117 as->i = (as->i + 1); 118 si = as->s[as->i]; 119 as->j = (as->j + si); 120 sj = as->s[as->j]; 121 as->s[as->i] = sj; 122 as->s[as->j] = si; 123 return (as->s[(si + sj) & 0xff]); 124 } 125 126 static inline u_int32_t 127 arc4_getword(struct arc4_stream *as) 128 { 129 u_int32_t val; 130 val = arc4_getbyte(as) << 24; 131 val |= arc4_getbyte(as) << 16; 132 val |= arc4_getbyte(as) << 8; 133 val |= arc4_getbyte(as); 134 return val; 135 } 136 137 void 138 arc4random_stir(void) 139 { 140 if (!rs_initialized) { 141 arc4_init(&rs); 142 rs_initialized = 1; 143 } 144 arc4_stir(&rs); 145 } 146 147 void 148 arc4random_addrandom(u_char *dat, int datlen) 149 { 150 if (!rs_initialized) 151 arc4random_stir(); 152 arc4_addrandom(&rs, dat, datlen); 153 } 154 155 u_int32_t 156 arc4random(void) 157 { 158 if (!rs_initialized || arc4_stir_pid != getpid()) 159 arc4random_stir(); 160 return arc4_getword(&rs); 161 } 162 163 #if 0 164 /*-------- Test code for i386 --------*/ 165 #include <stdio.h> 166 #include <machine/pctr.h> 167 int 168 main(int argc, char **argv) 169 { 170 const int iter = 1000000; 171 int i; 172 pctrval v; 173 174 v = rdtsc(); 175 for (i = 0; i < iter; i++) 176 arc4random(); 177 v = rdtsc() - v; 178 v /= iter; 179 180 printf("%qd cycles\n", v); 181 } 182 #endif 183