1 /* $NetBSD: arc4random.c,v 1.9 2005/12/24 21:11:16 perry 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.9 2005/12/24 21:11:16 perry 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 struct arc4_stream { 47 u_int8_t i; 48 u_int8_t j; 49 u_int8_t s[256]; 50 }; 51 52 static int rs_initialized; 53 static struct arc4_stream rs; 54 55 static inline void arc4_init(struct arc4_stream *); 56 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int); 57 static void arc4_stir(struct arc4_stream *); 58 static inline u_int8_t arc4_getbyte(struct arc4_stream *); 59 static inline u_int32_t arc4_getword(struct arc4_stream *); 60 61 static inline void 62 arc4_init(as) 63 struct arc4_stream *as; 64 { 65 int n; 66 67 for (n = 0; n < 256; n++) 68 as->s[n] = n; 69 as->i = 0; 70 as->j = 0; 71 } 72 73 static inline void 74 arc4_addrandom(as, dat, datlen) 75 struct arc4_stream *as; 76 u_char *dat; 77 int datlen; 78 { 79 int n; 80 u_int8_t si; 81 82 as->i--; 83 for (n = 0; n < 256; n++) { 84 as->i = (as->i + 1); 85 si = as->s[as->i]; 86 as->j = (as->j + si + dat[n % datlen]); 87 as->s[as->i] = as->s[as->j]; 88 as->s[as->j] = si; 89 } 90 as->j = as->i; 91 } 92 93 static void 94 arc4_stir(as) 95 struct arc4_stream *as; 96 { 97 int fd; 98 struct { 99 struct timeval tv; 100 u_int rnd[(128 - sizeof(struct timeval)) / sizeof(u_int)]; 101 } rdat; 102 int n; 103 104 gettimeofday(&rdat.tv, NULL); 105 fd = open("/dev/urandom", O_RDONLY); 106 if (fd != -1) { 107 read(fd, rdat.rnd, sizeof(rdat.rnd)); 108 close(fd); 109 } 110 #ifdef KERN_URND 111 else { 112 int mib[2]; 113 u_int i; 114 size_t len; 115 116 /* Device could not be opened, we might be chrooted, take 117 * randomness from sysctl. */ 118 119 mib[0] = CTL_KERN; 120 mib[1] = KERN_URND; 121 122 for (i = 0; i < sizeof(rdat.rnd) / sizeof(u_int); i++) { 123 len = sizeof(u_int); 124 if (sysctl(mib, 2, &rdat.rnd[i], &len, NULL, 0) == -1) 125 break; 126 } 127 } 128 #endif 129 /* fd < 0 or failed sysctl ? Ah, what the heck. We'll just take 130 * whatever was on the stack... */ 131 132 arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); 133 134 /* 135 * Throw away the first N words of output, as suggested in the 136 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 137 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 138 */ 139 for (n = 0; n < 256 * 4; n++) 140 arc4_getbyte(as); 141 } 142 143 static inline u_int8_t 144 arc4_getbyte(as) 145 struct arc4_stream *as; 146 { 147 u_int8_t si, sj; 148 149 as->i = (as->i + 1); 150 si = as->s[as->i]; 151 as->j = (as->j + si); 152 sj = as->s[as->j]; 153 as->s[as->i] = sj; 154 as->s[as->j] = si; 155 return (as->s[(si + sj) & 0xff]); 156 } 157 158 static inline u_int32_t 159 arc4_getword(as) 160 struct arc4_stream *as; 161 { 162 u_int32_t val; 163 val = arc4_getbyte(as) << 24; 164 val |= arc4_getbyte(as) << 16; 165 val |= arc4_getbyte(as) << 8; 166 val |= arc4_getbyte(as); 167 return val; 168 } 169 170 void 171 arc4random_stir() 172 { 173 if (!rs_initialized) { 174 arc4_init(&rs); 175 rs_initialized = 1; 176 } 177 arc4_stir(&rs); 178 } 179 180 void 181 arc4random_addrandom(dat, datlen) 182 u_char *dat; 183 int datlen; 184 { 185 if (!rs_initialized) 186 arc4random_stir(); 187 arc4_addrandom(&rs, dat, datlen); 188 } 189 190 u_int32_t 191 arc4random() 192 { 193 if (!rs_initialized) 194 arc4random_stir(); 195 return arc4_getword(&rs); 196 } 197 198 #if 0 199 /*-------- Test code for i386 --------*/ 200 #include <stdio.h> 201 #include <machine/pctr.h> 202 int 203 main(int argc, char **argv) 204 { 205 const int iter = 1000000; 206 int i; 207 pctrval v; 208 209 v = rdtsc(); 210 for (i = 0; i < iter; i++) 211 arc4random(); 212 v = rdtsc() - v; 213 v /= iter; 214 215 printf("%qd cycles\n", v); 216 } 217 #endif 218