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