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 0 109 /* No one call this function in ISR/ithread. */ 110 crit_enter(); 111 #endif 112 113 if (++(d->arc4_numruns) > ARC4_MAXRUNS || 114 time_uptime > d->arc4_nextreseed) 115 arc4_randomstir(d); 116 117 ret = arc4_randbyte(d); 118 ret |= arc4_randbyte(d) << 8; 119 ret |= arc4_randbyte(d) << 16; 120 ret |= arc4_randbyte(d) << 24; 121 122 #if 0 123 crit_exit(); 124 #endif 125 126 return ret; 127 } 128 129 void 130 karc4rand(void *ptr, size_t len) 131 { 132 struct arc4_data *d = arc4_data_pcpu[mycpuid]; 133 uint8_t *p = ptr; 134 135 #if 0 136 /* No one call this function in ISR/ithread. */ 137 crit_enter(); 138 #endif 139 140 if (++(d->arc4_numruns) > ARC4_MAXRUNS || 141 time_uptime > d->arc4_nextreseed) 142 arc4_randomstir(d); 143 144 while (len--) 145 *p++ = arc4_randbyte(d); 146 147 #if 0 148 crit_exit(); 149 #endif 150 } 151 152 /* 153 * Initialize our S-box to its beginning defaults. 154 */ 155 void 156 arc4_init_pcpu(int cpuid) 157 { 158 struct arc4_data *d; 159 int n; 160 161 KASSERT(arc4_data_pcpu[cpuid] == NULL, 162 ("arc4 was initialized on cpu%d", cpuid)); 163 164 d = (void *)kmem_alloc3(&kernel_map, sizeof(*d), VM_SUBSYS_GD, 165 KM_CPU(cpuid)); 166 memset(d, 0, sizeof(*d)); 167 168 for (n = 0; n < 256; n++) 169 d->arc4_sbox[n] = (uint8_t)n; 170 171 arc4_randomstir(d); 172 173 /* 174 * Discard early keystream, as per recommendations in: 175 * "(Not So) Random Shuffles of RC4" by Ilya Mironov. 176 */ 177 for (n = 0; n < 768 * 4; n++) 178 arc4_randbyte(d); 179 180 arc4_data_pcpu[cpuid] = d; 181 } 182