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