1 /* Jitter RNG: Noise Sources
2 *
3 * Copyright (C) 2021, Stephan Mueller <smueller@chronox.de>
4 *
5 * License: see LICENSE file in root directory
6 *
7 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
8 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
9 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
10 * WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
11 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
12 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
13 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
14 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
15 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
16 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
17 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
18 * DAMAGE.
19 */
20
21 #include "jitterentropy-noise.h"
22 #include "jitterentropy-health.h"
23 #include "jitterentropy-timer.h"
24 #include "jitterentropy-sha3.h"
25
26 #define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
27
28 /***************************************************************************
29 * Noise sources
30 ***************************************************************************/
31
32 /**
33 * Update of the loop count used for the next round of
34 * an entropy collection.
35 *
36 * @ec [in] entropy collector struct -- may be NULL
37 * @bits [in] is the number of low bits of the timer to consider
38 * @min [in] is the number of bits we shift the timer value to the right at
39 * the end to make sure we have a guaranteed minimum value
40 *
41 * @return Newly calculated loop counter
42 */
jent_loop_shuffle(struct rand_data * ec,unsigned int bits,unsigned int min)43 static uint64_t jent_loop_shuffle(struct rand_data *ec,
44 unsigned int bits, unsigned int min)
45 {
46 #ifdef JENT_CONF_DISABLE_LOOP_SHUFFLE
47
48 (void)ec;
49 (void)bits;
50
51 return (UINT64_C(1)<<min);
52
53 #else /* JENT_CONF_DISABLE_LOOP_SHUFFLE */
54
55 uint64_t time = 0;
56 uint64_t shuffle = 0;
57 uint64_t mask = (UINT64_C(1)<<bits) - 1;
58 unsigned int i = 0;
59
60 /*
61 * Mix the current state of the random number into the shuffle
62 * calculation to balance that shuffle a bit more.
63 */
64 if (ec) {
65 jent_get_nstime_internal(ec, &time);
66 time ^= ec->data[0];
67 }
68
69 /*
70 * We fold the time value as much as possible to ensure that as many
71 * bits of the time stamp are included as possible.
72 */
73 for (i = 0; ((DATA_SIZE_BITS + bits - 1) / bits) > i; i++) {
74 shuffle ^= time & mask;
75 time = time >> bits;
76 }
77
78 /*
79 * We add a lower boundary value to ensure we have a minimum
80 * RNG loop count.
81 */
82 return (shuffle + (UINT64_C(1)<<min));
83
84 #endif /* JENT_CONF_DISABLE_LOOP_SHUFFLE */
85 }
86
87 /**
88 * CPU Jitter noise source -- this is the noise source based on the CPU
89 * execution time jitter
90 *
91 * This function injects the individual bits of the time value into the
92 * entropy pool using a hash.
93 *
94 * @ec [in] entropy collector struct -- may be NULL
95 * @time [in] time stamp to be injected
96 * @loop_cnt [in] if a value not equal to 0 is set, use the given value as
97 * number of loops to perform the hash operation
98 * @stuck [in] Is the time stamp identified as stuck?
99 *
100 * Output:
101 * updated hash context
102 */
jent_hash_time(struct rand_data * ec,uint64_t time,uint64_t loop_cnt,unsigned int stuck)103 static void jent_hash_time(struct rand_data *ec, uint64_t time,
104 uint64_t loop_cnt, unsigned int stuck)
105 {
106 HASH_CTX_ON_STACK(ctx);
107 uint8_t itermediary[SHA3_256_SIZE_DIGEST];
108 uint64_t j = 0;
109 #define MAX_HASH_LOOP 3
110 #define MIN_HASH_LOOP 0
111
112 /* Ensure that macros cannot overflow jent_loop_shuffle() */
113 BUILD_BUG_ON((MAX_HASH_LOOP + MIN_HASH_LOOP) > 63);
114 uint64_t hash_loop_cnt =
115 jent_loop_shuffle(ec, MAX_HASH_LOOP, MIN_HASH_LOOP);
116
117 sha3_256_init(&ctx);
118
119 /*
120 * testing purposes -- allow test app to set the counter, not
121 * needed during runtime
122 */
123 if (loop_cnt)
124 hash_loop_cnt = loop_cnt;
125
126 /*
127 * This loop basically slows down the SHA-3 operation depending
128 * on the hash_loop_cnt. Each iteration of the loop generates the
129 * same result.
130 */
131 for (j = 0; j < hash_loop_cnt; j++) {
132 sha3_update(&ctx, ec->data, SHA3_256_SIZE_DIGEST);
133 sha3_update(&ctx, (uint8_t *)&time, sizeof(uint64_t));
134 sha3_update(&ctx, (uint8_t *)&j, sizeof(uint64_t));
135
136 /*
137 * If the time stamp is stuck, do not finally insert the value
138 * into the entropy pool. Although this operation should not do
139 * any harm even when the time stamp has no entropy, SP800-90B
140 * requires that any conditioning operation to have an identical
141 * amount of input data according to section 3.1.5.
142 */
143
144 /*
145 * The sha3_final operations re-initialize the context for the
146 * next loop iteration.
147 */
148 if (stuck || (j < hash_loop_cnt - 1))
149 sha3_final(&ctx, itermediary);
150 else
151 sha3_final(&ctx, ec->data);
152 }
153
154 jent_memset_secure(&ctx, SHA_MAX_CTX_SIZE);
155 jent_memset_secure(itermediary, sizeof(itermediary));
156 }
157
158 #define MAX_ACC_LOOP_BIT 7
159 #define MIN_ACC_LOOP_BIT 0
160 #ifdef JENT_RANDOM_MEMACCESS
161
uint32rotl(const uint32_t x,int k)162 static inline uint32_t uint32rotl(const uint32_t x, int k)
163 {
164 return (x << k) | (x >> (32 - k));
165 }
166
xoshiro128starstar(uint32_t * s)167 static inline uint32_t xoshiro128starstar(uint32_t *s)
168 {
169 const uint32_t result = uint32rotl(s[1] * 5, 7) * 9;
170 const uint32_t t = s[1] << 9;
171
172 s[2] ^= s[0];
173 s[3] ^= s[1];
174 s[1] ^= s[2];
175 s[0] ^= s[3];
176
177 s[2] ^= t;
178
179 s[3] = uint32rotl(s[3], 11);
180
181 return result;
182 }
183
jent_memaccess(struct rand_data * ec,uint64_t loop_cnt)184 static void jent_memaccess(struct rand_data *ec, uint64_t loop_cnt)
185 {
186 uint64_t i = 0;
187 union {
188 uint32_t u[4];
189 uint8_t b[sizeof(uint32_t) * 4];
190 } prngState = { .u = {0x8e93eec0, 0xce65608a, 0xa8d46b46, 0xe83cef69} };
191 uint32_t addressMask = ec->memmask;
192
193 /* Ensure that macros cannot overflow jent_loop_shuffle() */
194 BUILD_BUG_ON((MAX_ACC_LOOP_BIT + MIN_ACC_LOOP_BIT) > 63);
195 uint64_t acc_loop_cnt =
196 jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT);
197
198 if (NULL == ec || NULL == ec->mem)
199 return;
200
201 /*
202 * Mix the current data into prngState
203 *
204 * Any time you see a PRNG in a noise source, you should be concerned.
205 *
206 * The PRNG doesn’t directly produce the raw noise, it just adjusts the
207 * location being updated. The timing of the update is part of the raw
208 * sample. The main thing this process gets you isn’t better
209 * “per-update” timing, it gets you mostly independent “per-update”
210 * timing, so we can now benefit from the Central Limit Theorem!
211 */
212 for (i = 0; i < sizeof(prngState); i++)
213 prngState.b[i] ^= ec->data[i];
214
215 /*
216 * testing purposes -- allow test app to set the counter, not
217 * needed during runtime
218 */
219 if (loop_cnt)
220 acc_loop_cnt = loop_cnt;
221
222 for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) {
223 /* Take PRNG output to find the memory location to update. */
224 unsigned char *tmpval = ec->mem +
225 (xoshiro128starstar(prngState.u) &
226 addressMask);
227
228 /*
229 * memory access: just add 1 to one byte,
230 * wrap at 255 -- memory access implies read
231 * from and write to memory location
232 */
233 *tmpval = (unsigned char)((*tmpval + 1) & 0xff);
234 }
235 }
236
237 #else /* JENT_RANDOM_MEMACCESS */
238
239 /**
240 * Memory Access noise source -- this is a noise source based on variations in
241 * memory access times
242 *
243 * This function performs memory accesses which will add to the timing
244 * variations due to an unknown amount of CPU wait states that need to be
245 * added when accessing memory. The memory size should be larger than the L1
246 * caches as outlined in the documentation and the associated testing.
247 *
248 * The L1 cache has a very high bandwidth, albeit its access rate is usually
249 * slower than accessing CPU registers. Therefore, L1 accesses only add minimal
250 * variations as the CPU has hardly to wait. Starting with L2, significant
251 * variations are added because L2 typically does not belong to the CPU any more
252 * and therefore a wider range of CPU wait states is necessary for accesses.
253 * L3 and real memory accesses have even a wider range of wait states. However,
254 * to reliably access either L3 or memory, the ec->mem memory must be quite
255 * large which is usually not desirable.
256 *
257 * @ec [in] Reference to the entropy collector with the memory access data -- if
258 * the reference to the memory block to be accessed is NULL, this noise
259 * source is disabled
260 * @loop_cnt [in] if a value not equal to 0 is set, use the given value as
261 * number of loops to perform the hash operation
262 */
jent_memaccess(struct rand_data * ec,uint64_t loop_cnt)263 static void jent_memaccess(struct rand_data *ec, uint64_t loop_cnt)
264 {
265 unsigned int wrap = 0;
266 uint64_t i = 0;
267
268 /* Ensure that macros cannot overflow jent_loop_shuffle() */
269 BUILD_BUG_ON((MAX_ACC_LOOP_BIT + MIN_ACC_LOOP_BIT) > 63);
270 uint64_t acc_loop_cnt =
271 jent_loop_shuffle(ec, MAX_ACC_LOOP_BIT, MIN_ACC_LOOP_BIT);
272
273 if (NULL == ec || NULL == ec->mem)
274 return;
275 wrap = ec->memblocksize * ec->memblocks;
276
277 /*
278 * testing purposes -- allow test app to set the counter, not
279 * needed during runtime
280 */
281 if (loop_cnt)
282 acc_loop_cnt = loop_cnt;
283 for (i = 0; i < (ec->memaccessloops + acc_loop_cnt); i++) {
284 unsigned char *tmpval = ec->mem + ec->memlocation;
285 /*
286 * memory access: just add 1 to one byte,
287 * wrap at 255 -- memory access implies read
288 * from and write to memory location
289 */
290 *tmpval = (unsigned char)((*tmpval + 1) & 0xff);
291 /*
292 * Addition of memblocksize - 1 to pointer
293 * with wrap around logic to ensure that every
294 * memory location is hit evenly
295 */
296 ec->memlocation = ec->memlocation + ec->memblocksize - 1;
297 ec->memlocation = ec->memlocation % wrap;
298 }
299 }
300
301 #endif /* JENT_RANDOM_MEMACCESS */
302
303 /***************************************************************************
304 * Start of entropy processing logic
305 ***************************************************************************/
306
307 /**
308 * This is the heart of the entropy generation: calculate time deltas and
309 * use the CPU jitter in the time deltas. The jitter is injected into the
310 * entropy pool.
311 *
312 * WARNING: ensure that ->prev_time is primed before using the output
313 * of this function! This can be done by calling this function
314 * and not using its result.
315 *
316 * @ec [in] Reference to entropy collector
317 * @loop_cnt [in] see jent_hash_time
318 * @ret_current_delta [out] Test interface: return time delta - may be NULL
319 *
320 * @return: result of stuck test
321 */
jent_measure_jitter(struct rand_data * ec,uint64_t loop_cnt,uint64_t * ret_current_delta)322 unsigned int jent_measure_jitter(struct rand_data *ec,
323 uint64_t loop_cnt,
324 uint64_t *ret_current_delta)
325 {
326 uint64_t time = 0;
327 uint64_t current_delta = 0;
328 unsigned int stuck;
329
330 /* Invoke one noise source before time measurement to add variations */
331 jent_memaccess(ec, loop_cnt);
332
333 /*
334 * Get time stamp and calculate time delta to previous
335 * invocation to measure the timing variations
336 */
337 jent_get_nstime_internal(ec, &time);
338 current_delta = jent_delta(ec->prev_time, time) /
339 ec->jent_common_timer_gcd;
340 ec->prev_time = time;
341
342 /* Check whether we have a stuck measurement. */
343 stuck = jent_stuck(ec, current_delta);
344
345 /* Now call the next noise sources which also injects the data */
346 jent_hash_time(ec, current_delta, loop_cnt, stuck);
347
348 /* return the raw entropy value */
349 if (ret_current_delta)
350 *ret_current_delta = current_delta;
351
352 return stuck;
353 }
354
355 /**
356 * Generator of one 256 bit random number
357 * Function fills rand_data->data
358 *
359 * @ec [in] Reference to entropy collector
360 */
jent_random_data(struct rand_data * ec)361 void jent_random_data(struct rand_data *ec)
362 {
363 unsigned int k = 0, safety_factor = ENTROPY_SAFETY_FACTOR;
364
365 if (!ec->fips_enabled)
366 safety_factor = 0;
367
368 /* priming of the ->prev_time value */
369 jent_measure_jitter(ec, 0, NULL);
370
371 while (1) {
372 /* If a stuck measurement is received, repeat measurement */
373 if (jent_measure_jitter(ec, 0, NULL))
374 continue;
375
376 /*
377 * We multiply the loop value with ->osr to obtain the
378 * oversampling rate requested by the caller
379 */
380 if (++k >= ((DATA_SIZE_BITS + safety_factor) * ec->osr))
381 break;
382 }
383 }
384