arc4random.c revision 1.3.2.4
1 1.3.2.4 nathanw /* $NetBSD: arc4random.c,v 1.3.2.4 2002/11/11 22:22:01 nathanw Exp $ */ 2 1.3.2.2 nathanw /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */ 3 1.3.2.2 nathanw 4 1.3.2.2 nathanw /* 5 1.3.2.2 nathanw * Arc4 random number generator for OpenBSD. 6 1.3.2.2 nathanw * Copyright 1996 David Mazieres <dm (at) lcs.mit.edu>. 7 1.3.2.2 nathanw * 8 1.3.2.2 nathanw * Modification and redistribution in source and binary forms is 9 1.3.2.2 nathanw * permitted provided that due credit is given to the author and the 10 1.3.2.2 nathanw * OpenBSD project by leaving this copyright notice intact. 11 1.3.2.2 nathanw */ 12 1.3.2.2 nathanw 13 1.3.2.2 nathanw /* 14 1.3.2.2 nathanw * This code is derived from section 17.1 of Applied Cryptography, 15 1.3.2.2 nathanw * second edition, which describes a stream cipher allegedly 16 1.3.2.2 nathanw * compatible with RSA Labs "RC4" cipher (the actual description of 17 1.3.2.2 nathanw * which is a trade secret). The same algorithm is used as a stream 18 1.3.2.2 nathanw * cipher called "arcfour" in Tatu Ylonen's ssh package. 19 1.3.2.2 nathanw * 20 1.3.2.2 nathanw * Here the stream cipher has been modified always to include the time 21 1.3.2.2 nathanw * when initializing the state. That makes it impossible to 22 1.3.2.2 nathanw * regenerate the same random sequence twice, so this can't be used 23 1.3.2.2 nathanw * for encryption, but will generate good random numbers. 24 1.3.2.2 nathanw * 25 1.3.2.2 nathanw * RC4 is a registered trademark of RSA Laboratories. 26 1.3.2.2 nathanw */ 27 1.3.2.2 nathanw 28 1.3.2.2 nathanw #include <fcntl.h> 29 1.3.2.2 nathanw #include <stdlib.h> 30 1.3.2.2 nathanw #include <unistd.h> 31 1.3.2.2 nathanw #include <sys/types.h> 32 1.3.2.2 nathanw #include <sys/param.h> 33 1.3.2.2 nathanw #include <sys/time.h> 34 1.3.2.2 nathanw #include <sys/sysctl.h> 35 1.3.2.2 nathanw 36 1.3.2.2 nathanw #ifdef __GNUC__ 37 1.3.2.2 nathanw #define inline __inline 38 1.3.2.2 nathanw #else /* !__GNUC__ */ 39 1.3.2.2 nathanw #define inline 40 1.3.2.2 nathanw #endif /* !__GNUC__ */ 41 1.3.2.2 nathanw 42 1.3.2.2 nathanw struct arc4_stream { 43 1.3.2.2 nathanw u_int8_t i; 44 1.3.2.2 nathanw u_int8_t j; 45 1.3.2.2 nathanw u_int8_t s[256]; 46 1.3.2.2 nathanw }; 47 1.3.2.2 nathanw 48 1.3.2.2 nathanw int rs_initialized; 49 1.3.2.2 nathanw static struct arc4_stream rs; 50 1.3.2.2 nathanw 51 1.3.2.2 nathanw static inline void arc4_init(struct arc4_stream *); 52 1.3.2.2 nathanw static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 53 1.3.2.2 nathanw static void arc4_stir(struct arc4_stream *); 54 1.3.2.2 nathanw static inline u_int8_t arc4_getbyte(struct arc4_stream *); 55 1.3.2.2 nathanw static inline u_int32_t arc4_getword(struct arc4_stream *); 56 1.3.2.2 nathanw 57 1.3.2.2 nathanw static inline void 58 1.3.2.2 nathanw arc4_init(as) 59 1.3.2.2 nathanw struct arc4_stream *as; 60 1.3.2.2 nathanw { 61 1.3.2.2 nathanw int n; 62 1.3.2.2 nathanw 63 1.3.2.2 nathanw for (n = 0; n < 256; n++) 64 1.3.2.2 nathanw as->s[n] = n; 65 1.3.2.2 nathanw as->i = 0; 66 1.3.2.2 nathanw as->j = 0; 67 1.3.2.2 nathanw } 68 1.3.2.2 nathanw 69 1.3.2.2 nathanw static inline void 70 1.3.2.2 nathanw arc4_addrandom(as, dat, datlen) 71 1.3.2.2 nathanw struct arc4_stream *as; 72 1.3.2.2 nathanw u_char *dat; 73 1.3.2.2 nathanw int datlen; 74 1.3.2.2 nathanw { 75 1.3.2.2 nathanw int n; 76 1.3.2.2 nathanw u_int8_t si; 77 1.3.2.2 nathanw 78 1.3.2.2 nathanw as->i--; 79 1.3.2.2 nathanw for (n = 0; n < 256; n++) { 80 1.3.2.2 nathanw as->i = (as->i + 1); 81 1.3.2.2 nathanw si = as->s[as->i]; 82 1.3.2.2 nathanw as->j = (as->j + si + dat[n % datlen]); 83 1.3.2.2 nathanw as->s[as->i] = as->s[as->j]; 84 1.3.2.2 nathanw as->s[as->j] = si; 85 1.3.2.2 nathanw } 86 1.3.2.2 nathanw as->j = as->i; 87 1.3.2.2 nathanw } 88 1.3.2.2 nathanw 89 1.3.2.2 nathanw static void 90 1.3.2.2 nathanw arc4_stir(as) 91 1.3.2.2 nathanw struct arc4_stream *as; 92 1.3.2.2 nathanw { 93 1.3.2.2 nathanw int fd; 94 1.3.2.2 nathanw struct { 95 1.3.2.2 nathanw struct timeval tv; 96 1.3.2.2 nathanw u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 97 1.3.2.2 nathanw } rdat; 98 1.3.2.2 nathanw int n; 99 1.3.2.2 nathanw 100 1.3.2.2 nathanw gettimeofday(&rdat.tv, NULL); 101 1.3.2.2 nathanw fd = open("/dev/urandom", O_RDONLY); 102 1.3.2.2 nathanw if (fd != -1) { 103 1.3.2.2 nathanw read(fd, rdat.rnd, sizeof(rdat.rnd)); 104 1.3.2.2 nathanw close(fd); 105 1.3.2.2 nathanw } 106 1.3.2.3 nathanw #ifdef KERN_URND 107 1.3.2.2 nathanw else { 108 1.3.2.4 nathanw int mib[2]; 109 1.3.2.4 nathanw u_int i; 110 1.3.2.2 nathanw size_t len; 111 1.3.2.2 nathanw 112 1.3.2.2 nathanw /* Device could not be opened, we might be chrooted, take 113 1.3.2.2 nathanw * randomness from sysctl. */ 114 1.3.2.2 nathanw 115 1.3.2.2 nathanw mib[0] = CTL_KERN; 116 1.3.2.3 nathanw mib[1] = KERN_URND; 117 1.3.2.2 nathanw 118 1.3.2.4 nathanw for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i++) { 119 1.3.2.2 nathanw len = sizeof(u_int); 120 1.3.2.2 nathanw if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 121 1.3.2.2 nathanw break; 122 1.3.2.2 nathanw } 123 1.3.2.2 nathanw } 124 1.3.2.2 nathanw #endif 125 1.3.2.2 nathanw /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 126 1.3.2.2 nathanw * whatever was on the stack... */ 127 1.3.2.2 nathanw 128 1.3.2.2 nathanw arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 129 1.3.2.2 nathanw 130 1.3.2.2 nathanw /* 131 1.3.2.2 nathanw * Throw away the first N words of output, as suggested in the 132 1.3.2.2 nathanw * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 133 1.3.2.2 nathanw * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 134 1.3.2.2 nathanw */ 135 1.3.2.2 nathanw for (n = 0; n < 256 * 4; n++) 136 1.3.2.2 nathanw arc4_getbyte(as); 137 1.3.2.2 nathanw } 138 1.3.2.2 nathanw 139 1.3.2.2 nathanw static inline u_int8_t 140 1.3.2.2 nathanw arc4_getbyte(as) 141 1.3.2.2 nathanw struct arc4_stream *as; 142 1.3.2.2 nathanw { 143 1.3.2.2 nathanw u_int8_t si, sj; 144 1.3.2.2 nathanw 145 1.3.2.2 nathanw as->i = (as->i + 1); 146 1.3.2.2 nathanw si = as->s[as->i]; 147 1.3.2.2 nathanw as->j = (as->j + si); 148 1.3.2.2 nathanw sj = as->s[as->j]; 149 1.3.2.2 nathanw as->s[as->i] = sj; 150 1.3.2.2 nathanw as->s[as->j] = si; 151 1.3.2.2 nathanw return (as->s[(si + sj) & 0xff]); 152 1.3.2.2 nathanw } 153 1.3.2.2 nathanw 154 1.3.2.2 nathanw static inline u_int32_t 155 1.3.2.2 nathanw arc4_getword(as) 156 1.3.2.2 nathanw struct arc4_stream *as; 157 1.3.2.2 nathanw { 158 1.3.2.2 nathanw u_int32_t val; 159 1.3.2.2 nathanw val = arc4_getbyte(as) << 24; 160 1.3.2.2 nathanw val |= arc4_getbyte(as) << 16; 161 1.3.2.2 nathanw val |= arc4_getbyte(as) << 8; 162 1.3.2.2 nathanw val |= arc4_getbyte(as); 163 1.3.2.2 nathanw return val; 164 1.3.2.2 nathanw } 165 1.3.2.2 nathanw 166 1.3.2.2 nathanw void 167 1.3.2.2 nathanw arc4random_stir() 168 1.3.2.2 nathanw { 169 1.3.2.2 nathanw if (!rs_initialized) { 170 1.3.2.2 nathanw arc4_init(&rs); 171 1.3.2.2 nathanw rs_initialized = 1; 172 1.3.2.2 nathanw } 173 1.3.2.2 nathanw arc4_stir(&rs); 174 1.3.2.2 nathanw } 175 1.3.2.2 nathanw 176 1.3.2.2 nathanw void 177 1.3.2.2 nathanw arc4random_addrandom(dat, datlen) 178 1.3.2.2 nathanw u_char *dat; 179 1.3.2.2 nathanw int datlen; 180 1.3.2.2 nathanw { 181 1.3.2.2 nathanw if (!rs_initialized) 182 1.3.2.2 nathanw arc4random_stir(); 183 1.3.2.2 nathanw arc4_addrandom(&rs, dat, datlen); 184 1.3.2.2 nathanw } 185 1.3.2.2 nathanw 186 1.3.2.2 nathanw u_int32_t 187 1.3.2.2 nathanw arc4random() 188 1.3.2.2 nathanw { 189 1.3.2.2 nathanw if (!rs_initialized) 190 1.3.2.2 nathanw arc4random_stir(); 191 1.3.2.2 nathanw return arc4_getword(&rs); 192 1.3.2.2 nathanw } 193 1.3.2.2 nathanw 194 1.3.2.2 nathanw #if 0 195 1.3.2.2 nathanw /*-------- Test code for i386 --------*/ 196 1.3.2.2 nathanw #include <stdio.h> 197 1.3.2.2 nathanw #include <machine/pctr.h> 198 1.3.2.2 nathanw int 199 1.3.2.2 nathanw main(int argc, char **argv) 200 1.3.2.2 nathanw { 201 1.3.2.2 nathanw const int iter = 1000000; 202 1.3.2.2 nathanw int i; 203 1.3.2.2 nathanw pctrval v; 204 1.3.2.2 nathanw 205 1.3.2.2 nathanw v = rdtsc(); 206 1.3.2.2 nathanw for (i = 0; i < iter; i++) 207 1.3.2.2 nathanw arc4random(); 208 1.3.2.2 nathanw v = rdtsc() - v; 209 1.3.2.2 nathanw v /= iter; 210 1.3.2.2 nathanw 211 1.3.2.2 nathanw printf("%qd cycles\n", v); 212 1.3.2.2 nathanw } 213 1.3.2.2 nathanw #endif 214
Indexes created Mon Sep 29 21:09:56 GMT 2025