jitterentropy.c (50282fd57bcd3525c9d81eef58df8718e4337c6d) jitterentropy.c (bb897c55042e9330bcf88b4b13cbdd6f9fabdd5e)
1/*
2 * Non-physical true random number generator based on timing jitter --
3 * Jitter RNG standalone code.
4 *
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 - 2020
5 * Copyright Stephan Mueller <smueller@chronox.de>, 2015 - 2023
6 *
7 * Design
8 * ======
9 *
10 * See https://www.chronox.de/jent.html
11 *
12 * License
13 * =======

--- 28 unchanged lines hidden (view full) ---

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
6 *
7 * Design
8 * ======
9 *
10 * See https://www.chronox.de/jent.html
11 *
12 * License
13 * =======

--- 28 unchanged lines hidden (view full) ---

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.2.0 provided at https://www.chronox.de/jent.html
50 * version 3.4.0 provided at https://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
57typedef unsigned long long __u64;
58typedef long long __s64;
59typedef unsigned int __u32;
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
57typedef unsigned long long __u64;
58typedef long long __s64;
59typedef unsigned int __u32;
60typedef unsigned char u8;
60#define NULL ((void *) 0)
61
62/* The entropy pool */
63struct rand_data {
61#define NULL ((void *) 0)
62
63/* The entropy pool */
64struct rand_data {
65 /* SHA3-256 is used as conditioner */
66#define DATA_SIZE_BITS 256
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. */
67 /* all data values that are vital to maintain the security
68 * of the RNG are marked as SENSITIVE. A user must not
69 * access that information while the RNG executes its loops to
70 * 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 */
71 void *hash_state; /* SENSITIVE hash state entropy pool */
72 __u64 prev_time; /* SENSITIVE Previous time stamp */
73 __u64 last_delta; /* SENSITIVE stuck test */
74 __s64 last_delta2; /* SENSITIVE stuck test */
75 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 */

--- 214 unchanged lines hidden (view full) ---

297 * Noise sources
298 ***************************************************************************/
299
300/*
301 * Update of the loop count used for the next round of
302 * an entropy collection.
303 *
304 * Input:
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 */

--- 214 unchanged lines hidden (view full) ---

298 * Noise sources
299 ***************************************************************************/
300
301/*
302 * Update of the loop count used for the next round of
303 * an entropy collection.
304 *
305 * Input:
305 * @ec entropy collector struct -- may be NULL
306 * @bits is the number of low bits of the timer to consider
307 * @min is the number of bits we shift the timer value to the right at
308 * the end to make sure we have a guaranteed minimum value
309 *
310 * @return Newly calculated loop counter
311 */
306 * @bits is the number of low bits of the timer to consider
307 * @min is the number of bits we shift the timer value to the right at
308 * the end to make sure we have a guaranteed minimum value
309 *
310 * @return Newly calculated loop counter
311 */
312static __u64 jent_loop_shuffle(struct rand_data *ec,
313 unsigned int bits, unsigned int min)
312static __u64 jent_loop_shuffle(unsigned int bits, unsigned int min)
314{
315 __u64 time = 0;
316 __u64 shuffle = 0;
317 unsigned int i = 0;
318 unsigned int mask = (1<<bits) - 1;
319
320 jent_get_nstime(&time);
313{
314 __u64 time = 0;
315 __u64 shuffle = 0;
316 unsigned int i = 0;
317 unsigned int mask = (1<<bits) - 1;
318
319 jent_get_nstime(&time);
320
321 /*
321 /*
322 * Mix the current state of the random number into the shuffle
323 * calculation to balance that shuffle a bit more.
324 */
325 if (ec)
326 time ^= ec->data;
327 /*
328 * We fold the time value as much as possible to ensure that as many
329 * bits of the time stamp are included as possible.
330 */
331 for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) {
332 shuffle ^= time & mask;
333 time = time >> bits;
334 }
335

--- 4 unchanged lines hidden (view full) ---

340 return (shuffle + (1<<min));
341}
342
343/*
344 * CPU Jitter noise source -- this is the noise source based on the CPU
345 * execution time jitter
346 *
347 * This function injects the individual bits of the time value into the
322 * We fold the time value as much as possible to ensure that as many
323 * bits of the time stamp are included as possible.
324 */
325 for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) {
326 shuffle ^= time & mask;
327 time = time >> bits;
328 }
329

--- 4 unchanged lines hidden (view full) ---

334 return (shuffle + (1<<min));
335}
336
337/*
338 * CPU Jitter noise source -- this is the noise source based on the CPU
339 * execution time jitter
340 *
341 * This function injects the individual bits of the time value into the
348 * entropy pool using an LFSR.
342 * entropy pool using a hash.
349 *
343 *
350 * The code is deliberately inefficient with respect to the bit shifting
351 * and shall stay that way. This function is the root cause why the code
352 * shall be compiled without optimization. This function not only acts as
353 * folding operation, but this function's execution is used to measure
354 * the CPU execution time jitter. Any change to the loop in this function
355 * implies that careful retesting must be done.
344 * ec [in] entropy collector
345 * time [in] time stamp to be injected
346 * stuck [in] Is the time stamp identified as stuck?
356 *
347 *
357 * @ec [in] entropy collector struct
358 * @time [in] time stamp to be injected
359 * @loop_cnt [in] if a value not equal to 0 is set, use the given value as
360 * number of loops to perform the folding
361 * @stuck [in] Is the time stamp identified as stuck?
362 *
363 * Output:
348 * Output:
364 * updated ec->data
365 *
366 * @return Number of loops the folding operation is performed
349 * updated hash context in the entropy collector or error code
367 */
350 */
368static void jent_lfsr_time(struct rand_data *ec, __u64 time, __u64 loop_cnt,
369 int stuck)
351static int jent_condition_data(struct rand_data *ec, __u64 time, int stuck)
370{
352{
371 unsigned int i;
372 __u64 j = 0;
373 __u64 new = 0;
374#define MAX_FOLD_LOOP_BIT 4
375#define MIN_FOLD_LOOP_BIT 0
376 __u64 fold_loop_cnt =
377 jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT);
353#define SHA3_HASH_LOOP (1<<3)
354 struct {
355 int rct_count;
356 unsigned int apt_observations;
357 unsigned int apt_count;
358 unsigned int apt_base;
359 } addtl = {
360 ec->rct_count,
361 ec->apt_observations,
362 ec->apt_count,
363 ec->apt_base
364 };
378
365
379 /*
380 * testing purposes -- allow test app to set the counter, not
381 * needed during runtime
382 */
383 if (loop_cnt)
384 fold_loop_cnt = loop_cnt;
385 for (j = 0; j < fold_loop_cnt; j++) {
386 new = ec->data;
387 for (i = 1; (DATA_SIZE_BITS) >= i; i++) {
388 __u64 tmp = time << (DATA_SIZE_BITS - i);
389
390 tmp = tmp >> (DATA_SIZE_BITS - 1);
391
392 /*
393 * Fibonacci LSFR with polynomial of
394 * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is
395 * primitive according to
396 * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf
397 * (the shift values are the polynomial values minus one
398 * due to counting bits from 0 to 63). As the current
399 * position is always the LSB, the polynomial only needs
400 * to shift data in from the left without wrap.
401 */
402 tmp ^= ((new >> 63) & 1);
403 tmp ^= ((new >> 60) & 1);
404 tmp ^= ((new >> 55) & 1);
405 tmp ^= ((new >> 30) & 1);
406 tmp ^= ((new >> 27) & 1);
407 tmp ^= ((new >> 22) & 1);
408 new <<= 1;
409 new ^= tmp;
410 }
411 }
412
413 /*
414 * If the time stamp is stuck, do not finally insert the value into
415 * the entropy pool. Although this operation should not do any harm
416 * even when the time stamp has no entropy, SP800-90B requires that
417 * any conditioning operation (SP800-90B considers the LFSR to be a
418 * conditioning operation) to have an identical amount of input
419 * data according to section 3.1.5.
420 */
421 if (!stuck)
422 ec->data = new;
366 return jent_hash_time(ec->hash_state, time, (u8 *)&addtl, sizeof(addtl),
367 SHA3_HASH_LOOP, stuck);
423}
424
425/*
426 * Memory Access noise source -- this is a noise source based on variations in
427 * memory access times
428 *
429 * This function performs memory accesses which will add to the timing
430 * variations due to an unknown amount of CPU wait states that need to be

--- 17 unchanged lines hidden (view full) ---

448 */
449static void jent_memaccess(struct rand_data *ec, __u64 loop_cnt)
450{
451 unsigned int wrap = 0;
452 __u64 i = 0;
453#define MAX_ACC_LOOP_BIT 7
454#define MIN_ACC_LOOP_BIT 0
455 __u64 acc_loop_cnt =
368}
369
370/*
371 * Memory Access noise source -- this is a noise source based on variations in
372 * memory access times
373 *
374 * This function performs memory accesses which will add to the timing
375 * variations due to an unknown amount of CPU wait states that need to be

--- 17 unchanged lines hidden (view full) ---

393 */
394static void jent_memaccess(struct rand_data *ec, __u64 loop_cnt)
395{
396 unsigned int wrap = 0;
397 __u64 i = 0;
398#define MAX_ACC_LOOP_BIT 7
399#define MIN_ACC_LOOP_BIT 0
400 __u64 acc_loop_cnt =
456 jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT);
401 jent_loop_shuffle(MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT);
457
458 if (NULL == ec || NULL == ec->mem)
459 return;
460 wrap = ec->memblocksize * ec->memblocks;
461
462 /*
463 * testing purposes -- allow test app to set the counter, not
464 * needed during runtime

--- 51 unchanged lines hidden (view full) ---

516 jent_get_nstime(&time);
517 current_delta = jent_delta(ec->prev_time, time);
518 ec->prev_time = time;
519
520 /* Check whether we have a stuck measurement. */
521 stuck = jent_stuck(ec, current_delta);
522
523 /* Now call the next noise sources which also injects the data */
402
403 if (NULL == ec || NULL == ec->mem)
404 return;
405 wrap = ec->memblocksize * ec->memblocks;
406
407 /*
408 * testing purposes -- allow test app to set the counter, not
409 * needed during runtime

--- 51 unchanged lines hidden (view full) ---

461 jent_get_nstime(&time);
462 current_delta = jent_delta(ec->prev_time, time);
463 ec->prev_time = time;
464
465 /* Check whether we have a stuck measurement. */
466 stuck = jent_stuck(ec, current_delta);
467
468 /* Now call the next noise sources which also injects the data */
524 jent_lfsr_time(ec, current_delta, 0, stuck);
469 if (jent_condition_data(ec, current_delta, stuck))
470 stuck = 1;
525
526 return stuck;
527}
528
529/*
530 * Generator of one 64 bit random number
471
472 return stuck;
473}
474
475/*
476 * Generator of one 64 bit random number
531 * Function fills rand_data->data
477 * Function fills rand_data->hash_state
532 *
533 * @ec [in] Reference to entropy collector
534 */
535static void jent_gen_entropy(struct rand_data *ec)
536{
537 unsigned int k = 0, safety_factor = 0;
538
539 if (fips_enabled)

--- 30 unchanged lines hidden (view full) ---

570 * @data [in] pointer to buffer for storing random data -- buffer must already
571 * exist
572 * @len [in] size of the buffer, specifying also the requested number of random
573 * in bytes
574 *
575 * @return 0 when request is fulfilled or an error
576 *
577 * The following error codes can occur:
478 *
479 * @ec [in] Reference to entropy collector
480 */
481static void jent_gen_entropy(struct rand_data *ec)
482{
483 unsigned int k = 0, safety_factor = 0;
484
485 if (fips_enabled)

--- 30 unchanged lines hidden (view full) ---

516 * @data [in] pointer to buffer for storing random data -- buffer must already
517 * exist
518 * @len [in] size of the buffer, specifying also the requested number of random
519 * in bytes
520 *
521 * @return 0 when request is fulfilled or an error
522 *
523 * The following error codes can occur:
578 * -1 entropy_collector is NULL
524 * -1 entropy_collector is NULL or the generation failed
579 * -2 Intermittent health failure
580 * -3 Permanent health failure
581 */
582int jent_read_entropy(struct rand_data *ec, unsigned char *data,
583 unsigned int len)
584{
585 unsigned char *p = data;
586

--- 13 unchanged lines hidden (view full) ---

600 * is assumed to not further use this instance.
601 */
602 return -3;
603 } else if (jent_health_failure(ec)) {
604 /*
605 * Perform startup health tests and return permanent
606 * error if it fails.
607 */
525 * -2 Intermittent health failure
526 * -3 Permanent health failure
527 */
528int jent_read_entropy(struct rand_data *ec, unsigned char *data,
529 unsigned int len)
530{
531 unsigned char *p = data;
532

--- 13 unchanged lines hidden (view full) ---

546 * is assumed to not further use this instance.
547 */
548 return -3;
549 } else if (jent_health_failure(ec)) {
550 /*
551 * Perform startup health tests and return permanent
552 * error if it fails.
553 */
608 if (jent_entropy_init())
554 if (jent_entropy_init(ec->hash_state))
609 return -3;
610
611 return -2;
612 }
613
614 if ((DATA_SIZE_BITS / 8) < len)
615 tocopy = (DATA_SIZE_BITS / 8);
616 else
617 tocopy = len;
555 return -3;
556
557 return -2;
558 }
559
560 if ((DATA_SIZE_BITS / 8) < len)
561 tocopy = (DATA_SIZE_BITS / 8);
562 else
563 tocopy = len;
618 jent_memcpy(p, &ec->data, tocopy);
564 if (jent_read_random_block(ec->hash_state, p, tocopy))
565 return -1;
619
620 len -= tocopy;
621 p += tocopy;
622 }
623
624 return 0;
625}
626
627/***************************************************************************
628 * Initialization logic
629 ***************************************************************************/
630
631struct rand_data *jent_entropy_collector_alloc(unsigned int osr,
566
567 len -= tocopy;
568 p += tocopy;
569 }
570
571 return 0;
572}
573
574/***************************************************************************
575 * Initialization logic
576 ***************************************************************************/
577
578struct rand_data *jent_entropy_collector_alloc(unsigned int osr,
632 unsigned int flags)
579 unsigned int flags,
580 void *hash_state)
633{
634 struct rand_data *entropy_collector;
635
636 entropy_collector = jent_zalloc(sizeof(struct rand_data));
637 if (!entropy_collector)
638 return NULL;
639
640 if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) {

--- 10 unchanged lines hidden (view full) ---

651 entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS;
652 }
653
654 /* verify and set the oversampling rate */
655 if (osr == 0)
656 osr = 1; /* minimum sampling rate is 1 */
657 entropy_collector->osr = osr;
658
581{
582 struct rand_data *entropy_collector;
583
584 entropy_collector = jent_zalloc(sizeof(struct rand_data));
585 if (!entropy_collector)
586 return NULL;
587
588 if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) {

--- 10 unchanged lines hidden (view full) ---

599 entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS;
600 }
601
602 /* verify and set the oversampling rate */
603 if (osr == 0)
604 osr = 1; /* minimum sampling rate is 1 */
605 entropy_collector->osr = osr;
606
607 entropy_collector->hash_state = hash_state;
608
659 /* fill the data pad with non-zero values */
660 jent_gen_entropy(entropy_collector);
661
662 return entropy_collector;
663}
664
665void jent_entropy_collector_free(struct rand_data *entropy_collector)
666{
667 jent_zfree(entropy_collector->mem);
668 entropy_collector->mem = NULL;
669 jent_zfree(entropy_collector);
670}
671
609 /* fill the data pad with non-zero values */
610 jent_gen_entropy(entropy_collector);
611
612 return entropy_collector;
613}
614
615void jent_entropy_collector_free(struct rand_data *entropy_collector)
616{
617 jent_zfree(entropy_collector->mem);
618 entropy_collector->mem = NULL;
619 jent_zfree(entropy_collector);
620}
621
672int jent_entropy_init(void)
622int jent_entropy_init(void *hash_state)
673{
674 int i;
675 __u64 delta_sum = 0;
676 __u64 old_delta = 0;
677 unsigned int nonstuck = 0;
678 int time_backwards = 0;
679 int count_mod = 0;
680 int count_stuck = 0;
681 struct rand_data ec = { 0 };
682
683 /* Required for RCT */
684 ec.osr = 1;
623{
624 int i;
625 __u64 delta_sum = 0;
626 __u64 old_delta = 0;
627 unsigned int nonstuck = 0;
628 int time_backwards = 0;
629 int count_mod = 0;
630 int count_stuck = 0;
631 struct rand_data ec = { 0 };
632
633 /* Required for RCT */
634 ec.osr = 1;
635 ec.hash_state = hash_state;
685
686 /* We could perform statistical tests here, but the problem is
687 * that we only have a few loop counts to do testing. These
688 * loop counts may show some slight skew and we produce
689 * false positives.
690 *
691 * Moreover, only old systems show potentially problematic
692 * jitter entropy that could potentially be caught here. But

--- 21 unchanged lines hidden (view full) ---

714 __u64 time2 = 0;
715 __u64 delta = 0;
716 unsigned int lowdelta = 0;
717 int stuck;
718
719 /* Invoke core entropy collection logic */
720 jent_get_nstime(&time);
721 ec.prev_time = time;
636
637 /* We could perform statistical tests here, but the problem is
638 * that we only have a few loop counts to do testing. These
639 * loop counts may show some slight skew and we produce
640 * false positives.
641 *
642 * Moreover, only old systems show potentially problematic
643 * jitter entropy that could potentially be caught here. But

--- 21 unchanged lines hidden (view full) ---

665 __u64 time2 = 0;
666 __u64 delta = 0;
667 unsigned int lowdelta = 0;
668 int stuck;
669
670 /* Invoke core entropy collection logic */
671 jent_get_nstime(&time);
672 ec.prev_time = time;
722 jent_lfsr_time(&ec, time, 0, 0);
673 jent_condition_data(&ec, time, 0);
723 jent_get_nstime(&time2);
724
725 /* test whether timer works */
726 if (!time || !time2)
727 return JENT_ENOTIME;
728 delta = jent_delta(time, time2);
729 /*
730 * test whether timer is fine grained enough to provide

--- 100 unchanged lines hidden --- 		674 jent_get_nstime(&time2);
675
676 /* test whether timer works */
677 if (!time || !time2)
678 return JENT_ENOTIME;
679 delta = jent_delta(time, time2);
680 /*
681 * test whether timer is fine grained enough to provide

--- 100 unchanged lines hidden ---