1 /* 2 * random.c -- A strong random number generator 3 * 4 * Copyright (C) 2017 Jason A. Donenfeld <Jason@zx2c4.com>. All 5 * Rights Reserved. 6 * 7 * Copyright Matt Mackall <mpm@selenic.com>, 2003, 2004, 2005 8 * 9 * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All 10 * rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, and the entire permission notice in its entirety, 17 * including the disclaimer of warranties. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. The name of the author may not be used to endorse or promote 22 * products derived from this software without specific prior 23 * written permission. 24 * 25 * ALTERNATIVELY, this product may be distributed under the terms of 26 * the GNU General Public License, in which case the provisions of the GPL are 27 * required INSTEAD OF the above restrictions. (This clause is 28 * necessary due to a potential bad interaction between the GPL and 29 * the restrictions contained in a BSD-style copyright.) 30 * 31 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 32 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF 34 * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE 35 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 36 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 37 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 38 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 39 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 40 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 41 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH 42 * DAMAGE. 43 */ 44 45 /* 46 * (now, with legal B.S. out of the way.....) 47 * 48 * This routine gathers environmental noise from device drivers, etc., 49 * and returns good random numbers, suitable for cryptographic use. 50 * Besides the obvious cryptographic uses, these numbers are also good 51 * for seeding TCP sequence numbers, and other places where it is 52 * desirable to have numbers which are not only random, but hard to 53 * predict by an attacker. 54 * 55 * Theory of operation 56 * =================== 57 * 58 * Computers are very predictable devices. Hence it is extremely hard 59 * to produce truly random numbers on a computer --- as opposed to 60 * pseudo-random numbers, which can easily generated by using a 61 * algorithm. Unfortunately, it is very easy for attackers to guess 62 * the sequence of pseudo-random number generators, and for some 63 * applications this is not acceptable. So instead, we must try to 64 * gather "environmental noise" from the computer's environment, which 65 * must be hard for outside attackers to observe, and use that to 66 * generate random numbers. In a Unix environment, this is best done 67 * from inside the kernel. 68 * 69 * Sources of randomness from the environment include inter-keyboard 70 * timings, inter-interrupt timings from some interrupts, and other 71 * events which are both (a) non-deterministic and (b) hard for an 72 * outside observer to measure. Randomness from these sources are 73 * added to an "entropy pool", which is mixed using a CRC-like function. 74 * This is not cryptographically strong, but it is adequate assuming 75 * the randomness is not chosen maliciously, and it is fast enough that 76 * the overhead of doing it on every interrupt is very reasonable. 77 * As random bytes are mixed into the entropy pool, the routines keep 78 * an *estimate* of how many bits of randomness have been stored into 79 * the random number generator's internal state. 80 * 81 * When random bytes are desired, they are obtained by taking the SHA 82 * hash of the contents of the "entropy pool". The SHA hash avoids 83 * exposing the internal state of the entropy pool. It is believed to 84 * be computationally infeasible to derive any useful information 85 * about the input of SHA from its output. Even if it is possible to 86 * analyze SHA in some clever way, as long as the amount of data 87 * returned from the generator is less than the inherent entropy in 88 * the pool, the output data is totally unpredictable. For this 89 * reason, the routine decreases its internal estimate of how many 90 * bits of "true randomness" are contained in the entropy pool as it 91 * outputs random numbers. 92 * 93 * If this estimate goes to zero, the routine can still generate 94 * random numbers; however, an attacker may (at least in theory) be 95 * able to infer the future output of the generator from prior 96 * outputs. This requires successful cryptanalysis of SHA, which is 97 * not believed to be feasible, but there is a remote possibility. 98 * Nonetheless, these numbers should be useful for the vast majority 99 * of purposes. 100 * 101 * Exported interfaces ---- output 102 * =============================== 103 * 104 * There are three exported interfaces; the first is one designed to 105 * be used from within the kernel: 106 * 107 * void get_random_bytes(void *buf, int nbytes); 108 * 109 * This interface will return the requested number of random bytes, 110 * and place it in the requested buffer. 111 * 112 * The two other interfaces are two character devices /dev/random and 113 * /dev/urandom. /dev/random is suitable for use when very high 114 * quality randomness is desired (for example, for key generation or 115 * one-time pads), as it will only return a maximum of the number of 116 * bits of randomness (as estimated by the random number generator) 117 * contained in the entropy pool. 118 * 119 * The /dev/urandom device does not have this limit, and will return 120 * as many bytes as are requested. As more and more random bytes are 121 * requested without giving time for the entropy pool to recharge, 122 * this will result in random numbers that are merely cryptographically 123 * strong. For many applications, however, this is acceptable. 124 * 125 * Exported interfaces ---- input 126 * ============================== 127 * 128 * The current exported interfaces for gathering environmental noise 129 * from the devices are: 130 * 131 * void add_device_randomness(const void *buf, unsigned int size); 132 * void add_input_randomness(unsigned int type, unsigned int code, 133 * unsigned int value); 134 * void add_interrupt_randomness(int irq, int irq_flags); 135 * void add_disk_randomness(struct gendisk *disk); 136 * 137 * add_device_randomness() is for adding data to the random pool that 138 * is likely to differ between two devices (or possibly even per boot). 139 * This would be things like MAC addresses or serial numbers, or the 140 * read-out of the RTC. This does *not* add any actual entropy to the 141 * pool, but it initializes the pool to different values for devices 142 * that might otherwise be identical and have very little entropy 143 * available to them (particularly common in the embedded world). 144 * 145 * add_input_randomness() uses the input layer interrupt timing, as well as 146 * the event type information from the hardware. 147 * 148 * add_interrupt_randomness() uses the interrupt timing as random 149 * inputs to the entropy pool. Using the cycle counters and the irq source 150 * as inputs, it feeds the randomness roughly once a second. 151 * 152 * add_disk_randomness() uses what amounts to the seek time of block 153 * layer request events, on a per-disk_devt basis, as input to the 154 * entropy pool. Note that high-speed solid state drives with very low 155 * seek times do not make for good sources of entropy, as their seek 156 * times are usually fairly consistent. 157 * 158 * All of these routines try to estimate how many bits of randomness a 159 * particular randomness source. They do this by keeping track of the 160 * first and second order deltas of the event timings. 161 * 162 * Ensuring unpredictability at system startup 163 * ============================================ 164 * 165 * When any operating system starts up, it will go through a sequence 166 * of actions that are fairly predictable by an adversary, especially 167 * if the start-up does not involve interaction with a human operator. 168 * This reduces the actual number of bits of unpredictability in the 169 * entropy pool below the value in entropy_count. In order to 170 * counteract this effect, it helps to carry information in the 171 * entropy pool across shut-downs and start-ups. To do this, put the 172 * following lines an appropriate script which is run during the boot 173 * sequence: 174 * 175 * echo "Initializing random number generator..." 176 * random_seed=/var/run/random-seed 177 * # Carry a random seed from start-up to start-up 178 * # Load and then save the whole entropy pool 179 * if [ -f $random_seed ]; then 180 * cat $random_seed >/dev/urandom 181 * else 182 * touch $random_seed 183 * fi 184 * chmod 600 $random_seed 185 * dd if=/dev/urandom of=$random_seed count=1 bs=512 186 * 187 * and the following lines in an appropriate script which is run as 188 * the system is shutdown: 189 * 190 * # Carry a random seed from shut-down to start-up 191 * # Save the whole entropy pool 192 * echo "Saving random seed..." 193 * random_seed=/var/run/random-seed 194 * touch $random_seed 195 * chmod 600 $random_seed 196 * dd if=/dev/urandom of=$random_seed count=1 bs=512 197 * 198 * For example, on most modern systems using the System V init 199 * scripts, such code fragments would be found in 200 * /etc/rc.d/init.d/random. On older Linux systems, the correct script 201 * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0. 202 * 203 * Effectively, these commands cause the contents of the entropy pool 204 * to be saved at shut-down time and reloaded into the entropy pool at 205 * start-up. (The 'dd' in the addition to the bootup script is to 206 * make sure that /etc/random-seed is different for every start-up, 207 * even if the system crashes without executing rc.0.) Even with 208 * complete knowledge of the start-up activities, predicting the state 209 * of the entropy pool requires knowledge of the previous history of 210 * the system. 211 * 212 * Configuring the /dev/random driver under Linux 213 * ============================================== 214 * 215 * The /dev/random driver under Linux uses minor numbers 8 and 9 of 216 * the /dev/mem major number (#1). So if your system does not have 217 * /dev/random and /dev/urandom created already, they can be created 218 * by using the commands: 219 * 220 * mknod /dev/random c 1 8 221 * mknod /dev/urandom c 1 9 222 * 223 * Acknowledgements: 224 * ================= 225 * 226 * Ideas for constructing this random number generator were derived 227 * from Pretty Good Privacy's random number generator, and from private 228 * discussions with Phil Karn. Colin Plumb provided a faster random 229 * number generator, which speed up the mixing function of the entropy 230 * pool, taken from PGPfone. Dale Worley has also contributed many 231 * useful ideas and suggestions to improve this driver. 232 * 233 * Any flaws in the design are solely my responsibility, and should 234 * not be attributed to the Phil, Colin, or any of authors of PGP. 235 * 236 * Further background information on this topic may be obtained from 237 * RFC 1750, "Randomness Recommendations for Security", by Donald 238 * Eastlake, Steve Crocker, and Jeff Schiller. 239 */ 240 241 #include <linux/utsname.h> 242 #include <linux/module.h> 243 #include <linux/kernel.h> 244 #include <linux/major.h> 245 #include <linux/string.h> 246 #include <linux/fcntl.h> 247 #include <linux/slab.h> 248 #include <linux/random.h> 249 #include <linux/poll.h> 250 #include <linux/init.h> 251 #include <linux/fs.h> 252 #include <linux/genhd.h> 253 #include <linux/interrupt.h> 254 #include <linux/mm.h> 255 #include <linux/nodemask.h> 256 #include <linux/spinlock.h> 257 #include <linux/kthread.h> 258 #include <linux/percpu.h> 259 #include <linux/cryptohash.h> 260 #include <linux/fips.h> 261 #include <linux/ptrace.h> 262 #include <linux/kmemcheck.h> 263 #include <linux/workqueue.h> 264 #include <linux/irq.h> 265 #include <linux/syscalls.h> 266 #include <linux/completion.h> 267 #include <linux/uuid.h> 268 #include <crypto/chacha20.h> 269 270 #include <asm/processor.h> 271 #include <linux/uaccess.h> 272 #include <asm/irq.h> 273 #include <asm/irq_regs.h> 274 #include <asm/io.h> 275 276 #define CREATE_TRACE_POINTS 277 #include <trace/events/random.h> 278 279 /* #define ADD_INTERRUPT_BENCH */ 280 281 /* 282 * Configuration information 283 */ 284 #define INPUT_POOL_SHIFT 12 285 #define INPUT_POOL_WORDS (1 << (INPUT_POOL_SHIFT-5)) 286 #define OUTPUT_POOL_SHIFT 10 287 #define OUTPUT_POOL_WORDS (1 << (OUTPUT_POOL_SHIFT-5)) 288 #define SEC_XFER_SIZE 512 289 #define EXTRACT_SIZE 10 290 291 292 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long)) 293 294 /* 295 * To allow fractional bits to be tracked, the entropy_count field is 296 * denominated in units of 1/8th bits. 297 * 298 * 2*(ENTROPY_SHIFT + log2(poolbits)) must <= 31, or the multiply in 299 * credit_entropy_bits() needs to be 64 bits wide. 300 */ 301 #define ENTROPY_SHIFT 3 302 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT) 303 304 /* 305 * The minimum number of bits of entropy before we wake up a read on 306 * /dev/random. Should be enough to do a significant reseed. 307 */ 308 static int random_read_wakeup_bits = 64; 309 310 /* 311 * If the entropy count falls under this number of bits, then we 312 * should wake up processes which are selecting or polling on write 313 * access to /dev/random. 314 */ 315 static int random_write_wakeup_bits = 28 * OUTPUT_POOL_WORDS; 316 317 /* 318 * Originally, we used a primitive polynomial of degree .poolwords 319 * over GF(2). The taps for various sizes are defined below. They 320 * were chosen to be evenly spaced except for the last tap, which is 1 321 * to get the twisting happening as fast as possible. 322 * 323 * For the purposes of better mixing, we use the CRC-32 polynomial as 324 * well to make a (modified) twisted Generalized Feedback Shift 325 * Register. (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR 326 * generators. ACM Transactions on Modeling and Computer Simulation 327 * 2(3):179-194. Also see M. Matsumoto & Y. Kurita, 1994. Twisted 328 * GFSR generators II. ACM Transactions on Modeling and Computer 329 * Simulation 4:254-266) 330 * 331 * Thanks to Colin Plumb for suggesting this. 332 * 333 * The mixing operation is much less sensitive than the output hash, 334 * where we use SHA-1. All that we want of mixing operation is that 335 * it be a good non-cryptographic hash; i.e. it not produce collisions 336 * when fed "random" data of the sort we expect to see. As long as 337 * the pool state differs for different inputs, we have preserved the 338 * input entropy and done a good job. The fact that an intelligent 339 * attacker can construct inputs that will produce controlled 340 * alterations to the pool's state is not important because we don't 341 * consider such inputs to contribute any randomness. The only 342 * property we need with respect to them is that the attacker can't 343 * increase his/her knowledge of the pool's state. Since all 344 * additions are reversible (knowing the final state and the input, 345 * you can reconstruct the initial state), if an attacker has any 346 * uncertainty about the initial state, he/she can only shuffle that 347 * uncertainty about, but never cause any collisions (which would 348 * decrease the uncertainty). 349 * 350 * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and 351 * Videau in their paper, "The Linux Pseudorandom Number Generator 352 * Revisited" (see: http://eprint.iacr.org/2012/251.pdf). In their 353 * paper, they point out that we are not using a true Twisted GFSR, 354 * since Matsumoto & Kurita used a trinomial feedback polynomial (that 355 * is, with only three taps, instead of the six that we are using). 356 * As a result, the resulting polynomial is neither primitive nor 357 * irreducible, and hence does not have a maximal period over 358 * GF(2**32). They suggest a slight change to the generator 359 * polynomial which improves the resulting TGFSR polynomial to be 360 * irreducible, which we have made here. 361 */ 362 static struct poolinfo { 363 int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits; 364 #define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5) 365 int tap1, tap2, tap3, tap4, tap5; 366 } poolinfo_table[] = { 367 /* was: x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 */ 368 /* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */ 369 { S(128), 104, 76, 51, 25, 1 }, 370 /* was: x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 */ 371 /* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */ 372 { S(32), 26, 19, 14, 7, 1 }, 373 #if 0 374 /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ 375 { S(2048), 1638, 1231, 819, 411, 1 }, 376 377 /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */ 378 { S(1024), 817, 615, 412, 204, 1 }, 379 380 /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */ 381 { S(1024), 819, 616, 410, 207, 2 }, 382 383 /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */ 384 { S(512), 411, 308, 208, 104, 1 }, 385 386 /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */ 387 { S(512), 409, 307, 206, 102, 2 }, 388 /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */ 389 { S(512), 409, 309, 205, 103, 2 }, 390 391 /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */ 392 { S(256), 205, 155, 101, 52, 1 }, 393 394 /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ 395 { S(128), 103, 78, 51, 27, 2 }, 396 397 /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ 398 { S(64), 52, 39, 26, 14, 1 }, 399 #endif 400 }; 401 402 /* 403 * Static global variables 404 */ 405 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); 406 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); 407 static struct fasync_struct *fasync; 408 409 static DEFINE_SPINLOCK(random_ready_list_lock); 410 static LIST_HEAD(random_ready_list); 411 412 struct crng_state { 413 __u32 state[16]; 414 unsigned long init_time; 415 spinlock_t lock; 416 }; 417 418 struct crng_state primary_crng = { 419 .lock = __SPIN_LOCK_UNLOCKED(primary_crng.lock), 420 }; 421 422 /* 423 * crng_init = 0 --> Uninitialized 424 * 1 --> Initialized 425 * 2 --> Initialized from input_pool 426 * 427 * crng_init is protected by primary_crng->lock, and only increases 428 * its value (from 0->1->2). 429 */ 430 static int crng_init = 0; 431 #define crng_ready() (likely(crng_init > 0)) 432 static int crng_init_cnt = 0; 433 #define CRNG_INIT_CNT_THRESH (2*CHACHA20_KEY_SIZE) 434 static void _extract_crng(struct crng_state *crng, 435 __u8 out[CHACHA20_BLOCK_SIZE]); 436 static void _crng_backtrack_protect(struct crng_state *crng, 437 __u8 tmp[CHACHA20_BLOCK_SIZE], int used); 438 static void process_random_ready_list(void); 439 static void _get_random_bytes(void *buf, int nbytes); 440 441 /********************************************************************** 442 * 443 * OS independent entropy store. Here are the functions which handle 444 * storing entropy in an entropy pool. 445 * 446 **********************************************************************/ 447 448 struct entropy_store; 449 struct entropy_store { 450 /* read-only data: */ 451 const struct poolinfo *poolinfo; 452 __u32 *pool; 453 const char *name; 454 struct entropy_store *pull; 455 struct work_struct push_work; 456 457 /* read-write data: */ 458 unsigned long last_pulled; 459 spinlock_t lock; 460 unsigned short add_ptr; 461 unsigned short input_rotate; 462 int entropy_count; 463 int entropy_total; 464 unsigned int initialized:1; 465 unsigned int last_data_init:1; 466 __u8 last_data[EXTRACT_SIZE]; 467 }; 468 469 static ssize_t extract_entropy(struct entropy_store *r, void *buf, 470 size_t nbytes, int min, int rsvd); 471 static ssize_t _extract_entropy(struct entropy_store *r, void *buf, 472 size_t nbytes, int fips); 473 474 static void crng_reseed(struct crng_state *crng, struct entropy_store *r); 475 static void push_to_pool(struct work_struct *work); 476 static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy; 477 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy; 478 479 static struct entropy_store input_pool = { 480 .poolinfo = &poolinfo_table[0], 481 .name = "input", 482 .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), 483 .pool = input_pool_data 484 }; 485 486 static struct entropy_store blocking_pool = { 487 .poolinfo = &poolinfo_table[1], 488 .name = "blocking", 489 .pull = &input_pool, 490 .lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock), 491 .pool = blocking_pool_data, 492 .push_work = __WORK_INITIALIZER(blocking_pool.push_work, 493 push_to_pool), 494 }; 495 496 static __u32 const twist_table[8] = { 497 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 498 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; 499 500 /* 501 * This function adds bytes into the entropy "pool". It does not 502 * update the entropy estimate. The caller should call 503 * credit_entropy_bits if this is appropriate. 504 * 505 * The pool is stirred with a primitive polynomial of the appropriate 506 * degree, and then twisted. We twist by three bits at a time because 507 * it's cheap to do so and helps slightly in the expected case where 508 * the entropy is concentrated in the low-order bits. 509 */ 510 static void _mix_pool_bytes(struct entropy_store *r, const void *in, 511 int nbytes) 512 { 513 unsigned long i, tap1, tap2, tap3, tap4, tap5; 514 int input_rotate; 515 int wordmask = r->poolinfo->poolwords - 1; 516 const char *bytes = in; 517 __u32 w; 518 519 tap1 = r->poolinfo->tap1; 520 tap2 = r->poolinfo->tap2; 521 tap3 = r->poolinfo->tap3; 522 tap4 = r->poolinfo->tap4; 523 tap5 = r->poolinfo->tap5; 524 525 input_rotate = r->input_rotate; 526 i = r->add_ptr; 527 528 /* mix one byte at a time to simplify size handling and churn faster */ 529 while (nbytes--) { 530 w = rol32(*bytes++, input_rotate); 531 i = (i - 1) & wordmask; 532 533 /* XOR in the various taps */ 534 w ^= r->pool[i]; 535 w ^= r->pool[(i + tap1) & wordmask]; 536 w ^= r->pool[(i + tap2) & wordmask]; 537 w ^= r->pool[(i + tap3) & wordmask]; 538 w ^= r->pool[(i + tap4) & wordmask]; 539 w ^= r->pool[(i + tap5) & wordmask]; 540 541 /* Mix the result back in with a twist */ 542 r->pool[i] = (w >> 3) ^ twist_table[w & 7]; 543 544 /* 545 * Normally, we add 7 bits of rotation to the pool. 546 * At the beginning of the pool, add an extra 7 bits 547 * rotation, so that successive passes spread the 548 * input bits across the pool evenly. 549 */ 550 input_rotate = (input_rotate + (i ? 7 : 14)) & 31; 551 } 552 553 r->input_rotate = input_rotate; 554 r->add_ptr = i; 555 } 556 557 static void __mix_pool_bytes(struct entropy_store *r, const void *in, 558 int nbytes) 559 { 560 trace_mix_pool_bytes_nolock(r->name, nbytes, _RET_IP_); 561 _mix_pool_bytes(r, in, nbytes); 562 } 563 564 static void mix_pool_bytes(struct entropy_store *r, const void *in, 565 int nbytes) 566 { 567 unsigned long flags; 568 569 trace_mix_pool_bytes(r->name, nbytes, _RET_IP_); 570 spin_lock_irqsave(&r->lock, flags); 571 _mix_pool_bytes(r, in, nbytes); 572 spin_unlock_irqrestore(&r->lock, flags); 573 } 574 575 struct fast_pool { 576 __u32 pool[4]; 577 unsigned long last; 578 unsigned short reg_idx; 579 unsigned char count; 580 }; 581 582 /* 583 * This is a fast mixing routine used by the interrupt randomness 584 * collector. It's hardcoded for an 128 bit pool and assumes that any 585 * locks that might be needed are taken by the caller. 586 */ 587 static void fast_mix(struct fast_pool *f) 588 { 589 __u32 a = f->pool[0], b = f->pool[1]; 590 __u32 c = f->pool[2], d = f->pool[3]; 591 592 a += b; c += d; 593 b = rol32(b, 6); d = rol32(d, 27); 594 d ^= a; b ^= c; 595 596 a += b; c += d; 597 b = rol32(b, 16); d = rol32(d, 14); 598 d ^= a; b ^= c; 599 600 a += b; c += d; 601 b = rol32(b, 6); d = rol32(d, 27); 602 d ^= a; b ^= c; 603 604 a += b; c += d; 605 b = rol32(b, 16); d = rol32(d, 14); 606 d ^= a; b ^= c; 607 608 f->pool[0] = a; f->pool[1] = b; 609 f->pool[2] = c; f->pool[3] = d; 610 f->count++; 611 } 612 613 static void process_random_ready_list(void) 614 { 615 unsigned long flags; 616 struct random_ready_callback *rdy, *tmp; 617 618 spin_lock_irqsave(&random_ready_list_lock, flags); 619 list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) { 620 struct module *owner = rdy->owner; 621 622 list_del_init(&rdy->list); 623 rdy->func(rdy); 624 module_put(owner); 625 } 626 spin_unlock_irqrestore(&random_ready_list_lock, flags); 627 } 628 629 /* 630 * Credit (or debit) the entropy store with n bits of entropy. 631 * Use credit_entropy_bits_safe() if the value comes from userspace 632 * or otherwise should be checked for extreme values. 633 */ 634 static void credit_entropy_bits(struct entropy_store *r, int nbits) 635 { 636 int entropy_count, orig; 637 const int pool_size = r->poolinfo->poolfracbits; 638 int nfrac = nbits << ENTROPY_SHIFT; 639 640 if (!nbits) 641 return; 642 643 retry: 644 entropy_count = orig = ACCESS_ONCE(r->entropy_count); 645 if (nfrac < 0) { 646 /* Debit */ 647 entropy_count += nfrac; 648 } else { 649 /* 650 * Credit: we have to account for the possibility of 651 * overwriting already present entropy. Even in the 652 * ideal case of pure Shannon entropy, new contributions 653 * approach the full value asymptotically: 654 * 655 * entropy <- entropy + (pool_size - entropy) * 656 * (1 - exp(-add_entropy/pool_size)) 657 * 658 * For add_entropy <= pool_size/2 then 659 * (1 - exp(-add_entropy/pool_size)) >= 660 * (add_entropy/pool_size)*0.7869... 661 * so we can approximate the exponential with 662 * 3/4*add_entropy/pool_size and still be on the 663 * safe side by adding at most pool_size/2 at a time. 664 * 665 * The use of pool_size-2 in the while statement is to 666 * prevent rounding artifacts from making the loop 667 * arbitrarily long; this limits the loop to log2(pool_size)*2 668 * turns no matter how large nbits is. 669 */ 670 int pnfrac = nfrac; 671 const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2; 672 /* The +2 corresponds to the /4 in the denominator */ 673 674 do { 675 unsigned int anfrac = min(pnfrac, pool_size/2); 676 unsigned int add = 677 ((pool_size - entropy_count)*anfrac*3) >> s; 678 679 entropy_count += add; 680 pnfrac -= anfrac; 681 } while (unlikely(entropy_count < pool_size-2 && pnfrac)); 682 } 683 684 if (unlikely(entropy_count < 0)) { 685 pr_warn("random: negative entropy/overflow: pool %s count %d\n", 686 r->name, entropy_count); 687 WARN_ON(1); 688 entropy_count = 0; 689 } else if (entropy_count > pool_size) 690 entropy_count = pool_size; 691 if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) 692 goto retry; 693 694 r->entropy_total += nbits; 695 if (!r->initialized && r->entropy_total > 128) { 696 r->initialized = 1; 697 r->entropy_total = 0; 698 } 699 700 trace_credit_entropy_bits(r->name, nbits, 701 entropy_count >> ENTROPY_SHIFT, 702 r->entropy_total, _RET_IP_); 703 704 if (r == &input_pool) { 705 int entropy_bits = entropy_count >> ENTROPY_SHIFT; 706 707 if (crng_init < 2 && entropy_bits >= 128) { 708 crng_reseed(&primary_crng, r); 709 entropy_bits = r->entropy_count >> ENTROPY_SHIFT; 710 } 711 712 /* should we wake readers? */ 713 if (entropy_bits >= random_read_wakeup_bits) { 714 wake_up_interruptible(&random_read_wait); 715 kill_fasync(&fasync, SIGIO, POLL_IN); 716 } 717 /* If the input pool is getting full, send some 718 * entropy to the blocking pool until it is 75% full. 719 */ 720 if (entropy_bits > random_write_wakeup_bits && 721 r->initialized && 722 r->entropy_total >= 2*random_read_wakeup_bits) { 723 struct entropy_store *other = &blocking_pool; 724 725 if (other->entropy_count <= 726 3 * other->poolinfo->poolfracbits / 4) { 727 schedule_work(&other->push_work); 728 r->entropy_total = 0; 729 } 730 } 731 } 732 } 733 734 static int credit_entropy_bits_safe(struct entropy_store *r, int nbits) 735 { 736 const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1)); 737 738 if (nbits < 0) 739 return -EINVAL; 740 741 /* Cap the value to avoid overflows */ 742 nbits = min(nbits, nbits_max); 743 744 credit_entropy_bits(r, nbits); 745 return 0; 746 } 747 748 /********************************************************************* 749 * 750 * CRNG using CHACHA20 751 * 752 *********************************************************************/ 753 754 #define CRNG_RESEED_INTERVAL (300*HZ) 755 756 static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait); 757 758 #ifdef CONFIG_NUMA 759 /* 760 * Hack to deal with crazy userspace progams when they are all trying 761 * to access /dev/urandom in parallel. The programs are almost 762 * certainly doing something terribly wrong, but we'll work around 763 * their brain damage. 764 */ 765 static struct crng_state **crng_node_pool __read_mostly; 766 #endif 767 768 static void invalidate_batched_entropy(void); 769 770 static void crng_initialize(struct crng_state *crng) 771 { 772 int i; 773 unsigned long rv; 774 775 memcpy(&crng->state[0], "expand 32-byte k", 16); 776 if (crng == &primary_crng) 777 _extract_entropy(&input_pool, &crng->state[4], 778 sizeof(__u32) * 12, 0); 779 else 780 _get_random_bytes(&crng->state[4], sizeof(__u32) * 12); 781 for (i = 4; i < 16; i++) { 782 if (!arch_get_random_seed_long(&rv) && 783 !arch_get_random_long(&rv)) 784 rv = random_get_entropy(); 785 crng->state[i] ^= rv; 786 } 787 crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1; 788 } 789 790 static int crng_fast_load(const char *cp, size_t len) 791 { 792 unsigned long flags; 793 char *p; 794 795 if (!spin_trylock_irqsave(&primary_crng.lock, flags)) 796 return 0; 797 if (crng_ready()) { 798 spin_unlock_irqrestore(&primary_crng.lock, flags); 799 return 0; 800 } 801 p = (unsigned char *) &primary_crng.state[4]; 802 while (len > 0 && crng_init_cnt < CRNG_INIT_CNT_THRESH) { 803 p[crng_init_cnt % CHACHA20_KEY_SIZE] ^= *cp; 804 cp++; crng_init_cnt++; len--; 805 } 806 spin_unlock_irqrestore(&primary_crng.lock, flags); 807 if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) { 808 invalidate_batched_entropy(); 809 crng_init = 1; 810 wake_up_interruptible(&crng_init_wait); 811 pr_notice("random: fast init done\n"); 812 } 813 return 1; 814 } 815 816 static void crng_reseed(struct crng_state *crng, struct entropy_store *r) 817 { 818 unsigned long flags; 819 int i, num; 820 union { 821 __u8 block[CHACHA20_BLOCK_SIZE]; 822 __u32 key[8]; 823 } buf; 824 825 if (r) { 826 num = extract_entropy(r, &buf, 32, 16, 0); 827 if (num == 0) 828 return; 829 } else { 830 _extract_crng(&primary_crng, buf.block); 831 _crng_backtrack_protect(&primary_crng, buf.block, 832 CHACHA20_KEY_SIZE); 833 } 834 spin_lock_irqsave(&primary_crng.lock, flags); 835 for (i = 0; i < 8; i++) { 836 unsigned long rv; 837 if (!arch_get_random_seed_long(&rv) && 838 !arch_get_random_long(&rv)) 839 rv = random_get_entropy(); 840 crng->state[i+4] ^= buf.key[i] ^ rv; 841 } 842 memzero_explicit(&buf, sizeof(buf)); 843 crng->init_time = jiffies; 844 spin_unlock_irqrestore(&primary_crng.lock, flags); 845 if (crng == &primary_crng && crng_init < 2) { 846 invalidate_batched_entropy(); 847 crng_init = 2; 848 process_random_ready_list(); 849 wake_up_interruptible(&crng_init_wait); 850 pr_notice("random: crng init done\n"); 851 } 852 } 853 854 static void _extract_crng(struct crng_state *crng, 855 __u8 out[CHACHA20_BLOCK_SIZE]) 856 { 857 unsigned long v, flags; 858 859 if (crng_init > 1 && 860 time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)) 861 crng_reseed(crng, crng == &primary_crng ? &input_pool : NULL); 862 spin_lock_irqsave(&crng->lock, flags); 863 if (arch_get_random_long(&v)) 864 crng->state[14] ^= v; 865 chacha20_block(&crng->state[0], out); 866 if (crng->state[12] == 0) 867 crng->state[13]++; 868 spin_unlock_irqrestore(&crng->lock, flags); 869 } 870 871 static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE]) 872 { 873 struct crng_state *crng = NULL; 874 875 #ifdef CONFIG_NUMA 876 if (crng_node_pool) 877 crng = crng_node_pool[numa_node_id()]; 878 if (crng == NULL) 879 #endif 880 crng = &primary_crng; 881 _extract_crng(crng, out); 882 } 883 884 /* 885 * Use the leftover bytes from the CRNG block output (if there is 886 * enough) to mutate the CRNG key to provide backtracking protection. 887 */ 888 static void _crng_backtrack_protect(struct crng_state *crng, 889 __u8 tmp[CHACHA20_BLOCK_SIZE], int used) 890 { 891 unsigned long flags; 892 __u32 *s, *d; 893 int i; 894 895 used = round_up(used, sizeof(__u32)); 896 if (used + CHACHA20_KEY_SIZE > CHACHA20_BLOCK_SIZE) { 897 extract_crng(tmp); 898 used = 0; 899 } 900 spin_lock_irqsave(&crng->lock, flags); 901 s = (__u32 *) &tmp[used]; 902 d = &crng->state[4]; 903 for (i=0; i < 8; i++) 904 *d++ ^= *s++; 905 spin_unlock_irqrestore(&crng->lock, flags); 906 } 907 908 static void crng_backtrack_protect(__u8 tmp[CHACHA20_BLOCK_SIZE], int used) 909 { 910 struct crng_state *crng = NULL; 911 912 #ifdef CONFIG_NUMA 913 if (crng_node_pool) 914 crng = crng_node_pool[numa_node_id()]; 915 if (crng == NULL) 916 #endif 917 crng = &primary_crng; 918 _crng_backtrack_protect(crng, tmp, used); 919 } 920 921 static ssize_t extract_crng_user(void __user *buf, size_t nbytes) 922 { 923 ssize_t ret = 0, i = CHACHA20_BLOCK_SIZE; 924 __u8 tmp[CHACHA20_BLOCK_SIZE]; 925 int large_request = (nbytes > 256); 926 927 while (nbytes) { 928 if (large_request && need_resched()) { 929 if (signal_pending(current)) { 930 if (ret == 0) 931 ret = -ERESTARTSYS; 932 break; 933 } 934 schedule(); 935 } 936 937 extract_crng(tmp); 938 i = min_t(int, nbytes, CHACHA20_BLOCK_SIZE); 939 if (copy_to_user(buf, tmp, i)) { 940 ret = -EFAULT; 941 break; 942 } 943 944 nbytes -= i; 945 buf += i; 946 ret += i; 947 } 948 crng_backtrack_protect(tmp, i); 949 950 /* Wipe data just written to memory */ 951 memzero_explicit(tmp, sizeof(tmp)); 952 953 return ret; 954 } 955 956 957 /********************************************************************* 958 * 959 * Entropy input management 960 * 961 *********************************************************************/ 962 963 /* There is one of these per entropy source */ 964 struct timer_rand_state { 965 cycles_t last_time; 966 long last_delta, last_delta2; 967 unsigned dont_count_entropy:1; 968 }; 969 970 #define INIT_TIMER_RAND_STATE { INITIAL_JIFFIES, }; 971 972 /* 973 * Add device- or boot-specific data to the input pool to help 974 * initialize it. 975 * 976 * None of this adds any entropy; it is meant to avoid the problem of 977 * the entropy pool having similar initial state across largely 978 * identical devices. 979 */ 980 void add_device_randomness(const void *buf, unsigned int size) 981 { 982 unsigned long time = random_get_entropy() ^ jiffies; 983 unsigned long flags; 984 985 if (!crng_ready()) { 986 crng_fast_load(buf, size); 987 return; 988 } 989 990 trace_add_device_randomness(size, _RET_IP_); 991 spin_lock_irqsave(&input_pool.lock, flags); 992 _mix_pool_bytes(&input_pool, buf, size); 993 _mix_pool_bytes(&input_pool, &time, sizeof(time)); 994 spin_unlock_irqrestore(&input_pool.lock, flags); 995 } 996 EXPORT_SYMBOL(add_device_randomness); 997 998 static struct timer_rand_state input_timer_state = INIT_TIMER_RAND_STATE; 999 1000 /* 1001 * This function adds entropy to the entropy "pool" by using timing 1002 * delays. It uses the timer_rand_state structure to make an estimate 1003 * of how many bits of entropy this call has added to the pool. 1004 * 1005 * The number "num" is also added to the pool - it should somehow describe 1006 * the type of event which just happened. This is currently 0-255 for 1007 * keyboard scan codes, and 256 upwards for interrupts. 1008 * 1009 */ 1010 static void add_timer_randomness(struct timer_rand_state *state, unsigned num) 1011 { 1012 struct entropy_store *r; 1013 struct { 1014 long jiffies; 1015 unsigned cycles; 1016 unsigned num; 1017 } sample; 1018 long delta, delta2, delta3; 1019 1020 preempt_disable(); 1021 1022 sample.jiffies = jiffies; 1023 sample.cycles = random_get_entropy(); 1024 sample.num = num; 1025 r = &input_pool; 1026 mix_pool_bytes(r, &sample, sizeof(sample)); 1027 1028 /* 1029 * Calculate number of bits of randomness we probably added. 1030 * We take into account the first, second and third-order deltas 1031 * in order to make our estimate. 1032 */ 1033 1034 if (!state->dont_count_entropy) { 1035 delta = sample.jiffies - state->last_time; 1036 state->last_time = sample.jiffies; 1037 1038 delta2 = delta - state->last_delta; 1039 state->last_delta = delta; 1040 1041 delta3 = delta2 - state->last_delta2; 1042 state->last_delta2 = delta2; 1043 1044 if (delta < 0) 1045 delta = -delta; 1046 if (delta2 < 0) 1047 delta2 = -delta2; 1048 if (delta3 < 0) 1049 delta3 = -delta3; 1050 if (delta > delta2) 1051 delta = delta2; 1052 if (delta > delta3) 1053 delta = delta3; 1054 1055 /* 1056 * delta is now minimum absolute delta. 1057 * Round down by 1 bit on general principles, 1058 * and limit entropy entimate to 12 bits. 1059 */ 1060 credit_entropy_bits(r, min_t(int, fls(delta>>1), 11)); 1061 } 1062 preempt_enable(); 1063 } 1064 1065 void add_input_randomness(unsigned int type, unsigned int code, 1066 unsigned int value) 1067 { 1068 static unsigned char last_value; 1069 1070 /* ignore autorepeat and the like */ 1071 if (value == last_value) 1072 return; 1073 1074 last_value = value; 1075 add_timer_randomness(&input_timer_state, 1076 (type << 4) ^ code ^ (code >> 4) ^ value); 1077 trace_add_input_randomness(ENTROPY_BITS(&input_pool)); 1078 } 1079 EXPORT_SYMBOL_GPL(add_input_randomness); 1080 1081 static DEFINE_PER_CPU(struct fast_pool, irq_randomness); 1082 1083 #ifdef ADD_INTERRUPT_BENCH 1084 static unsigned long avg_cycles, avg_deviation; 1085 1086 #define AVG_SHIFT 8 /* Exponential average factor k=1/256 */ 1087 #define FIXED_1_2 (1 << (AVG_SHIFT-1)) 1088 1089 static void add_interrupt_bench(cycles_t start) 1090 { 1091 long delta = random_get_entropy() - start; 1092 1093 /* Use a weighted moving average */ 1094 delta = delta - ((avg_cycles + FIXED_1_2) >> AVG_SHIFT); 1095 avg_cycles += delta; 1096 /* And average deviation */ 1097 delta = abs(delta) - ((avg_deviation + FIXED_1_2) >> AVG_SHIFT); 1098 avg_deviation += delta; 1099 } 1100 #else 1101 #define add_interrupt_bench(x) 1102 #endif 1103 1104 static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs) 1105 { 1106 __u32 *ptr = (__u32 *) regs; 1107 unsigned int idx; 1108 1109 if (regs == NULL) 1110 return 0; 1111 idx = READ_ONCE(f->reg_idx); 1112 if (idx >= sizeof(struct pt_regs) / sizeof(__u32)) 1113 idx = 0; 1114 ptr += idx++; 1115 WRITE_ONCE(f->reg_idx, idx); 1116 return *ptr; 1117 } 1118 1119 void add_interrupt_randomness(int irq, int irq_flags) 1120 { 1121 struct entropy_store *r; 1122 struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness); 1123 struct pt_regs *regs = get_irq_regs(); 1124 unsigned long now = jiffies; 1125 cycles_t cycles = random_get_entropy(); 1126 __u32 c_high, j_high; 1127 __u64 ip; 1128 unsigned long seed; 1129 int credit = 0; 1130 1131 if (cycles == 0) 1132 cycles = get_reg(fast_pool, regs); 1133 c_high = (sizeof(cycles) > 4) ? cycles >> 32 : 0; 1134 j_high = (sizeof(now) > 4) ? now >> 32 : 0; 1135 fast_pool->pool[0] ^= cycles ^ j_high ^ irq; 1136 fast_pool->pool[1] ^= now ^ c_high; 1137 ip = regs ? instruction_pointer(regs) : _RET_IP_; 1138 fast_pool->pool[2] ^= ip; 1139 fast_pool->pool[3] ^= (sizeof(ip) > 4) ? ip >> 32 : 1140 get_reg(fast_pool, regs); 1141 1142 fast_mix(fast_pool); 1143 add_interrupt_bench(cycles); 1144 1145 if (!crng_ready()) { 1146 if ((fast_pool->count >= 64) && 1147 crng_fast_load((char *) fast_pool->pool, 1148 sizeof(fast_pool->pool))) { 1149 fast_pool->count = 0; 1150 fast_pool->last = now; 1151 } 1152 return; 1153 } 1154 1155 if ((fast_pool->count < 64) && 1156 !time_after(now, fast_pool->last + HZ)) 1157 return; 1158 1159 r = &input_pool; 1160 if (!spin_trylock(&r->lock)) 1161 return; 1162 1163 fast_pool->last = now; 1164 __mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool)); 1165 1166 /* 1167 * If we have architectural seed generator, produce a seed and 1168 * add it to the pool. For the sake of paranoia don't let the 1169 * architectural seed generator dominate the input from the 1170 * interrupt noise. 1171 */ 1172 if (arch_get_random_seed_long(&seed)) { 1173 __mix_pool_bytes(r, &seed, sizeof(seed)); 1174 credit = 1; 1175 } 1176 spin_unlock(&r->lock); 1177 1178 fast_pool->count = 0; 1179 1180 /* award one bit for the contents of the fast pool */ 1181 credit_entropy_bits(r, credit + 1); 1182 } 1183 EXPORT_SYMBOL_GPL(add_interrupt_randomness); 1184 1185 #ifdef CONFIG_BLOCK 1186 void add_disk_randomness(struct gendisk *disk) 1187 { 1188 if (!disk || !disk->random) 1189 return; 1190 /* first major is 1, so we get >= 0x200 here */ 1191 add_timer_randomness(disk->random, 0x100 + disk_devt(disk)); 1192 trace_add_disk_randomness(disk_devt(disk), ENTROPY_BITS(&input_pool)); 1193 } 1194 EXPORT_SYMBOL_GPL(add_disk_randomness); 1195 #endif 1196 1197 /********************************************************************* 1198 * 1199 * Entropy extraction routines 1200 * 1201 *********************************************************************/ 1202 1203 /* 1204 * This utility inline function is responsible for transferring entropy 1205 * from the primary pool to the secondary extraction pool. We make 1206 * sure we pull enough for a 'catastrophic reseed'. 1207 */ 1208 static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes); 1209 static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) 1210 { 1211 if (!r->pull || 1212 r->entropy_count >= (nbytes << (ENTROPY_SHIFT + 3)) || 1213 r->entropy_count > r->poolinfo->poolfracbits) 1214 return; 1215 1216 _xfer_secondary_pool(r, nbytes); 1217 } 1218 1219 static void _xfer_secondary_pool(struct entropy_store *r, size_t nbytes) 1220 { 1221 __u32 tmp[OUTPUT_POOL_WORDS]; 1222 1223 int bytes = nbytes; 1224 1225 /* pull at least as much as a wakeup */ 1226 bytes = max_t(int, bytes, random_read_wakeup_bits / 8); 1227 /* but never more than the buffer size */ 1228 bytes = min_t(int, bytes, sizeof(tmp)); 1229 1230 trace_xfer_secondary_pool(r->name, bytes * 8, nbytes * 8, 1231 ENTROPY_BITS(r), ENTROPY_BITS(r->pull)); 1232 bytes = extract_entropy(r->pull, tmp, bytes, 1233 random_read_wakeup_bits / 8, 0); 1234 mix_pool_bytes(r, tmp, bytes); 1235 credit_entropy_bits(r, bytes*8); 1236 } 1237 1238 /* 1239 * Used as a workqueue function so that when the input pool is getting 1240 * full, we can "spill over" some entropy to the output pools. That 1241 * way the output pools can store some of the excess entropy instead 1242 * of letting it go to waste. 1243 */ 1244 static void push_to_pool(struct work_struct *work) 1245 { 1246 struct entropy_store *r = container_of(work, struct entropy_store, 1247 push_work); 1248 BUG_ON(!r); 1249 _xfer_secondary_pool(r, random_read_wakeup_bits/8); 1250 trace_push_to_pool(r->name, r->entropy_count >> ENTROPY_SHIFT, 1251 r->pull->entropy_count >> ENTROPY_SHIFT); 1252 } 1253 1254 /* 1255 * This function decides how many bytes to actually take from the 1256 * given pool, and also debits the entropy count accordingly. 1257 */ 1258 static size_t account(struct entropy_store *r, size_t nbytes, int min, 1259 int reserved) 1260 { 1261 int entropy_count, orig, have_bytes; 1262 size_t ibytes, nfrac; 1263 1264 BUG_ON(r->entropy_count > r->poolinfo->poolfracbits); 1265 1266 /* Can we pull enough? */ 1267 retry: 1268 entropy_count = orig = ACCESS_ONCE(r->entropy_count); 1269 ibytes = nbytes; 1270 /* never pull more than available */ 1271 have_bytes = entropy_count >> (ENTROPY_SHIFT + 3); 1272 1273 if ((have_bytes -= reserved) < 0) 1274 have_bytes = 0; 1275 ibytes = min_t(size_t, ibytes, have_bytes); 1276 if (ibytes < min) 1277 ibytes = 0; 1278 1279 if (unlikely(entropy_count < 0)) { 1280 pr_warn("random: negative entropy count: pool %s count %d\n", 1281 r->name, entropy_count); 1282 WARN_ON(1); 1283 entropy_count = 0; 1284 } 1285 nfrac = ibytes << (ENTROPY_SHIFT + 3); 1286 if ((size_t) entropy_count > nfrac) 1287 entropy_count -= nfrac; 1288 else 1289 entropy_count = 0; 1290 1291 if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig) 1292 goto retry; 1293 1294 trace_debit_entropy(r->name, 8 * ibytes); 1295 if (ibytes && 1296 (r->entropy_count >> ENTROPY_SHIFT) < random_write_wakeup_bits) { 1297 wake_up_interruptible(&random_write_wait); 1298 kill_fasync(&fasync, SIGIO, POLL_OUT); 1299 } 1300 1301 return ibytes; 1302 } 1303 1304 /* 1305 * This function does the actual extraction for extract_entropy and 1306 * extract_entropy_user. 1307 * 1308 * Note: we assume that .poolwords is a multiple of 16 words. 1309 */ 1310 static void extract_buf(struct entropy_store *r, __u8 *out) 1311 { 1312 int i; 1313 union { 1314 __u32 w[5]; 1315 unsigned long l[LONGS(20)]; 1316 } hash; 1317 __u32 workspace[SHA_WORKSPACE_WORDS]; 1318 unsigned long flags; 1319 1320 /* 1321 * If we have an architectural hardware random number 1322 * generator, use it for SHA's initial vector 1323 */ 1324 sha_init(hash.w); 1325 for (i = 0; i < LONGS(20); i++) { 1326 unsigned long v; 1327 if (!arch_get_random_long(&v)) 1328 break; 1329 hash.l[i] = v; 1330 } 1331 1332 /* Generate a hash across the pool, 16 words (512 bits) at a time */ 1333 spin_lock_irqsave(&r->lock, flags); 1334 for (i = 0; i < r->poolinfo->poolwords; i += 16) 1335 sha_transform(hash.w, (__u8 *)(r->pool + i), workspace); 1336 1337 /* 1338 * We mix the hash back into the pool to prevent backtracking 1339 * attacks (where the attacker knows the state of the pool 1340 * plus the current outputs, and attempts to find previous 1341 * ouputs), unless the hash function can be inverted. By 1342 * mixing at least a SHA1 worth of hash data back, we make 1343 * brute-forcing the feedback as hard as brute-forcing the 1344 * hash. 1345 */ 1346 __mix_pool_bytes(r, hash.w, sizeof(hash.w)); 1347 spin_unlock_irqrestore(&r->lock, flags); 1348 1349 memzero_explicit(workspace, sizeof(workspace)); 1350 1351 /* 1352 * In case the hash function has some recognizable output 1353 * pattern, we fold it in half. Thus, we always feed back 1354 * twice as much data as we output. 1355 */ 1356 hash.w[0] ^= hash.w[3]; 1357 hash.w[1] ^= hash.w[4]; 1358 hash.w[2] ^= rol32(hash.w[2], 16); 1359 1360 memcpy(out, &hash, EXTRACT_SIZE); 1361 memzero_explicit(&hash, sizeof(hash)); 1362 } 1363 1364 static ssize_t _extract_entropy(struct entropy_store *r, void *buf, 1365 size_t nbytes, int fips) 1366 { 1367 ssize_t ret = 0, i; 1368 __u8 tmp[EXTRACT_SIZE]; 1369 unsigned long flags; 1370 1371 while (nbytes) { 1372 extract_buf(r, tmp); 1373 1374 if (fips) { 1375 spin_lock_irqsave(&r->lock, flags); 1376 if (!memcmp(tmp, r->last_data, EXTRACT_SIZE)) 1377 panic("Hardware RNG duplicated output!\n"); 1378 memcpy(r->last_data, tmp, EXTRACT_SIZE); 1379 spin_unlock_irqrestore(&r->lock, flags); 1380 } 1381 i = min_t(int, nbytes, EXTRACT_SIZE); 1382 memcpy(buf, tmp, i); 1383 nbytes -= i; 1384 buf += i; 1385 ret += i; 1386 } 1387 1388 /* Wipe data just returned from memory */ 1389 memzero_explicit(tmp, sizeof(tmp)); 1390 1391 return ret; 1392 } 1393 1394 /* 1395 * This function extracts randomness from the "entropy pool", and 1396 * returns it in a buffer. 1397 * 1398 * The min parameter specifies the minimum amount we can pull before 1399 * failing to avoid races that defeat catastrophic reseeding while the 1400 * reserved parameter indicates how much entropy we must leave in the 1401 * pool after each pull to avoid starving other readers. 1402 */ 1403 static ssize_t extract_entropy(struct entropy_store *r, void *buf, 1404 size_t nbytes, int min, int reserved) 1405 { 1406 __u8 tmp[EXTRACT_SIZE]; 1407 unsigned long flags; 1408 1409 /* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */ 1410 if (fips_enabled) { 1411 spin_lock_irqsave(&r->lock, flags); 1412 if (!r->last_data_init) { 1413 r->last_data_init = 1; 1414 spin_unlock_irqrestore(&r->lock, flags); 1415 trace_extract_entropy(r->name, EXTRACT_SIZE, 1416 ENTROPY_BITS(r), _RET_IP_); 1417 xfer_secondary_pool(r, EXTRACT_SIZE); 1418 extract_buf(r, tmp); 1419 spin_lock_irqsave(&r->lock, flags); 1420 memcpy(r->last_data, tmp, EXTRACT_SIZE); 1421 } 1422 spin_unlock_irqrestore(&r->lock, flags); 1423 } 1424 1425 trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); 1426 xfer_secondary_pool(r, nbytes); 1427 nbytes = account(r, nbytes, min, reserved); 1428 1429 return _extract_entropy(r, buf, nbytes, fips_enabled); 1430 } 1431 1432 /* 1433 * This function extracts randomness from the "entropy pool", and 1434 * returns it in a userspace buffer. 1435 */ 1436 static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, 1437 size_t nbytes) 1438 { 1439 ssize_t ret = 0, i; 1440 __u8 tmp[EXTRACT_SIZE]; 1441 int large_request = (nbytes > 256); 1442 1443 trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_); 1444 xfer_secondary_pool(r, nbytes); 1445 nbytes = account(r, nbytes, 0, 0); 1446 1447 while (nbytes) { 1448 if (large_request && need_resched()) { 1449 if (signal_pending(current)) { 1450 if (ret == 0) 1451 ret = -ERESTARTSYS; 1452 break; 1453 } 1454 schedule(); 1455 } 1456 1457 extract_buf(r, tmp); 1458 i = min_t(int, nbytes, EXTRACT_SIZE); 1459 if (copy_to_user(buf, tmp, i)) { 1460 ret = -EFAULT; 1461 break; 1462 } 1463 1464 nbytes -= i; 1465 buf += i; 1466 ret += i; 1467 } 1468 1469 /* Wipe data just returned from memory */ 1470 memzero_explicit(tmp, sizeof(tmp)); 1471 1472 return ret; 1473 } 1474 1475 #define warn_unseeded_randomness(previous) \ 1476 _warn_unseeded_randomness(__func__, (void *) _RET_IP_, (previous)) 1477 1478 static void _warn_unseeded_randomness(const char *func_name, void *caller, 1479 void **previous) 1480 { 1481 #ifdef CONFIG_WARN_ALL_UNSEEDED_RANDOM 1482 const bool print_once = false; 1483 #else 1484 static bool print_once __read_mostly; 1485 #endif 1486 1487 if (print_once || 1488 crng_ready() || 1489 (previous && (caller == READ_ONCE(*previous)))) 1490 return; 1491 WRITE_ONCE(*previous, caller); 1492 #ifndef CONFIG_WARN_ALL_UNSEEDED_RANDOM 1493 print_once = true; 1494 #endif 1495 pr_notice("random: %s called from %pF with crng_init=%d\n", 1496 func_name, caller, crng_init); 1497 } 1498 1499 /* 1500 * This function is the exported kernel interface. It returns some 1501 * number of good random numbers, suitable for key generation, seeding 1502 * TCP sequence numbers, etc. It does not rely on the hardware random 1503 * number generator. For random bytes direct from the hardware RNG 1504 * (when available), use get_random_bytes_arch(). In order to ensure 1505 * that the randomness provided by this function is okay, the function 1506 * wait_for_random_bytes() should be called and return 0 at least once 1507 * at any point prior. 1508 */ 1509 static void _get_random_bytes(void *buf, int nbytes) 1510 { 1511 __u8 tmp[CHACHA20_BLOCK_SIZE]; 1512 1513 trace_get_random_bytes(nbytes, _RET_IP_); 1514 1515 while (nbytes >= CHACHA20_BLOCK_SIZE) { 1516 extract_crng(buf); 1517 buf += CHACHA20_BLOCK_SIZE; 1518 nbytes -= CHACHA20_BLOCK_SIZE; 1519 } 1520 1521 if (nbytes > 0) { 1522 extract_crng(tmp); 1523 memcpy(buf, tmp, nbytes); 1524 crng_backtrack_protect(tmp, nbytes); 1525 } else 1526 crng_backtrack_protect(tmp, CHACHA20_BLOCK_SIZE); 1527 memzero_explicit(tmp, sizeof(tmp)); 1528 } 1529 1530 void get_random_bytes(void *buf, int nbytes) 1531 { 1532 static void *previous; 1533 1534 warn_unseeded_randomness(&previous); 1535 _get_random_bytes(buf, nbytes); 1536 } 1537 EXPORT_SYMBOL(get_random_bytes); 1538 1539 /* 1540 * Wait for the urandom pool to be seeded and thus guaranteed to supply 1541 * cryptographically secure random numbers. This applies to: the /dev/urandom 1542 * device, the get_random_bytes function, and the get_random_{u32,u64,int,long} 1543 * family of functions. Using any of these functions without first calling 1544 * this function forfeits the guarantee of security. 1545 * 1546 * Returns: 0 if the urandom pool has been seeded. 1547 * -ERESTARTSYS if the function was interrupted by a signal. 1548 */ 1549 int wait_for_random_bytes(void) 1550 { 1551 if (likely(crng_ready())) 1552 return 0; 1553 return wait_event_interruptible(crng_init_wait, crng_ready()); 1554 } 1555 EXPORT_SYMBOL(wait_for_random_bytes); 1556 1557 /* 1558 * Add a callback function that will be invoked when the nonblocking 1559 * pool is initialised. 1560 * 1561 * returns: 0 if callback is successfully added 1562 * -EALREADY if pool is already initialised (callback not called) 1563 * -ENOENT if module for callback is not alive 1564 */ 1565 int add_random_ready_callback(struct random_ready_callback *rdy) 1566 { 1567 struct module *owner; 1568 unsigned long flags; 1569 int err = -EALREADY; 1570 1571 if (crng_ready()) 1572 return err; 1573 1574 owner = rdy->owner; 1575 if (!try_module_get(owner)) 1576 return -ENOENT; 1577 1578 spin_lock_irqsave(&random_ready_list_lock, flags); 1579 if (crng_ready()) 1580 goto out; 1581 1582 owner = NULL; 1583 1584 list_add(&rdy->list, &random_ready_list); 1585 err = 0; 1586 1587 out: 1588 spin_unlock_irqrestore(&random_ready_list_lock, flags); 1589 1590 module_put(owner); 1591 1592 return err; 1593 } 1594 EXPORT_SYMBOL(add_random_ready_callback); 1595 1596 /* 1597 * Delete a previously registered readiness callback function. 1598 */ 1599 void del_random_ready_callback(struct random_ready_callback *rdy) 1600 { 1601 unsigned long flags; 1602 struct module *owner = NULL; 1603 1604 spin_lock_irqsave(&random_ready_list_lock, flags); 1605 if (!list_empty(&rdy->list)) { 1606 list_del_init(&rdy->list); 1607 owner = rdy->owner; 1608 } 1609 spin_unlock_irqrestore(&random_ready_list_lock, flags); 1610 1611 module_put(owner); 1612 } 1613 EXPORT_SYMBOL(del_random_ready_callback); 1614 1615 /* 1616 * This function will use the architecture-specific hardware random 1617 * number generator if it is available. The arch-specific hw RNG will 1618 * almost certainly be faster than what we can do in software, but it 1619 * is impossible to verify that it is implemented securely (as 1620 * opposed, to, say, the AES encryption of a sequence number using a 1621 * key known by the NSA). So it's useful if we need the speed, but 1622 * only if we're willing to trust the hardware manufacturer not to 1623 * have put in a back door. 1624 */ 1625 void get_random_bytes_arch(void *buf, int nbytes) 1626 { 1627 char *p = buf; 1628 1629 trace_get_random_bytes_arch(nbytes, _RET_IP_); 1630 while (nbytes) { 1631 unsigned long v; 1632 int chunk = min(nbytes, (int)sizeof(unsigned long)); 1633 1634 if (!arch_get_random_long(&v)) 1635 break; 1636 1637 memcpy(p, &v, chunk); 1638 p += chunk; 1639 nbytes -= chunk; 1640 } 1641 1642 if (nbytes) 1643 get_random_bytes(p, nbytes); 1644 } 1645 EXPORT_SYMBOL(get_random_bytes_arch); 1646 1647 1648 /* 1649 * init_std_data - initialize pool with system data 1650 * 1651 * @r: pool to initialize 1652 * 1653 * This function clears the pool's entropy count and mixes some system 1654 * data into the pool to prepare it for use. The pool is not cleared 1655 * as that can only decrease the entropy in the pool. 1656 */ 1657 static void init_std_data(struct entropy_store *r) 1658 { 1659 int i; 1660 ktime_t now = ktime_get_real(); 1661 unsigned long rv; 1662 1663 r->last_pulled = jiffies; 1664 mix_pool_bytes(r, &now, sizeof(now)); 1665 for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { 1666 if (!arch_get_random_seed_long(&rv) && 1667 !arch_get_random_long(&rv)) 1668 rv = random_get_entropy(); 1669 mix_pool_bytes(r, &rv, sizeof(rv)); 1670 } 1671 mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); 1672 } 1673 1674 /* 1675 * Note that setup_arch() may call add_device_randomness() 1676 * long before we get here. This allows seeding of the pools 1677 * with some platform dependent data very early in the boot 1678 * process. But it limits our options here. We must use 1679 * statically allocated structures that already have all 1680 * initializations complete at compile time. We should also 1681 * take care not to overwrite the precious per platform data 1682 * we were given. 1683 */ 1684 static int rand_initialize(void) 1685 { 1686 #ifdef CONFIG_NUMA 1687 int i; 1688 struct crng_state *crng; 1689 struct crng_state **pool; 1690 #endif 1691 1692 init_std_data(&input_pool); 1693 init_std_data(&blocking_pool); 1694 crng_initialize(&primary_crng); 1695 1696 #ifdef CONFIG_NUMA 1697 pool = kcalloc(nr_node_ids, sizeof(*pool), GFP_KERNEL|__GFP_NOFAIL); 1698 for_each_online_node(i) { 1699 crng = kmalloc_node(sizeof(struct crng_state), 1700 GFP_KERNEL | __GFP_NOFAIL, i); 1701 spin_lock_init(&crng->lock); 1702 crng_initialize(crng); 1703 pool[i] = crng; 1704 } 1705 mb(); 1706 crng_node_pool = pool; 1707 #endif 1708 return 0; 1709 } 1710 early_initcall(rand_initialize); 1711 1712 #ifdef CONFIG_BLOCK 1713 void rand_initialize_disk(struct gendisk *disk) 1714 { 1715 struct timer_rand_state *state; 1716 1717 /* 1718 * If kzalloc returns null, we just won't use that entropy 1719 * source. 1720 */ 1721 state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL); 1722 if (state) { 1723 state->last_time = INITIAL_JIFFIES; 1724 disk->random = state; 1725 } 1726 } 1727 #endif 1728 1729 static ssize_t 1730 _random_read(int nonblock, char __user *buf, size_t nbytes) 1731 { 1732 ssize_t n; 1733 1734 if (nbytes == 0) 1735 return 0; 1736 1737 nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE); 1738 while (1) { 1739 n = extract_entropy_user(&blocking_pool, buf, nbytes); 1740 if (n < 0) 1741 return n; 1742 trace_random_read(n*8, (nbytes-n)*8, 1743 ENTROPY_BITS(&blocking_pool), 1744 ENTROPY_BITS(&input_pool)); 1745 if (n > 0) 1746 return n; 1747 1748 /* Pool is (near) empty. Maybe wait and retry. */ 1749 if (nonblock) 1750 return -EAGAIN; 1751 1752 wait_event_interruptible(random_read_wait, 1753 ENTROPY_BITS(&input_pool) >= 1754 random_read_wakeup_bits); 1755 if (signal_pending(current)) 1756 return -ERESTARTSYS; 1757 } 1758 } 1759 1760 static ssize_t 1761 random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) 1762 { 1763 return _random_read(file->f_flags & O_NONBLOCK, buf, nbytes); 1764 } 1765 1766 static ssize_t 1767 urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) 1768 { 1769 unsigned long flags; 1770 static int maxwarn = 10; 1771 int ret; 1772 1773 if (!crng_ready() && maxwarn > 0) { 1774 maxwarn--; 1775 printk(KERN_NOTICE "random: %s: uninitialized urandom read " 1776 "(%zd bytes read)\n", 1777 current->comm, nbytes); 1778 spin_lock_irqsave(&primary_crng.lock, flags); 1779 crng_init_cnt = 0; 1780 spin_unlock_irqrestore(&primary_crng.lock, flags); 1781 } 1782 nbytes = min_t(size_t, nbytes, INT_MAX >> (ENTROPY_SHIFT + 3)); 1783 ret = extract_crng_user(buf, nbytes); 1784 trace_urandom_read(8 * nbytes, 0, ENTROPY_BITS(&input_pool)); 1785 return ret; 1786 } 1787 1788 static unsigned int 1789 random_poll(struct file *file, poll_table * wait) 1790 { 1791 unsigned int mask; 1792 1793 poll_wait(file, &random_read_wait, wait); 1794 poll_wait(file, &random_write_wait, wait); 1795 mask = 0; 1796 if (ENTROPY_BITS(&input_pool) >= random_read_wakeup_bits) 1797 mask |= POLLIN | POLLRDNORM; 1798 if (ENTROPY_BITS(&input_pool) < random_write_wakeup_bits) 1799 mask |= POLLOUT | POLLWRNORM; 1800 return mask; 1801 } 1802 1803 static int 1804 write_pool(struct entropy_store *r, const char __user *buffer, size_t count) 1805 { 1806 size_t bytes; 1807 __u32 buf[16]; 1808 const char __user *p = buffer; 1809 1810 while (count > 0) { 1811 bytes = min(count, sizeof(buf)); 1812 if (copy_from_user(&buf, p, bytes)) 1813 return -EFAULT; 1814 1815 count -= bytes; 1816 p += bytes; 1817 1818 mix_pool_bytes(r, buf, bytes); 1819 cond_resched(); 1820 } 1821 1822 return 0; 1823 } 1824 1825 static ssize_t random_write(struct file *file, const char __user *buffer, 1826 size_t count, loff_t *ppos) 1827 { 1828 size_t ret; 1829 1830 ret = write_pool(&input_pool, buffer, count); 1831 if (ret) 1832 return ret; 1833 1834 return (ssize_t)count; 1835 } 1836 1837 static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) 1838 { 1839 int size, ent_count; 1840 int __user *p = (int __user *)arg; 1841 int retval; 1842 1843 switch (cmd) { 1844 case RNDGETENTCNT: 1845 /* inherently racy, no point locking */ 1846 ent_count = ENTROPY_BITS(&input_pool); 1847 if (put_user(ent_count, p)) 1848 return -EFAULT; 1849 return 0; 1850 case RNDADDTOENTCNT: 1851 if (!capable(CAP_SYS_ADMIN)) 1852 return -EPERM; 1853 if (get_user(ent_count, p)) 1854 return -EFAULT; 1855 return credit_entropy_bits_safe(&input_pool, ent_count); 1856 case RNDADDENTROPY: 1857 if (!capable(CAP_SYS_ADMIN)) 1858 return -EPERM; 1859 if (get_user(ent_count, p++)) 1860 return -EFAULT; 1861 if (ent_count < 0) 1862 return -EINVAL; 1863 if (get_user(size, p++)) 1864 return -EFAULT; 1865 retval = write_pool(&input_pool, (const char __user *)p, 1866 size); 1867 if (retval < 0) 1868 return retval; 1869 return credit_entropy_bits_safe(&input_pool, ent_count); 1870 case RNDZAPENTCNT: 1871 case RNDCLEARPOOL: 1872 /* 1873 * Clear the entropy pool counters. We no longer clear 1874 * the entropy pool, as that's silly. 1875 */ 1876 if (!capable(CAP_SYS_ADMIN)) 1877 return -EPERM; 1878 input_pool.entropy_count = 0; 1879 blocking_pool.entropy_count = 0; 1880 return 0; 1881 default: 1882 return -EINVAL; 1883 } 1884 } 1885 1886 static int random_fasync(int fd, struct file *filp, int on) 1887 { 1888 return fasync_helper(fd, filp, on, &fasync); 1889 } 1890 1891 const struct file_operations random_fops = { 1892 .read = random_read, 1893 .write = random_write, 1894 .poll = random_poll, 1895 .unlocked_ioctl = random_ioctl, 1896 .fasync = random_fasync, 1897 .llseek = noop_llseek, 1898 }; 1899 1900 const struct file_operations urandom_fops = { 1901 .read = urandom_read, 1902 .write = random_write, 1903 .unlocked_ioctl = random_ioctl, 1904 .fasync = random_fasync, 1905 .llseek = noop_llseek, 1906 }; 1907 1908 SYSCALL_DEFINE3(getrandom, char __user *, buf, size_t, count, 1909 unsigned int, flags) 1910 { 1911 int ret; 1912 1913 if (flags & ~(GRND_NONBLOCK|GRND_RANDOM)) 1914 return -EINVAL; 1915 1916 if (count > INT_MAX) 1917 count = INT_MAX; 1918 1919 if (flags & GRND_RANDOM) 1920 return _random_read(flags & GRND_NONBLOCK, buf, count); 1921 1922 if (!crng_ready()) { 1923 if (flags & GRND_NONBLOCK) 1924 return -EAGAIN; 1925 ret = wait_for_random_bytes(); 1926 if (unlikely(ret)) 1927 return ret; 1928 } 1929 return urandom_read(NULL, buf, count, NULL); 1930 } 1931 1932 /******************************************************************** 1933 * 1934 * Sysctl interface 1935 * 1936 ********************************************************************/ 1937 1938 #ifdef CONFIG_SYSCTL 1939 1940 #include <linux/sysctl.h> 1941 1942 static int min_read_thresh = 8, min_write_thresh; 1943 static int max_read_thresh = OUTPUT_POOL_WORDS * 32; 1944 static int max_write_thresh = INPUT_POOL_WORDS * 32; 1945 static int random_min_urandom_seed = 60; 1946 static char sysctl_bootid[16]; 1947 1948 /* 1949 * This function is used to return both the bootid UUID, and random 1950 * UUID. The difference is in whether table->data is NULL; if it is, 1951 * then a new UUID is generated and returned to the user. 1952 * 1953 * If the user accesses this via the proc interface, the UUID will be 1954 * returned as an ASCII string in the standard UUID format; if via the 1955 * sysctl system call, as 16 bytes of binary data. 1956 */ 1957 static int proc_do_uuid(struct ctl_table *table, int write, 1958 void __user *buffer, size_t *lenp, loff_t *ppos) 1959 { 1960 struct ctl_table fake_table; 1961 unsigned char buf[64], tmp_uuid[16], *uuid; 1962 1963 uuid = table->data; 1964 if (!uuid) { 1965 uuid = tmp_uuid; 1966 generate_random_uuid(uuid); 1967 } else { 1968 static DEFINE_SPINLOCK(bootid_spinlock); 1969 1970 spin_lock(&bootid_spinlock); 1971 if (!uuid[8]) 1972 generate_random_uuid(uuid); 1973 spin_unlock(&bootid_spinlock); 1974 } 1975 1976 sprintf(buf, "%pU", uuid); 1977 1978 fake_table.data = buf; 1979 fake_table.maxlen = sizeof(buf); 1980 1981 return proc_dostring(&fake_table, write, buffer, lenp, ppos); 1982 } 1983 1984 /* 1985 * Return entropy available scaled to integral bits 1986 */ 1987 static int proc_do_entropy(struct ctl_table *table, int write, 1988 void __user *buffer, size_t *lenp, loff_t *ppos) 1989 { 1990 struct ctl_table fake_table; 1991 int entropy_count; 1992 1993 entropy_count = *(int *)table->data >> ENTROPY_SHIFT; 1994 1995 fake_table.data = &entropy_count; 1996 fake_table.maxlen = sizeof(entropy_count); 1997 1998 return proc_dointvec(&fake_table, write, buffer, lenp, ppos); 1999 } 2000 2001 static int sysctl_poolsize = INPUT_POOL_WORDS * 32; 2002 extern struct ctl_table random_table[]; 2003 struct ctl_table random_table[] = { 2004 { 2005 .procname = "poolsize", 2006 .data = &sysctl_poolsize, 2007 .maxlen = sizeof(int), 2008 .mode = 0444, 2009 .proc_handler = proc_dointvec, 2010 }, 2011 { 2012 .procname = "entropy_avail", 2013 .maxlen = sizeof(int), 2014 .mode = 0444, 2015 .proc_handler = proc_do_entropy, 2016 .data = &input_pool.entropy_count, 2017 }, 2018 { 2019 .procname = "read_wakeup_threshold", 2020 .data = &random_read_wakeup_bits, 2021 .maxlen = sizeof(int), 2022 .mode = 0644, 2023 .proc_handler = proc_dointvec_minmax, 2024 .extra1 = &min_read_thresh, 2025 .extra2 = &max_read_thresh, 2026 }, 2027 { 2028 .procname = "write_wakeup_threshold", 2029 .data = &random_write_wakeup_bits, 2030 .maxlen = sizeof(int), 2031 .mode = 0644, 2032 .proc_handler = proc_dointvec_minmax, 2033 .extra1 = &min_write_thresh, 2034 .extra2 = &max_write_thresh, 2035 }, 2036 { 2037 .procname = "urandom_min_reseed_secs", 2038 .data = &random_min_urandom_seed, 2039 .maxlen = sizeof(int), 2040 .mode = 0644, 2041 .proc_handler = proc_dointvec, 2042 }, 2043 { 2044 .procname = "boot_id", 2045 .data = &sysctl_bootid, 2046 .maxlen = 16, 2047 .mode = 0444, 2048 .proc_handler = proc_do_uuid, 2049 }, 2050 { 2051 .procname = "uuid", 2052 .maxlen = 16, 2053 .mode = 0444, 2054 .proc_handler = proc_do_uuid, 2055 }, 2056 #ifdef ADD_INTERRUPT_BENCH 2057 { 2058 .procname = "add_interrupt_avg_cycles", 2059 .data = &avg_cycles, 2060 .maxlen = sizeof(avg_cycles), 2061 .mode = 0444, 2062 .proc_handler = proc_doulongvec_minmax, 2063 }, 2064 { 2065 .procname = "add_interrupt_avg_deviation", 2066 .data = &avg_deviation, 2067 .maxlen = sizeof(avg_deviation), 2068 .mode = 0444, 2069 .proc_handler = proc_doulongvec_minmax, 2070 }, 2071 #endif 2072 { } 2073 }; 2074 #endif /* CONFIG_SYSCTL */ 2075 2076 struct batched_entropy { 2077 union { 2078 u64 entropy_u64[CHACHA20_BLOCK_SIZE / sizeof(u64)]; 2079 u32 entropy_u32[CHACHA20_BLOCK_SIZE / sizeof(u32)]; 2080 }; 2081 unsigned int position; 2082 }; 2083 static rwlock_t batched_entropy_reset_lock = __RW_LOCK_UNLOCKED(batched_entropy_reset_lock); 2084 2085 /* 2086 * Get a random word for internal kernel use only. The quality of the random 2087 * number is either as good as RDRAND or as good as /dev/urandom, with the 2088 * goal of being quite fast and not depleting entropy. In order to ensure 2089 * that the randomness provided by this function is okay, the function 2090 * wait_for_random_bytes() should be called and return 0 at least once 2091 * at any point prior. 2092 */ 2093 static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64); 2094 u64 get_random_u64(void) 2095 { 2096 u64 ret; 2097 bool use_lock; 2098 unsigned long flags = 0; 2099 struct batched_entropy *batch; 2100 static void *previous; 2101 2102 #if BITS_PER_LONG == 64 2103 if (arch_get_random_long((unsigned long *)&ret)) 2104 return ret; 2105 #else 2106 if (arch_get_random_long((unsigned long *)&ret) && 2107 arch_get_random_long((unsigned long *)&ret + 1)) 2108 return ret; 2109 #endif 2110 2111 warn_unseeded_randomness(&previous); 2112 2113 use_lock = READ_ONCE(crng_init) < 2; 2114 batch = &get_cpu_var(batched_entropy_u64); 2115 if (use_lock) 2116 read_lock_irqsave(&batched_entropy_reset_lock, flags); 2117 if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) { 2118 extract_crng((u8 *)batch->entropy_u64); 2119 batch->position = 0; 2120 } 2121 ret = batch->entropy_u64[batch->position++]; 2122 if (use_lock) 2123 read_unlock_irqrestore(&batched_entropy_reset_lock, flags); 2124 put_cpu_var(batched_entropy_u64); 2125 return ret; 2126 } 2127 EXPORT_SYMBOL(get_random_u64); 2128 2129 static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32); 2130 u32 get_random_u32(void) 2131 { 2132 u32 ret; 2133 bool use_lock; 2134 unsigned long flags = 0; 2135 struct batched_entropy *batch; 2136 static void *previous; 2137 2138 if (arch_get_random_int(&ret)) 2139 return ret; 2140 2141 warn_unseeded_randomness(&previous); 2142 2143 use_lock = READ_ONCE(crng_init) < 2; 2144 batch = &get_cpu_var(batched_entropy_u32); 2145 if (use_lock) 2146 read_lock_irqsave(&batched_entropy_reset_lock, flags); 2147 if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) { 2148 extract_crng((u8 *)batch->entropy_u32); 2149 batch->position = 0; 2150 } 2151 ret = batch->entropy_u32[batch->position++]; 2152 if (use_lock) 2153 read_unlock_irqrestore(&batched_entropy_reset_lock, flags); 2154 put_cpu_var(batched_entropy_u32); 2155 return ret; 2156 } 2157 EXPORT_SYMBOL(get_random_u32); 2158 2159 /* It's important to invalidate all potential batched entropy that might 2160 * be stored before the crng is initialized, which we can do lazily by 2161 * simply resetting the counter to zero so that it's re-extracted on the 2162 * next usage. */ 2163 static void invalidate_batched_entropy(void) 2164 { 2165 int cpu; 2166 unsigned long flags; 2167 2168 write_lock_irqsave(&batched_entropy_reset_lock, flags); 2169 for_each_possible_cpu (cpu) { 2170 per_cpu_ptr(&batched_entropy_u32, cpu)->position = 0; 2171 per_cpu_ptr(&batched_entropy_u64, cpu)->position = 0; 2172 } 2173 write_unlock_irqrestore(&batched_entropy_reset_lock, flags); 2174 } 2175 2176 /** 2177 * randomize_page - Generate a random, page aligned address 2178 * @start: The smallest acceptable address the caller will take. 2179 * @range: The size of the area, starting at @start, within which the 2180 * random address must fall. 2181 * 2182 * If @start + @range would overflow, @range is capped. 2183 * 2184 * NOTE: Historical use of randomize_range, which this replaces, presumed that 2185 * @start was already page aligned. We now align it regardless. 2186 * 2187 * Return: A page aligned address within [start, start + range). On error, 2188 * @start is returned. 2189 */ 2190 unsigned long 2191 randomize_page(unsigned long start, unsigned long range) 2192 { 2193 if (!PAGE_ALIGNED(start)) { 2194 range -= PAGE_ALIGN(start) - start; 2195 start = PAGE_ALIGN(start); 2196 } 2197 2198 if (start > ULONG_MAX - range) 2199 range = ULONG_MAX - start; 2200 2201 range >>= PAGE_SHIFT; 2202 2203 if (range == 0) 2204 return start; 2205 2206 return start + (get_random_long() % range << PAGE_SHIFT); 2207 } 2208 2209 /* Interface for in-kernel drivers of true hardware RNGs. 2210 * Those devices may produce endless random bits and will be throttled 2211 * when our pool is full. 2212 */ 2213 void add_hwgenerator_randomness(const char *buffer, size_t count, 2214 size_t entropy) 2215 { 2216 struct entropy_store *poolp = &input_pool; 2217 2218 if (!crng_ready()) { 2219 crng_fast_load(buffer, count); 2220 return; 2221 } 2222 2223 /* Suspend writing if we're above the trickle threshold. 2224 * We'll be woken up again once below random_write_wakeup_thresh, 2225 * or when the calling thread is about to terminate. 2226 */ 2227 wait_event_interruptible(random_write_wait, kthread_should_stop() || 2228 ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits); 2229 mix_pool_bytes(poolp, buffer, count); 2230 credit_entropy_bits(poolp, entropy); 2231 } 2232 EXPORT_SYMBOL_GPL(add_hwgenerator_randomness); 2233