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