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