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