1 /* $OpenBSD: arc4random.c,v 1.15 2005/11/30 07:51:02 otto Exp $ */ 2 3 /* 4 * Copyright (c) 1996, David Mazieres <dm@uun.org> 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 sysctl(mib, 2, rnd, &len, NULL, 0); 103 104 arc4_stir_pid = getpid(); 105 arc4_addrandom(as, rnd, sizeof(rnd)); 106 107 /* 108 * Discard early keystream, as per recommendations in: 109 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 110 */ 111 for (i = 0; i < 256; i++) 112 (void)arc4_getbyte(as); 113 arc4_count = 400000; 114 } 115 116 static inline u_int8_t 117 arc4_getbyte(struct arc4_stream *as) 118 { 119 u_int8_t si, sj; 120 121 as->i = (as->i + 1); 122 si = as->s[as->i]; 123 as->j = (as->j + si); 124 sj = as->s[as->j]; 125 as->s[as->i] = sj; 126 as->s[as->j] = si; 127 return (as->s[(si + sj) & 0xff]); 128 } 129 130 static inline u_int32_t 131 arc4_getword(struct arc4_stream *as) 132 { 133 u_int32_t val; 134 val = arc4_getbyte(as) << 24; 135 val |= arc4_getbyte(as) << 16; 136 val |= arc4_getbyte(as) << 8; 137 val |= arc4_getbyte(as); 138 return val; 139 } 140 141 void 142 arc4random_stir(void) 143 { 144 if (!rs_initialized) { 145 arc4_init(&rs); 146 rs_initialized = 1; 147 } 148 arc4_stir(&rs); 149 } 150 151 void 152 arc4random_addrandom(u_char *dat, int datlen) 153 { 154 if (!rs_initialized) 155 arc4random_stir(); 156 arc4_addrandom(&rs, dat, datlen); 157 } 158 159 u_int32_t 160 arc4random(void) 161 { 162 if (--arc4_count == 0 || !rs_initialized || arc4_stir_pid != getpid()) 163 arc4random_stir(); 164 return arc4_getword(&rs); 165 } 166 167 #if 0 168 /*-------- Test code for i386 --------*/ 169 #include <stdio.h> 170 #include <machine/pctr.h> 171 int 172 main(int argc, char **argv) 173 { 174 const int iter = 1000000; 175 int i; 176 pctrval v; 177 178 v = rdtsc(); 179 for (i = 0; i < iter; i++) 180 arc4random(); 181 v = rdtsc() - v; 182 v /= iter; 183 184 printf("%qd cycles\n", v); 185 } 186 #endif 187