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