1 /* $NetBSD: arc4random.c,v 1.6 2024/08/18 20:47:20 christos Exp $ */
2
3 /* Portable arc4random.c based on arc4random.c from OpenBSD.
4 * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
5 * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
6 * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
7 *
8 * Note that in Libevent, this file isn't compiled directly. Instead,
9 * it's included from evutil_rand.c
10 */
11
12 /*
13 * Copyright (c) 1996, David Mazieres <dm@uun.org>
14 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
15 *
16 * Permission to use, copy, modify, and distribute this software for any
17 * purpose with or without fee is hereby granted, provided that the above
18 * copyright notice and this permission notice appear in all copies.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
21 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
22 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
23 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
24 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
25 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
26 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
27 */
28
29 /*
30 * Arc4 random number generator for OpenBSD.
31 *
32 * This code is derived from section 17.1 of Applied Cryptography,
33 * second edition, which describes a stream cipher allegedly
34 * compatible with RSA Labs "RC4" cipher (the actual description of
35 * which is a trade secret). The same algorithm is used as a stream
36 * cipher called "arcfour" in Tatu Ylonen's ssh package.
37 *
38 * Here the stream cipher has been modified always to include the time
39 * when initializing the state. That makes it impossible to
40 * regenerate the same random sequence twice, so this can't be used
41 * for encryption, but will generate good random numbers.
42 *
43 * RC4 is a registered trademark of RSA Laboratories.
44 */
45
46 #ifndef ARC4RANDOM_EXPORT
47 #define ARC4RANDOM_EXPORT
48 #endif
49
50 #ifndef ARC4RANDOM_UINT32
51 #define ARC4RANDOM_UINT32 uint32_t
52 #endif
53
54 #ifndef ARC4RANDOM_NO_INCLUDES
55 #include "evconfig-private.h"
56 #ifdef _WIN32
57 #include <wincrypt.h>
58 #include <process.h>
59 #include <winerror.h>
60 #else
61 #include <fcntl.h>
62 #include <unistd.h>
63 #include <sys/param.h>
64 #include <sys/time.h>
65 #ifdef EVENT__HAVE_SYS_SYSCTL_H
66 #include <sys/sysctl.h>
67 #endif
68 #ifdef EVENT__HAVE_SYS_RANDOM_H
69 #include <sys/random.h>
70 #endif
71 #endif
72 #include <limits.h>
73 #include <stdlib.h>
74 #include <string.h>
75 #endif
76
77 /* Add platform entropy 32 bytes (256 bits) at a time. */
78 #define ADD_ENTROPY 32
79
80 /* Re-seed from the platform RNG after generating this many bytes. */
81 #define BYTES_BEFORE_RESEED 1600000
82
83 struct arc4_stream {
84 unsigned char i;
85 unsigned char j;
86 unsigned char s[256];
87 };
88
89 #ifdef _WIN32
90 #define getpid _getpid
91 #define pid_t int
92 #endif
93
94 static int rs_initialized;
95 static struct arc4_stream rs;
96 static pid_t arc4_stir_pid;
97 static int arc4_count;
98
99 static inline unsigned char arc4_getbyte(void);
100
101 static inline void
arc4_init(void)102 arc4_init(void)
103 {
104 int n;
105
106 for (n = 0; n < 256; n++)
107 rs.s[n] = n;
108 rs.i = 0;
109 rs.j = 0;
110 }
111
112 static inline void
arc4_addrandom(const unsigned char * dat,int datlen)113 arc4_addrandom(const unsigned char *dat, int datlen)
114 {
115 int n;
116 unsigned char si;
117
118 rs.i--;
119 for (n = 0; n < 256; n++) {
120 rs.i = (rs.i + 1);
121 si = rs.s[rs.i];
122 rs.j = (rs.j + si + dat[n % datlen]);
123 rs.s[rs.i] = rs.s[rs.j];
124 rs.s[rs.j] = si;
125 }
126 rs.j = rs.i;
127 }
128
129 #ifndef _WIN32
130 static ssize_t
read_all(int fd,unsigned char * buf,size_t count)131 read_all(int fd, unsigned char *buf, size_t count)
132 {
133 size_t numread = 0;
134 ssize_t result;
135
136 while (numread < count) {
137 result = read(fd, buf+numread, count-numread);
138 if (result<0)
139 return -1;
140 else if (result == 0)
141 break;
142 numread += result;
143 }
144
145 return (ssize_t)numread;
146 }
147 #endif
148
149 #ifdef _WIN32
150 #define TRY_SEED_WIN32
151 static int
arc4_seed_win32(void)152 arc4_seed_win32(void)
153 {
154 /* This is adapted from Tor's crypto_seed_rng() */
155 static int provider_set = 0;
156 static HCRYPTPROV provider;
157 unsigned char buf[ADD_ENTROPY];
158
159 if (!provider_set) {
160 if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
161 CRYPT_VERIFYCONTEXT)) {
162 if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
163 return -1;
164 }
165 provider_set = 1;
166 }
167 if (!CryptGenRandom(provider, sizeof(buf), buf))
168 return -1;
169 arc4_addrandom(buf, sizeof(buf));
170 evutil_memclear_(buf, sizeof(buf));
171 return 0;
172 }
173 #endif
174
175 #if defined(EVENT__HAVE_GETRANDOM)
176 #define TRY_SEED_GETRANDOM
177 static int
arc4_seed_getrandom(void)178 arc4_seed_getrandom(void)
179 {
180 unsigned char buf[ADD_ENTROPY];
181 size_t len, n;
182 unsigned i;
183 int any_set;
184
185 memset(buf, 0, sizeof(buf));
186
187 for (len = 0; len < sizeof(buf); len += n) {
188 n = sizeof(buf) - len;
189
190 if (0 == getrandom(&buf[len], n, 0))
191 return -1;
192 }
193 /* make sure that the buffer actually got set. */
194 for (i=0,any_set=0; i<sizeof(buf); ++i) {
195 any_set |= buf[i];
196 }
197 if (!any_set)
198 return -1;
199
200 arc4_addrandom(buf, sizeof(buf));
201 evutil_memclear_(buf, sizeof(buf));
202 return 0;
203 }
204 #endif /* EVENT__HAVE_GETRANDOM */
205
206 #if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL)
207 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
208 #define TRY_SEED_SYSCTL_BSD
209 static int
arc4_seed_sysctl_bsd(void)210 arc4_seed_sysctl_bsd(void)
211 {
212 /* Based on code from William Ahern and from OpenBSD, this function
213 * tries to use the KERN_ARND syscall to get entropy from the kernel.
214 * This can work even if /dev/urandom is inaccessible for some reason
215 * (e.g., we're running in a chroot). */
216 int mib[] = { CTL_KERN, KERN_ARND };
217 unsigned char buf[ADD_ENTROPY];
218 size_t len, n;
219 int i, any_set;
220
221 memset(buf, 0, sizeof(buf));
222
223 len = sizeof(buf);
224 if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) {
225 for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) {
226 n = sizeof(unsigned);
227 if (n + len > sizeof(buf))
228 n = len - sizeof(buf);
229 if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1)
230 return -1;
231 }
232 }
233 /* make sure that the buffer actually got set. */
234 for (i=any_set=0; i<sizeof(buf); ++i) {
235 any_set |= buf[i];
236 }
237 if (!any_set)
238 return -1;
239
240 arc4_addrandom(buf, sizeof(buf));
241 evutil_memclear_(buf, sizeof(buf));
242 return 0;
243 }
244 #endif
245 #endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */
246
247 #ifdef __linux__
248 #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
249 static int
arc4_seed_proc_sys_kernel_random_uuid(void)250 arc4_seed_proc_sys_kernel_random_uuid(void)
251 {
252 /* Occasionally, somebody will make /proc/sys accessible in a chroot,
253 * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid.
254 * Its format is stupid, so we need to decode it from hex.
255 */
256 int fd;
257 char buf[128];
258 unsigned char entropy[64];
259 int bytes, n, i, nybbles;
260 for (bytes = 0; bytes<ADD_ENTROPY; ) {
261 fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
262 if (fd < 0)
263 return -1;
264 n = read(fd, buf, sizeof(buf));
265 close(fd);
266 if (n<=0)
267 return -1;
268 memset(entropy, 0, sizeof(entropy));
269 for (i=nybbles=0; i<n; ++i) {
270 if (EVUTIL_ISXDIGIT_(buf[i])) {
271 int nyb = evutil_hex_char_to_int_(buf[i]);
272 if (nybbles & 1) {
273 entropy[nybbles/2] |= nyb;
274 } else {
275 entropy[nybbles/2] |= nyb<<4;
276 }
277 ++nybbles;
278 }
279 }
280 if (nybbles < 2)
281 return -1;
282 arc4_addrandom(entropy, nybbles/2);
283 bytes += nybbles/2;
284 }
285 evutil_memclear_(entropy, sizeof(entropy));
286 evutil_memclear_(buf, sizeof(buf));
287 return 0;
288 }
289 #endif
290
291 #ifndef _WIN32
292 #define TRY_SEED_URANDOM
293 static char *arc4random_urandom_filename = NULL;
294
arc4_seed_urandom_helper_(const char * fname)295 static int arc4_seed_urandom_helper_(const char *fname)
296 {
297 unsigned char buf[ADD_ENTROPY];
298 int fd;
299 size_t n;
300
301 fd = evutil_open_closeonexec_(fname, O_RDONLY, 0);
302 if (fd<0)
303 return -1;
304 n = read_all(fd, buf, sizeof(buf));
305 close(fd);
306 if (n != sizeof(buf))
307 return -1;
308 arc4_addrandom(buf, sizeof(buf));
309 evutil_memclear_(buf, sizeof(buf));
310 return 0;
311 }
312
313 static int
arc4_seed_urandom(void)314 arc4_seed_urandom(void)
315 {
316 /* This is adapted from Tor's crypto_seed_rng() */
317 static const char *filenames[] = {
318 "/dev/srandom", "/dev/urandom", "/dev/random", NULL
319 };
320 int i;
321 if (arc4random_urandom_filename)
322 return arc4_seed_urandom_helper_(arc4random_urandom_filename);
323
324 for (i = 0; filenames[i]; ++i) {
325 if (arc4_seed_urandom_helper_(filenames[i]) == 0) {
326 return 0;
327 }
328 }
329
330 return -1;
331 }
332 #endif
333
334 static int
arc4_seed(void)335 arc4_seed(void)
336 {
337 int ok = 0;
338 /* We try every method that might work, and don't give up even if one
339 * does seem to work. There's no real harm in over-seeding, and if
340 * one of these sources turns out to be broken, that would be bad. */
341 #ifdef TRY_SEED_WIN32
342 if (0 == arc4_seed_win32())
343 ok = 1;
344 #endif
345 #ifdef TRY_SEED_GETRANDOM
346 if (0 == arc4_seed_getrandom())
347 ok = 1;
348 #endif
349 #ifdef TRY_SEED_URANDOM
350 if (0 == arc4_seed_urandom())
351 ok = 1;
352 #endif
353 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
354 if (arc4random_urandom_filename == NULL &&
355 0 == arc4_seed_proc_sys_kernel_random_uuid())
356 ok = 1;
357 #endif
358 #ifdef TRY_SEED_SYSCTL_BSD
359 if (0 == arc4_seed_sysctl_bsd())
360 ok = 1;
361 #endif
362 return ok ? 0 : -1;
363 }
364
365 static int
arc4_stir(void)366 arc4_stir(void)
367 {
368 int i;
369
370 if (!rs_initialized) {
371 arc4_init();
372 rs_initialized = 1;
373 }
374
375 if (0 != arc4_seed())
376 return -1;
377
378 /*
379 * Discard early keystream, as per recommendations in
380 * "Weaknesses in the Key Scheduling Algorithm of RC4" by
381 * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
382 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
383 *
384 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
385 * we drop at least 2*256 bytes, with 12*256 as a conservative
386 * value.
387 *
388 * RFC4345 says to drop 6*256.
389 *
390 * At least some versions of this code drop 4*256, in a mistaken
391 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
392 * to processor words.
393 *
394 * We add another sect to the cargo cult, and choose 12*256.
395 */
396 for (i = 0; i < 12*256; i++)
397 (void)arc4_getbyte();
398
399 arc4_count = BYTES_BEFORE_RESEED;
400
401 return 0;
402 }
403
404
405 static void
arc4_stir_if_needed(void)406 arc4_stir_if_needed(void)
407 {
408 pid_t pid = getpid();
409
410 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
411 {
412 arc4_stir_pid = pid;
413 arc4_stir();
414 }
415 }
416
417 static inline unsigned char
arc4_getbyte(void)418 arc4_getbyte(void)
419 {
420 unsigned char si, sj;
421
422 rs.i = (rs.i + 1);
423 si = rs.s[rs.i];
424 rs.j = (rs.j + si);
425 sj = rs.s[rs.j];
426 rs.s[rs.i] = sj;
427 rs.s[rs.j] = si;
428 return (rs.s[(si + sj) & 0xff]);
429 }
430
431 static inline unsigned int
arc4_getword(void)432 arc4_getword(void)
433 {
434 unsigned int val;
435
436 val = arc4_getbyte() << 24;
437 val |= arc4_getbyte() << 16;
438 val |= arc4_getbyte() << 8;
439 val |= arc4_getbyte();
440
441 return val;
442 }
443
444 #ifndef ARC4RANDOM_NOSTIR
445 ARC4RANDOM_EXPORT int
arc4random_stir(void)446 arc4random_stir(void)
447 {
448 int val;
449 ARC4_LOCK_();
450 val = arc4_stir();
451 ARC4_UNLOCK_();
452 return val;
453 }
454 #endif
455
456 #ifndef ARC4RANDOM_NOADDRANDOM
457 ARC4RANDOM_EXPORT void
arc4random_addrandom(const unsigned char * dat,int datlen)458 arc4random_addrandom(const unsigned char *dat, int datlen)
459 {
460 int j;
461 ARC4_LOCK_();
462 if (!rs_initialized)
463 arc4_stir();
464 for (j = 0; j < datlen; j += 256) {
465 /* arc4_addrandom() ignores all but the first 256 bytes of
466 * its input. We want to make sure to look at ALL the
467 * data in 'dat', just in case the user is doing something
468 * crazy like passing us all the files in /var/log. */
469 arc4_addrandom(dat + j, datlen - j);
470 }
471 ARC4_UNLOCK_();
472 }
473 #endif
474
475 #ifndef ARC4RANDOM_NORANDOM
476 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
arc4random(void)477 arc4random(void)
478 {
479 ARC4RANDOM_UINT32 val;
480 ARC4_LOCK_();
481 arc4_count -= 4;
482 arc4_stir_if_needed();
483 val = arc4_getword();
484 ARC4_UNLOCK_();
485 return val;
486 }
487 #endif
488
489 ARC4RANDOM_EXPORT void
arc4random_buf(void * buf_,size_t n)490 arc4random_buf(void *buf_, size_t n)
491 {
492 unsigned char *buf = buf_;
493 ARC4_LOCK_();
494 arc4_stir_if_needed();
495 while (n--) {
496 if (--arc4_count <= 0)
497 arc4_stir();
498 buf[n] = arc4_getbyte();
499 }
500 ARC4_UNLOCK_();
501 }
502
503 #ifndef ARC4RANDOM_NOUNIFORM
504 /*
505 * Calculate a uniformly distributed random number less than upper_bound
506 * avoiding "modulo bias".
507 *
508 * Uniformity is achieved by generating new random numbers until the one
509 * returned is outside the range [0, 2**32 % upper_bound). This
510 * guarantees the selected random number will be inside
511 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
512 * after reduction modulo upper_bound.
513 */
514 ARC4RANDOM_EXPORT unsigned int
arc4random_uniform(unsigned int upper_bound)515 arc4random_uniform(unsigned int upper_bound)
516 {
517 ARC4RANDOM_UINT32 r, min;
518
519 if (upper_bound < 2)
520 return 0;
521
522 #if (UINT_MAX > 0xffffffffUL)
523 min = 0x100000000UL % upper_bound;
524 #else
525 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
526 if (upper_bound > 0x80000000)
527 min = 1 + ~upper_bound; /* 2**32 - upper_bound */
528 else {
529 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
530 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
531 }
532 #endif
533
534 /*
535 * This could theoretically loop forever but each retry has
536 * p > 0.5 (worst case, usually far better) of selecting a
537 * number inside the range we need, so it should rarely need
538 * to re-roll.
539 */
540 for (;;) {
541 r = arc4random();
542 if (r >= min)
543 break;
544 }
545
546 return r % upper_bound;
547 }
548 #endif
549