Line data Source code
1 : /* $OpenBSD: rnd.c,v 1.199 2018/04/28 15:44:59 jasper Exp $ */
2 :
3 : /*
4 : * Copyright (c) 2011 Theo de Raadt.
5 : * Copyright (c) 2008 Damien Miller.
6 : * Copyright (c) 1996, 1997, 2000-2002 Michael Shalayeff.
7 : * Copyright (c) 2013 Markus Friedl.
8 : * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.
9 : * All rights reserved.
10 : *
11 : * Redistribution and use in source and binary forms, with or without
12 : * modification, are permitted provided that the following conditions
13 : * are met:
14 : * 1. Redistributions of source code must retain the above copyright
15 : * notice, and the entire permission notice in its entirety,
16 : * including the disclaimer of warranties.
17 : * 2. Redistributions in binary form must reproduce the above copyright
18 : * notice, this list of conditions and the following disclaimer in the
19 : * documentation and/or other materials provided with the distribution.
20 : * 3. The name of the author may not be used to endorse or promote
21 : * products derived from this software without specific prior
22 : * written permission.
23 : *
24 : * ALTERNATIVELY, this product may be distributed under the terms of
25 : * the GNU Public License, in which case the provisions of the GPL are
26 : * required INSTEAD OF the above restrictions. (This clause is
27 : * necessary due to a potential bad interaction between the GPL and
28 : * the restrictions contained in a BSD-style copyright.)
29 : *
30 : * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
31 : * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
33 : * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
34 : * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
35 : * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
36 : * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
38 : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
39 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
40 : * OF THE POSSIBILITY OF SUCH DAMAGE.
41 : */
42 :
43 : /*
44 : * Computers are very predictable devices. Hence it is extremely hard
45 : * to produce truly random numbers on a computer --- as opposed to
46 : * pseudo-random numbers, which can be easily generated by using an
47 : * algorithm. Unfortunately, it is very easy for attackers to guess
48 : * the sequence of pseudo-random number generators, and for some
49 : * applications this is not acceptable. Instead, we must try to
50 : * gather "environmental noise" from the computer's environment, which
51 : * must be hard for outside attackers to observe and use to
52 : * generate random numbers. In a Unix environment, this is best done
53 : * from inside the kernel.
54 : *
55 : * Sources of randomness from the environment include inter-keyboard
56 : * timings, inter-interrupt timings from some interrupts, and other
57 : * events which are both (a) non-deterministic and (b) hard for an
58 : * outside observer to measure. Randomness from these sources is
59 : * added to the "rnd states" queue; this is used as much of the
60 : * source material which is mixed on occasion using a CRC-like function
61 : * into the "entropy pool". This is not cryptographically strong, but
62 : * it is adequate assuming the randomness is not chosen maliciously,
63 : * and it is very fast because the interrupt-time event is only to add
64 : * a small random token to the "rnd states" queue.
65 : *
66 : * When random bytes are desired, they are obtained by pulling from
67 : * the entropy pool and running a SHA512 hash. The SHA512 hash avoids
68 : * exposing the internal state of the entropy pool. Even if it is
69 : * possible to analyze SHA512 in some clever way, as long as the amount
70 : * of data returned from the generator is less than the inherent
71 : * entropy in the pool, the output data is totally unpredictable. For
72 : * this reason, the routine decreases its internal estimate of how many
73 : * bits of "true randomness" are contained in the entropy pool as it
74 : * outputs random numbers.
75 : *
76 : * If this estimate goes to zero, the SHA512 hash will continue to generate
77 : * output since there is no true risk because the SHA512 output is not
78 : * exported outside this subsystem. It is next used as input to seed a
79 : * ChaCha20 stream cipher, which is re-seeded from time to time. This
80 : * design provides very high amounts of output data from a potentially
81 : * small entropy base, at high enough speeds to encourage use of random
82 : * numbers in nearly any situation. Before OpenBSD 5.5, the RC4 stream
83 : * cipher (also known as ARC4) was used instead of ChaCha20.
84 : *
85 : * The output of this single ChaCha20 engine is then shared amongst many
86 : * consumers in the kernel and userland via a few interfaces:
87 : * arc4random_buf(), arc4random(), arc4random_uniform(), randomread()
88 : * for the set of /dev/random nodes and the system call getentropy(),
89 : * which provides seeds for process-context pseudorandom generators.
90 : *
91 : * Acknowledgements:
92 : * =================
93 : *
94 : * Ideas for constructing this random number generator were derived
95 : * from Pretty Good Privacy's random number generator, and from private
96 : * discussions with Phil Karn. Colin Plumb provided a faster random
97 : * number generator, which speeds up the mixing function of the entropy
98 : * pool, taken from PGPfone. Dale Worley has also contributed many
99 : * useful ideas and suggestions to improve this driver.
100 : *
101 : * Any flaws in the design are solely my responsibility, and should
102 : * not be attributed to the Phil, Colin, or any of the authors of PGP.
103 : *
104 : * Further background information on this topic may be obtained from
105 : * RFC 1750, "Randomness Recommendations for Security", by Donald
106 : * Eastlake, Steve Crocker, and Jeff Schiller.
107 : *
108 : * Using a RC4 stream cipher as 2nd stage after the MD5 (now SHA512) output
109 : * is the result of work by David Mazieres.
110 : */
111 :
112 : #include <sys/param.h>
113 : #include <sys/systm.h>
114 : #include <sys/disk.h>
115 : #include <sys/event.h>
116 : #include <sys/limits.h>
117 : #include <sys/time.h>
118 : #include <sys/ioctl.h>
119 : #include <sys/malloc.h>
120 : #include <sys/fcntl.h>
121 : #include <sys/timeout.h>
122 : #include <sys/mutex.h>
123 : #include <sys/task.h>
124 : #include <sys/msgbuf.h>
125 : #include <sys/mount.h>
126 : #include <sys/syscallargs.h>
127 :
128 : #include <crypto/sha2.h>
129 :
130 : #define KEYSTREAM_ONLY
131 : #include <crypto/chacha_private.h>
132 :
133 : #include <dev/rndvar.h>
134 :
135 : #include <uvm/uvm_param.h>
136 : #include <uvm/uvm_extern.h>
137 :
138 : /*
139 : * For the purposes of better mixing, we use the CRC-32 polynomial as
140 : * well to make a twisted Generalized Feedback Shift Register
141 : *
142 : * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM
143 : * Transactions on Modeling and Computer Simulation 2(3):179-194.
144 : * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators
145 : * II. ACM Transactions on Modeling and Computer Simulation 4:254-266)
146 : *
147 : * Thanks to Colin Plumb for suggesting this.
148 : *
149 : * We have not analyzed the resultant polynomial to prove it primitive;
150 : * in fact it almost certainly isn't. Nonetheless, the irreducible factors
151 : * of a random large-degree polynomial over GF(2) are more than large enough
152 : * that periodicity is not a concern.
153 : *
154 : * The input hash is much less sensitive than the output hash. All
155 : * we want from it is to be a good non-cryptographic hash -
156 : * i.e. to not produce collisions when fed "random" data of the sort
157 : * we expect to see. As long as the pool state differs for different
158 : * inputs, we have preserved the input entropy and done a good job.
159 : * The fact that an intelligent attacker can construct inputs that
160 : * will produce controlled alterations to the pool's state is not
161 : * important because we don't consider such inputs to contribute any
162 : * randomness. The only property we need with respect to them is that
163 : * the attacker can't increase his/her knowledge of the pool's state.
164 : * Since all additions are reversible (knowing the final state and the
165 : * input, you can reconstruct the initial state), if an attacker has
166 : * any uncertainty about the initial state, he/she can only shuffle
167 : * that uncertainty about, but never cause any collisions (which would
168 : * decrease the uncertainty).
169 : *
170 : * The chosen system lets the state of the pool be (essentially) the input
171 : * modulo the generator polynomial. Now, for random primitive polynomials,
172 : * this is a universal class of hash functions, meaning that the chance
173 : * of a collision is limited by the attacker's knowledge of the generator
174 : * polynomial, so if it is chosen at random, an attacker can never force
175 : * a collision. Here, we use a fixed polynomial, but we *can* assume that
176 : * ###--> it is unknown to the processes generating the input entropy. <-###
177 : * Because of this important property, this is a good, collision-resistant
178 : * hash; hash collisions will occur no more often than chance.
179 : */
180 :
181 : /*
182 : * Stirring polynomials over GF(2) for various pool sizes. Used in
183 : * add_entropy_words() below.
184 : *
185 : * The polynomial terms are chosen to be evenly spaced (minimum RMS
186 : * distance from evenly spaced; except for the last tap, which is 1 to
187 : * get the twisting happening as fast as possible.
188 : *
189 : * The resultant polynomial is:
190 : * 2^POOLWORDS + 2^POOL_TAP1 + 2^POOL_TAP2 + 2^POOL_TAP3 + 2^POOL_TAP4 + 1
191 : */
192 : #define POOLWORDS 2048
193 : #define POOLBYTES (POOLWORDS*4)
194 : #define POOLMASK (POOLWORDS - 1)
195 : #define POOL_TAP1 1638
196 : #define POOL_TAP2 1231
197 : #define POOL_TAP3 819
198 : #define POOL_TAP4 411
199 :
200 : /*
201 : * Raw entropy collection from device drivers; at interrupt context or not.
202 : * enqueue_randomness() provide data which is put into the entropy queue.
203 : */
204 :
205 : #define QEVLEN 128 /* must be a power of 2 */
206 : #define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */
207 :
208 : #define KEYSZ 32
209 : #define IVSZ 8
210 : #define BLOCKSZ 64
211 : #define RSBUFSZ (16*BLOCKSZ)
212 : #define EBUFSIZE KEYSZ + IVSZ
213 :
214 : struct rand_event {
215 : u_int re_time;
216 : u_int re_val;
217 : } rnd_event_space[QEVLEN];
218 :
219 : u_int rnd_event_cons;
220 : u_int rnd_event_prod;
221 :
222 : struct mutex rnd_enqlck = MUTEX_INITIALIZER(IPL_HIGH);
223 : struct mutex rnd_deqlck = MUTEX_INITIALIZER(IPL_HIGH);
224 :
225 : struct timeout rnd_timeout;
226 :
227 : static u_int32_t entropy_pool[POOLWORDS];
228 : u_int32_t entropy_pool0[POOLWORDS] __attribute__((section(".openbsd.randomdata")));
229 : u_int entropy_add_ptr;
230 : u_char entropy_input_rotate;
231 :
232 : void dequeue_randomness(void *);
233 : void add_entropy_words(const u_int32_t *, u_int);
234 : void extract_entropy(u_int8_t *)
235 : __attribute__((__bounded__(__minbytes__,1,EBUFSIZE)));
236 :
237 : int filt_randomread(struct knote *, long);
238 : void filt_randomdetach(struct knote *);
239 : int filt_randomwrite(struct knote *, long);
240 :
241 : static void _rs_seed(u_char *, size_t);
242 : static void _rs_clearseed(const void *p, size_t s);
243 :
244 : struct filterops randomread_filtops =
245 : { 1, NULL, filt_randomdetach, filt_randomread };
246 : struct filterops randomwrite_filtops =
247 : { 1, NULL, filt_randomdetach, filt_randomwrite };
248 :
249 : static inline struct rand_event *
250 0 : rnd_get(void)
251 : {
252 : u_int idx;
253 :
254 : /* nothing to do if queue is empty */
255 0 : if (rnd_event_prod == rnd_event_cons)
256 0 : return NULL;
257 :
258 0 : if (rnd_event_prod - rnd_event_cons > QEVLEN)
259 0 : rnd_event_cons = rnd_event_prod - QEVLEN;
260 0 : idx = rnd_event_cons++;
261 0 : return &rnd_event_space[idx & (QEVLEN - 1)];
262 0 : }
263 :
264 : static inline struct rand_event *
265 0 : rnd_put(void)
266 : {
267 0 : u_int idx = rnd_event_prod++;
268 :
269 : /* allow wrapping. caller will mix it in. */
270 0 : return &rnd_event_space[idx & (QEVLEN - 1)];
271 : }
272 :
273 : static inline u_int
274 0 : rnd_qlen(void)
275 : {
276 0 : return rnd_event_prod - rnd_event_cons;
277 : }
278 :
279 : /*
280 : * This function adds entropy to the entropy pool by using timing delays.
281 : *
282 : * The number "val" is also added to the pool - it should somehow describe
283 : * the type of event which just happened. Currently the values of 0-255
284 : * are for keyboard scan codes, 256 and upwards - for interrupts.
285 : */
286 : void
287 0 : enqueue_randomness(u_int val)
288 : {
289 : struct rand_event *rep;
290 0 : struct timespec ts;
291 : u_int qlen;
292 :
293 0 : if (timeout_initialized(&rnd_timeout))
294 0 : nanotime(&ts);
295 :
296 0 : mtx_enter(&rnd_enqlck);
297 0 : rep = rnd_put();
298 0 : rep->re_time += ts.tv_nsec ^ (ts.tv_sec << 20);
299 0 : rep->re_val += val;
300 0 : qlen = rnd_qlen();
301 0 : mtx_leave(&rnd_enqlck);
302 :
303 0 : if (qlen > QEVSLOW/2 && timeout_initialized(&rnd_timeout) &&
304 0 : !timeout_pending(&rnd_timeout))
305 0 : timeout_add(&rnd_timeout, 1);
306 0 : }
307 :
308 : /*
309 : * This function adds a byte into the entropy pool. It does not
310 : * update the entropy estimate. The caller must do this if appropriate.
311 : *
312 : * The pool is stirred with a polynomial of degree POOLWORDS over GF(2);
313 : * see POOL_TAP[1-4] above
314 : *
315 : * Rotate the input word by a changing number of bits, to help assure
316 : * that all bits in the entropy get toggled. Otherwise, if the pool
317 : * is consistently fed small numbers (such as keyboard scan codes)
318 : * then the upper bits of the entropy pool will frequently remain
319 : * untouched.
320 : */
321 : void
322 0 : add_entropy_words(const u_int32_t *buf, u_int n)
323 : {
324 : /* derived from IEEE 802.3 CRC-32 */
325 : static const u_int32_t twist_table[8] = {
326 : 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
327 : 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
328 : };
329 :
330 0 : for (; n--; buf++) {
331 0 : u_int32_t w = (*buf << entropy_input_rotate) |
332 0 : (*buf >> ((32 - entropy_input_rotate) & 31));
333 0 : u_int i = entropy_add_ptr =
334 0 : (entropy_add_ptr - 1) & POOLMASK;
335 : /*
336 : * Normally, we add 7 bits of rotation to the pool.
337 : * At the beginning of the pool, add an extra 7 bits
338 : * rotation, so that successive passes spread the
339 : * input bits across the pool evenly.
340 : */
341 0 : entropy_input_rotate =
342 0 : (entropy_input_rotate + (i ? 7 : 14)) & 31;
343 :
344 : /* XOR pool contents corresponding to polynomial terms */
345 0 : w ^= entropy_pool[(i + POOL_TAP1) & POOLMASK] ^
346 0 : entropy_pool[(i + POOL_TAP2) & POOLMASK] ^
347 0 : entropy_pool[(i + POOL_TAP3) & POOLMASK] ^
348 0 : entropy_pool[(i + POOL_TAP4) & POOLMASK] ^
349 0 : entropy_pool[(i + 1) & POOLMASK] ^
350 0 : entropy_pool[i]; /* + 2^POOLWORDS */
351 :
352 0 : entropy_pool[i] = (w >> 3) ^ twist_table[w & 7];
353 : }
354 0 : }
355 :
356 : /*
357 : * Pulls entropy out of the queue and merges it into the pool
358 : * with the CRC.
359 : */
360 : /* ARGSUSED */
361 : void
362 0 : dequeue_randomness(void *v)
363 : {
364 : struct rand_event *rep;
365 0 : u_int32_t buf[2];
366 :
367 0 : if (timeout_initialized(&rnd_timeout))
368 0 : timeout_del(&rnd_timeout);
369 :
370 0 : mtx_enter(&rnd_deqlck);
371 0 : while ((rep = rnd_get())) {
372 0 : buf[0] = rep->re_time;
373 0 : buf[1] = rep->re_val;
374 0 : mtx_leave(&rnd_deqlck);
375 0 : add_entropy_words(buf, 2);
376 0 : mtx_enter(&rnd_deqlck);
377 : }
378 0 : mtx_leave(&rnd_deqlck);
379 0 : }
380 :
381 : /*
382 : * Grabs a chunk from the entropy_pool[] and slams it through SHA512 when
383 : * requested.
384 : */
385 : void
386 0 : extract_entropy(u_int8_t *buf)
387 : {
388 : static u_int32_t extract_pool[POOLWORDS];
389 0 : u_char digest[SHA512_DIGEST_LENGTH];
390 0 : SHA2_CTX shactx;
391 :
392 : #if SHA512_DIGEST_LENGTH < EBUFSIZE
393 : #error "need more bigger hash output"
394 : #endif
395 :
396 : /*
397 : * INTENTIONALLY not protected by any lock. Races during
398 : * memcpy() result in acceptable input data; races during
399 : * SHA512Update() would create nasty data dependencies. We
400 : * do not rely on this as a benefit, but if it happens, cool.
401 : */
402 0 : memcpy(extract_pool, entropy_pool, sizeof(extract_pool));
403 :
404 : /* Hash the pool to get the output */
405 0 : SHA512Init(&shactx);
406 0 : SHA512Update(&shactx, (u_int8_t *)extract_pool, sizeof(extract_pool));
407 0 : SHA512Final(digest, &shactx);
408 :
409 : /* Copy data to destination buffer */
410 0 : memcpy(buf, digest, EBUFSIZE);
411 :
412 : /* Modify pool so next hash will produce different results */
413 0 : enqueue_randomness(EBUFSIZE);
414 0 : dequeue_randomness(NULL);
415 :
416 : /* Wipe data from memory */
417 0 : explicit_bzero(extract_pool, sizeof(extract_pool));
418 0 : explicit_bzero(digest, sizeof(digest));
419 0 : }
420 :
421 : /* random keystream by ChaCha */
422 :
423 : void arc4_reinit(void *v); /* timeout to start reinit */
424 : void arc4_init(void *); /* actually do the reinit */
425 :
426 : struct mutex rndlock = MUTEX_INITIALIZER(IPL_HIGH);
427 : struct timeout arc4_timeout;
428 : struct task arc4_task = TASK_INITIALIZER(arc4_init, NULL);
429 :
430 : static chacha_ctx rs; /* chacha context for random keystream */
431 : /* keystream blocks (also chacha seed from boot) */
432 : static u_char rs_buf[RSBUFSZ];
433 : u_char rs_buf0[RSBUFSZ] __attribute__((section(".openbsd.randomdata")));
434 : static size_t rs_have; /* valid bytes at end of rs_buf */
435 : static size_t rs_count; /* bytes till reseed */
436 :
437 : void
438 0 : suspend_randomness(void)
439 : {
440 0 : struct timespec ts;
441 :
442 0 : getnanotime(&ts);
443 0 : enqueue_randomness(ts.tv_sec);
444 0 : enqueue_randomness(ts.tv_nsec);
445 :
446 0 : dequeue_randomness(NULL);
447 0 : rs_count = 0;
448 0 : arc4random_buf(entropy_pool, sizeof(entropy_pool));
449 0 : }
450 :
451 : void
452 0 : resume_randomness(char *buf, size_t buflen)
453 : {
454 0 : struct timespec ts;
455 :
456 0 : if (buf && buflen)
457 0 : _rs_seed(buf, buflen);
458 0 : getnanotime(&ts);
459 0 : enqueue_randomness(ts.tv_sec);
460 0 : enqueue_randomness(ts.tv_nsec);
461 :
462 0 : dequeue_randomness(NULL);
463 0 : rs_count = 0;
464 0 : }
465 :
466 : static inline void _rs_rekey(u_char *dat, size_t datlen);
467 :
468 : static inline void
469 0 : _rs_init(u_char *buf, size_t n)
470 : {
471 0 : KASSERT(n >= KEYSZ + IVSZ);
472 0 : chacha_keysetup(&rs, buf, KEYSZ * 8);
473 0 : chacha_ivsetup(&rs, buf + KEYSZ, NULL);
474 0 : }
475 :
476 : static void
477 0 : _rs_seed(u_char *buf, size_t n)
478 : {
479 0 : _rs_rekey(buf, n);
480 :
481 : /* invalidate rs_buf */
482 0 : rs_have = 0;
483 0 : memset(rs_buf, 0, RSBUFSZ);
484 :
485 0 : rs_count = 1600000;
486 0 : }
487 :
488 : static void
489 0 : _rs_stir(int do_lock)
490 : {
491 0 : struct timespec ts;
492 0 : u_int8_t buf[EBUFSIZE], *p;
493 : int i;
494 :
495 : /*
496 : * Use SHA512 PRNG data and a system timespec; early in the boot
497 : * process this is the best we can do -- some architectures do
498 : * not collect entropy very well during this time, but may have
499 : * clock information which is better than nothing.
500 : */
501 0 : extract_entropy(buf);
502 :
503 0 : nanotime(&ts);
504 0 : for (p = (u_int8_t *)&ts, i = 0; i < sizeof(ts); i++)
505 0 : buf[i] ^= p[i];
506 :
507 0 : if (do_lock)
508 0 : mtx_enter(&rndlock);
509 0 : _rs_seed(buf, sizeof(buf));
510 0 : if (do_lock)
511 0 : mtx_leave(&rndlock);
512 :
513 0 : explicit_bzero(buf, sizeof(buf));
514 0 : }
515 :
516 : static inline void
517 0 : _rs_stir_if_needed(size_t len)
518 : {
519 : static int rs_initialized;
520 :
521 0 : if (!rs_initialized) {
522 0 : memcpy(entropy_pool, entropy_pool0, sizeof entropy_pool);
523 0 : memcpy(rs_buf, rs_buf0, sizeof rs_buf);
524 : /* seeds cannot be cleaned yet, random_start() will do so */
525 0 : _rs_init(rs_buf, KEYSZ + IVSZ);
526 0 : rs_count = 1024 * 1024 * 1024; /* until main() runs */
527 0 : rs_initialized = 1;
528 0 : } else if (rs_count <= len)
529 0 : _rs_stir(0);
530 : else
531 0 : rs_count -= len;
532 0 : }
533 :
534 : static void
535 0 : _rs_clearseed(const void *p, size_t s)
536 : {
537 0 : struct kmem_dyn_mode kd_avoidalias;
538 0 : vaddr_t va = trunc_page((vaddr_t)p);
539 0 : vsize_t off = (vaddr_t)p - va;
540 : vsize_t len;
541 : vaddr_t rwva;
542 0 : paddr_t pa;
543 :
544 0 : while (s > 0) {
545 0 : pmap_extract(pmap_kernel(), va, &pa);
546 :
547 0 : memset(&kd_avoidalias, 0, sizeof kd_avoidalias);
548 0 : kd_avoidalias.kd_prefer = pa;
549 0 : kd_avoidalias.kd_waitok = 1;
550 0 : rwva = (vaddr_t)km_alloc(PAGE_SIZE, &kv_any, &kp_none,
551 : &kd_avoidalias);
552 0 : if (!rwva)
553 0 : panic("_rs_clearseed");
554 :
555 0 : pmap_kenter_pa(rwva, pa, PROT_READ | PROT_WRITE);
556 : pmap_update(pmap_kernel());
557 :
558 0 : len = MIN(s, PAGE_SIZE - off);
559 0 : explicit_bzero((void *)(rwva + off), len);
560 :
561 0 : pmap_kremove(rwva, PAGE_SIZE);
562 0 : km_free((void *)rwva, PAGE_SIZE, &kv_any, &kp_none);
563 :
564 0 : va += PAGE_SIZE;
565 0 : s -= len;
566 : off = 0;
567 : }
568 0 : }
569 :
570 : static inline void
571 0 : _rs_rekey(u_char *dat, size_t datlen)
572 : {
573 : #ifndef KEYSTREAM_ONLY
574 : memset(rs_buf, 0, RSBUFSZ);
575 : #endif
576 : /* fill rs_buf with the keystream */
577 0 : chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
578 : /* mix in optional user provided data */
579 0 : if (dat) {
580 : size_t i, m;
581 :
582 0 : m = MIN(datlen, KEYSZ + IVSZ);
583 0 : for (i = 0; i < m; i++)
584 0 : rs_buf[i] ^= dat[i];
585 0 : }
586 : /* immediately reinit for backtracking resistance */
587 0 : _rs_init(rs_buf, KEYSZ + IVSZ);
588 0 : memset(rs_buf, 0, KEYSZ + IVSZ);
589 0 : rs_have = RSBUFSZ - KEYSZ - IVSZ;
590 0 : }
591 :
592 : static inline void
593 0 : _rs_random_buf(void *_buf, size_t n)
594 : {
595 : u_char *buf = (u_char *)_buf;
596 : size_t m;
597 :
598 0 : _rs_stir_if_needed(n);
599 0 : while (n > 0) {
600 0 : if (rs_have > 0) {
601 0 : m = MIN(n, rs_have);
602 0 : memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
603 0 : memset(rs_buf + RSBUFSZ - rs_have, 0, m);
604 0 : buf += m;
605 0 : n -= m;
606 0 : rs_have -= m;
607 0 : }
608 0 : if (rs_have == 0)
609 0 : _rs_rekey(NULL, 0);
610 : }
611 0 : }
612 :
613 : static inline void
614 0 : _rs_random_u32(u_int32_t *val)
615 : {
616 0 : _rs_stir_if_needed(sizeof(*val));
617 0 : if (rs_have < sizeof(*val))
618 0 : _rs_rekey(NULL, 0);
619 0 : memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
620 0 : memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
621 0 : rs_have -= sizeof(*val);
622 0 : }
623 :
624 : /* Return one word of randomness from a ChaCha20 generator */
625 : u_int32_t
626 0 : arc4random(void)
627 : {
628 0 : u_int32_t ret;
629 :
630 0 : mtx_enter(&rndlock);
631 0 : _rs_random_u32(&ret);
632 0 : mtx_leave(&rndlock);
633 0 : return ret;
634 0 : }
635 :
636 : /*
637 : * Fill a buffer of arbitrary length with ChaCha20-derived randomness.
638 : */
639 : void
640 0 : arc4random_buf(void *buf, size_t n)
641 : {
642 0 : mtx_enter(&rndlock);
643 0 : _rs_random_buf(buf, n);
644 0 : mtx_leave(&rndlock);
645 0 : }
646 :
647 : /*
648 : * Allocate a new ChaCha20 context for the caller to use.
649 : */
650 : struct arc4random_ctx *
651 0 : arc4random_ctx_new()
652 : {
653 0 : char keybuf[KEYSZ + IVSZ];
654 :
655 0 : chacha_ctx *ctx = malloc(sizeof(chacha_ctx), M_TEMP, M_WAITOK);
656 0 : arc4random_buf(keybuf, KEYSZ + IVSZ);
657 0 : chacha_keysetup(ctx, keybuf, KEYSZ * 8);
658 0 : chacha_ivsetup(ctx, keybuf + KEYSZ, NULL);
659 0 : explicit_bzero(keybuf, sizeof(keybuf));
660 0 : return (struct arc4random_ctx *)ctx;
661 0 : }
662 :
663 : /*
664 : * Free a ChaCha20 context created by arc4random_ctx_new()
665 : */
666 : void
667 0 : arc4random_ctx_free(struct arc4random_ctx *ctx)
668 : {
669 0 : explicit_bzero(ctx, sizeof(chacha_ctx));
670 0 : free(ctx, M_TEMP, sizeof(chacha_ctx));
671 0 : }
672 :
673 : /*
674 : * Use a given ChaCha20 context to fill a buffer
675 : */
676 : void
677 0 : arc4random_ctx_buf(struct arc4random_ctx *ctx, void *buf, size_t n)
678 : {
679 0 : chacha_encrypt_bytes((chacha_ctx *)ctx, buf, buf, n);
680 0 : }
681 :
682 : /*
683 : * Calculate a uniformly distributed random number less than upper_bound
684 : * avoiding "modulo bias".
685 : *
686 : * Uniformity is achieved by generating new random numbers until the one
687 : * returned is outside the range [0, 2**32 % upper_bound). This
688 : * guarantees the selected random number will be inside
689 : * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
690 : * after reduction modulo upper_bound.
691 : */
692 : u_int32_t
693 0 : arc4random_uniform(u_int32_t upper_bound)
694 : {
695 : u_int32_t r, min;
696 :
697 0 : if (upper_bound < 2)
698 0 : return 0;
699 :
700 : /* 2**32 % x == (2**32 - x) % x */
701 0 : min = -upper_bound % upper_bound;
702 :
703 : /*
704 : * This could theoretically loop forever but each retry has
705 : * p > 0.5 (worst case, usually far better) of selecting a
706 : * number inside the range we need, so it should rarely need
707 : * to re-roll.
708 : */
709 0 : for (;;) {
710 0 : r = arc4random();
711 0 : if (r >= min)
712 : break;
713 : }
714 :
715 0 : return r % upper_bound;
716 0 : }
717 :
718 : /* ARGSUSED */
719 : void
720 0 : arc4_init(void *null)
721 : {
722 0 : _rs_stir(1);
723 0 : }
724 :
725 : /*
726 : * Called by timeout to mark arc4 for stirring,
727 : */
728 : void
729 0 : arc4_reinit(void *v)
730 : {
731 0 : task_add(systq, &arc4_task);
732 : /* 10 minutes, per dm@'s suggestion */
733 0 : timeout_add_sec(&arc4_timeout, 10 * 60);
734 0 : }
735 :
736 : /*
737 : * Start periodic services inside the random subsystem, which pull
738 : * entropy forward, hash it, and re-seed the random stream as needed.
739 : */
740 : void
741 0 : random_start(void)
742 : {
743 : extern char etext[];
744 :
745 : #if !defined(NO_PROPOLICE)
746 : extern long __guard_local;
747 :
748 0 : if (__guard_local == 0)
749 0 : printf("warning: no entropy supplied by boot loader\n");
750 : #endif
751 :
752 0 : _rs_clearseed(entropy_pool0, sizeof entropy_pool0);
753 0 : _rs_clearseed(rs_buf0, sizeof rs_buf0);
754 :
755 : /* Message buffer may contain data from previous boot */
756 0 : if (msgbufp->msg_magic == MSG_MAGIC)
757 0 : add_entropy_words((u_int32_t *)msgbufp->msg_bufc,
758 0 : msgbufp->msg_bufs / sizeof(u_int32_t));
759 0 : add_entropy_words((u_int32_t *)etext - 32*1024,
760 : 8192/sizeof(u_int32_t));
761 :
762 0 : dequeue_randomness(NULL);
763 0 : arc4_init(NULL);
764 0 : timeout_set(&arc4_timeout, arc4_reinit, NULL);
765 0 : arc4_reinit(NULL);
766 0 : timeout_set(&rnd_timeout, dequeue_randomness, NULL);
767 0 : }
768 :
769 : int
770 0 : randomopen(dev_t dev, int flag, int mode, struct proc *p)
771 : {
772 0 : return 0;
773 : }
774 :
775 : int
776 0 : randomclose(dev_t dev, int flag, int mode, struct proc *p)
777 : {
778 0 : return 0;
779 : }
780 :
781 : /*
782 : * Maximum number of bytes to serve directly from the main ChaCha
783 : * pool. Larger requests are served from a discrete ChaCha instance keyed
784 : * from the main pool.
785 : */
786 : #define ARC4_MAIN_MAX_BYTES 2048
787 :
788 : int
789 0 : randomread(dev_t dev, struct uio *uio, int ioflag)
790 : {
791 0 : u_char lbuf[KEYSZ+IVSZ];
792 0 : chacha_ctx lctx;
793 0 : size_t total = uio->uio_resid;
794 : u_char *buf;
795 : int myctx = 0, ret = 0;
796 :
797 0 : if (uio->uio_resid == 0)
798 0 : return 0;
799 :
800 0 : buf = malloc(POOLBYTES, M_TEMP, M_WAITOK);
801 0 : if (total > ARC4_MAIN_MAX_BYTES) {
802 0 : arc4random_buf(lbuf, sizeof(lbuf));
803 0 : chacha_keysetup(&lctx, lbuf, KEYSZ * 8);
804 0 : chacha_ivsetup(&lctx, lbuf + KEYSZ, NULL);
805 0 : explicit_bzero(lbuf, sizeof(lbuf));
806 : myctx = 1;
807 0 : }
808 :
809 0 : while (ret == 0 && uio->uio_resid > 0) {
810 0 : size_t n = ulmin(POOLBYTES, uio->uio_resid);
811 :
812 0 : if (myctx) {
813 : #ifndef KEYSTREAM_ONLY
814 : memset(buf, 0, n);
815 : #endif
816 0 : chacha_encrypt_bytes(&lctx, buf, buf, n);
817 0 : } else
818 0 : arc4random_buf(buf, n);
819 0 : ret = uiomove(buf, n, uio);
820 0 : if (ret == 0 && uio->uio_resid > 0)
821 0 : yield();
822 : }
823 0 : if (myctx)
824 0 : explicit_bzero(&lctx, sizeof(lctx));
825 0 : explicit_bzero(buf, POOLBYTES);
826 0 : free(buf, M_TEMP, POOLBYTES);
827 0 : return ret;
828 0 : }
829 :
830 : int
831 0 : randomwrite(dev_t dev, struct uio *uio, int flags)
832 : {
833 : int ret = 0, newdata = 0;
834 : u_int32_t *buf;
835 :
836 0 : if (uio->uio_resid == 0)
837 0 : return 0;
838 :
839 0 : buf = malloc(POOLBYTES, M_TEMP, M_WAITOK);
840 :
841 0 : while (ret == 0 && uio->uio_resid > 0) {
842 0 : size_t n = ulmin(POOLBYTES, uio->uio_resid);
843 :
844 0 : ret = uiomove(buf, n, uio);
845 0 : if (ret != 0)
846 0 : break;
847 0 : while (n % sizeof(u_int32_t))
848 0 : ((u_int8_t *)buf)[n++] = 0;
849 0 : add_entropy_words(buf, n / 4);
850 0 : if (uio->uio_resid > 0)
851 0 : yield();
852 : newdata = 1;
853 0 : }
854 :
855 0 : if (newdata)
856 0 : arc4_init(NULL);
857 :
858 0 : explicit_bzero(buf, POOLBYTES);
859 0 : free(buf, M_TEMP, POOLBYTES);
860 0 : return ret;
861 0 : }
862 :
863 : int
864 0 : randomkqfilter(dev_t dev, struct knote *kn)
865 : {
866 0 : switch (kn->kn_filter) {
867 : case EVFILT_READ:
868 0 : kn->kn_fop = &randomread_filtops;
869 0 : break;
870 : case EVFILT_WRITE:
871 0 : kn->kn_fop = &randomwrite_filtops;
872 0 : break;
873 : default:
874 0 : return (EINVAL);
875 : }
876 :
877 0 : return (0);
878 0 : }
879 :
880 : void
881 0 : filt_randomdetach(struct knote *kn)
882 : {
883 0 : }
884 :
885 : int
886 0 : filt_randomread(struct knote *kn, long hint)
887 : {
888 0 : kn->kn_data = ARC4_MAIN_MAX_BYTES;
889 0 : return (1);
890 : }
891 :
892 : int
893 0 : filt_randomwrite(struct knote *kn, long hint)
894 : {
895 0 : kn->kn_data = POOLBYTES;
896 0 : return (1);
897 : }
898 :
899 : int
900 0 : randomioctl(dev_t dev, u_long cmd, caddr_t data, int flag, struct proc *p)
901 : {
902 0 : switch (cmd) {
903 : case FIOASYNC:
904 : /* No async flag in softc so this is a no-op. */
905 : break;
906 : case FIONBIO:
907 : /* Handled in the upper FS layer. */
908 : break;
909 : default:
910 0 : return ENOTTY;
911 : }
912 0 : return 0;
913 0 : }
914 :
915 : int
916 0 : sys_getentropy(struct proc *p, void *v, register_t *retval)
917 : {
918 : struct sys_getentropy_args /* {
919 : syscallarg(void *) buf;
920 : syscallarg(size_t) nbyte;
921 0 : } */ *uap = v;
922 0 : char buf[256];
923 : int error;
924 :
925 0 : if (SCARG(uap, nbyte) > sizeof(buf))
926 0 : return (EIO);
927 0 : arc4random_buf(buf, SCARG(uap, nbyte));
928 0 : if ((error = copyout(buf, SCARG(uap, buf), SCARG(uap, nbyte))) != 0)
929 0 : return (error);
930 0 : explicit_bzero(buf, sizeof(buf));
931 0 : retval[0] = 0;
932 0 : return (0);
933 0 : }
|
