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_input_randomness(unsigned int type, unsigned int code, 129 * unsigned int value); 130 * void add_interrupt_randomness(int irq); 131 * 132 * add_input_randomness() uses the input layer interrupt timing, as well as 133 * the event type information from the hardware. 134 * 135 * add_interrupt_randomness() uses the inter-interrupt timing as random 136 * inputs to the entropy pool. Note that not all interrupts are good 137 * sources of randomness! For example, the timer interrupts is not a 138 * good choice, because the periodicity of the interrupts is too 139 * regular, and hence predictable to an attacker. Disk interrupts are 140 * a better measure, since the timing of the disk interrupts are more 141 * unpredictable. 142 * 143 * All of these routines try to estimate how many bits of randomness a 144 * particular randomness source. They do this by keeping track of the 145 * first and second order deltas of the event timings. 146 * 147 * Ensuring unpredictability at system startup 148 * ============================================ 149 * 150 * When any operating system starts up, it will go through a sequence 151 * of actions that are fairly predictable by an adversary, especially 152 * if the start-up does not involve interaction with a human operator. 153 * This reduces the actual number of bits of unpredictability in the 154 * entropy pool below the value in entropy_count. In order to 155 * counteract this effect, it helps to carry information in the 156 * entropy pool across shut-downs and start-ups. To do this, put the 157 * following lines an appropriate script which is run during the boot 158 * sequence: 159 * 160 * echo "Initializing random number generator..." 161 * random_seed=/var/run/random-seed 162 * # Carry a random seed from start-up to start-up 163 * # Load and then save the whole entropy pool 164 * if [ -f $random_seed ]; then 165 * cat $random_seed >/dev/urandom 166 * else 167 * touch $random_seed 168 * fi 169 * chmod 600 $random_seed 170 * dd if=/dev/urandom of=$random_seed count=1 bs=512 171 * 172 * and the following lines in an appropriate script which is run as 173 * the system is shutdown: 174 * 175 * # Carry a random seed from shut-down to start-up 176 * # Save the whole entropy pool 177 * echo "Saving random seed..." 178 * random_seed=/var/run/random-seed 179 * touch $random_seed 180 * chmod 600 $random_seed 181 * dd if=/dev/urandom of=$random_seed count=1 bs=512 182 * 183 * For example, on most modern systems using the System V init 184 * scripts, such code fragments would be found in 185 * /etc/rc.d/init.d/random. On older Linux systems, the correct script 186 * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0. 187 * 188 * Effectively, these commands cause the contents of the entropy pool 189 * to be saved at shut-down time and reloaded into the entropy pool at 190 * start-up. (The 'dd' in the addition to the bootup script is to 191 * make sure that /etc/random-seed is different for every start-up, 192 * even if the system crashes without executing rc.0.) Even with 193 * complete knowledge of the start-up activities, predicting the state 194 * of the entropy pool requires knowledge of the previous history of 195 * the system. 196 * 197 * Configuring the /dev/random driver under Linux 198 * ============================================== 199 * 200 * The /dev/random driver under Linux uses minor numbers 8 and 9 of 201 * the /dev/mem major number (#1). So if your system does not have 202 * /dev/random and /dev/urandom created already, they can be created 203 * by using the commands: 204 * 205 * mknod /dev/random c 1 8 206 * mknod /dev/urandom c 1 9 207 * 208 * Acknowledgements: 209 * ================= 210 * 211 * Ideas for constructing this random number generator were derived 212 * from Pretty Good Privacy's random number generator, and from private 213 * discussions with Phil Karn. Colin Plumb provided a faster random 214 * number generator, which speed up the mixing function of the entropy 215 * pool, taken from PGPfone. Dale Worley has also contributed many 216 * useful ideas and suggestions to improve this driver. 217 * 218 * Any flaws in the design are solely my responsibility, and should 219 * not be attributed to the Phil, Colin, or any of authors of PGP. 220 * 221 * Further background information on this topic may be obtained from 222 * RFC 1750, "Randomness Recommendations for Security", by Donald 223 * Eastlake, Steve Crocker, and Jeff Schiller. 224 */ 225 226#include <linux/utsname.h> 227#include <linux/module.h> 228#include <linux/kernel.h> 229#include <linux/major.h> 230#include <linux/string.h> 231#include <linux/fcntl.h> 232#include <linux/slab.h> 233#include <linux/random.h> 234#include <linux/poll.h> 235#include <linux/init.h> 236#include <linux/fs.h> 237#include <linux/genhd.h> 238#include <linux/interrupt.h> 239#include <linux/mm.h> 240#include <linux/spinlock.h> 241#include <linux/percpu.h> 242#include <linux/cryptohash.h> 243#include <linux/fips.h> 244 245#ifdef CONFIG_GENERIC_HARDIRQS 246# include <linux/irq.h> 247#endif 248 249#include <asm/processor.h> 250#include <asm/uaccess.h> 251#include <asm/irq.h> 252#include <asm/io.h> 253 254/* 255 * Configuration information 256 */ 257#define INPUT_POOL_WORDS 128 258#define OUTPUT_POOL_WORDS 32 259#define SEC_XFER_SIZE 512 260#define EXTRACT_SIZE 10 261 262/* 263 * The minimum number of bits of entropy before we wake up a read on 264 * /dev/random. Should be enough to do a significant reseed. 265 */ 266static int random_read_wakeup_thresh = 64; 267 268/* 269 * If the entropy count falls under this number of bits, then we 270 * should wake up processes which are selecting or polling on write 271 * access to /dev/random. 272 */ 273static int random_write_wakeup_thresh = 128; 274 275/* 276 * When the input pool goes over trickle_thresh, start dropping most 277 * samples to avoid wasting CPU time and reduce lock contention. 278 */ 279 280static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28; 281 282static DEFINE_PER_CPU(int, trickle_count); 283 284/* 285 * A pool of size .poolwords is stirred with a primitive polynomial 286 * of degree .poolwords over GF(2). The taps for various sizes are 287 * defined below. They are chosen to be evenly spaced (minimum RMS 288 * distance from evenly spaced; the numbers in the comments are a 289 * scaled squared error sum) except for the last tap, which is 1 to 290 * get the twisting happening as fast as possible. 291 */ 292static struct poolinfo { 293 int poolwords; 294 int tap1, tap2, tap3, tap4, tap5; 295} poolinfo_table[] = { 296 /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ 297 { 128, 103, 76, 51, 25, 1 }, 298 /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ 299 { 32, 26, 20, 14, 7, 1 }, 300}; 301 302#define POOLBITS poolwords*32 303#define POOLBYTES poolwords*4 304 305/* 306 * For the purposes of better mixing, we use the CRC-32 polynomial as 307 * well to make a twisted Generalized Feedback Shift Reigster 308 * 309 * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM 310 * Transactions on Modeling and Computer Simulation 2(3):179-194. 311 * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators 312 * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) 313 * 314 * Thanks to Colin Plumb for suggesting this. 315 * 316 * We have not analyzed the resultant polynomial to prove it primitive; 317 * in fact it almost certainly isn't. Nonetheless, the irreducible factors 318 * of a random large-degree polynomial over GF(2) are more than large enough 319 * that periodicity is not a concern. 320 * 321 * The input hash is much less sensitive than the output hash. All 322 * that we want of it is that it be a good non-cryptographic hash; 323 * i.e. it not produce collisions when fed "random" data of the sort 324 * we expect to see. As long as the pool state differs for different 325 * inputs, we have preserved the input entropy and done a good job. 326 * The fact that an intelligent attacker can construct inputs that 327 * will produce controlled alterations to the pool's state is not 328 * important because we don't consider such inputs to contribute any 329 * randomness. The only property we need with respect to them is that 330 * the attacker can't increase his/her knowledge of the pool's state. 331 * Since all additions are reversible (knowing the final state and the 332 * input, you can reconstruct the initial state), if an attacker has 333 * any uncertainty about the initial state, he/she can only shuffle 334 * that uncertainty about, but never cause any collisions (which would 335 * decrease the uncertainty). 336 * 337 * The chosen system lets the state of the pool be (essentially) the input 338 * modulo the generator polymnomial. Now, for random primitive polynomials, 339 * this is a universal class of hash functions, meaning that the chance 340 * of a collision is limited by the attacker's knowledge of the generator 341 * polynomail, so if it is chosen at random, an attacker can never force 342 * a collision. Here, we use a fixed polynomial, but we *can* assume that 343 * ###--> it is unknown to the processes generating the input entropy. <-### 344 * Because of this important property, this is a good, collision-resistant 345 * hash; hash collisions will occur no more often than chance. 346 */ 347 348/* 349 * Static global variables 350 */ 351static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); 352static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); 353static struct fasync_struct *fasync; 354 355#define DEBUG_ENT(fmt, arg...) do {} while (0) 356 357/********************************************************************** 358 * 359 * OS independent entropy store. Here are the functions which handle 360 * storing entropy in an entropy pool. 361 * 362 **********************************************************************/ 363 364struct entropy_store; 365struct entropy_store { 366 /* read-only data: */ 367 struct poolinfo *poolinfo; 368 __u32 *pool; 369 const char *name; 370 struct entropy_store *pull; 371 int limit; 372 373 /* read-write data: */ 374 spinlock_t lock; 375 unsigned add_ptr; 376 int entropy_count; 377 int input_rotate; 378 __u8 last_data[EXTRACT_SIZE]; 379}; 380 381static __u32 input_pool_data[INPUT_POOL_WORDS]; 382static __u32 blocking_pool_data[OUTPUT_POOL_WORDS]; 383static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS]; 384 385static struct entropy_store input_pool = { 386 .poolinfo = &poolinfo_table[0], 387 .name = "input", 388 .limit = 1, 389 .lock = __SPIN_LOCK_UNLOCKED(&input_pool.lock), 390 .pool = input_pool_data 391}; 392 393static struct entropy_store blocking_pool = { 394 .poolinfo = &poolinfo_table[1], 395 .name = "blocking", 396 .limit = 1, 397 .pull = &input_pool, 398 .lock = __SPIN_LOCK_UNLOCKED(&blocking_pool.lock), 399 .pool = blocking_pool_data 400}; 401 402static struct entropy_store nonblocking_pool = { 403 .poolinfo = &poolinfo_table[1], 404 .name = "nonblocking", 405 .pull = &input_pool, 406 .lock = __SPIN_LOCK_UNLOCKED(&nonblocking_pool.lock), 407 .pool = nonblocking_pool_data 408}; 409 410/* 411 * This function adds bytes into the entropy "pool". It does not 412 * update the entropy estimate. The caller should call 413 * credit_entropy_bits if this is appropriate. 414 * 415 * The pool is stirred with a primitive polynomial of the appropriate 416 * degree, and then twisted. We twist by three bits at a time because 417 * it's cheap to do so and helps slightly in the expected case where 418 * the entropy is concentrated in the low-order bits. 419 */ 420static void mix_pool_bytes_extract(struct entropy_store *r, const void *in, 421 int nbytes, __u8 out[64]) 422{ 423 static __u32 const twist_table[8] = { 424 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 425 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; 426 unsigned long i, j, tap1, tap2, tap3, tap4, tap5; 427 int input_rotate; 428 int wordmask = r->poolinfo->poolwords - 1; 429 const char *bytes = in; 430 __u32 w; 431 unsigned long flags; 432 433 /* Taps are constant, so we can load them without holding r->lock. */ 434 tap1 = r->poolinfo->tap1; 435 tap2 = r->poolinfo->tap2; 436 tap3 = r->poolinfo->tap3; 437 tap4 = r->poolinfo->tap4; 438 tap5 = r->poolinfo->tap5; 439 440 spin_lock_irqsave(&r->lock, flags); 441 input_rotate = r->input_rotate; 442 i = r->add_ptr; 443 444 /* mix one byte at a time to simplify size handling and churn faster */ 445 while (nbytes--) { 446 w = rol32(*bytes++, input_rotate & 31); 447 i = (i - 1) & wordmask; 448 449 /* XOR in the various taps */ 450 w ^= r->pool[i]; 451 w ^= r->pool[(i + tap1) & wordmask]; 452 w ^= r->pool[(i + tap2) & wordmask]; 453 w ^= r->pool[(i + tap3) & wordmask]; 454 w ^= r->pool[(i + tap4) & wordmask]; 455 w ^= r->pool[(i + tap5) & wordmask]; 456 457 /* Mix the result back in with a twist */ 458 r->pool[i] = (w >> 3) ^ twist_table[w & 7]; 459 460 /* 461 * Normally, we add 7 bits of rotation to the pool. 462 * At the beginning of the pool, add an extra 7 bits 463 * rotation, so that successive passes spread the 464 * input bits across the pool evenly. 465 */ 466 input_rotate += i ? 7 : 14; 467 } 468 469 r->input_rotate = input_rotate; 470 r->add_ptr = i; 471 472 if (out) 473 for (j = 0; j < 16; j++) 474 ((__u32 *)out)[j] = r->pool[(i - j) & wordmask]; 475 476 spin_unlock_irqrestore(&r->lock, flags); 477} 478 479static void mix_pool_bytes(struct entropy_store *r, const void *in, int bytes) 480{ 481 mix_pool_bytes_extract(r, in, bytes, NULL); 482} 483 484/* 485 * Credit (or debit) the entropy store with n bits of entropy 486 */ 487static void credit_entropy_bits(struct entropy_store *r, int nbits) 488{ 489 unsigned long flags; 490 int entropy_count; 491 492 if (!nbits) 493 return; 494 495 spin_lock_irqsave(&r->lock, flags); 496 497 DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name); 498 entropy_count = r->entropy_count; 499 entropy_count += nbits; 500 if (entropy_count < 0) { 501 DEBUG_ENT("negative entropy/overflow\n"); 502 entropy_count = 0; 503 } else if (entropy_count > r->poolinfo->POOLBITS) 504 entropy_count = r->poolinfo->POOLBITS; 505 r->entropy_count = entropy_count; 506 507 /* should we wake readers? */ 508 if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) { 509 wake_up_interruptible(&random_read_wait); 510 kill_fasync(&fasync, SIGIO, POLL_IN); 511 } 512 spin_unlock_irqrestore(&r->lock, flags); 513} 514 515/********************************************************************* 516 * 517 * Entropy input management 518 * 519 *********************************************************************/ 520 521/* There is one of these per entropy source */ 522struct timer_rand_state { 523 cycles_t last_time; 524 long last_delta, last_delta2; 525 unsigned dont_count_entropy:1; 526}; 527 528#ifndef CONFIG_GENERIC_HARDIRQS 529 530static struct timer_rand_state *irq_timer_state[NR_IRQS]; 531 532static struct timer_rand_state *get_timer_rand_state(unsigned int irq) 533{ 534 return irq_timer_state[irq]; 535} 536 537static void set_timer_rand_state(unsigned int irq, 538 struct timer_rand_state *state) 539{ 540 irq_timer_state[irq] = state; 541} 542 543#else 544 545static struct timer_rand_state *get_timer_rand_state(unsigned int irq) 546{ 547 struct irq_desc *desc; 548 549 desc = irq_to_desc(irq); 550 551 return desc->timer_rand_state; 552} 553 554static void set_timer_rand_state(unsigned int irq, 555 struct timer_rand_state *state) 556{ 557 struct irq_desc *desc; 558 559 desc = irq_to_desc(irq); 560 561 desc->timer_rand_state = state; 562} 563#endif 564 565static struct timer_rand_state input_timer_state; 566 567/* 568 * This function adds entropy to the entropy "pool" by using timing 569 * delays. It uses the timer_rand_state structure to make an estimate 570 * of how many bits of entropy this call has added to the pool. 571 * 572 * The number "num" is also added to the pool - it should somehow describe 573 * the type of event which just happened. This is currently 0-255 for 574 * keyboard scan codes, and 256 upwards for interrupts. 575 * 576 */ 577static void add_timer_randomness(struct timer_rand_state *state, unsigned num) 578{ 579 struct { 580 cycles_t cycles; 581 long jiffies; 582 unsigned num; 583 } sample; 584 long delta, delta2, delta3; 585 586 preempt_disable(); 587 /* if over the trickle threshold, use only 1 in 4096 samples */ 588 if (input_pool.entropy_count > trickle_thresh && 589 (__get_cpu_var(trickle_count)++ & 0xfff)) 590 goto out; 591 592 sample.jiffies = jiffies; 593 sample.cycles = get_cycles(); 594 sample.num = num; 595 mix_pool_bytes(&input_pool, &sample, sizeof(sample)); 596 597 /* 598 * Calculate number of bits of randomness we probably added. 599 * We take into account the first, second and third-order deltas 600 * in order to make our estimate. 601 */ 602 603 if (!state->dont_count_entropy) { 604 delta = sample.jiffies - state->last_time; 605 state->last_time = sample.jiffies; 606 607 delta2 = delta - state->last_delta; 608 state->last_delta = delta; 609 610 delta3 = delta2 - state->last_delta2; 611 state->last_delta2 = delta2; 612 613 if (delta < 0) 614 delta = -delta; 615 if (delta2 < 0) 616 delta2 = -delta2; 617 if (delta3 < 0) 618 delta3 = -delta3; 619 if (delta > delta2) 620 delta = delta2; 621 if (delta > delta3) 622 delta = delta3; 623 624 /* 625 * delta is now minimum absolute delta. 626 * Round down by 1 bit on general principles, 627 * and limit entropy entimate to 12 bits. 628 */ 629 credit_entropy_bits(&input_pool, 630 min_t(int, fls(delta>>1), 11)); 631 } 632out: 633 preempt_enable(); 634} 635 636void add_input_randomness(unsigned int type, unsigned int code, 637 unsigned int value) 638{ 639 static unsigned char last_value; 640 641 /* ignore autorepeat and the like */ 642 if (value == last_value) 643 return; 644 645 DEBUG_ENT("input event\n"); 646 last_value = value; 647 add_timer_randomness(&input_timer_state, 648 (type << 4) ^ code ^ (code >> 4) ^ value); 649} 650EXPORT_SYMBOL_GPL(add_input_randomness); 651 652void add_interrupt_randomness(int irq) 653{ 654 struct timer_rand_state *state; 655 656 state = get_timer_rand_state(irq); 657 658 if (state == NULL) 659 return; 660 661 DEBUG_ENT("irq event %d\n", irq); 662 add_timer_randomness(state, 0x100 + irq); 663} 664 665#ifdef CONFIG_BLOCK 666void add_disk_randomness(struct gendisk *disk) 667{ 668 if (!disk || !disk->random) 669 return; 670 /* first major is 1, so we get >= 0x200 here */ 671 DEBUG_ENT("disk event %d:%d\n", 672 MAJOR(disk_devt(disk)), MINOR(disk_devt(disk))); 673 674 add_timer_randomness(disk->random, 0x100 + disk_devt(disk)); 675} 676#endif 677 678/********************************************************************* 679 * 680 * Entropy extraction routines 681 * 682 *********************************************************************/ 683 684static ssize_t extract_entropy(struct entropy_store *r, void *buf, 685 size_t nbytes, int min, int rsvd); 686 687/* 688 * This utility inline function is responsible for transfering entropy 689 * from the primary pool to the secondary extraction pool. We make 690 * sure we pull enough for a 'catastrophic reseed'. 691 */ 692static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) 693{ 694 __u32 tmp[OUTPUT_POOL_WORDS]; 695 696 if (r->pull && r->entropy_count < nbytes * 8 && 697 r->entropy_count < r->poolinfo->POOLBITS) { 698 /* If we're limited, always leave two wakeup worth's BITS */ 699 int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; 700 int bytes = nbytes; 701 702 /* pull at least as many as BYTES as wakeup BITS */ 703 bytes = max_t(int, bytes, random_read_wakeup_thresh / 8); 704 /* but never more than the buffer size */ 705 bytes = min_t(int, bytes, sizeof(tmp)); 706 707 DEBUG_ENT("going to reseed %s with %d bits " 708 "(%d of %d requested)\n", 709 r->name, bytes * 8, nbytes * 8, r->entropy_count); 710 711 bytes = extract_entropy(r->pull, tmp, bytes, 712 random_read_wakeup_thresh / 8, rsvd); 713 mix_pool_bytes(r, tmp, bytes); 714 credit_entropy_bits(r, bytes*8); 715 } 716} 717 718/* 719 * These functions extracts randomness from the "entropy pool", and 720 * returns it in a buffer. 721 * 722 * The min parameter specifies the minimum amount we can pull before 723 * failing to avoid races that defeat catastrophic reseeding while the 724 * reserved parameter indicates how much entropy we must leave in the 725 * pool after each pull to avoid starving other readers. 726 * 727 * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words. 728 */ 729 730static size_t account(struct entropy_store *r, size_t nbytes, int min, 731 int reserved) 732{ 733 unsigned long flags; 734 735 /* Hold lock while accounting */ 736 spin_lock_irqsave(&r->lock, flags); 737 738 BUG_ON(r->entropy_count > r->poolinfo->POOLBITS); 739 DEBUG_ENT("trying to extract %d bits from %s\n", 740 nbytes * 8, r->name); 741 742 /* Can we pull enough? */ 743 if (r->entropy_count / 8 < min + reserved) { 744 nbytes = 0; 745 } else { 746 /* If limited, never pull more than available */ 747 if (r->limit && nbytes + reserved >= r->entropy_count / 8) 748 nbytes = r->entropy_count/8 - reserved; 749 750 if (r->entropy_count / 8 >= nbytes + reserved) 751 r->entropy_count -= nbytes*8; 752 else 753 r->entropy_count = reserved; 754 755 if (r->entropy_count < random_write_wakeup_thresh) { 756 wake_up_interruptible(&random_write_wait); 757 kill_fasync(&fasync, SIGIO, POLL_OUT); 758 } 759 } 760 761 DEBUG_ENT("debiting %d entropy credits from %s%s\n", 762 nbytes * 8, r->name, r->limit ? "" : " (unlimited)"); 763 764 spin_unlock_irqrestore(&r->lock, flags); 765 766 return nbytes; 767} 768 769static void extract_buf(struct entropy_store *r, __u8 *out) 770{ 771 int i; 772 __u32 hash[5], workspace[SHA_WORKSPACE_WORDS]; 773 __u8 extract[64]; 774 775 /* Generate a hash across the pool, 16 words (512 bits) at a time */ 776 sha_init(hash); 777 for (i = 0; i < r->poolinfo->poolwords; i += 16) 778 sha_transform(hash, (__u8 *)(r->pool + i), workspace); 779 780 /* 781 * We mix the hash back into the pool to prevent backtracking 782 * attacks (where the attacker knows the state of the pool 783 * plus the current outputs, and attempts to find previous 784 * ouputs), unless the hash function can be inverted. By 785 * mixing at least a SHA1 worth of hash data back, we make 786 * brute-forcing the feedback as hard as brute-forcing the 787 * hash. 788 */ 789 mix_pool_bytes_extract(r, hash, sizeof(hash), extract); 790 791 /* 792 * To avoid duplicates, we atomically extract a portion of the 793 * pool while mixing, and hash one final time. 794 */ 795 sha_transform(hash, extract, workspace); 796 memset(extract, 0, sizeof(extract)); 797 memset(workspace, 0, sizeof(workspace)); 798 799 /* 800 * In case the hash function has some recognizable output 801 * pattern, we fold it in half. Thus, we always feed back 802 * twice as much data as we output. 803 */ 804 hash[0] ^= hash[3]; 805 hash[1] ^= hash[4]; 806 hash[2] ^= rol32(hash[2], 16); 807 memcpy(out, hash, EXTRACT_SIZE); 808 memset(hash, 0, sizeof(hash)); 809} 810 811static ssize_t extract_entropy(struct entropy_store *r, void *buf, 812 size_t nbytes, int min, int reserved) 813{ 814 ssize_t ret = 0, i; 815 __u8 tmp[EXTRACT_SIZE]; 816 unsigned long flags; 817 818 xfer_secondary_pool(r, nbytes); 819 nbytes = account(r, nbytes, min, reserved); 820 821 while (nbytes) { 822 extract_buf(r, tmp); 823 824 if (fips_enabled) { 825 spin_lock_irqsave(&r->lock, flags); 826 if (!memcmp(tmp, r->last_data, EXTRACT_SIZE)) 827 panic("Hardware RNG duplicated output!\n"); 828 memcpy(r->last_data, tmp, EXTRACT_SIZE); 829 spin_unlock_irqrestore(&r->lock, flags); 830 } 831 i = min_t(int, nbytes, EXTRACT_SIZE); 832 memcpy(buf, tmp, i); 833 nbytes -= i; 834 buf += i; 835 ret += i; 836 } 837 838 /* Wipe data just returned from memory */ 839 memset(tmp, 0, sizeof(tmp)); 840 841 return ret; 842} 843 844static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, 845 size_t nbytes) 846{ 847 ssize_t ret = 0, i; 848 __u8 tmp[EXTRACT_SIZE]; 849 850 xfer_secondary_pool(r, nbytes); 851 nbytes = account(r, nbytes, 0, 0); 852 853 while (nbytes) { 854 if (need_resched()) { 855 if (signal_pending(current)) { 856 if (ret == 0) 857 ret = -ERESTARTSYS; 858 break; 859 } 860 schedule(); 861 } 862 863 extract_buf(r, tmp); 864 i = min_t(int, nbytes, EXTRACT_SIZE); 865 if (copy_to_user(buf, tmp, i)) { 866 ret = -EFAULT; 867 break; 868 } 869 870 nbytes -= i; 871 buf += i; 872 ret += i; 873 } 874 875 /* Wipe data just returned from memory */ 876 memset(tmp, 0, sizeof(tmp)); 877 878 return ret; 879} 880 881/* 882 * This function is the exported kernel interface. It returns some 883 * number of good random numbers, suitable for seeding TCP sequence 884 * numbers, etc. 885 */ 886void get_random_bytes(void *buf, int nbytes) 887{ 888 extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0); 889} 890EXPORT_SYMBOL(get_random_bytes); 891 892/* 893 * init_std_data - initialize pool with system data 894 * 895 * @r: pool to initialize 896 * 897 * This function clears the pool's entropy count and mixes some system 898 * data into the pool to prepare it for use. The pool is not cleared 899 * as that can only decrease the entropy in the pool. 900 */ 901static void init_std_data(struct entropy_store *r) 902{ 903 ktime_t now; 904 unsigned long flags; 905 906 spin_lock_irqsave(&r->lock, flags); 907 r->entropy_count = 0; 908 spin_unlock_irqrestore(&r->lock, flags); 909 910 now = ktime_get_real(); 911 mix_pool_bytes(r, &now, sizeof(now)); 912 mix_pool_bytes(r, utsname(), sizeof(*(utsname()))); 913} 914 915static int rand_initialize(void) 916{ 917 init_std_data(&input_pool); 918 init_std_data(&blocking_pool); 919 init_std_data(&nonblocking_pool); 920 return 0; 921} 922module_init(rand_initialize); 923 924void rand_initialize_irq(int irq) 925{ 926 struct timer_rand_state *state; 927 928 state = get_timer_rand_state(irq); 929 930 if (state) 931 return; 932 933 /* 934 * If kzalloc returns null, we just won't use that entropy 935 * source. 936 */ 937 state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL); 938 if (state) 939 set_timer_rand_state(irq, state); 940} 941 942#ifdef CONFIG_BLOCK 943void rand_initialize_disk(struct gendisk *disk) 944{ 945 struct timer_rand_state *state; 946 947 /* 948 * If kzalloc returns null, we just won't use that entropy 949 * source. 950 */ 951 state = kzalloc(sizeof(struct timer_rand_state), GFP_KERNEL); 952 if (state) 953 disk->random = state; 954} 955#endif 956 957static ssize_t 958random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) 959{ 960 ssize_t n, retval = 0, count = 0; 961 962 if (nbytes == 0) 963 return 0; 964 965 while (nbytes > 0) { 966 n = nbytes; 967 if (n > SEC_XFER_SIZE) 968 n = SEC_XFER_SIZE; 969 970 DEBUG_ENT("reading %d bits\n", n*8); 971 972 n = extract_entropy_user(&blocking_pool, buf, n); 973 974 DEBUG_ENT("read got %d bits (%d still needed)\n", 975 n*8, (nbytes-n)*8); 976 977 if (n == 0) { 978 if (file->f_flags & O_NONBLOCK) { 979 retval = -EAGAIN; 980 break; 981 } 982 983 DEBUG_ENT("sleeping?\n"); 984 985 wait_event_interruptible(random_read_wait, 986 input_pool.entropy_count >= 987 random_read_wakeup_thresh); 988 989 DEBUG_ENT("awake\n"); 990 991 if (signal_pending(current)) { 992 retval = -ERESTARTSYS; 993 break; 994 } 995 996 continue; 997 } 998 999 if (n < 0) { 1000 retval = n; 1001 break; 1002 } 1003 count += n; 1004 buf += n; 1005 nbytes -= n; 1006 break; /* This break makes the device work */ 1007 /* like a named pipe */ 1008 } 1009 1010 return (count ? count : retval); 1011} 1012 1013static ssize_t 1014urandom_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) 1015{ 1016 return extract_entropy_user(&nonblocking_pool, buf, nbytes); 1017} 1018 1019static unsigned int 1020random_poll(struct file *file, poll_table * wait) 1021{ 1022 unsigned int mask; 1023 1024 poll_wait(file, &random_read_wait, wait); 1025 poll_wait(file, &random_write_wait, wait); 1026 mask = 0; 1027 if (input_pool.entropy_count >= random_read_wakeup_thresh) 1028 mask |= POLLIN | POLLRDNORM; 1029 if (input_pool.entropy_count < random_write_wakeup_thresh) 1030 mask |= POLLOUT | POLLWRNORM; 1031 return mask; 1032} 1033 1034static int 1035write_pool(struct entropy_store *r, const char __user *buffer, size_t count) 1036{ 1037 size_t bytes; 1038 __u32 buf[16]; 1039 const char __user *p = buffer; 1040 1041 while (count > 0) { 1042 bytes = min(count, sizeof(buf)); 1043 if (copy_from_user(&buf, p, bytes)) 1044 return -EFAULT; 1045 1046 count -= bytes; 1047 p += bytes; 1048 1049 mix_pool_bytes(r, buf, bytes); 1050 cond_resched(); 1051 } 1052 1053 return 0; 1054} 1055 1056static ssize_t random_write(struct file *file, const char __user *buffer, 1057 size_t count, loff_t *ppos) 1058{ 1059 size_t ret; 1060 1061 ret = write_pool(&blocking_pool, buffer, count); 1062 if (ret) 1063 return ret; 1064 ret = write_pool(&nonblocking_pool, buffer, count); 1065 if (ret) 1066 return ret; 1067 1068 return (ssize_t)count; 1069} 1070 1071static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg) 1072{ 1073 int size, ent_count; 1074 int __user *p = (int __user *)arg; 1075 int retval; 1076 1077 switch (cmd) { 1078 case RNDGETENTCNT: 1079 /* inherently racy, no point locking */ 1080 if (put_user(input_pool.entropy_count, p)) 1081 return -EFAULT; 1082 return 0; 1083 case RNDADDTOENTCNT: 1084 if (!capable(CAP_SYS_ADMIN)) 1085 return -EPERM; 1086 if (get_user(ent_count, p)) 1087 return -EFAULT; 1088 credit_entropy_bits(&input_pool, ent_count); 1089 return 0; 1090 case RNDADDENTROPY: 1091 if (!capable(CAP_SYS_ADMIN)) 1092 return -EPERM; 1093 if (get_user(ent_count, p++)) 1094 return -EFAULT; 1095 if (ent_count < 0) 1096 return -EINVAL; 1097 if (get_user(size, p++)) 1098 return -EFAULT; 1099 retval = write_pool(&input_pool, (const char __user *)p, 1100 size); 1101 if (retval < 0) 1102 return retval; 1103 credit_entropy_bits(&input_pool, ent_count); 1104 return 0; 1105 case RNDZAPENTCNT: 1106 case RNDCLEARPOOL: 1107 /* Clear the entropy pool counters. */ 1108 if (!capable(CAP_SYS_ADMIN)) 1109 return -EPERM; 1110 rand_initialize(); 1111 return 0; 1112 default: 1113 return -EINVAL; 1114 } 1115} 1116 1117static int random_fasync(int fd, struct file *filp, int on) 1118{ 1119 return fasync_helper(fd, filp, on, &fasync); 1120} 1121 1122const struct file_operations random_fops = { 1123 .read = random_read, 1124 .write = random_write, 1125 .poll = random_poll, 1126 .unlocked_ioctl = random_ioctl, 1127 .fasync = random_fasync, 1128}; 1129 1130const struct file_operations urandom_fops = { 1131 .read = urandom_read, 1132 .write = random_write, 1133 .unlocked_ioctl = random_ioctl, 1134 .fasync = random_fasync, 1135}; 1136 1137/*************************************************************** 1138 * Random UUID interface 1139 * 1140 * Used here for a Boot ID, but can be useful for other kernel 1141 * drivers. 1142 ***************************************************************/ 1143 1144/* 1145 * Generate random UUID 1146 */ 1147void generate_random_uuid(unsigned char uuid_out[16]) 1148{ 1149 get_random_bytes(uuid_out, 16); 1150 /* Set UUID version to 4 --- truly random generation */ 1151 uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40; 1152 /* Set the UUID variant to DCE */ 1153 uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80; 1154} 1155EXPORT_SYMBOL(generate_random_uuid); 1156 1157/******************************************************************** 1158 * 1159 * Sysctl interface 1160 * 1161 ********************************************************************/ 1162 1163#ifdef CONFIG_SYSCTL 1164 1165#include <linux/sysctl.h> 1166 1167static int min_read_thresh = 8, min_write_thresh; 1168static int max_read_thresh = INPUT_POOL_WORDS * 32; 1169static int max_write_thresh = INPUT_POOL_WORDS * 32; 1170static char sysctl_bootid[16]; 1171 1172/* 1173 * These functions is used to return both the bootid UUID, and random 1174 * UUID. The difference is in whether table->data is NULL; if it is, 1175 * then a new UUID is generated and returned to the user. 1176 * 1177 * If the user accesses this via the proc interface, it will be returned 1178 * as an ASCII string in the standard UUID format. If accesses via the 1179 * sysctl system call, it is returned as 16 bytes of binary data. 1180 */ 1181static int proc_do_uuid(ctl_table *table, int write, 1182 void __user *buffer, size_t *lenp, loff_t *ppos) 1183{ 1184 ctl_table fake_table; 1185 unsigned char buf[64], tmp_uuid[16], *uuid; 1186 1187 uuid = table->data; 1188 if (!uuid) { 1189 uuid = tmp_uuid; 1190 uuid[8] = 0; 1191 } 1192 if (uuid[8] == 0) 1193 generate_random_uuid(uuid); 1194 1195 sprintf(buf, "%pU", uuid); 1196 1197 fake_table.data = buf; 1198 fake_table.maxlen = sizeof(buf); 1199 1200 return proc_dostring(&fake_table, write, buffer, lenp, ppos); 1201} 1202 1203static int sysctl_poolsize = INPUT_POOL_WORDS * 32; 1204ctl_table random_table[] = { 1205 { 1206 .procname = "poolsize", 1207 .data = &sysctl_poolsize, 1208 .maxlen = sizeof(int), 1209 .mode = 0444, 1210 .proc_handler = proc_dointvec, 1211 }, 1212 { 1213 .procname = "entropy_avail", 1214 .maxlen = sizeof(int), 1215 .mode = 0444, 1216 .proc_handler = proc_dointvec, 1217 .data = &input_pool.entropy_count, 1218 }, 1219 { 1220 .procname = "read_wakeup_threshold", 1221 .data = &random_read_wakeup_thresh, 1222 .maxlen = sizeof(int), 1223 .mode = 0644, 1224 .proc_handler = proc_dointvec_minmax, 1225 .extra1 = &min_read_thresh, 1226 .extra2 = &max_read_thresh, 1227 }, 1228 { 1229 .procname = "write_wakeup_threshold", 1230 .data = &random_write_wakeup_thresh, 1231 .maxlen = sizeof(int), 1232 .mode = 0644, 1233 .proc_handler = proc_dointvec_minmax, 1234 .extra1 = &min_write_thresh, 1235 .extra2 = &max_write_thresh, 1236 }, 1237 { 1238 .procname = "boot_id", 1239 .data = &sysctl_bootid, 1240 .maxlen = 16, 1241 .mode = 0444, 1242 .proc_handler = proc_do_uuid, 1243 }, 1244 { 1245 .procname = "uuid", 1246 .maxlen = 16, 1247 .mode = 0444, 1248 .proc_handler = proc_do_uuid, 1249 }, 1250 { } 1251}; 1252#endif /* CONFIG_SYSCTL */ 1253 1254/******************************************************************** 1255 * 1256 * Random functions for networking 1257 * 1258 ********************************************************************/ 1259 1260/* 1261 * TCP initial sequence number picking. This uses the random number 1262 * generator to pick an initial secret value. This value is hashed 1263 * along with the TCP endpoint information to provide a unique 1264 * starting point for each pair of TCP endpoints. This defeats 1265 * attacks which rely on guessing the initial TCP sequence number. 1266 * This algorithm was suggested by Steve Bellovin. 1267 * 1268 * Using a very strong hash was taking an appreciable amount of the total 1269 * TCP connection establishment time, so this is a weaker hash, 1270 * compensated for by changing the secret periodically. 1271 */ 1272 1273/* F, G and H are basic MD4 functions: selection, majority, parity */ 1274#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z)))) 1275#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z))) 1276#define H(x, y, z) ((x) ^ (y) ^ (z)) 1277 1278/* 1279 * The generic round function. The application is so specific that 1280 * we don't bother protecting all the arguments with parens, as is generally 1281 * good macro practice, in favor of extra legibility. 1282 * Rotation is separate from addition to prevent recomputation 1283 */ 1284#define ROUND(f, a, b, c, d, x, s) \ 1285 (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s))) 1286#define K1 0 1287#define K2 013240474631UL 1288#define K3 015666365641UL 1289 1290#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE) 1291 1292static __u32 twothirdsMD4Transform(__u32 const buf[4], __u32 const in[12]) 1293{ 1294 __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 1295 1296 /* Round 1 */ 1297 ROUND(F, a, b, c, d, in[ 0] + K1, 3); 1298 ROUND(F, d, a, b, c, in[ 1] + K1, 7); 1299 ROUND(F, c, d, a, b, in[ 2] + K1, 11); 1300 ROUND(F, b, c, d, a, in[ 3] + K1, 19); 1301 ROUND(F, a, b, c, d, in[ 4] + K1, 3); 1302 ROUND(F, d, a, b, c, in[ 5] + K1, 7); 1303 ROUND(F, c, d, a, b, in[ 6] + K1, 11); 1304 ROUND(F, b, c, d, a, in[ 7] + K1, 19); 1305 ROUND(F, a, b, c, d, in[ 8] + K1, 3); 1306 ROUND(F, d, a, b, c, in[ 9] + K1, 7); 1307 ROUND(F, c, d, a, b, in[10] + K1, 11); 1308 ROUND(F, b, c, d, a, in[11] + K1, 19); 1309 1310 /* Round 2 */ 1311 ROUND(G, a, b, c, d, in[ 1] + K2, 3); 1312 ROUND(G, d, a, b, c, in[ 3] + K2, 5); 1313 ROUND(G, c, d, a, b, in[ 5] + K2, 9); 1314 ROUND(G, b, c, d, a, in[ 7] + K2, 13); 1315 ROUND(G, a, b, c, d, in[ 9] + K2, 3); 1316 ROUND(G, d, a, b, c, in[11] + K2, 5); 1317 ROUND(G, c, d, a, b, in[ 0] + K2, 9); 1318 ROUND(G, b, c, d, a, in[ 2] + K2, 13); 1319 ROUND(G, a, b, c, d, in[ 4] + K2, 3); 1320 ROUND(G, d, a, b, c, in[ 6] + K2, 5); 1321 ROUND(G, c, d, a, b, in[ 8] + K2, 9); 1322 ROUND(G, b, c, d, a, in[10] + K2, 13); 1323 1324 /* Round 3 */ 1325 ROUND(H, a, b, c, d, in[ 3] + K3, 3); 1326 ROUND(H, d, a, b, c, in[ 7] + K3, 9); 1327 ROUND(H, c, d, a, b, in[11] + K3, 11); 1328 ROUND(H, b, c, d, a, in[ 2] + K3, 15); 1329 ROUND(H, a, b, c, d, in[ 6] + K3, 3); 1330 ROUND(H, d, a, b, c, in[10] + K3, 9); 1331 ROUND(H, c, d, a, b, in[ 1] + K3, 11); 1332 ROUND(H, b, c, d, a, in[ 5] + K3, 15); 1333 ROUND(H, a, b, c, d, in[ 9] + K3, 3); 1334 ROUND(H, d, a, b, c, in[ 0] + K3, 9); 1335 ROUND(H, c, d, a, b, in[ 4] + K3, 11); 1336 ROUND(H, b, c, d, a, in[ 8] + K3, 15); 1337 1338 return buf[1] + b; /* "most hashed" word */ 1339 /* Alternative: return sum of all words? */ 1340} 1341#endif 1342 1343#undef ROUND 1344#undef F 1345#undef G 1346#undef H 1347#undef K1 1348#undef K2 1349#undef K3 1350 1351/* This should not be decreased so low that ISNs wrap too fast. */ 1352#define REKEY_INTERVAL (300 * HZ) 1353/* 1354 * Bit layout of the tcp sequence numbers (before adding current time): 1355 * bit 24-31: increased after every key exchange 1356 * bit 0-23: hash(source,dest) 1357 * 1358 * The implementation is similar to the algorithm described 1359 * in the Appendix of RFC 1185, except that 1360 * - it uses a 1 MHz clock instead of a 250 kHz clock 1361 * - it performs a rekey every 5 minutes, which is equivalent 1362 * to a (source,dest) tulple dependent forward jump of the 1363 * clock by 0..2^(HASH_BITS+1) 1364 * 1365 * Thus the average ISN wraparound time is 68 minutes instead of 1366 * 4.55 hours. 1367 * 1368 * SMP cleanup and lock avoidance with poor man's RCU. 1369 * Manfred Spraul <manfred@colorfullife.com> 1370 * 1371 */ 1372#define COUNT_BITS 8 1373#define COUNT_MASK ((1 << COUNT_BITS) - 1) 1374#define HASH_BITS 24 1375#define HASH_MASK ((1 << HASH_BITS) - 1) 1376 1377static struct keydata { 1378 __u32 count; /* already shifted to the final position */ 1379 __u32 secret[12]; 1380} ____cacheline_aligned ip_keydata[2]; 1381 1382static unsigned int ip_cnt; 1383 1384static void rekey_seq_generator(struct work_struct *work); 1385 1386static DECLARE_DELAYED_WORK(rekey_work, rekey_seq_generator); 1387 1388/* 1389 * Lock avoidance: 1390 * The ISN generation runs lockless - it's just a hash over random data. 1391 * State changes happen every 5 minutes when the random key is replaced. 1392 * Synchronization is performed by having two copies of the hash function 1393 * state and rekey_seq_generator always updates the inactive copy. 1394 * The copy is then activated by updating ip_cnt. 1395 * The implementation breaks down if someone blocks the thread 1396 * that processes SYN requests for more than 5 minutes. Should never 1397 * happen, and even if that happens only a not perfectly compliant 1398 * ISN is generated, nothing fatal. 1399 */ 1400static void rekey_seq_generator(struct work_struct *work) 1401{ 1402 struct keydata *keyptr = &ip_keydata[1 ^ (ip_cnt & 1)]; 1403 1404 get_random_bytes(keyptr->secret, sizeof(keyptr->secret)); 1405 keyptr->count = (ip_cnt & COUNT_MASK) << HASH_BITS; 1406 smp_wmb(); 1407 ip_cnt++; 1408 schedule_delayed_work(&rekey_work, 1409 round_jiffies_relative(REKEY_INTERVAL)); 1410} 1411 1412static inline struct keydata *get_keyptr(void) 1413{ 1414 struct keydata *keyptr = &ip_keydata[ip_cnt & 1]; 1415 1416 smp_rmb(); 1417 1418 return keyptr; 1419} 1420 1421static __init int seqgen_init(void) 1422{ 1423 rekey_seq_generator(NULL); 1424 return 0; 1425} 1426late_initcall(seqgen_init); 1427 1428#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE) 1429__u32 secure_tcpv6_sequence_number(__be32 *saddr, __be32 *daddr, 1430 __be16 sport, __be16 dport) 1431{ 1432 __u32 seq; 1433 __u32 hash[12]; 1434 struct keydata *keyptr = get_keyptr(); 1435 1436 /* The procedure is the same as for IPv4, but addresses are longer. 1437 * Thus we must use twothirdsMD4Transform. 1438 */ 1439 1440 memcpy(hash, saddr, 16); 1441 hash[4] = ((__force u16)sport << 16) + (__force u16)dport; 1442 memcpy(&hash[5], keyptr->secret, sizeof(__u32) * 7); 1443 1444 seq = twothirdsMD4Transform((const __u32 *)daddr, hash) & HASH_MASK; 1445 seq += keyptr->count; 1446 1447 seq += ktime_to_ns(ktime_get_real()); 1448 1449 return seq; 1450} 1451EXPORT_SYMBOL(secure_tcpv6_sequence_number); 1452#endif 1453 1454/* The code below is shamelessly stolen from secure_tcp_sequence_number(). 1455 * All blames to Andrey V. Savochkin <saw@msu.ru>. 1456 */ 1457__u32 secure_ip_id(__be32 daddr) 1458{ 1459 struct keydata *keyptr; 1460 __u32 hash[4]; 1461 1462 keyptr = get_keyptr(); 1463 1464 /* 1465 * Pick a unique starting offset for each IP destination. 1466 * The dest ip address is placed in the starting vector, 1467 * which is then hashed with random data. 1468 */ 1469 hash[0] = (__force __u32)daddr; 1470 hash[1] = keyptr->secret[9]; 1471 hash[2] = keyptr->secret[10]; 1472 hash[3] = keyptr->secret[11]; 1473 1474 return half_md4_transform(hash, keyptr->secret); 1475} 1476 1477#ifdef CONFIG_INET 1478 1479__u32 secure_tcp_sequence_number(__be32 saddr, __be32 daddr, 1480 __be16 sport, __be16 dport) 1481{ 1482 __u32 seq; 1483 __u32 hash[4]; 1484 struct keydata *keyptr = get_keyptr(); 1485 1486 /* 1487 * Pick a unique starting offset for each TCP connection endpoints 1488 * (saddr, daddr, sport, dport). 1489 * Note that the words are placed into the starting vector, which is 1490 * then mixed with a partial MD4 over random data. 1491 */ 1492 hash[0] = (__force u32)saddr; 1493 hash[1] = (__force u32)daddr; 1494 hash[2] = ((__force u16)sport << 16) + (__force u16)dport; 1495 hash[3] = keyptr->secret[11]; 1496 1497 seq = half_md4_transform(hash, keyptr->secret) & HASH_MASK; 1498 seq += keyptr->count; 1499 /* 1500 * As close as possible to RFC 793, which 1501 * suggests using a 250 kHz clock. 1502 * Further reading shows this assumes 2 Mb/s networks. 1503 * For 10 Mb/s Ethernet, a 1 MHz clock is appropriate. 1504 * For 10 Gb/s Ethernet, a 1 GHz clock should be ok, but 1505 * we also need to limit the resolution so that the u32 seq 1506 * overlaps less than one time per MSL (2 minutes). 1507 * Choosing a clock of 64 ns period is OK. (period of 274 s) 1508 */ 1509 seq += ktime_to_ns(ktime_get_real()) >> 6; 1510 1511 return seq; 1512} 1513 1514/* Generate secure starting point for ephemeral IPV4 transport port search */ 1515u32 secure_ipv4_port_ephemeral(__be32 saddr, __be32 daddr, __be16 dport) 1516{ 1517 struct keydata *keyptr = get_keyptr(); 1518 u32 hash[4]; 1519 1520 /* 1521 * Pick a unique starting offset for each ephemeral port search 1522 * (saddr, daddr, dport) and 48bits of random data. 1523 */ 1524 hash[0] = (__force u32)saddr; 1525 hash[1] = (__force u32)daddr; 1526 hash[2] = (__force u32)dport ^ keyptr->secret[10]; 1527 hash[3] = keyptr->secret[11]; 1528 1529 return half_md4_transform(hash, keyptr->secret); 1530} 1531EXPORT_SYMBOL_GPL(secure_ipv4_port_ephemeral); 1532 1533#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE) 1534u32 secure_ipv6_port_ephemeral(const __be32 *saddr, const __be32 *daddr, 1535 __be16 dport) 1536{ 1537 struct keydata *keyptr = get_keyptr(); 1538 u32 hash[12]; 1539 1540 memcpy(hash, saddr, 16); 1541 hash[4] = (__force u32)dport; 1542 memcpy(&hash[5], keyptr->secret, sizeof(__u32) * 7); 1543 1544 return twothirdsMD4Transform((const __u32 *)daddr, hash); 1545} 1546#endif 1547 1548#if defined(CONFIG_IP_DCCP) || defined(CONFIG_IP_DCCP_MODULE) 1549/* Similar to secure_tcp_sequence_number but generate a 48 bit value 1550 * bit's 32-47 increase every key exchange 1551 * 0-31 hash(source, dest) 1552 */ 1553u64 secure_dccp_sequence_number(__be32 saddr, __be32 daddr, 1554 __be16 sport, __be16 dport) 1555{ 1556 u64 seq; 1557 __u32 hash[4]; 1558 struct keydata *keyptr = get_keyptr(); 1559 1560 hash[0] = (__force u32)saddr; 1561 hash[1] = (__force u32)daddr; 1562 hash[2] = ((__force u16)sport << 16) + (__force u16)dport; 1563 hash[3] = keyptr->secret[11]; 1564 1565 seq = half_md4_transform(hash, keyptr->secret); 1566 seq |= ((u64)keyptr->count) << (32 - HASH_BITS); 1567 1568 seq += ktime_to_ns(ktime_get_real()); 1569 seq &= (1ull << 48) - 1; 1570 1571 return seq; 1572} 1573EXPORT_SYMBOL(secure_dccp_sequence_number); 1574#endif 1575 1576#endif /* CONFIG_INET */ 1577 1578 1579/* 1580 * Get a random word for internal kernel use only. Similar to urandom but 1581 * with the goal of minimal entropy pool depletion. As a result, the random 1582 * value is not cryptographically secure but for several uses the cost of 1583 * depleting entropy is too high 1584 */ 1585DEFINE_PER_CPU(__u32 [4], get_random_int_hash); 1586unsigned int get_random_int(void) 1587{ 1588 struct keydata *keyptr; 1589 __u32 *hash = get_cpu_var(get_random_int_hash); 1590 int ret; 1591 1592 keyptr = get_keyptr(); 1593 hash[0] += current->pid + jiffies + get_cycles(); 1594 1595 ret = half_md4_transform(hash, keyptr->secret); 1596 put_cpu_var(get_random_int_hash); 1597 1598 return ret; 1599} 1600 1601/* 1602 * randomize_range() returns a start address such that 1603 * 1604 * [...... <range> .....] 1605 * start end 1606 * 1607 * a <range> with size "len" starting at the return value is inside in the 1608 * area defined by [start, end], but is otherwise randomized. 1609 */ 1610unsigned long 1611randomize_range(unsigned long start, unsigned long end, unsigned long len) 1612{ 1613 unsigned long range = end - len - start; 1614 1615 if (end <= start + len) 1616 return 0; 1617 return PAGE_ALIGN(get_random_int() % range + start); 1618} 1619