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 = 768 in our case.)
88 *
89 * http://dl.acm.org/citation.cfm?id=646557.694759
90 */
91 for (n = 0; n < 768*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 }
Cache object: b2720943ede01be14bb09cf97d4978e2
|