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