jitterentropy.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855
  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
  6. *
  7. * Design
  8. * ======
  9. *
  10. * See https://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. * This Jitterentropy RNG is based on the jitterentropy library
  49. * version 2.2.0 provided at https://www.chronox.de/jent.html
  50. */
  51. #ifdef __OPTIMIZE__
  52. #error "The CPU Jitter random number generator must not be compiled with optimizations. See documentation. Use the compiler switch -O0 for compiling jitterentropy.c."
  53. #endif
  54. typedef unsigned long long __u64;
  55. typedef long long __s64;
  56. typedef unsigned int __u32;
  57. #define NULL ((void *) 0)
  58. /* The entropy pool */
  59. struct rand_data {
  60. /* all data values that are vital to maintain the security
  61. * of the RNG are marked as SENSITIVE. A user must not
  62. * access that information while the RNG executes its loops to
  63. * calculate the next random value. */
  64. __u64 data; /* SENSITIVE Actual random number */
  65. __u64 old_data; /* SENSITIVE Previous random number */
  66. __u64 prev_time; /* SENSITIVE Previous time stamp */
  67. #define DATA_SIZE_BITS ((sizeof(__u64)) * 8)
  68. __u64 last_delta; /* SENSITIVE stuck test */
  69. __s64 last_delta2; /* SENSITIVE stuck test */
  70. unsigned int osr; /* Oversample rate */
  71. #define JENT_MEMORY_BLOCKS 64
  72. #define JENT_MEMORY_BLOCKSIZE 32
  73. #define JENT_MEMORY_ACCESSLOOPS 128
  74. #define JENT_MEMORY_SIZE (JENT_MEMORY_BLOCKS*JENT_MEMORY_BLOCKSIZE)
  75. unsigned char *mem; /* Memory access location with size of
  76. * memblocks * memblocksize */
  77. unsigned int memlocation; /* Pointer to byte in *mem */
  78. unsigned int memblocks; /* Number of memory blocks in *mem */
  79. unsigned int memblocksize; /* Size of one memory block in bytes */
  80. unsigned int memaccessloops; /* Number of memory accesses per random
  81. * bit generation */
  82. /* Repetition Count Test */
  83. int rct_count; /* Number of stuck values */
  84. /* Adaptive Proportion Test for a significance level of 2^-30 */
  85. #define JENT_APT_CUTOFF 325 /* Taken from SP800-90B sec 4.4.2 */
  86. #define JENT_APT_WINDOW_SIZE 512 /* Data window size */
  87. /* LSB of time stamp to process */
  88. #define JENT_APT_LSB 16
  89. #define JENT_APT_WORD_MASK (JENT_APT_LSB - 1)
  90. unsigned int apt_observations; /* Number of collected observations */
  91. unsigned int apt_count; /* APT counter */
  92. unsigned int apt_base; /* APT base reference */
  93. unsigned int apt_base_set:1; /* APT base reference set? */
  94. unsigned int health_failure:1; /* Permanent health failure */
  95. };
  96. /* Flags that can be used to initialize the RNG */
  97. #define JENT_DISABLE_MEMORY_ACCESS (1<<2) /* Disable memory access for more
  98. * entropy, saves MEMORY_SIZE RAM for
  99. * entropy collector */
  100. /* -- error codes for init function -- */
  101. #define JENT_ENOTIME 1 /* Timer service not available */
  102. #define JENT_ECOARSETIME 2 /* Timer too coarse for RNG */
  103. #define JENT_ENOMONOTONIC 3 /* Timer is not monotonic increasing */
  104. #define JENT_EVARVAR 5 /* Timer does not produce variations of
  105. * variations (2nd derivation of time is
  106. * zero). */
  107. #define JENT_ESTUCK 8 /* Too many stuck results during init. */
  108. #define JENT_EHEALTH 9 /* Health test failed during initialization */
  109. #define JENT_ERCT 10 /* RCT failed during initialization */
  110. #include "jitterentropy.h"
  111. /***************************************************************************
  112. * Adaptive Proportion Test
  113. *
  114. * This test complies with SP800-90B section 4.4.2.
  115. ***************************************************************************/
  116. /**
  117. * Reset the APT counter
  118. *
  119. * @ec [in] Reference to entropy collector
  120. */
  121. static void jent_apt_reset(struct rand_data *ec, unsigned int delta_masked)
  122. {
  123. /* Reset APT counter */
  124. ec->apt_count = 0;
  125. ec->apt_base = delta_masked;
  126. ec->apt_observations = 0;
  127. }
  128. /**
  129. * Insert a new entropy event into APT
  130. *
  131. * @ec [in] Reference to entropy collector
  132. * @delta_masked [in] Masked time delta to process
  133. */
  134. static void jent_apt_insert(struct rand_data *ec, unsigned int delta_masked)
  135. {
  136. /* Initialize the base reference */
  137. if (!ec->apt_base_set) {
  138. ec->apt_base = delta_masked;
  139. ec->apt_base_set = 1;
  140. return;
  141. }
  142. if (delta_masked == ec->apt_base) {
  143. ec->apt_count++;
  144. if (ec->apt_count >= JENT_APT_CUTOFF)
  145. ec->health_failure = 1;
  146. }
  147. ec->apt_observations++;
  148. if (ec->apt_observations >= JENT_APT_WINDOW_SIZE)
  149. jent_apt_reset(ec, delta_masked);
  150. }
  151. /***************************************************************************
  152. * Stuck Test and its use as Repetition Count Test
  153. *
  154. * The Jitter RNG uses an enhanced version of the Repetition Count Test
  155. * (RCT) specified in SP800-90B section 4.4.1. Instead of counting identical
  156. * back-to-back values, the input to the RCT is the counting of the stuck
  157. * values during the generation of one Jitter RNG output block.
  158. *
  159. * The RCT is applied with an alpha of 2^{-30} compliant to FIPS 140-2 IG 9.8.
  160. *
  161. * During the counting operation, the Jitter RNG always calculates the RCT
  162. * cut-off value of C. If that value exceeds the allowed cut-off value,
  163. * the Jitter RNG output block will be calculated completely but discarded at
  164. * the end. The caller of the Jitter RNG is informed with an error code.
  165. ***************************************************************************/
  166. /**
  167. * Repetition Count Test as defined in SP800-90B section 4.4.1
  168. *
  169. * @ec [in] Reference to entropy collector
  170. * @stuck [in] Indicator whether the value is stuck
  171. */
  172. static void jent_rct_insert(struct rand_data *ec, int stuck)
  173. {
  174. /*
  175. * If we have a count less than zero, a previous RCT round identified
  176. * a failure. We will not overwrite it.
  177. */
  178. if (ec->rct_count < 0)
  179. return;
  180. if (stuck) {
  181. ec->rct_count++;
  182. /*
  183. * The cutoff value is based on the following consideration:
  184. * alpha = 2^-30 as recommended in FIPS 140-2 IG 9.8.
  185. * In addition, we require an entropy value H of 1/OSR as this
  186. * is the minimum entropy required to provide full entropy.
  187. * Note, we collect 64 * OSR deltas for inserting them into
  188. * the entropy pool which should then have (close to) 64 bits
  189. * of entropy.
  190. *
  191. * Note, ec->rct_count (which equals to value B in the pseudo
  192. * code of SP800-90B section 4.4.1) starts with zero. Hence
  193. * we need to subtract one from the cutoff value as calculated
  194. * following SP800-90B.
  195. */
  196. if ((unsigned int)ec->rct_count >= (31 * ec->osr)) {
  197. ec->rct_count = -1;
  198. ec->health_failure = 1;
  199. }
  200. } else {
  201. ec->rct_count = 0;
  202. }
  203. }
  204. /**
  205. * Is there an RCT health test failure?
  206. *
  207. * @ec [in] Reference to entropy collector
  208. *
  209. * @return
  210. * 0 No health test failure
  211. * 1 Permanent health test failure
  212. */
  213. static int jent_rct_failure(struct rand_data *ec)
  214. {
  215. if (ec->rct_count < 0)
  216. return 1;
  217. return 0;
  218. }
  219. static inline __u64 jent_delta(__u64 prev, __u64 next)
  220. {
  221. #define JENT_UINT64_MAX (__u64)(~((__u64) 0))
  222. return (prev < next) ? (next - prev) :
  223. (JENT_UINT64_MAX - prev + 1 + next);
  224. }
  225. /**
  226. * Stuck test by checking the:
  227. * 1st derivative of the jitter measurement (time delta)
  228. * 2nd derivative of the jitter measurement (delta of time deltas)
  229. * 3rd derivative of the jitter measurement (delta of delta of time deltas)
  230. *
  231. * All values must always be non-zero.
  232. *
  233. * @ec [in] Reference to entropy collector
  234. * @current_delta [in] Jitter time delta
  235. *
  236. * @return
  237. * 0 jitter measurement not stuck (good bit)
  238. * 1 jitter measurement stuck (reject bit)
  239. */
  240. static int jent_stuck(struct rand_data *ec, __u64 current_delta)
  241. {
  242. __u64 delta2 = jent_delta(ec->last_delta, current_delta);
  243. __u64 delta3 = jent_delta(ec->last_delta2, delta2);
  244. ec->last_delta = current_delta;
  245. ec->last_delta2 = delta2;
  246. /*
  247. * Insert the result of the comparison of two back-to-back time
  248. * deltas.
  249. */
  250. jent_apt_insert(ec, current_delta);
  251. if (!current_delta || !delta2 || !delta3) {
  252. /* RCT with a stuck bit */
  253. jent_rct_insert(ec, 1);
  254. return 1;
  255. }
  256. /* RCT with a non-stuck bit */
  257. jent_rct_insert(ec, 0);
  258. return 0;
  259. }
  260. /**
  261. * Report any health test failures
  262. *
  263. * @ec [in] Reference to entropy collector
  264. *
  265. * @return
  266. * 0 No health test failure
  267. * 1 Permanent health test failure
  268. */
  269. static int jent_health_failure(struct rand_data *ec)
  270. {
  271. /* Test is only enabled in FIPS mode */
  272. if (!jent_fips_enabled())
  273. return 0;
  274. return ec->health_failure;
  275. }
  276. /***************************************************************************
  277. * Noise sources
  278. ***************************************************************************/
  279. /**
  280. * Update of the loop count used for the next round of
  281. * an entropy collection.
  282. *
  283. * Input:
  284. * @ec entropy collector struct -- may be NULL
  285. * @bits is the number of low bits of the timer to consider
  286. * @min is the number of bits we shift the timer value to the right at
  287. * the end to make sure we have a guaranteed minimum value
  288. *
  289. * @return Newly calculated loop counter
  290. */
  291. static __u64 jent_loop_shuffle(struct rand_data *ec,
  292. unsigned int bits, unsigned int min)
  293. {
  294. __u64 time = 0;
  295. __u64 shuffle = 0;
  296. unsigned int i = 0;
  297. unsigned int mask = (1<<bits) - 1;
  298. jent_get_nstime(&time);
  299. /*
  300. * Mix the current state of the random number into the shuffle
  301. * calculation to balance that shuffle a bit more.
  302. */
  303. if (ec)
  304. time ^= ec->data;
  305. /*
  306. * We fold the time value as much as possible to ensure that as many
  307. * bits of the time stamp are included as possible.
  308. */
  309. for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) {
  310. shuffle ^= time & mask;
  311. time = time >> bits;
  312. }
  313. /*
  314. * We add a lower boundary value to ensure we have a minimum
  315. * RNG loop count.
  316. */
  317. return (shuffle + (1<<min));
  318. }
  319. /**
  320. * CPU Jitter noise source -- this is the noise source based on the CPU
  321. * execution time jitter
  322. *
  323. * This function injects the individual bits of the time value into the
  324. * entropy pool using an LFSR.
  325. *
  326. * The code is deliberately inefficient with respect to the bit shifting
  327. * and shall stay that way. This function is the root cause why the code
  328. * shall be compiled without optimization. This function not only acts as
  329. * folding operation, but this function's execution is used to measure
  330. * the CPU execution time jitter. Any change to the loop in this function
  331. * implies that careful retesting must be done.
  332. *
  333. * @ec [in] entropy collector struct
  334. * @time [in] time stamp to be injected
  335. * @loop_cnt [in] if a value not equal to 0 is set, use the given value as
  336. * number of loops to perform the folding
  337. * @stuck [in] Is the time stamp identified as stuck?
  338. *
  339. * Output:
  340. * updated ec->data
  341. *
  342. * @return Number of loops the folding operation is performed
  343. */
  344. static void jent_lfsr_time(struct rand_data *ec, __u64 time, __u64 loop_cnt,
  345. int stuck)
  346. {
  347. unsigned int i;
  348. __u64 j = 0;
  349. __u64 new = 0;
  350. #define MAX_FOLD_LOOP_BIT 4
  351. #define MIN_FOLD_LOOP_BIT 0
  352. __u64 fold_loop_cnt =
  353. jent_loop_shuffle(ec, MAX_FOLD_LOOP_BIT, MIN_FOLD_LOOP_BIT);
  354. /*
  355. * testing purposes -- allow test app to set the counter, not
  356. * needed during runtime
  357. */
  358. if (loop_cnt)
  359. fold_loop_cnt = loop_cnt;
  360. for (j = 0; j < fold_loop_cnt; j++) {
  361. new = ec->data;
  362. for (i = 1; (DATA_SIZE_BITS) >= i; i++) {
  363. __u64 tmp = time << (DATA_SIZE_BITS - i);
  364. tmp = tmp >> (DATA_SIZE_BITS - 1);
  365. /*
  366. * Fibonacci LSFR with polynomial of
  367. * x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is
  368. * primitive according to
  369. * http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf
  370. * (the shift values are the polynomial values minus one
  371. * due to counting bits from 0 to 63). As the current
  372. * position is always the LSB, the polynomial only needs
  373. * to shift data in from the left without wrap.
  374. */
  375. tmp ^= ((new >> 63) & 1);
  376. tmp ^= ((new >> 60) & 1);
  377. tmp ^= ((new >> 55) & 1);
  378. tmp ^= ((new >> 30) & 1);
  379. tmp ^= ((new >> 27) & 1);
  380. tmp ^= ((new >> 22) & 1);
  381. new <<= 1;
  382. new ^= tmp;
  383. }
  384. }
  385. /*
  386. * If the time stamp is stuck, do not finally insert the value into
  387. * the entropy pool. Although this operation should not do any harm
  388. * even when the time stamp has no entropy, SP800-90B requires that
  389. * any conditioning operation (SP800-90B considers the LFSR to be a
  390. * conditioning operation) to have an identical amount of input
  391. * data according to section 3.1.5.
  392. */
  393. if (!stuck)
  394. ec->data = new;
  395. }
  396. /**
  397. * Memory Access noise source -- this is a noise source based on variations in
  398. * memory access times
  399. *
  400. * This function performs memory accesses which will add to the timing
  401. * variations due to an unknown amount of CPU wait states that need to be
  402. * added when accessing memory. The memory size should be larger than the L1
  403. * caches as outlined in the documentation and the associated testing.
  404. *
  405. * The L1 cache has a very high bandwidth, albeit its access rate is usually
  406. * slower than accessing CPU registers. Therefore, L1 accesses only add minimal
  407. * variations as the CPU has hardly to wait. Starting with L2, significant
  408. * variations are added because L2 typically does not belong to the CPU any more
  409. * and therefore a wider range of CPU wait states is necessary for accesses.
  410. * L3 and real memory accesses have even a wider range of wait states. However,
  411. * to reliably access either L3 or memory, the ec->mem memory must be quite
  412. * large which is usually not desirable.
  413. *
  414. * @ec [in] Reference to the entropy collector with the memory access data -- if
  415. * the reference to the memory block to be accessed is NULL, this noise
  416. * source is disabled
  417. * @loop_cnt [in] if a value not equal to 0 is set, use the given value
  418. * number of loops to perform the LFSR
  419. */
  420. static void jent_memaccess(struct rand_data *ec, __u64 loop_cnt)
  421. {
  422. unsigned int wrap = 0;
  423. __u64 i = 0;
  424. #define MAX_ACC_LOOP_BIT 7
  425. #define MIN_ACC_LOOP_BIT 0
  426. __u64 acc_loop_cnt =
  427. jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT);
  428. if (NULL == ec || NULL == ec->mem)
  429. return;
  430. wrap = ec->memblocksize * ec->memblocks;
  431. /*
  432. * testing purposes -- allow test app to set the counter, not
  433. * needed during runtime
  434. */
  435. if (loop_cnt)
  436. acc_loop_cnt = loop_cnt;
  437. for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) {
  438. unsigned char *tmpval = ec->mem + ec->memlocation;
  439. /*
  440. * memory access: just add 1 to one byte,
  441. * wrap at 255 -- memory access implies read
  442. * from and write to memory location
  443. */
  444. *tmpval = (*tmpval + 1) & 0xff;
  445. /*
  446. * Addition of memblocksize - 1 to pointer
  447. * with wrap around logic to ensure that every
  448. * memory location is hit evenly
  449. */
  450. ec->memlocation = ec->memlocation + ec->memblocksize - 1;
  451. ec->memlocation = ec->memlocation % wrap;
  452. }
  453. }
  454. /***************************************************************************
  455. * Start of entropy processing logic
  456. ***************************************************************************/
  457. /**
  458. * This is the heart of the entropy generation: calculate time deltas and
  459. * use the CPU jitter in the time deltas. The jitter is injected into the
  460. * entropy pool.
  461. *
  462. * WARNING: ensure that ->prev_time is primed before using the output
  463. * of this function! This can be done by calling this function
  464. * and not using its result.
  465. *
  466. * @ec [in] Reference to entropy collector
  467. *
  468. * @return result of stuck test
  469. */
  470. static int jent_measure_jitter(struct rand_data *ec)
  471. {
  472. __u64 time = 0;
  473. __u64 current_delta = 0;
  474. int stuck;
  475. /* Invoke one noise source before time measurement to add variations */
  476. jent_memaccess(ec, 0);
  477. /*
  478. * Get time stamp and calculate time delta to previous
  479. * invocation to measure the timing variations
  480. */
  481. jent_get_nstime(&time);
  482. current_delta = jent_delta(ec->prev_time, time);
  483. ec->prev_time = time;
  484. /* Check whether we have a stuck measurement. */
  485. stuck = jent_stuck(ec, current_delta);
  486. /* Now call the next noise sources which also injects the data */
  487. jent_lfsr_time(ec, current_delta, 0, stuck);
  488. return stuck;
  489. }
  490. /**
  491. * Generator of one 64 bit random number
  492. * Function fills rand_data->data
  493. *
  494. * @ec [in] Reference to entropy collector
  495. */
  496. static void jent_gen_entropy(struct rand_data *ec)
  497. {
  498. unsigned int k = 0;
  499. /* priming of the ->prev_time value */
  500. jent_measure_jitter(ec);
  501. while (1) {
  502. /* If a stuck measurement is received, repeat measurement */
  503. if (jent_measure_jitter(ec))
  504. continue;
  505. /*
  506. * We multiply the loop value with ->osr to obtain the
  507. * oversampling rate requested by the caller
  508. */
  509. if (++k >= (DATA_SIZE_BITS * ec->osr))
  510. break;
  511. }
  512. }
  513. /**
  514. * Entry function: Obtain entropy for the caller.
  515. *
  516. * This function invokes the entropy gathering logic as often to generate
  517. * as many bytes as requested by the caller. The entropy gathering logic
  518. * creates 64 bit per invocation.
  519. *
  520. * This function truncates the last 64 bit entropy value output to the exact
  521. * size specified by the caller.
  522. *
  523. * @ec [in] Reference to entropy collector
  524. * @data [in] pointer to buffer for storing random data -- buffer must already
  525. * exist
  526. * @len [in] size of the buffer, specifying also the requested number of random
  527. * in bytes
  528. *
  529. * @return 0 when request is fulfilled or an error
  530. *
  531. * The following error codes can occur:
  532. * -1 entropy_collector is NULL
  533. * -2 RCT failed
  534. * -3 APT test failed
  535. */
  536. int jent_read_entropy(struct rand_data *ec, unsigned char *data,
  537. unsigned int len)
  538. {
  539. unsigned char *p = data;
  540. if (!ec)
  541. return -1;
  542. while (0 < len) {
  543. unsigned int tocopy;
  544. jent_gen_entropy(ec);
  545. if (jent_health_failure(ec)) {
  546. int ret;
  547. if (jent_rct_failure(ec))
  548. ret = -2;
  549. else
  550. ret = -3;
  551. /*
  552. * Re-initialize the noise source
  553. *
  554. * If the health test fails, the Jitter RNG remains
  555. * in failure state and will return a health failure
  556. * during next invocation.
  557. */
  558. if (jent_entropy_init())
  559. return ret;
  560. /* Set APT to initial state */
  561. jent_apt_reset(ec, 0);
  562. ec->apt_base_set = 0;
  563. /* Set RCT to initial state */
  564. ec->rct_count = 0;
  565. /* Re-enable Jitter RNG */
  566. ec->health_failure = 0;
  567. /*
  568. * Return the health test failure status to the
  569. * caller as the generated value is not appropriate.
  570. */
  571. return ret;
  572. }
  573. if ((DATA_SIZE_BITS / 8) < len)
  574. tocopy = (DATA_SIZE_BITS / 8);
  575. else
  576. tocopy = len;
  577. jent_memcpy(p, &ec->data, tocopy);
  578. len -= tocopy;
  579. p += tocopy;
  580. }
  581. return 0;
  582. }
  583. /***************************************************************************
  584. * Initialization logic
  585. ***************************************************************************/
  586. struct rand_data *jent_entropy_collector_alloc(unsigned int osr,
  587. unsigned int flags)
  588. {
  589. struct rand_data *entropy_collector;
  590. entropy_collector = jent_zalloc(sizeof(struct rand_data));
  591. if (!entropy_collector)
  592. return NULL;
  593. if (!(flags & JENT_DISABLE_MEMORY_ACCESS)) {
  594. /* Allocate memory for adding variations based on memory
  595. * access
  596. */
  597. entropy_collector->mem = jent_zalloc(JENT_MEMORY_SIZE);
  598. if (!entropy_collector->mem) {
  599. jent_zfree(entropy_collector);
  600. return NULL;
  601. }
  602. entropy_collector->memblocksize = JENT_MEMORY_BLOCKSIZE;
  603. entropy_collector->memblocks = JENT_MEMORY_BLOCKS;
  604. entropy_collector->memaccessloops = JENT_MEMORY_ACCESSLOOPS;
  605. }
  606. /* verify and set the oversampling rate */
  607. if (0 == osr)
  608. osr = 1; /* minimum sampling rate is 1 */
  609. entropy_collector->osr = osr;
  610. /* fill the data pad with non-zero values */
  611. jent_gen_entropy(entropy_collector);
  612. return entropy_collector;
  613. }
  614. void jent_entropy_collector_free(struct rand_data *entropy_collector)
  615. {
  616. jent_zfree(entropy_collector->mem);
  617. entropy_collector->mem = NULL;
  618. jent_zfree(entropy_collector);
  619. }
  620. int jent_entropy_init(void)
  621. {
  622. int i;
  623. __u64 delta_sum = 0;
  624. __u64 old_delta = 0;
  625. unsigned int nonstuck = 0;
  626. int time_backwards = 0;
  627. int count_mod = 0;
  628. int count_stuck = 0;
  629. struct rand_data ec = { 0 };
  630. /* Required for RCT */
  631. ec.osr = 1;
  632. /* We could perform statistical tests here, but the problem is
  633. * that we only have a few loop counts to do testing. These
  634. * loop counts may show some slight skew and we produce
  635. * false positives.
  636. *
  637. * Moreover, only old systems show potentially problematic
  638. * jitter entropy that could potentially be caught here. But
  639. * the RNG is intended for hardware that is available or widely
  640. * used, but not old systems that are long out of favor. Thus,
  641. * no statistical tests.
  642. */
  643. /*
  644. * We could add a check for system capabilities such as clock_getres or
  645. * check for CONFIG_X86_TSC, but it does not make much sense as the
  646. * following sanity checks verify that we have a high-resolution
  647. * timer.
  648. */
  649. /*
  650. * TESTLOOPCOUNT needs some loops to identify edge systems. 100 is
  651. * definitely too little.
  652. *
  653. * SP800-90B requires at least 1024 initial test cycles.
  654. */
  655. #define TESTLOOPCOUNT 1024
  656. #define CLEARCACHE 100
  657. for (i = 0; (TESTLOOPCOUNT + CLEARCACHE) > i; i++) {
  658. __u64 time = 0;
  659. __u64 time2 = 0;
  660. __u64 delta = 0;
  661. unsigned int lowdelta = 0;
  662. int stuck;
  663. /* Invoke core entropy collection logic */
  664. jent_get_nstime(&time);
  665. ec.prev_time = time;
  666. jent_lfsr_time(&ec, time, 0, 0);
  667. jent_get_nstime(&time2);
  668. /* test whether timer works */
  669. if (!time || !time2)
  670. return JENT_ENOTIME;
  671. delta = jent_delta(time, time2);
  672. /*
  673. * test whether timer is fine grained enough to provide
  674. * delta even when called shortly after each other -- this
  675. * implies that we also have a high resolution timer
  676. */
  677. if (!delta)
  678. return JENT_ECOARSETIME;
  679. stuck = jent_stuck(&ec, delta);
  680. /*
  681. * up to here we did not modify any variable that will be
  682. * evaluated later, but we already performed some work. Thus we
  683. * already have had an impact on the caches, branch prediction,
  684. * etc. with the goal to clear it to get the worst case
  685. * measurements.
  686. */
  687. if (CLEARCACHE > i)
  688. continue;
  689. if (stuck)
  690. count_stuck++;
  691. else {
  692. nonstuck++;
  693. /*
  694. * Ensure that the APT succeeded.
  695. *
  696. * With the check below that count_stuck must be less
  697. * than 10% of the overall generated raw entropy values
  698. * it is guaranteed that the APT is invoked at
  699. * floor((TESTLOOPCOUNT * 0.9) / 64) == 14 times.
  700. */
  701. if ((nonstuck % JENT_APT_WINDOW_SIZE) == 0) {
  702. jent_apt_reset(&ec,
  703. delta & JENT_APT_WORD_MASK);
  704. if (jent_health_failure(&ec))
  705. return JENT_EHEALTH;
  706. }
  707. }
  708. /* Validate RCT */
  709. if (jent_rct_failure(&ec))
  710. return JENT_ERCT;
  711. /* test whether we have an increasing timer */
  712. if (!(time2 > time))
  713. time_backwards++;
  714. /* use 32 bit value to ensure compilation on 32 bit arches */
  715. lowdelta = time2 - time;
  716. if (!(lowdelta % 100))
  717. count_mod++;
  718. /*
  719. * ensure that we have a varying delta timer which is necessary
  720. * for the calculation of entropy -- perform this check
  721. * only after the first loop is executed as we need to prime
  722. * the old_data value
  723. */
  724. if (delta > old_delta)
  725. delta_sum += (delta - old_delta);
  726. else
  727. delta_sum += (old_delta - delta);
  728. old_delta = delta;
  729. }
  730. /*
  731. * we allow up to three times the time running backwards.
  732. * CLOCK_REALTIME is affected by adjtime and NTP operations. Thus,
  733. * if such an operation just happens to interfere with our test, it
  734. * should not fail. The value of 3 should cover the NTP case being
  735. * performed during our test run.
  736. */
  737. if (3 < time_backwards)
  738. return JENT_ENOMONOTONIC;
  739. /*
  740. * Variations of deltas of time must on average be larger
  741. * than 1 to ensure the entropy estimation
  742. * implied with 1 is preserved
  743. */
  744. if ((delta_sum) <= 1)
  745. return JENT_EVARVAR;
  746. /*
  747. * Ensure that we have variations in the time stamp below 10 for at
  748. * least 10% of all checks -- on some platforms, the counter increments
  749. * in multiples of 100, but not always
  750. */
  751. if ((TESTLOOPCOUNT/10 * 9) < count_mod)
  752. return JENT_ECOARSETIME;
  753. /*
  754. * If we have more than 90% stuck results, then this Jitter RNG is
  755. * likely to not work well.
  756. */
  757. if ((TESTLOOPCOUNT/10 * 9) < count_stuck)
  758. return JENT_ESTUCK;
  759. return 0;
  760. }