1 /* $OpenBSD: arc4random.c,v 1.13 2005/06/06 04:54:28 kjell Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm@lcs.mit.edu> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 /* 20 * Arc4 random number generator for OpenBSD. 21 * 22 * This code is derived from section 17.1 of Applied Cryptography, 23 * second edition, which describes a stream cipher allegedly 24 * compatible with RSA Labs "RC4" cipher (the actual description of 25 * which is a trade secret). The same algorithm is used as a stream 26 * cipher called "arcfour" in Tatu Ylonen's ssh package. 27 * 28 * Here the stream cipher has been modified always to include the time 29 * when initializing the state. That makes it impossible to 30 * regenerate the same random sequence twice, so this can't be used 31 * for encryption, but will generate good random numbers. 32 * 33 * RC4 is a registered trademark of RSA Laboratories. 34 */ 35 36 #include <fcntl.h> 37 #include <stdlib.h> 38 #include <unistd.h> 39 #include <sys/types.h> 40 #include <sys/param.h> 41 #include <sys/time.h> 42 #include <sys/sysctl.h> 43 44 #ifdef __GNUC__ 45 #define inline __inline 46 #else /* !__GNUC__ */ 47 #define inline 48 #endif /* !__GNUC__ */ 49 50 struct arc4_stream { 51 u_int8_t i; 52 u_int8_t j; 53 u_int8_t s[256]; 54 }; 55 56 static int rs_initialized; 57 static struct arc4_stream rs; 58 static pid_t arc4_stir_pid; 59 static int arc4_count; 60 61 static inline u_int8_t arc4_getbyte(struct arc4_stream *); 62 63 static inline void 64 arc4_init(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(struct arc4_stream *as, u_char *dat, int datlen) 76 { 77 int n; 78 u_int8_t si; 79 80 as->i--; 81 for (n = 0; n < 256; n++) { 82 as->i = (as->i + 1); 83 si = as->s[as->i]; 84 as->j = (as->j + si + dat[n % datlen]); 85 as->s[as->i] = as->s[as->j]; 86 as->s[as->j] = si; 87 } 88 as->j = as->i; 89 } 90 91 static void 92 arc4_stir(struct arc4_stream *as) 93 { 94 int i, mib[2]; 95 size_t len; 96 u_char rnd[128]; 97 98 mib[0] = CTL_KERN; 99 mib[1] = KERN_ARND; 100 101 len = sizeof(rnd); 102 if (sysctl(mib, 2, rnd, &len, NULL, 0) == -1) { 103 for (i = 0; i < sizeof(rnd) / sizeof(u_int); i ++) { 104 len = sizeof(u_int); 105 if (sysctl(mib, 2, &rnd[i * sizeof(u_int)], &len, 106 NULL, 0) == -1) 107 break; 108 } 109 } 110 111 arc4_stir_pid = getpid(); 112 arc4_addrandom(as, rnd, sizeof(rnd)); 113 114 /* 115 * Discard early keystream, as per recommendations in: 116 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 117 */ 118 for (i = 0; i < 256; i++) 119 (void)arc4_getbyte(as); 120 arc4_count = 400000; 121 } 122 123 static inline u_int8_t 124 arc4_getbyte(struct arc4_stream *as) 125 { 126 u_int8_t si, sj; 127 128 as->i = (as->i + 1); 129 si = as->s[as->i]; 130 as->j = (as->j + si); 131 sj = as->s[as->j]; 132 as->s[as->i] = sj; 133 as->s[as->j] = si; 134 return (as->s[(si + sj) & 0xff]); 135 } 136 137 static inline u_int32_t 138 arc4_getword(struct arc4_stream *as) 139 { 140 u_int32_t val; 141 val = arc4_getbyte(as) << 24; 142 val |= arc4_getbyte(as) << 16; 143 val |= arc4_getbyte(as) << 8; 144 val |= arc4_getbyte(as); 145 return val; 146 } 147 148 void 149 arc4random_stir(void) 150 { 151 if (!rs_initialized) { 152 arc4_init(&rs); 153 rs_initialized = 1; 154 } 155 arc4_stir(&rs); 156 } 157 158 void 159 arc4random_addrandom(u_char *dat, int datlen) 160 { 161 if (!rs_initialized) 162 arc4random_stir(); 163 arc4_addrandom(&rs, dat, datlen); 164 } 165 166 u_int32_t 167 arc4random(void) 168 { 169 if (--arc4_count == 0 || !rs_initialized || arc4_stir_pid != getpid()) 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