1 /* 2 * Non-physical true random number generator based on timing jitter. 3 * 4 * Copyright Stephan Mueller <smueller@chronox.de>, 2014 5 * 6 * Design 7 * ====== 8 * 9 * See http://www.chronox.de/jent.html 10 * 11 * License 12 * ======= 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 1. Redistributions of source code must retain the above copyright 18 * notice, and the entire permission notice in its entirety, 19 * including the disclaimer of warranties. 20 * 2. Redistributions in binary form must reproduce the above copyright 21 * notice, this list of conditions and the following disclaimer in the 22 * documentation and/or other materials provided with the distribution. 23 * 3. The name of the author may not be used to endorse or promote 24 * products derived from this software without specific prior 25 * written permission. 26 * 27 * ALTERNATIVELY, this product may be distributed under the terms of 28 * the GNU General Public License, in which case the provisions of the GPL2 are 29 * required INSTEAD OF the above restrictions. (This clause is 30 * necessary due to a potential bad interaction between the GPL and 31 * the restrictions contained in a BSD-style copyright.) 32 * 33 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 34 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 35 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF 36 * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE 37 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 38 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 39 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 40 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 41 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 42 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 43 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH 44 * DAMAGE. 45 */ 46 47 /* 48 * This Jitterentropy RNG is based on the jitterentropy library 49 * version 1.1.0 provided at http://www.chronox.de/jent.html 50 */ 51 52 #include <linux/module.h> 53 #include <linux/slab.h> 54 #include <linux/module.h> 55 #include <linux/fips.h> 56 #include <linux/time.h> 57 #include <linux/crypto.h> 58 #include <crypto/internal/rng.h> 59 60 /* The entropy pool */ 61 struct rand_data { 62 /* all data values that are vital to maintain the security 63 * of the RNG are marked as SENSITIVE. A user must not 64 * access that information while the RNG executes its loops to 65 * calculate the next random value. */ 66 __u64 data; /* SENSITIVE Actual random number */ 67 __u64 old_data; /* SENSITIVE Previous random number */ 68 __u64 prev_time; /* SENSITIVE Previous time stamp */ 69 #define DATA_SIZE_BITS ((sizeof(__u64)) * 8) 70 __u64 last_delta; /* SENSITIVE stuck test */ 71 __s64 last_delta2; /* SENSITIVE stuck test */ 72 unsigned int stuck:1; /* Time measurement stuck */ 73 unsigned int osr; /* Oversample rate */ 74 unsigned int stir:1; /* Post-processing stirring */ 75 unsigned int disable_unbias:1; /* Deactivate Von-Neuman unbias */ 76 #define JENT_MEMORY_BLOCKS 64 77 #define JENT_MEMORY_BLOCKSIZE 32 78 #define JENT_MEMORY_ACCESSLOOPS 128 79 #define JENT_MEMORY_SIZE (JENT_MEMORY_BLOCKS*JENT_MEMORY_BLOCKSIZE) 80 unsigned char *mem; /* Memory access location with size of 81 * memblocks * memblocksize */ 82 unsigned int memlocation; /* Pointer to byte in *mem */ 83 unsigned int memblocks; /* Number of memory blocks in *mem */ 84 unsigned int memblocksize; /* Size of one memory block in bytes */ 85 unsigned int memaccessloops; /* Number of memory accesses per random 86 * bit generation */ 87 }; 88 89 /* Flags that can be used to initialize the RNG */ 90 #define JENT_DISABLE_STIR (1<<0) /* Disable stirring the entropy pool */ 91 #define JENT_DISABLE_UNBIAS (1<<1) /* Disable the Von-Neuman Unbiaser */ 92 #define JENT_DISABLE_MEMORY_ACCESS (1<<2) /* Disable memory access for more 93 * entropy, saves MEMORY_SIZE RAM for 94 * entropy collector */ 95 96 #define DRIVER_NAME "jitterentropy" 97 98 /* -- error codes for init function -- */ 99 #define JENT_ENOTIME 1 /* Timer service not available */ 100 #define JENT_ECOARSETIME 2 /* Timer too coarse for RNG */ 101 #define JENT_ENOMONOTONIC 3 /* Timer is not monotonic increasing */ 102 #define JENT_EMINVARIATION 4 /* Timer variations too small for RNG */ 103 #define JENT_EVARVAR 5 /* Timer does not produce variations of 104 * variations (2nd derivation of time is 105 * zero). */ 106 #define JENT_EMINVARVAR 6 /* Timer variations of variations is tooi 107 * small. */ 108 109 /*************************************************************************** 110 * Helper functions 111 ***************************************************************************/ 112 113 static inline void jent_get_nstime(__u64 *out) 114 { 115 struct timespec ts; 116 __u64 tmp = 0; 117 118 tmp = random_get_entropy(); 119 120 /* 121 * If random_get_entropy does not return a value (which is possible on, 122 * for example, MIPS), invoke __getnstimeofday 123 * hoping that there are timers we can work with. 124 * 125 * The list of available timers can be obtained from 126 * /sys/devices/system/clocksource/clocksource0/available_clocksource 127 * and are registered with clocksource_register() 128 */ 129 if ((0 == tmp) && 130 (0 == __getnstimeofday(&ts))) { 131 tmp = ts.tv_sec; 132 tmp = tmp << 32; 133 tmp = tmp | ts.tv_nsec; 134 } 135 136 *out = tmp; 137 } 138 139 140 /** 141 * Update of the loop count used for the next round of 142 * an entropy collection. 143 * 144 * Input: 145 * @ec entropy collector struct -- may be NULL 146 * @bits is the number of low bits of the timer to consider 147 * @min is the number of bits we shift the timer value to the right at 148 * the end to make sure we have a guaranteed minimum value 149 * 150 * @return Newly calculated loop counter 151 */ 152 static __u64 jent_loop_shuffle(struct rand_data *ec, 153 unsigned int bits, unsigned int min) 154 { 155 __u64 time = 0; 156 __u64 shuffle = 0; 157 unsigned int i = 0; 158 unsigned int mask = (1<<bits) - 1; 159 160 jent_get_nstime(&time); 161 /* 162 * mix the current state of the random number into the shuffle 163 * calculation to balance that shuffle a bit more 164 */ 165 if (ec) 166 time ^= ec->data; 167 /* 168 * we fold the time value as much as possible to ensure that as many 169 * bits of the time stamp are included as possible 170 */ 171 for (i = 0; (DATA_SIZE_BITS / bits) > i; i++) { 172 shuffle ^= time & mask; 173 time = time >> bits; 174 } 175 176 /* 177 * We add a lower boundary value to ensure we have a minimum 178 * RNG loop count. 179 */ 180 return (shuffle + (1<<min)); 181 } 182 183 /*************************************************************************** 184 * Noise sources 185 ***************************************************************************/ 186 187 /* 188 * The disabling of the optimizations is performed as documented and assessed 189 * thoroughly in http://www.chronox.de/jent.html. However, instead of disabling 190 * the optimization of the entire C file, only the main functions the jitter is 191 * measured for are not optimized. These functions include the noise sources as 192 * well as the main functions triggering the noise sources. As the time 193 * measurement is done from one invocation of the jitter noise source to the 194 * next, even the execution jitter of the code invoking the noise sources 195 * contribute to the overall randomness as well. The behavior of the RNG and the 196 * statistical characteristics when only the mentioned functions are not 197 * optimized is almost equal to the a completely non-optimized RNG compilation 198 * as tested with the test tools provided at the initially mentioned web site. 199 */ 200 201 /** 202 * CPU Jitter noise source -- this is the noise source based on the CPU 203 * execution time jitter 204 * 205 * This function folds the time into one bit units by iterating 206 * through the DATA_SIZE_BITS bit time value as follows: assume our time value 207 * is 0xabcd 208 * 1st loop, 1st shift generates 0xd000 209 * 1st loop, 2nd shift generates 0x000d 210 * 2nd loop, 1st shift generates 0xcd00 211 * 2nd loop, 2nd shift generates 0x000c 212 * 3rd loop, 1st shift generates 0xbcd0 213 * 3rd loop, 2nd shift generates 0x000b 214 * 4th loop, 1st shift generates 0xabcd 215 * 4th loop, 2nd shift generates 0x000a 216 * Now, the values at the end of the 2nd shifts are XORed together. 217 * 218 * The code is deliberately inefficient and shall stay that way. This function 219 * is the root cause why the code shall be compiled without optimization. This 220 * function not only acts as folding operation, but this function's execution 221 * is used to measure the CPU execution time jitter. Any change to the loop in 222 * this function implies that careful retesting must be done. 223 * 224 * Input: 225 * @ec entropy collector struct -- may be NULL 226 * @time time stamp to be folded 227 * @loop_cnt if a value not equal to 0 is set, use the given value as number of 228 * loops to perform the folding 229 * 230 * Output: 231 * @folded result of folding operation 232 * 233 * @return Number of loops the folding operation is performed 234 */ 235 #pragma GCC push_options 236 #pragma GCC optimize ("-O0") 237 static __u64 jent_fold_time(struct rand_data *ec, __u64 time, 238 __u64 *folded, __u64 loop_cnt) 239 { 240 unsigned int i; 241 __u64 j = 0; 242 __u64 new = 0; 243 #define MAX_FOLD_LOOP_BIT 4 244 #define MIN_FOLD_LOOP_BIT 0 245 __u64 fold_loop_cnt = 246 jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT); 247 248 /* 249 * testing purposes -- allow test app to set the counter, not 250 * needed during runtime 251 */ 252 if (loop_cnt) 253 fold_loop_cnt = loop_cnt; 254 for (j = 0; j < fold_loop_cnt; j++) { 255 new = 0; 256 for (i = 1; (DATA_SIZE_BITS) >= i; i++) { 257 __u64 tmp = time << (DATA_SIZE_BITS - i); 258 259 tmp = tmp >> (DATA_SIZE_BITS - 1); 260 new ^= tmp; 261 } 262 } 263 *folded = new; 264 return fold_loop_cnt; 265 } 266 #pragma GCC pop_options 267 268 /** 269 * Memory Access noise source -- this is a noise source based on variations in 270 * memory access times 271 * 272 * This function performs memory accesses which will add to the timing 273 * variations due to an unknown amount of CPU wait states that need to be 274 * added when accessing memory. The memory size should be larger than the L1 275 * caches as outlined in the documentation and the associated testing. 276 * 277 * The L1 cache has a very high bandwidth, albeit its access rate is usually 278 * slower than accessing CPU registers. Therefore, L1 accesses only add minimal 279 * variations as the CPU has hardly to wait. Starting with L2, significant 280 * variations are added because L2 typically does not belong to the CPU any more 281 * and therefore a wider range of CPU wait states is necessary for accesses. 282 * L3 and real memory accesses have even a wider range of wait states. However, 283 * to reliably access either L3 or memory, the ec->mem memory must be quite 284 * large which is usually not desirable. 285 * 286 * Input: 287 * @ec Reference to the entropy collector with the memory access data -- if 288 * the reference to the memory block to be accessed is NULL, this noise 289 * source is disabled 290 * @loop_cnt if a value not equal to 0 is set, use the given value as number of 291 * loops to perform the folding 292 * 293 * @return Number of memory access operations 294 */ 295 #pragma GCC push_options 296 #pragma GCC optimize ("-O0") 297 static unsigned int jent_memaccess(struct rand_data *ec, __u64 loop_cnt) 298 { 299 unsigned char *tmpval = NULL; 300 unsigned int wrap = 0; 301 __u64 i = 0; 302 #define MAX_ACC_LOOP_BIT 7 303 #define MIN_ACC_LOOP_BIT 0 304 __u64 acc_loop_cnt = 305 jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); 306 307 if (NULL == ec || NULL == ec->mem) 308 return 0; 309 wrap = ec->memblocksize * ec->memblocks; 310 311 /* 312 * testing purposes -- allow test app to set the counter, not 313 * needed during runtime 314 */ 315 if (loop_cnt) 316 acc_loop_cnt = loop_cnt; 317 318 for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { 319 tmpval = ec->mem + ec->memlocation; 320 /* 321 * memory access: just add 1 to one byte, 322 * wrap at 255 -- memory access implies read 323 * from and write to memory location 324 */ 325 *tmpval = (*tmpval + 1) & 0xff; 326 /* 327 * Addition of memblocksize - 1 to pointer 328 * with wrap around logic to ensure that every 329 * memory location is hit evenly 330 */ 331 ec->memlocation = ec->memlocation + ec->memblocksize - 1; 332 ec->memlocation = ec->memlocation % wrap; 333 } 334 return i; 335 } 336 #pragma GCC pop_options 337 338 /*************************************************************************** 339 * Start of entropy processing logic 340 ***************************************************************************/ 341 342 /** 343 * Stuck test by checking the: 344 * 1st derivation of the jitter measurement (time delta) 345 * 2nd derivation of the jitter measurement (delta of time deltas) 346 * 3rd derivation of the jitter measurement (delta of delta of time deltas) 347 * 348 * All values must always be non-zero. 349 * 350 * Input: 351 * @ec Reference to entropy collector 352 * @current_delta Jitter time delta 353 * 354 * @return 355 * 0 jitter measurement not stuck (good bit) 356 * 1 jitter measurement stuck (reject bit) 357 */ 358 static void jent_stuck(struct rand_data *ec, __u64 current_delta) 359 { 360 __s64 delta2 = ec->last_delta - current_delta; 361 __s64 delta3 = delta2 - ec->last_delta2; 362 363 ec->last_delta = current_delta; 364 ec->last_delta2 = delta2; 365 366 if (!current_delta || !delta2 || !delta3) 367 ec->stuck = 1; 368 } 369 370 /** 371 * This is the heart of the entropy generation: calculate time deltas and 372 * use the CPU jitter in the time deltas. The jitter is folded into one 373 * bit. You can call this function the "random bit generator" as it 374 * produces one random bit per invocation. 375 * 376 * WARNING: ensure that ->prev_time is primed before using the output 377 * of this function! This can be done by calling this function 378 * and not using its result. 379 * 380 * Input: 381 * @entropy_collector Reference to entropy collector 382 * 383 * @return One random bit 384 */ 385 #pragma GCC push_options 386 #pragma GCC optimize ("-O0") 387 static __u64 jent_measure_jitter(struct rand_data *ec) 388 { 389 __u64 time = 0; 390 __u64 data = 0; 391 __u64 current_delta = 0; 392 393 /* Invoke one noise source before time measurement to add variations */ 394 jent_memaccess(ec, 0); 395 396 /* 397 * Get time stamp and calculate time delta to previous 398 * invocation to measure the timing variations 399 */ 400 jent_get_nstime(&time); 401 current_delta = time - ec->prev_time; 402 ec->prev_time = time; 403 404 /* Now call the next noise sources which also folds the data */ 405 jent_fold_time(ec, current_delta, &data, 0); 406 407 /* 408 * Check whether we have a stuck measurement. The enforcement 409 * is performed after the stuck value has been mixed into the 410 * entropy pool. 411 */ 412 jent_stuck(ec, current_delta); 413 414 return data; 415 } 416 #pragma GCC pop_options 417 418 /** 419 * Von Neuman unbias as explained in RFC 4086 section 4.2. As shown in the 420 * documentation of that RNG, the bits from jent_measure_jitter are considered 421 * independent which implies that the Von Neuman unbias operation is applicable. 422 * A proof of the Von-Neumann unbias operation to remove skews is given in the 423 * document "A proposal for: Functionality classes for random number 424 * generators", version 2.0 by Werner Schindler, section 5.4.1. 425 * 426 * Input: 427 * @entropy_collector Reference to entropy collector 428 * 429 * @return One random bit 430 */ 431 static __u64 jent_unbiased_bit(struct rand_data *entropy_collector) 432 { 433 do { 434 __u64 a = jent_measure_jitter(entropy_collector); 435 __u64 b = jent_measure_jitter(entropy_collector); 436 437 if (a == b) 438 continue; 439 if (1 == a) 440 return 1; 441 else 442 return 0; 443 } while (1); 444 } 445 446 /** 447 * Shuffle the pool a bit by mixing some value with a bijective function (XOR) 448 * into the pool. 449 * 450 * The function generates a mixer value that depends on the bits set and the 451 * location of the set bits in the random number generated by the entropy 452 * source. Therefore, based on the generated random number, this mixer value 453 * can have 2**64 different values. That mixer value is initialized with the 454 * first two SHA-1 constants. After obtaining the mixer value, it is XORed into 455 * the random number. 456 * 457 * The mixer value is not assumed to contain any entropy. But due to the XOR 458 * operation, it can also not destroy any entropy present in the entropy pool. 459 * 460 * Input: 461 * @entropy_collector Reference to entropy collector 462 */ 463 static void jent_stir_pool(struct rand_data *entropy_collector) 464 { 465 /* 466 * to shut up GCC on 32 bit, we have to initialize the 64 variable 467 * with two 32 bit variables 468 */ 469 union c { 470 __u64 u64; 471 __u32 u32[2]; 472 }; 473 /* 474 * This constant is derived from the first two 32 bit initialization 475 * vectors of SHA-1 as defined in FIPS 180-4 section 5.3.1 476 */ 477 union c constant; 478 /* 479 * The start value of the mixer variable is derived from the third 480 * and fourth 32 bit initialization vector of SHA-1 as defined in 481 * FIPS 180-4 section 5.3.1 482 */ 483 union c mixer; 484 unsigned int i = 0; 485 486 /* 487 * Store the SHA-1 constants in reverse order to make up the 64 bit 488 * value -- this applies to a little endian system, on a big endian 489 * system, it reverses as expected. But this really does not matter 490 * as we do not rely on the specific numbers. We just pick the SHA-1 491 * constants as they have a good mix of bit set and unset. 492 */ 493 constant.u32[1] = 0x67452301; 494 constant.u32[0] = 0xefcdab89; 495 mixer.u32[1] = 0x98badcfe; 496 mixer.u32[0] = 0x10325476; 497 498 for (i = 0; i < DATA_SIZE_BITS; i++) { 499 /* 500 * get the i-th bit of the input random number and only XOR 501 * the constant into the mixer value when that bit is set 502 */ 503 if ((entropy_collector->data >> i) & 1) 504 mixer.u64 ^= constant.u64; 505 mixer.u64 = rol64(mixer.u64, 1); 506 } 507 entropy_collector->data ^= mixer.u64; 508 } 509 510 /** 511 * Generator of one 64 bit random number 512 * Function fills rand_data->data 513 * 514 * Input: 515 * @ec Reference to entropy collector 516 */ 517 #pragma GCC push_options 518 #pragma GCC optimize ("-O0") 519 static void jent_gen_entropy(struct rand_data *ec) 520 { 521 unsigned int k = 0; 522 523 /* priming of the ->prev_time value */ 524 jent_measure_jitter(ec); 525 526 while (1) { 527 __u64 data = 0; 528 529 if (ec->disable_unbias == 1) 530 data = jent_measure_jitter(ec); 531 else 532 data = jent_unbiased_bit(ec); 533 534 /* enforcement of the jent_stuck test */ 535 if (ec->stuck) { 536 /* 537 * We only mix in the bit considered not appropriate 538 * without the LSFR. The reason is that if we apply 539 * the LSFR and we do not rotate, the 2nd bit with LSFR 540 * will cancel out the first LSFR application on the 541 * bad bit. 542 * 543 * And we do not rotate as we apply the next bit to the 544 * current bit location again. 545 */ 546 ec->data ^= data; 547 ec->stuck = 0; 548 continue; 549 } 550 551 /* 552 * Fibonacci LSFR with polynom of 553 * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is 554 * primitive according to 555 * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf 556 * (the shift values are the polynom values minus one 557 * due to counting bits from 0 to 63). As the current 558 * position is always the LSB, the polynom only needs 559 * to shift data in from the left without wrap. 560 */ 561 ec->data ^= data; 562 ec->data ^= ((ec->data >> 63) & 1); 563 ec->data ^= ((ec->data >> 60) & 1); 564 ec->data ^= ((ec->data >> 55) & 1); 565 ec->data ^= ((ec->data >> 30) & 1); 566 ec->data ^= ((ec->data >> 27) & 1); 567 ec->data ^= ((ec->data >> 22) & 1); 568 ec->data = rol64(ec->data, 1); 569 570 /* 571 * We multiply the loop value with ->osr to obtain the 572 * oversampling rate requested by the caller 573 */ 574 if (++k >= (DATA_SIZE_BITS * ec->osr)) 575 break; 576 } 577 if (ec->stir) 578 jent_stir_pool(ec); 579 } 580 #pragma GCC pop_options 581 582 /** 583 * The continuous test required by FIPS 140-2 -- the function automatically 584 * primes the test if needed. 585 * 586 * Return: 587 * 0 if FIPS test passed 588 * < 0 if FIPS test failed 589 */ 590 static void jent_fips_test(struct rand_data *ec) 591 { 592 if (!fips_enabled) 593 return; 594 595 /* prime the FIPS test */ 596 if (!ec->old_data) { 597 ec->old_data = ec->data; 598 jent_gen_entropy(ec); 599 } 600 601 if (ec->data == ec->old_data) 602 panic(DRIVER_NAME ": Duplicate output detected\n"); 603 604 ec->old_data = ec->data; 605 } 606 607 608 /** 609 * Entry function: Obtain entropy for the caller. 610 * 611 * This function invokes the entropy gathering logic as often to generate 612 * as many bytes as requested by the caller. The entropy gathering logic 613 * creates 64 bit per invocation. 614 * 615 * This function truncates the last 64 bit entropy value output to the exact 616 * size specified by the caller. 617 * 618 * Input: 619 * @ec Reference to entropy collector 620 * @data pointer to buffer for storing random data -- buffer must already 621 * exist 622 * @len size of the buffer, specifying also the requested number of random 623 * in bytes 624 * 625 * @return 0 when request is fulfilled or an error 626 * 627 * The following error codes can occur: 628 * -1 entropy_collector is NULL 629 */ 630 static ssize_t jent_read_entropy(struct rand_data *ec, u8 *data, size_t len) 631 { 632 u8 *p = data; 633 634 if (!ec) 635 return -EINVAL; 636 637 while (0 < len) { 638 size_t tocopy; 639 640 jent_gen_entropy(ec); 641 jent_fips_test(ec); 642 if ((DATA_SIZE_BITS / 8) < len) 643 tocopy = (DATA_SIZE_BITS / 8); 644 else 645 tocopy = len; 646 memcpy(p, &ec->data, tocopy); 647 648 len -= tocopy; 649 p += tocopy; 650 } 651 652 return 0; 653 } 654 655 /*************************************************************************** 656 * Initialization logic 657 ***************************************************************************/ 658 659 static struct rand_data *jent_entropy_collector_alloc(unsigned int osr, 660 unsigned int flags) 661 { 662 struct rand_data *entropy_collector; 663 664 entropy_collector = kzalloc(sizeof(struct rand_data), GFP_KERNEL); 665 if (!entropy_collector) 666 return NULL; 667 668 if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) { 669 /* Allocate memory for adding variations based on memory 670 * access 671 */ 672 entropy_collector->mem = kzalloc(JENT_MEMORY_SIZE, GFP_KERNEL); 673 if (!entropy_collector->mem) { 674 kfree(entropy_collector); 675 return NULL; 676 } 677 entropy_collector->memblocksize = JENT_MEMORY_BLOCKSIZE; 678 entropy_collector->memblocks = JENT_MEMORY_BLOCKS; 679 entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS; 680 } 681 682 /* verify and set the oversampling rate */ 683 if (0 == osr) 684 osr = 1; /* minimum sampling rate is 1 */ 685 entropy_collector->osr = osr; 686 687 entropy_collector->stir = 1; 688 if (flags & JENT_DISABLE_STIR) 689 entropy_collector->stir = 0; 690 if (flags & JENT_DISABLE_UNBIAS) 691 entropy_collector->disable_unbias = 1; 692 693 /* fill the data pad with non-zero values */ 694 jent_gen_entropy(entropy_collector); 695 696 return entropy_collector; 697 } 698 699 static void jent_entropy_collector_free(struct rand_data *entropy_collector) 700 { 701 if (entropy_collector->mem) 702 kzfree(entropy_collector->mem); 703 entropy_collector->mem = NULL; 704 if (entropy_collector) 705 kzfree(entropy_collector); 706 entropy_collector = NULL; 707 } 708 709 static int jent_entropy_init(void) 710 { 711 int i; 712 __u64 delta_sum = 0; 713 __u64 old_delta = 0; 714 int time_backwards = 0; 715 int count_var = 0; 716 int count_mod = 0; 717 718 /* We could perform statistical tests here, but the problem is 719 * that we only have a few loop counts to do testing. These 720 * loop counts may show some slight skew and we produce 721 * false positives. 722 * 723 * Moreover, only old systems show potentially problematic 724 * jitter entropy that could potentially be caught here. But 725 * the RNG is intended for hardware that is available or widely 726 * used, but not old systems that are long out of favor. Thus, 727 * no statistical tests. 728 */ 729 730 /* 731 * We could add a check for system capabilities such as clock_getres or 732 * check for CONFIG_X86_TSC, but it does not make much sense as the 733 * following sanity checks verify that we have a high-resolution 734 * timer. 735 */ 736 /* 737 * TESTLOOPCOUNT needs some loops to identify edge systems. 100 is 738 * definitely too little. 739 */ 740 #define TESTLOOPCOUNT 300 741 #define CLEARCACHE 100 742 for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) { 743 __u64 time = 0; 744 __u64 time2 = 0; 745 __u64 folded = 0; 746 __u64 delta = 0; 747 unsigned int lowdelta = 0; 748 749 jent_get_nstime(&time); 750 jent_fold_time(NULL, time, &folded, 1<<MIN_FOLD_LOOP_BIT); 751 jent_get_nstime(&time2); 752 753 /* test whether timer works */ 754 if (!time || !time2) 755 return JENT_ENOTIME; 756 delta = time2 - time; 757 /* 758 * test whether timer is fine grained enough to provide 759 * delta even when called shortly after each other -- this 760 * implies that we also have a high resolution timer 761 */ 762 if (!delta) 763 return JENT_ECOARSETIME; 764 765 /* 766 * up to here we did not modify any variable that will be 767 * evaluated later, but we already performed some work. Thus we 768 * already have had an impact on the caches, branch prediction, 769 * etc. with the goal to clear it to get the worst case 770 * measurements. 771 */ 772 if (CLEARCACHE > i) 773 continue; 774 775 /* test whether we have an increasing timer */ 776 if (!(time2 > time)) 777 time_backwards++; 778 779 /* 780 * Avoid modulo of 64 bit integer to allow code to compile 781 * on 32 bit architectures. 782 */ 783 lowdelta = time2 - time; 784 if (!(lowdelta % 100)) 785 count_mod++; 786 787 /* 788 * ensure that we have a varying delta timer which is necessary 789 * for the calculation of entropy -- perform this check 790 * only after the first loop is executed as we need to prime 791 * the old_data value 792 */ 793 if (i) { 794 if (delta != old_delta) 795 count_var++; 796 if (delta > old_delta) 797 delta_sum += (delta - old_delta); 798 else 799 delta_sum += (old_delta - delta); 800 } 801 old_delta = delta; 802 } 803 804 /* 805 * we allow up to three times the time running backwards. 806 * CLOCK_REALTIME is affected by adjtime and NTP operations. Thus, 807 * if such an operation just happens to interfere with our test, it 808 * should not fail. The value of 3 should cover the NTP case being 809 * performed during our test run. 810 */ 811 if (3 < time_backwards) 812 return JENT_ENOMONOTONIC; 813 /* Error if the time variances are always identical */ 814 if (!delta_sum) 815 return JENT_EVARVAR; 816 817 /* 818 * Variations of deltas of time must on average be larger 819 * than 1 to ensure the entropy estimation 820 * implied with 1 is preserved 821 */ 822 if (delta_sum <= 1) 823 return JENT_EMINVARVAR; 824 825 /* 826 * Ensure that we have variations in the time stamp below 10 for at 827 * least 10% of all checks -- on some platforms, the counter 828 * increments in multiples of 100, but not always 829 */ 830 if ((TESTLOOPCOUNT/10 * 9) < count_mod) 831 return JENT_ECOARSETIME; 832 833 return 0; 834 } 835 836 /*************************************************************************** 837 * Kernel crypto API interface 838 ***************************************************************************/ 839 840 struct jitterentropy { 841 spinlock_t jent_lock; 842 struct rand_data *entropy_collector; 843 }; 844 845 static int jent_kcapi_init(struct crypto_tfm *tfm) 846 { 847 struct jitterentropy *rng = crypto_tfm_ctx(tfm); 848 int ret = 0; 849 850 rng->entropy_collector = jent_entropy_collector_alloc(1, 0); 851 if (!rng->entropy_collector) 852 ret = -ENOMEM; 853 854 spin_lock_init(&rng->jent_lock); 855 return ret; 856 } 857 858 static void jent_kcapi_cleanup(struct crypto_tfm *tfm) 859 { 860 struct jitterentropy *rng = crypto_tfm_ctx(tfm); 861 862 spin_lock(&rng->jent_lock); 863 if (rng->entropy_collector) 864 jent_entropy_collector_free(rng->entropy_collector); 865 rng->entropy_collector = NULL; 866 spin_unlock(&rng->jent_lock); 867 } 868 869 static int jent_kcapi_random(struct crypto_rng *tfm, 870 const u8 *src, unsigned int slen, 871 u8 *rdata, unsigned int dlen) 872 { 873 struct jitterentropy *rng = crypto_rng_ctx(tfm); 874 int ret = 0; 875 876 spin_lock(&rng->jent_lock); 877 ret = jent_read_entropy(rng->entropy_collector, rdata, dlen); 878 spin_unlock(&rng->jent_lock); 879 880 return ret; 881 } 882 883 static int jent_kcapi_reset(struct crypto_rng *tfm, 884 const u8 *seed, unsigned int slen) 885 { 886 return 0; 887 } 888 889 static struct rng_alg jent_alg = { 890 .generate = jent_kcapi_random, 891 .seed = jent_kcapi_reset, 892 .seedsize = 0, 893 .base = { 894 .cra_name = "jitterentropy_rng", 895 .cra_driver_name = "jitterentropy_rng", 896 .cra_priority = 100, 897 .cra_ctxsize = sizeof(struct jitterentropy), 898 .cra_module = THIS_MODULE, 899 .cra_init = jent_kcapi_init, 900 .cra_exit = jent_kcapi_cleanup, 901 902 } 903 }; 904 905 static int __init jent_mod_init(void) 906 { 907 int ret = 0; 908 909 ret = jent_entropy_init(); 910 if (ret) { 911 pr_info(DRIVER_NAME ": Initialization failed with host not compliant with requirements: %d\n", ret); 912 return -EFAULT; 913 } 914 return crypto_register_rng(&jent_alg); 915 } 916 917 static void __exit jent_mod_exit(void) 918 { 919 crypto_unregister_rng(&jent_alg); 920 } 921 922 module_init(jent_mod_init); 923 module_exit(jent_mod_exit); 924 925 MODULE_LICENSE("Dual BSD/GPL"); 926 MODULE_AUTHOR("Stephan Mueller <smueller@chronox.de>"); 927 MODULE_DESCRIPTION("Non-physical True Random Number Generator based on CPU Jitter"); 928 MODULE_ALIAS_CRYPTO("jitterentropy_rng"); 929