1 /* 2 * Non-physical true random number generator based on timing jitter -- 3 * Jitter RNG standalone code. 4 * 5 * Copyright Stephan Mueller <smueller@chronox.de>, 2015 - 2019 6 * 7 * Design 8 * ====== 9 * 10 * See http://www.chronox.de/jent.html 11 * 12 * License 13 * ======= 14 * 15 * Redistribution and use in source and binary forms, with or without 16 * modification, are permitted provided that the following conditions 17 * are met: 18 * 1. Redistributions of source code must retain the above copyright 19 * notice, and the entire permission notice in its entirety, 20 * including the disclaimer of warranties. 21 * 2. Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution. 24 * 3. The name of the author may not be used to endorse or promote 25 * products derived from this software without specific prior 26 * written permission. 27 * 28 * ALTERNATIVELY, this product may be distributed under the terms of 29 * the GNU General Public License, in which case the provisions of the GPL2 are 30 * required INSTEAD OF the above restrictions. (This clause is 31 * necessary due to a potential bad interaction between the GPL and 32 * the restrictions contained in a BSD-style copyright.) 33 * 34 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED 35 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 36 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF 37 * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE 38 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 39 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 40 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 41 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 42 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 43 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 44 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH 45 * DAMAGE. 46 */ 47 48 /* 49 * This Jitterentropy RNG is based on the jitterentropy library 50 * version 2.1.2 provided at http://www.chronox.de/jent.html 51 */ 52 53 #ifdef __OPTIMIZE__ 54 #error "The CPU Jitter random number generator must not be compiled with optimizations. See documentation. Use the compiler switch -O0 for compiling jitterentropy.c." 55 #endif 56 57 typedef unsigned long long __u64; 58 typedef long long __s64; 59 typedef unsigned int __u32; 60 #define NULL ((void *) 0) 61 62 /* The entropy pool */ 63 struct rand_data { 64 /* all data values that are vital to maintain the security 65 * of the RNG are marked as SENSITIVE. A user must not 66 * access that information while the RNG executes its loops to 67 * calculate the next random value. */ 68 __u64 data; /* SENSITIVE Actual random number */ 69 __u64 old_data; /* SENSITIVE Previous random number */ 70 __u64 prev_time; /* SENSITIVE Previous time stamp */ 71 #define DATA_SIZE_BITS ((sizeof(__u64)) * 8) 72 __u64 last_delta; /* SENSITIVE stuck test */ 73 __s64 last_delta2; /* SENSITIVE stuck test */ 74 unsigned int osr; /* Oversample rate */ 75 #define JENT_MEMORY_BLOCKS 64 76 #define JENT_MEMORY_BLOCKSIZE 32 77 #define JENT_MEMORY_ACCESSLOOPS 128 78 #define JENT_MEMORY_SIZE (JENT_MEMORY_BLOCKS*JENT_MEMORY_BLOCKSIZE) 79 unsigned char *mem; /* Memory access location with size of 80 * memblocks * memblocksize */ 81 unsigned int memlocation; /* Pointer to byte in *mem */ 82 unsigned int memblocks; /* Number of memory blocks in *mem */ 83 unsigned int memblocksize; /* Size of one memory block in bytes */ 84 unsigned int memaccessloops; /* Number of memory accesses per random 85 * bit generation */ 86 }; 87 88 /* Flags that can be used to initialize the RNG */ 89 #define JENT_DISABLE_MEMORY_ACCESS (1<<2) /* Disable memory access for more 90 * entropy, saves MEMORY_SIZE RAM for 91 * entropy collector */ 92 93 /* -- error codes for init function -- */ 94 #define JENT_ENOTIME 1 /* Timer service not available */ 95 #define JENT_ECOARSETIME 2 /* Timer too coarse for RNG */ 96 #define JENT_ENOMONOTONIC 3 /* Timer is not monotonic increasing */ 97 #define JENT_EVARVAR 5 /* Timer does not produce variations of 98 * variations (2nd derivation of time is 99 * zero). */ 100 #define JENT_ESTUCK 8 /* Too many stuck results during init. */ 101 102 /*************************************************************************** 103 * Helper functions 104 ***************************************************************************/ 105 106 void jent_get_nstime(__u64 *out); 107 void *jent_zalloc(unsigned int len); 108 void jent_zfree(void *ptr); 109 int jent_fips_enabled(void); 110 void jent_panic(char *s); 111 void jent_memcpy(void *dest, const void *src, unsigned int n); 112 113 /** 114 * Update of the loop count used for the next round of 115 * an entropy collection. 116 * 117 * Input: 118 * @ec entropy collector struct -- may be NULL 119 * @bits is the number of low bits of the timer to consider 120 * @min is the number of bits we shift the timer value to the right at 121 * the end to make sure we have a guaranteed minimum value 122 * 123 * @return Newly calculated loop counter 124 */ 125 static __u64 jent_loop_shuffle(struct rand_data *ec, 126 unsigned int bits, unsigned int min) 127 { 128 __u64 time = 0; 129 __u64 shuffle = 0; 130 unsigned int i = 0; 131 unsigned int mask = (1<<bits) - 1; 132 133 jent_get_nstime(&time); 134 /* 135 * Mix the current state of the random number into the shuffle 136 * calculation to balance that shuffle a bit more. 137 */ 138 if (ec) 139 time ^= ec->data; 140 /* 141 * We fold the time value as much as possible to ensure that as many 142 * bits of the time stamp are included as possible. 143 */ 144 for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) { 145 shuffle ^= time & mask; 146 time = time >> bits; 147 } 148 149 /* 150 * We add a lower boundary value to ensure we have a minimum 151 * RNG loop count. 152 */ 153 return (shuffle + (1<<min)); 154 } 155 156 /*************************************************************************** 157 * Noise sources 158 ***************************************************************************/ 159 160 /** 161 * CPU Jitter noise source -- this is the noise source based on the CPU 162 * execution time jitter 163 * 164 * This function injects the individual bits of the time value into the 165 * entropy pool using an LFSR. 166 * 167 * The code is deliberately inefficient with respect to the bit shifting 168 * and shall stay that way. This function is the root cause why the code 169 * shall be compiled without optimization. This function not only acts as 170 * folding operation, but this function's execution is used to measure 171 * the CPU execution time jitter. Any change to the loop in this function 172 * implies that careful retesting must be done. 173 * 174 * Input: 175 * @ec entropy collector struct -- may be NULL 176 * @time time stamp to be injected 177 * @loop_cnt if a value not equal to 0 is set, use the given value as number of 178 * loops to perform the folding 179 * 180 * Output: 181 * updated ec->data 182 * 183 * @return Number of loops the folding operation is performed 184 */ 185 static __u64 jent_lfsr_time(struct rand_data *ec, __u64 time, __u64 loop_cnt) 186 { 187 unsigned int i; 188 __u64 j = 0; 189 __u64 new = 0; 190 #define MAX_FOLD_LOOP_BIT 4 191 #define MIN_FOLD_LOOP_BIT 0 192 __u64 fold_loop_cnt = 193 jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT); 194 195 /* 196 * testing purposes -- allow test app to set the counter, not 197 * needed during runtime 198 */ 199 if (loop_cnt) 200 fold_loop_cnt = loop_cnt; 201 for (j = 0; j < fold_loop_cnt; j++) { 202 new = ec->data; 203 for (i = 1; (DATA_SIZE_BITS) >= i; i++) { 204 __u64 tmp = time << (DATA_SIZE_BITS - i); 205 206 tmp = tmp >> (DATA_SIZE_BITS - 1); 207 208 /* 209 * Fibonacci LSFR with polynomial of 210 * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is 211 * primitive according to 212 * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf 213 * (the shift values are the polynomial values minus one 214 * due to counting bits from 0 to 63). As the current 215 * position is always the LSB, the polynomial only needs 216 * to shift data in from the left without wrap. 217 */ 218 tmp ^= ((new >> 63) & 1); 219 tmp ^= ((new >> 60) & 1); 220 tmp ^= ((new >> 55) & 1); 221 tmp ^= ((new >> 30) & 1); 222 tmp ^= ((new >> 27) & 1); 223 tmp ^= ((new >> 22) & 1); 224 new <<= 1; 225 new ^= tmp; 226 } 227 } 228 ec->data = new; 229 230 return fold_loop_cnt; 231 } 232 233 /** 234 * Memory Access noise source -- this is a noise source based on variations in 235 * memory access times 236 * 237 * This function performs memory accesses which will add to the timing 238 * variations due to an unknown amount of CPU wait states that need to be 239 * added when accessing memory. The memory size should be larger than the L1 240 * caches as outlined in the documentation and the associated testing. 241 * 242 * The L1 cache has a very high bandwidth, albeit its access rate is usually 243 * slower than accessing CPU registers. Therefore, L1 accesses only add minimal 244 * variations as the CPU has hardly to wait. Starting with L2, significant 245 * variations are added because L2 typically does not belong to the CPU any more 246 * and therefore a wider range of CPU wait states is necessary for accesses. 247 * L3 and real memory accesses have even a wider range of wait states. However, 248 * to reliably access either L3 or memory, the ec->mem memory must be quite 249 * large which is usually not desirable. 250 * 251 * Input: 252 * @ec Reference to the entropy collector with the memory access data -- if 253 * the reference to the memory block to be accessed is NULL, this noise 254 * source is disabled 255 * @loop_cnt if a value not equal to 0 is set, use the given value as number of 256 * loops to perform the folding 257 * 258 * @return Number of memory access operations 259 */ 260 static unsigned int jent_memaccess(struct rand_data *ec, __u64 loop_cnt) 261 { 262 unsigned int wrap = 0; 263 __u64 i = 0; 264 #define MAX_ACC_LOOP_BIT 7 265 #define MIN_ACC_LOOP_BIT 0 266 __u64 acc_loop_cnt = 267 jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT); 268 269 if (NULL == ec || NULL == ec->mem) 270 return 0; 271 wrap = ec->memblocksize * ec->memblocks; 272 273 /* 274 * testing purposes -- allow test app to set the counter, not 275 * needed during runtime 276 */ 277 if (loop_cnt) 278 acc_loop_cnt = loop_cnt; 279 280 for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) { 281 unsigned char *tmpval = ec->mem + ec->memlocation; 282 /* 283 * memory access: just add 1 to one byte, 284 * wrap at 255 -- memory access implies read 285 * from and write to memory location 286 */ 287 *tmpval = (*tmpval + 1) & 0xff; 288 /* 289 * Addition of memblocksize - 1 to pointer 290 * with wrap around logic to ensure that every 291 * memory location is hit evenly 292 */ 293 ec->memlocation = ec->memlocation + ec->memblocksize - 1; 294 ec->memlocation = ec->memlocation % wrap; 295 } 296 return i; 297 } 298 299 /*************************************************************************** 300 * Start of entropy processing logic 301 ***************************************************************************/ 302 303 /** 304 * Stuck test by checking the: 305 * 1st derivation of the jitter measurement (time delta) 306 * 2nd derivation of the jitter measurement (delta of time deltas) 307 * 3rd derivation of the jitter measurement (delta of delta of time deltas) 308 * 309 * All values must always be non-zero. 310 * 311 * Input: 312 * @ec Reference to entropy collector 313 * @current_delta Jitter time delta 314 * 315 * @return 316 * 0 jitter measurement not stuck (good bit) 317 * 1 jitter measurement stuck (reject bit) 318 */ 319 static int jent_stuck(struct rand_data *ec, __u64 current_delta) 320 { 321 __s64 delta2 = ec->last_delta - current_delta; 322 __s64 delta3 = delta2 - ec->last_delta2; 323 324 ec->last_delta = current_delta; 325 ec->last_delta2 = delta2; 326 327 if (!current_delta || !delta2 || !delta3) 328 return 1; 329 330 return 0; 331 } 332 333 /** 334 * This is the heart of the entropy generation: calculate time deltas and 335 * use the CPU jitter in the time deltas. The jitter is injected into the 336 * entropy pool. 337 * 338 * WARNING: ensure that ->prev_time is primed before using the output 339 * of this function! This can be done by calling this function 340 * and not using its result. 341 * 342 * Input: 343 * @entropy_collector Reference to entropy collector 344 * 345 * @return result of stuck test 346 */ 347 static int jent_measure_jitter(struct rand_data *ec) 348 { 349 __u64 time = 0; 350 __u64 current_delta = 0; 351 352 /* Invoke one noise source before time measurement to add variations */ 353 jent_memaccess(ec, 0); 354 355 /* 356 * Get time stamp and calculate time delta to previous 357 * invocation to measure the timing variations 358 */ 359 jent_get_nstime(&time); 360 current_delta = time - ec->prev_time; 361 ec->prev_time = time; 362 363 /* Now call the next noise sources which also injects the data */ 364 jent_lfsr_time(ec, current_delta, 0); 365 366 /* Check whether we have a stuck measurement. */ 367 return jent_stuck(ec, current_delta); 368 } 369 370 /** 371 * Generator of one 64 bit random number 372 * Function fills rand_data->data 373 * 374 * Input: 375 * @ec Reference to entropy collector 376 */ 377 static void jent_gen_entropy(struct rand_data *ec) 378 { 379 unsigned int k = 0; 380 381 /* priming of the ->prev_time value */ 382 jent_measure_jitter(ec); 383 384 while (1) { 385 /* If a stuck measurement is received, repeat measurement */ 386 if (jent_measure_jitter(ec)) 387 continue; 388 389 /* 390 * We multiply the loop value with ->osr to obtain the 391 * oversampling rate requested by the caller 392 */ 393 if (++k >= (DATA_SIZE_BITS * ec->osr)) 394 break; 395 } 396 } 397 398 /** 399 * The continuous test required by FIPS 140-2 -- the function automatically 400 * primes the test if needed. 401 * 402 * Return: 403 * 0 if FIPS test passed 404 * < 0 if FIPS test failed 405 */ 406 static void jent_fips_test(struct rand_data *ec) 407 { 408 if (!jent_fips_enabled()) 409 return; 410 411 /* prime the FIPS test */ 412 if (!ec->old_data) { 413 ec->old_data = ec->data; 414 jent_gen_entropy(ec); 415 } 416 417 if (ec->data == ec->old_data) 418 jent_panic("jitterentropy: Duplicate output detected\n"); 419 420 ec->old_data = ec->data; 421 } 422 423 /** 424 * Entry function: Obtain entropy for the caller. 425 * 426 * This function invokes the entropy gathering logic as often to generate 427 * as many bytes as requested by the caller. The entropy gathering logic 428 * creates 64 bit per invocation. 429 * 430 * This function truncates the last 64 bit entropy value output to the exact 431 * size specified by the caller. 432 * 433 * Input: 434 * @ec Reference to entropy collector 435 * @data pointer to buffer for storing random data -- buffer must already 436 * exist 437 * @len size of the buffer, specifying also the requested number of random 438 * in bytes 439 * 440 * @return 0 when request is fulfilled or an error 441 * 442 * The following error codes can occur: 443 * -1 entropy_collector is NULL 444 */ 445 int jent_read_entropy(struct rand_data *ec, unsigned char *data, 446 unsigned int len) 447 { 448 unsigned char *p = data; 449 450 if (!ec) 451 return -1; 452 453 while (0 < len) { 454 unsigned int tocopy; 455 456 jent_gen_entropy(ec); 457 jent_fips_test(ec); 458 if ((DATA_SIZE_BITS / 8) < len) 459 tocopy = (DATA_SIZE_BITS / 8); 460 else 461 tocopy = len; 462 jent_memcpy(p, &ec->data, tocopy); 463 464 len -= tocopy; 465 p += tocopy; 466 } 467 468 return 0; 469 } 470 471 /*************************************************************************** 472 * Initialization logic 473 ***************************************************************************/ 474 475 struct rand_data *jent_entropy_collector_alloc(unsigned int osr, 476 unsigned int flags) 477 { 478 struct rand_data *entropy_collector; 479 480 entropy_collector = jent_zalloc(sizeof(struct rand_data)); 481 if (!entropy_collector) 482 return NULL; 483 484 if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) { 485 /* Allocate memory for adding variations based on memory 486 * access 487 */ 488 entropy_collector->mem = jent_zalloc(JENT_MEMORY_SIZE); 489 if (!entropy_collector->mem) { 490 jent_zfree(entropy_collector); 491 return NULL; 492 } 493 entropy_collector->memblocksize = JENT_MEMORY_BLOCKSIZE; 494 entropy_collector->memblocks = JENT_MEMORY_BLOCKS; 495 entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS; 496 } 497 498 /* verify and set the oversampling rate */ 499 if (0 == osr) 500 osr = 1; /* minimum sampling rate is 1 */ 501 entropy_collector->osr = osr; 502 503 /* fill the data pad with non-zero values */ 504 jent_gen_entropy(entropy_collector); 505 506 return entropy_collector; 507 } 508 509 void jent_entropy_collector_free(struct rand_data *entropy_collector) 510 { 511 jent_zfree(entropy_collector->mem); 512 entropy_collector->mem = NULL; 513 jent_zfree(entropy_collector); 514 } 515 516 int jent_entropy_init(void) 517 { 518 int i; 519 __u64 delta_sum = 0; 520 __u64 old_delta = 0; 521 int time_backwards = 0; 522 int count_mod = 0; 523 int count_stuck = 0; 524 struct rand_data ec = { 0 }; 525 526 /* We could perform statistical tests here, but the problem is 527 * that we only have a few loop counts to do testing. These 528 * loop counts may show some slight skew and we produce 529 * false positives. 530 * 531 * Moreover, only old systems show potentially problematic 532 * jitter entropy that could potentially be caught here. But 533 * the RNG is intended for hardware that is available or widely 534 * used, but not old systems that are long out of favor. Thus, 535 * no statistical tests. 536 */ 537 538 /* 539 * We could add a check for system capabilities such as clock_getres or 540 * check for CONFIG_X86_TSC, but it does not make much sense as the 541 * following sanity checks verify that we have a high-resolution 542 * timer. 543 */ 544 /* 545 * TESTLOOPCOUNT needs some loops to identify edge systems. 100 is 546 * definitely too little. 547 */ 548 #define TESTLOOPCOUNT 300 549 #define CLEARCACHE 100 550 for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) { 551 __u64 time = 0; 552 __u64 time2 = 0; 553 __u64 delta = 0; 554 unsigned int lowdelta = 0; 555 int stuck; 556 557 /* Invoke core entropy collection logic */ 558 jent_get_nstime(&time); 559 ec.prev_time = time; 560 jent_lfsr_time(&ec, time, 0); 561 jent_get_nstime(&time2); 562 563 /* test whether timer works */ 564 if (!time || !time2) 565 return JENT_ENOTIME; 566 delta = time2 - time; 567 /* 568 * test whether timer is fine grained enough to provide 569 * delta even when called shortly after each other -- this 570 * implies that we also have a high resolution timer 571 */ 572 if (!delta) 573 return JENT_ECOARSETIME; 574 575 stuck = jent_stuck(&ec, delta); 576 577 /* 578 * up to here we did not modify any variable that will be 579 * evaluated later, but we already performed some work. Thus we 580 * already have had an impact on the caches, branch prediction, 581 * etc. with the goal to clear it to get the worst case 582 * measurements. 583 */ 584 if (CLEARCACHE > i) 585 continue; 586 587 if (stuck) 588 count_stuck++; 589 590 /* test whether we have an increasing timer */ 591 if (!(time2 > time)) 592 time_backwards++; 593 594 /* use 32 bit value to ensure compilation on 32 bit arches */ 595 lowdelta = time2 - time; 596 if (!(lowdelta % 100)) 597 count_mod++; 598 599 /* 600 * ensure that we have a varying delta timer which is necessary 601 * for the calculation of entropy -- perform this check 602 * only after the first loop is executed as we need to prime 603 * the old_data value 604 */ 605 if (delta > old_delta) 606 delta_sum += (delta - old_delta); 607 else 608 delta_sum += (old_delta - delta); 609 old_delta = delta; 610 } 611 612 /* 613 * we allow up to three times the time running backwards. 614 * CLOCK_REALTIME is affected by adjtime and NTP operations. Thus, 615 * if such an operation just happens to interfere with our test, it 616 * should not fail. The value of 3 should cover the NTP case being 617 * performed during our test run. 618 */ 619 if (3 < time_backwards) 620 return JENT_ENOMONOTONIC; 621 622 /* 623 * Variations of deltas of time must on average be larger 624 * than 1 to ensure the entropy estimation 625 * implied with 1 is preserved 626 */ 627 if ((delta_sum) <= 1) 628 return JENT_EVARVAR; 629 630 /* 631 * Ensure that we have variations in the time stamp below 10 for at 632 * least 10% of all checks -- on some platforms, the counter increments 633 * in multiples of 100, but not always 634 */ 635 if ((TESTLOOPCOUNT/10 * 9) < count_mod) 636 return JENT_ECOARSETIME; 637 638 /* 639 * If we have more than 90% stuck results, then this Jitter RNG is 640 * likely to not work well. 641 */ 642 if ((TESTLOOPCOUNT/10 * 9) < count_stuck) 643 return JENT_ESTUCK; 644 645 return 0; 646 } 647