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 * $FreeBSD: src/sys/libkern/arc4random.c,v 1.3.2.2 2001/09/17 07:06:50 silby Exp $ 11 * $DragonFly: src/sys/libkern/arc4random.c,v 1.3 2006/09/03 17:31:55 dillon Exp $ 12 */ 13 14 #include <sys/types.h> 15 #include <sys/systm.h> 16 #include <sys/random.h> 17 #include <sys/libkern.h> 18 #include <sys/time.h> 19 20 #include <vm/vm_extern.h> 21 22 #define ARC4_MAXRUNS 16384 23 #define ARC4_RESEED_SECONDS 300 24 #define ARC4_KEYBYTES 32 /* 256 bit key */ 25 26 struct arc4_data { 27 uint8_t arc4_i; 28 uint8_t arc4_j; 29 int arc4_numruns; 30 time_t arc4_nextreseed; 31 uint8_t arc4_sbox[256]; 32 }; 33 34 static struct arc4_data *arc4_data_pcpu[MAXCPU]; 35 36 static uint8_t arc4_randbyte(struct arc4_data *); 37 38 static __inline void 39 arc4_swap(uint8_t *a, uint8_t *b) 40 { 41 uint8_t c; 42 43 c = *a; 44 *a = *b; 45 *b = c; 46 } 47 48 /* 49 * Stir our S-box. 50 */ 51 static void 52 arc4_randomstir(struct arc4_data *d) 53 { 54 uint8_t key[256]; 55 int r, n; 56 57 /* 58 * XXX read_random() returns unsafe numbers if the entropy 59 * device is not loaded -- MarkM. 60 */ 61 r = read_random_unlimited(key, ARC4_KEYBYTES); 62 /* If r == 0 || -1, just use what was on the stack. */ 63 if (r > 0) { 64 for (n = r; n < sizeof(key); n++) 65 key[n] = key[n % r]; 66 } 67 68 for (n = 0; n < 256; n++) { 69 d->arc4_j = (d->arc4_j + d->arc4_sbox[n] + key[n]) % 256; 70 arc4_swap(&d->arc4_sbox[n], &d->arc4_sbox[d->arc4_j]); 71 } 72 73 /* 74 * Discard early keystream, as per recommendations in: 75 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 76 */ 77 for (n = 0; n < 768 * 4; n++) 78 arc4_randbyte(d); 79 80 /* Reset for next reseed cycle. */ 81 d->arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS; 82 d->arc4_numruns = 0; 83 } 84 85 /* 86 * Generate a random byte. 87 */ 88 static uint8_t 89 arc4_randbyte(struct arc4_data *d) 90 { 91 uint8_t arc4_t; 92 93 d->arc4_i = (d->arc4_i + 1) % 256; 94 d->arc4_j = (d->arc4_j + d->arc4_sbox[d->arc4_i]) % 256; 95 96 arc4_swap(&d->arc4_sbox[d->arc4_i], &d->arc4_sbox[d->arc4_j]); 97 98 arc4_t = (d->arc4_sbox[d->arc4_i] + d->arc4_sbox[d->arc4_j]) % 256; 99 return d->arc4_sbox[arc4_t]; 100 } 101 102 uint32_t 103 karc4random(void) 104 { 105 struct arc4_data *d = arc4_data_pcpu[mycpuid]; 106 uint32_t ret; 107 108 if (++(d->arc4_numruns) > ARC4_MAXRUNS || 109 time_uptime > d->arc4_nextreseed) 110 arc4_randomstir(d); 111 112 ret = arc4_randbyte(d); 113 ret |= arc4_randbyte(d) << 8; 114 ret |= arc4_randbyte(d) << 16; 115 ret |= arc4_randbyte(d) << 24; 116 117 return ret; 118 } 119 120 uint64_t 121 karc4random64(void) 122 { 123 struct arc4_data *d = arc4_data_pcpu[mycpuid]; 124 uint64_t ret; 125 126 if (++(d->arc4_numruns) > ARC4_MAXRUNS || 127 time_uptime > d->arc4_nextreseed) 128 arc4_randomstir(d); 129 130 ret = arc4_randbyte(d); 131 ret |= arc4_randbyte(d) << 8; 132 ret |= arc4_randbyte(d) << 16; 133 ret |= arc4_randbyte(d) << 24; 134 ret |= (uint64_t)arc4_randbyte(d) << 32; 135 ret |= (uint64_t)arc4_randbyte(d) << 40; 136 ret |= (uint64_t)arc4_randbyte(d) << 48; 137 ret |= (uint64_t)arc4_randbyte(d) << 56; 138 139 return ret; 140 } 141 142 void 143 karc4rand(void *ptr, size_t len) 144 { 145 struct arc4_data *d = arc4_data_pcpu[mycpuid]; 146 uint8_t *p = ptr; 147 148 #if 0 149 /* No one call this function in ISR/ithread. */ 150 crit_enter(); 151 #endif 152 153 if (++(d->arc4_numruns) > ARC4_MAXRUNS || 154 time_uptime > d->arc4_nextreseed) 155 arc4_randomstir(d); 156 157 while (len--) 158 *p++ = arc4_randbyte(d); 159 160 #if 0 161 crit_exit(); 162 #endif 163 } 164 165 /* 166 * Initialize our S-box to its beginning defaults. 167 */ 168 void 169 arc4_init_pcpu(int cpuid) 170 { 171 struct arc4_data *d; 172 int n; 173 174 KASSERT(arc4_data_pcpu[cpuid] == NULL, 175 ("arc4 was initialized on cpu%d", cpuid)); 176 177 d = (void *)kmem_alloc3(&kernel_map, sizeof(*d), VM_SUBSYS_GD, 178 KM_CPU(cpuid)); 179 memset(d, 0, sizeof(*d)); 180 181 for (n = 0; n < 256; n++) 182 d->arc4_sbox[n] = (uint8_t)n; 183 184 arc4_randomstir(d); 185 186 /* 187 * Discard early keystream, as per recommendations in: 188 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 189 */ 190 for (n = 0; n < 768 * 4; n++) 191 arc4_randbyte(d); 192 193 arc4_data_pcpu[cpuid] = d; 194 } 195