1 | /*␊ |
2 | * Copyright (c) 1996, David Mazieres <dm@uun.org>␊ |
3 | * Copyright (c) 2008, Damien Miller <djm@openbsd.org>␊ |
4 | *␊ |
5 | * Permission to use, copy, modify, and distribute this software for any␊ |
6 | * purpose with or without fee is hereby granted, provided that the above␊ |
7 | * copyright notice and this permission notice appear in all copies.␊ |
8 | *␊ |
9 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES␊ |
10 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF␊ |
11 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR␊ |
12 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES␊ |
13 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN␊ |
14 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF␊ |
15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.␊ |
16 | */␊ |
17 | ␊ |
18 | /*␊ |
19 | * Arc4 random number generator for OpenBSD.␊ |
20 | *␊ |
21 | * This code is derived from section 17.1 of Applied Cryptography,␊ |
22 | * second edition, which describes a stream cipher allegedly␊ |
23 | * compatible with RSA Labs "RC4" cipher (the actual description of␊ |
24 | * which is a trade secret). The same algorithm is used as a stream␊ |
25 | * cipher called "arcfour" in Tatu Ylonen's ssh package.␊ |
26 | *␊ |
27 | * Here the stream cipher has been modified always to include the time␊ |
28 | * when initializing the state. That makes it impossible to␊ |
29 | * regenerate the same random sequence twice, so this can't be used␊ |
30 | * for encryption, but will generate good random numbers.␊ |
31 | *␊ |
32 | * RC4 is a registered trademark of RSA Laboratories.␊ |
33 | */␊ |
34 | ␊ |
35 | ␊ |
36 | #include "libsaio.h"␊ |
37 | ␊ |
38 | ␊ |
39 | struct arc4_stream {␊ |
40 | ␉u_int8_t i;␊ |
41 | ␉u_int8_t j;␊ |
42 | ␉u_int8_t s[256];␊ |
43 | };␊ |
44 | ␊ |
45 | ␊ |
46 | #define KEYSIZE␉␉128␊ |
47 | ␊ |
48 | static struct arc4_stream rs = {␊ |
49 | ␉.i = 0,␊ |
50 | ␉.j = 0,␊ |
51 | ␉.s = {␊ |
52 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,␊ |
53 | 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,␊ |
54 | 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,␊ |
55 | 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,␊ |
56 | 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,␊ |
57 | 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,␊ |
58 | 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,␊ |
59 | ␉␉112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,␊ |
60 | ␉␉128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,␊ |
61 | ␉␉144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,␊ |
62 | ␉␉160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,␊ |
63 | ␉␉176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,␊ |
64 | ␉␉192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,␊ |
65 | ␉␉208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,␊ |
66 | ␉␉224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,␊ |
67 | ␉␉240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255␊ |
68 | ␉}␊ |
69 | };␊ |
70 | //static int rs_initialized;␊ |
71 | static int rs_stired;␊ |
72 | static int arc4_count;␊ |
73 | ␊ |
74 | static inline u_int8_t arc4_getbyte(void);␊ |
75 | static void arc4_stir(void);␊ |
76 | ␊ |
77 | static struct {␊ |
78 | ␉struct timeval␉tv;␊ |
79 | ␉u_int8_t␉rnd[KEYSIZE];␊ |
80 | } rdat;␊ |
81 | static volatile int rs_data_available = 0;␊ |
82 | ␊ |
83 | static inline void␊ |
84 | arc4_addrandom(u_char *dat, int datlen)␊ |
85 | {␊ |
86 | ␉int n;␊ |
87 | ␉u_int8_t si;␊ |
88 | ␊ |
89 | ␉rs.i--;␊ |
90 | ␉for (n = 0; n < 256; n++) {␊ |
91 | ␉␉rs.i = (rs.i + 1);␊ |
92 | ␉␉si = rs.s[rs.i];␊ |
93 | ␉␉rs.j = (rs.j + si + dat[n % datlen]);␊ |
94 | ␉␉rs.s[rs.i] = rs.s[rs.j];␊ |
95 | ␉␉rs.s[rs.j] = si;␊ |
96 | ␉}␊ |
97 | ␉rs.j = rs.i;␊ |
98 | }␊ |
99 | ␊ |
100 | static void␊ |
101 | arc4_fetch(void)␊ |
102 | {␊ |
103 | ␉␊ |
104 | ␉(void)gettimeofday(&rdat.tv, NULL);␊ |
105 | ␉␊ |
106 | }␊ |
107 | ␊ |
108 | static void␊ |
109 | arc4_stir(void)␊ |
110 | {␊ |
111 | ␉int n;␊ |
112 | ␉/*␊ |
113 | ␉ * If we don't have data, we need some now before we can integrate␊ |
114 | ␉ * it into the static buffers␊ |
115 | ␉ */␊ |
116 | ␉if (!rs_data_available)␊ |
117 | ␉{␊ |
118 | ␉␉arc4_fetch();␊ |
119 | ␉}␊ |
120 | ␉rs_data_available = 0;␊ |
121 | ␉__sync_synchronize();␊ |
122 | ␊ |
123 | ␉arc4_addrandom((u_char *)&rdat, KEYSIZE);␊ |
124 | ␊ |
125 | ␉/*␊ |
126 | ␉ * Throw away the first N bytes of output, as suggested in the␊ |
127 | ␉ * paper "Weaknesses in the Key Scheduling Algorithm of RC4"␊ |
128 | ␉ * by Fluher, Mantin, and Shamir. N=1024 is based on␊ |
129 | ␉ * suggestions in the paper "(Not So) Random Shuffles of RC4"␊ |
130 | ␉ * by Ilya Mironov.␊ |
131 | ␉ */␊ |
132 | ␉for (n = 0; n < 1024; n++)␊ |
133 | ␉␉(void) arc4_getbyte();␊ |
134 | ␉arc4_count = 1600000;␊ |
135 | ␉rs_stired = 1;␊ |
136 | }␊ |
137 | ␊ |
138 | static inline u_int8_t␊ |
139 | arc4_getbyte(void)␊ |
140 | {␊ |
141 | ␉u_int8_t si, sj;␊ |
142 | ␊ |
143 | ␉rs.i = (rs.i + 1);␊ |
144 | ␉si = rs.s[rs.i];␊ |
145 | ␉rs.j = (rs.j + si);␊ |
146 | ␉sj = rs.s[rs.j];␊ |
147 | ␉rs.s[rs.i] = sj;␊ |
148 | ␉rs.s[rs.j] = si;␊ |
149 | ␊ |
150 | ␉return (rs.s[(si + sj) & 0xff]);␊ |
151 | }␊ |
152 | ␊ |
153 | static inline u_int32_t␊ |
154 | arc4_getword(void)␊ |
155 | {␊ |
156 | ␉u_int32_t val;␊ |
157 | ␊ |
158 | ␉val = arc4_getbyte() << 24;␊ |
159 | ␉val |= arc4_getbyte() << 16;␊ |
160 | ␉val |= arc4_getbyte() << 8;␊ |
161 | ␉val |= arc4_getbyte();␊ |
162 | ␊ |
163 | ␉return (val);␊ |
164 | }␊ |
165 | ␊ |
166 | /* 7944700: force restir in child */␊ |
167 | __private_extern__ void␊ |
168 | _arc4_fork_child(void)␊ |
169 | {␊ |
170 | ␉rs_stired = 0;␊ |
171 | ␉rs_data_available = 0;␊ |
172 | }␊ |
173 | ␊ |
174 | static inline int␊ |
175 | arc4_check_stir(void)␊ |
176 | {␊ |
177 | ␉if (!rs_stired || arc4_count <= 0) {␊ |
178 | ␉␉arc4_stir();␊ |
179 | ␉␉return 1;␊ |
180 | ␉}␊ |
181 | ␉return 0;␊ |
182 | }␊ |
183 | ␊ |
184 | void␊ |
185 | arc4random_stir(void)␊ |
186 | {␊ |
187 | ␉arc4_stir();␊ |
188 | }␊ |
189 | ␊ |
190 | void␊ |
191 | arc4random_addrandom(u_char *dat, int datlen)␊ |
192 | {␊ |
193 | ␉arc4_check_stir();␊ |
194 | ␉arc4_addrandom(dat, datlen);␊ |
195 | }␊ |
196 | ␊ |
197 | u_int32_t␊ |
198 | arc4random(void)␊ |
199 | {␊ |
200 | ␉u_int32_t rnd;␊ |
201 | ␊ |
202 | ␉int did_stir = arc4_check_stir();␊ |
203 | ␉rnd = arc4_getword();␊ |
204 | ␉arc4_count -= 4;␊ |
205 | ␊ |
206 | ␉if (did_stir)␊ |
207 | ␉{␊ |
208 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
209 | ␉␉arc4_fetch();␊ |
210 | ␉␉rs_data_available = 1;␊ |
211 | ␉␉__sync_synchronize();␊ |
212 | ␉}␊ |
213 | ␊ |
214 | ␉return (rnd);␊ |
215 | }␊ |
216 | ␊ |
217 | void␊ |
218 | arc4random_buf(void *_buf, size_t n)␊ |
219 | {␊ |
220 | ␉u_char *buf = (u_char *)_buf;␊ |
221 | ␉int did_stir = 0;␊ |
222 | ␊ |
223 | ␉while (n--) {␊ |
224 | ␉␉if (arc4_check_stir())␊ |
225 | ␉␉{␊ |
226 | ␉␉␉did_stir = 1;␊ |
227 | ␉␉}␊ |
228 | ␉␉buf[n] = arc4_getbyte();␊ |
229 | ␉␉arc4_count--;␊ |
230 | ␉}␊ |
231 | ␉␊ |
232 | ␉if (did_stir)␊ |
233 | ␉{␊ |
234 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
235 | ␉␉arc4_fetch();␊ |
236 | ␉␉rs_data_available = 1;␊ |
237 | ␉␉__sync_synchronize();␊ |
238 | ␉}␊ |
239 | }␊ |
240 | ␊ |
241 | /*␊ |
242 | * Calculate a uniformly distributed random number less than upper_bound␊ |
243 | * avoiding "modulo bias".␊ |
244 | *␊ |
245 | * Uniformity is achieved by generating new random numbers until the one␊ |
246 | * returned is outside the range [0, 2**32 % upper_bound). This␊ |
247 | * guarantees the selected random number will be inside␊ |
248 | * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)␊ |
249 | * after reduction modulo upper_bound.␊ |
250 | */␊ |
251 | u_int32_t␊ |
252 | arc4random_uniform(u_int32_t upper_bound)␊ |
253 | {␊ |
254 | ␉u_int32_t r, min;␊ |
255 | ␊ |
256 | ␉if (upper_bound < 2)␊ |
257 | ␉␉return (0);␊ |
258 | ␊ |
259 | #if (ULONG_MAX > 0xffffffffUL)␊ |
260 | ␉min = 0x100000000UL % upper_bound;␊ |
261 | #else␊ |
262 | ␉/* Calculate (2**32 % upper_bound) avoiding 64-bit math */␊ |
263 | ␉if (upper_bound > 0x80000000)␊ |
264 | ␉␉min = 1 + ~upper_bound;␉␉/* 2**32 - upper_bound */␊ |
265 | ␉else {␊ |
266 | ␉␉/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */␊ |
267 | ␉␉min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;␊ |
268 | ␉}␊ |
269 | #endif␊ |
270 | ␊ |
271 | ␉/*␊ |
272 | ␉ * This could theoretically loop forever but each retry has␊ |
273 | ␉ * p > 0.5 (worst case, usually far better) of selecting a␊ |
274 | ␉ * number inside the range we need, so it should rarely need␊ |
275 | ␉ * to re-roll.␊ |
276 | ␉ */␊ |
277 | ␉for (;;) {␊ |
278 | ␉␉r = arc4random();␊ |
279 | ␉␉if (r >= min)␊ |
280 | ␉␉␉break;␊ |
281 | ␉}␊ |
282 | ␊ |
283 | ␉return (r % upper_bound);␊ |
284 | }␊ |
285 | ␊ |
286 | void␊ |
287 | arc4_init(void)␊ |
288 | {␉␊ |
289 | }␊ |
290 | ␊ |
291 | #if 0␊ |
292 | /*-------- Test code for i386 --------*/␊ |
293 | #include <stdio.h>␊ |
294 | #include <machine/pctr.h>␊ |
295 | int␊ |
296 | main(int argc, char **argv)␊ |
297 | {␊ |
298 | ␉const int iter = 1000000;␊ |
299 | ␉int i;␊ |
300 | ␉pctrval v;␊ |
301 | ␊ |
302 | ␉v = rdtsc();␊ |
303 | ␉for (i = 0; i < iter; i++)␊ |
304 | ␉␉arc4random();␊ |
305 | ␉v = rdtsc() - v;␊ |
306 | ␉v /= iter;␊ |
307 | ␊ |
308 | ␉printf("%qd cycles\n", v);␊ |
309 | }␊ |
310 | #endif␊ |
311 | |