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