1 /* 2 * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */ 7 8 /* 9 * Arc4 random number generator for OpenBSD. 10 * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. 11 * 12 * Modification and redistribution in source and binary forms is 13 * permitted provided that due credit is given to the author and the 14 * OpenBSD project by leaving this copyright notice intact. 15 */ 16 17 /* 18 * This code is derived from section 17.1 of Applied Cryptography, 19 * second edition, which describes a stream cipher allegedly 20 * compatible with RSA Labs "RC4" cipher (the actual description of 21 * which is a trade secret). The same algorithm is used as a stream 22 * cipher called "arcfour" in Tatu Ylonen's ssh package. 23 * 24 * Here the stream cipher has been modified always to include the time 25 * when initializing the state. That makes it impossible to 26 * regenerate the same random sequence twice, so this can't be used 27 * for encryption, but will generate good random numbers. 28 * 29 * RC4 is a registered trademark of RSA Laboratories. 30 */ 31 32 #include <fcntl.h> 33 #include <stdlib.h> 34 #include <unistd.h> 35 #include <sys/types.h> 36 #include <sys/param.h> 37 #include <sys/time.h> 38 39 #ifdef __GNUC__ 40 #define inline __inline 41 #else /* !__GNUC__ */ 42 #define inline 43 #endif /* !__GNUC__ */ 44 45 struct arc4_stream { 46 uint8_t i; 47 uint8_t j; 48 uint8_t s[256]; 49 }; 50 51 int rs_initialized; 52 static struct arc4_stream rs; 53 54 static inline void 55 arc4_init(as) 56 struct arc4_stream *as; 57 { 58 int n; 59 60 for (n = 0; n < 256; n++) 61 as->s[n] = n; 62 as->i = 0; 63 as->j = 0; 64 } 65 66 static inline void 67 arc4_addrandom(as, dat, datlen) 68 struct arc4_stream *as; 69 u_char *dat; 70 size_t datlen; 71 { 72 int n; 73 uint8_t si; 74 75 as->i--; 76 for (n = 0; n < 256; n++) { 77 as->i = (as->i + 1); 78 si = as->s[as->i]; 79 as->j = (as->j + si + dat[n % datlen]); 80 as->s[as->i] = as->s[as->j]; 81 as->s[as->j] = si; 82 } 83 as->j = as->i; 84 } 85 86 static void 87 arc4_stir(as) 88 struct arc4_stream *as; 89 { 90 int fd; 91 struct { 92 struct timeval tv; 93 uint rnd[(128 - sizeof(struct timeval)) / sizeof(uint)]; 94 } rdat; 95 96 (void) gettimeofday(&rdat.tv, NULL); 97 fd = open("/dev/urandom", O_RDONLY); 98 if (fd != -1) { 99 (void) read(fd, rdat.rnd, sizeof(rdat.rnd)); 100 (void) close(fd); 101 } 102 /* fd < 0 ? Ah, what the heck. We'll just take 103 * whatever was on the stack... */ 104 105 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 106 } 107 108 static inline uint8_t 109 arc4_getbyte(as) 110 struct arc4_stream *as; 111 { 112 uint8_t si, sj; 113 114 as->i = (as->i + 1); 115 si = as->s[as->i]; 116 as->j = (as->j + si); 117 sj = as->s[as->j]; 118 as->s[as->i] = sj; 119 as->s[as->j] = si; 120 return (as->s[(si + sj) & 0xff]); 121 } 122 123 static inline uint32_t 124 arc4_getword(as) 125 struct arc4_stream *as; 126 { 127 uint32_t val; 128 val = arc4_getbyte(as) << 24; 129 val |= arc4_getbyte(as) << 16; 130 val |= arc4_getbyte(as) << 8; 131 val |= arc4_getbyte(as); 132 return val; 133 } 134 135 void 136 arc4random_stir() 137 { 138 if (!rs_initialized) { 139 arc4_init(&rs); 140 rs_initialized = 1; 141 } 142 arc4_stir(&rs); 143 } 144 145 void 146 arc4random_addrandom(dat, datlen) 147 u_char *dat; 148 size_t datlen; 149 { 150 if (!rs_initialized) 151 arc4random_stir(); 152 arc4_addrandom(&rs, dat, datlen); 153 } 154 155 uint32_t 156 arc4random() 157 { 158 if (!rs_initialized) 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