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