1 /*- 2 * THE BEER-WARE LICENSE 3 * 4 * <dan@FreeBSD.ORG> wrote this file. As long as you retain this notice you 5 * can do whatever you want with this stuff. If we meet some day, and you 6 * think this stuff is worth it, you can buy me a beer in return. 7 * 8 * Dan Moschuk 9 */ 10 11 #include <sys/cdefs.h> 12 __FBSDID("$FreeBSD$"); 13 14 #include <sys/types.h> 15 #include <sys/param.h> 16 #include <sys/kernel.h> 17 #include <sys/random.h> 18 #include <sys/libkern.h> 19 #include <sys/lock.h> 20 #include <sys/mutex.h> 21 #include <sys/time.h> 22 #include <sys/smp.h> 23 #include <sys/malloc.h> 24 25 #define ARC4_RESEED_BYTES 65536 26 #define ARC4_RESEED_SECONDS 300 27 #define ARC4_KEYBYTES 256 28 29 int arc4rand_iniseed_state = ARC4_ENTR_NONE; 30 31 MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures"); 32 33 struct arc4_s { 34 struct mtx mtx; 35 u_int8_t i, j; 36 int numruns; 37 u_int8_t sbox[256]; 38 time_t t_reseed; 39 40 } __aligned(CACHE_LINE_SIZE); 41 42 static struct arc4_s *arc4inst = NULL; 43 44 #define ARC4_FOREACH(_arc4) \ 45 for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++) 46 47 static u_int8_t arc4_randbyte(struct arc4_s *arc4); 48 49 static __inline void 50 arc4_swap(u_int8_t *a, u_int8_t *b) 51 { 52 u_int8_t c; 53 54 c = *a; 55 *a = *b; 56 *b = c; 57 } 58 59 /* 60 * Stir our S-box. 61 */ 62 static void 63 arc4_randomstir(struct arc4_s* arc4) 64 { 65 u_int8_t key[ARC4_KEYBYTES]; 66 int n; 67 struct timeval tv_now; 68 69 /* 70 * XXX: FIX!! This isn't brilliant. Need more confidence. 71 * This returns zero entropy before random(4) is seeded. 72 */ 73 (void)read_random(key, ARC4_KEYBYTES); 74 getmicrouptime(&tv_now); 75 mtx_lock(&arc4->mtx); 76 for (n = 0; n < 256; n++) { 77 arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256; 78 arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]); 79 } 80 arc4->i = arc4->j = 0; 81 /* Reset for next reseed cycle. */ 82 arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS; 83 arc4->numruns = 0; 84 /* 85 * Throw away the first N words of output, as suggested in the 86 * paper "Weaknesses in the Key Scheduling Algorithm of RC4" 87 * by Fluher, Mantin, and Shamir. (N = 256 in our case.) 88 * 89 * http://dl.acm.org/citation.cfm?id=646557.694759 90 */ 91 for (n = 0; n < 256*4; n++) 92 arc4_randbyte(arc4); 93 94 mtx_unlock(&arc4->mtx); 95 } 96 97 /* 98 * Initialize our S-box to its beginning defaults. 99 */ 100 static void 101 arc4_init(void) 102 { 103 struct arc4_s *arc4; 104 int n; 105 106 arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s), 107 M_ARC4RANDOM, M_NOWAIT | M_ZERO); 108 KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error")); 109 110 ARC4_FOREACH(arc4) { 111 mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF); 112 113 arc4->i = arc4->j = 0; 114 for (n = 0; n < 256; n++) 115 arc4->sbox[n] = (u_int8_t) n; 116 117 arc4->t_reseed = -1; 118 arc4->numruns = 0; 119 } 120 } 121 SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL); 122 123 124 static void 125 arc4_uninit(void) 126 { 127 struct arc4_s *arc4; 128 129 ARC4_FOREACH(arc4) { 130 mtx_destroy(&arc4->mtx); 131 } 132 133 free(arc4inst, M_ARC4RANDOM); 134 } 135 136 SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL); 137 138 139 /* 140 * Generate a random byte. 141 */ 142 static u_int8_t 143 arc4_randbyte(struct arc4_s *arc4) 144 { 145 u_int8_t arc4_t; 146 147 arc4->i = (arc4->i + 1) % 256; 148 arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256; 149 150 arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]); 151 152 arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256; 153 return arc4->sbox[arc4_t]; 154 } 155 156 /* 157 * MPSAFE 158 */ 159 void 160 arc4rand(void *ptr, u_int len, int reseed) 161 { 162 u_char *p; 163 struct timeval tv; 164 struct arc4_s *arc4; 165 166 if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state, 167 ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) { 168 ARC4_FOREACH(arc4) 169 arc4_randomstir(arc4); 170 } 171 172 arc4 = &arc4inst[curcpu]; 173 getmicrouptime(&tv); 174 if ((arc4->numruns > ARC4_RESEED_BYTES) || 175 (tv.tv_sec > arc4->t_reseed)) 176 arc4_randomstir(arc4); 177 178 mtx_lock(&arc4->mtx); 179 arc4->numruns += len; 180 p = ptr; 181 while (len--) 182 *p++ = arc4_randbyte(arc4); 183 mtx_unlock(&arc4->mtx); 184 } 185 186 uint32_t 187 arc4random(void) 188 { 189 uint32_t ret; 190 191 arc4rand(&ret, sizeof ret, 0); 192 return ret; 193 } 194