crypto/jitterentropy.c

   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");