1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis */
2 /* SPDX-License-Identifier: Unlicense */
3 #include "tomcrypt_private.h"
4
5 #ifdef LTC_FORTUNA_RESEED_RATELIMIT_TIMED
6 #if defined(_WIN32)
7 #include <windows.h>
8 #elif defined(LTC_CLOCK_GETTIME)
9 #include <time.h> /* struct timespec + clock_gettime */
10 #else
11 #include <sys/time.h> /* struct timeval + gettimeofday */
12 #endif
13 #endif
14
15 /**
16 @file fortuna.c
17 Fortuna PRNG, Tom St Denis
18 */
19
20 /* Implementation of Fortuna by Tom St Denis
21
22 We deviate slightly here for reasons of simplicity [and to fit in the API]. First all "sources"
23 in the AddEntropy function are fixed to 0. Second since no reliable timer is provided
24 we reseed automatically when len(pool0) >= 64 or every LTC_FORTUNA_WD calls to the read function */
25
26 #ifdef LTC_FORTUNA
27
28 /* requries LTC_SHA256 and AES */
29 #if !(defined(LTC_RIJNDAEL) && defined(LTC_SHA256))
30 #error LTC_FORTUNA requires LTC_SHA256 and LTC_RIJNDAEL (AES)
31 #endif
32
33 #ifndef LTC_FORTUNA_POOLS
34 #warning LTC_FORTUNA_POOLS was not previously defined (old headers?)
35 #define LTC_FORTUNA_POOLS 32
36 #endif
37
38 #if LTC_FORTUNA_POOLS < 4 || LTC_FORTUNA_POOLS > 32
39 #error LTC_FORTUNA_POOLS must be in [4..32]
40 #endif
41
42 const struct ltc_prng_descriptor fortuna_desc = {
43 "fortuna",
44 64,
45 &fortuna_start,
46 &fortuna_add_entropy,
47 &fortuna_ready,
48 &fortuna_read,
49 &fortuna_done,
50 &fortuna_export,
51 &fortuna_import,
52 &fortuna_test
53 };
54
55 /* update the IV */
s_fortuna_update_iv(prng_state * prng)56 static void s_fortuna_update_iv(prng_state *prng)
57 {
58 int x;
59 unsigned char *IV;
60 /* update IV */
61 IV = prng->u.fortuna.IV;
62 for (x = 0; x < 16; x++) {
63 IV[x] = (IV[x] + 1) & 255;
64 if (IV[x] != 0) break;
65 }
66 }
67
68 #ifdef LTC_FORTUNA_RESEED_RATELIMIT_TIMED
69 /* get the current time in 100ms steps */
s_fortuna_current_time(void)70 static ulong64 s_fortuna_current_time(void)
71 {
72 ulong64 cur_time;
73 #if defined(_WIN32)
74 FILETIME CurrentTime;
75 ULARGE_INTEGER ul;
76 GetSystemTimeAsFileTime(&CurrentTime);
77 ul.LowPart = CurrentTime.dwLowDateTime;
78 ul.HighPart = CurrentTime.dwHighDateTime;
79 cur_time = ul.QuadPart; /* now we have 100ns intervals since 1 January 1601 */
80 cur_time -= CONST64(116444736000000000); /* subtract 100ns intervals between 1601-1970 */
81 cur_time /= 10; /* 100ns intervals > microseconds */
82 #elif defined(LTC_CLOCK_GETTIME)
83 struct timespec ts;
84 clock_gettime(CLOCK_MONOTONIC, &ts);
85 cur_time = (ulong64)(ts.tv_sec) * 1000000 + (ulong64)(ts.tv_nsec) / 1000; /* get microseconds */
86 #else
87 struct timeval tv;
88 gettimeofday(&tv, NULL);
89 cur_time = (ulong64)(tv.tv_sec) * 1000000 + (ulong64)(tv.tv_usec); /* get microseconds */
90 #endif
91 return cur_time / 100;
92 }
93 #endif
94
95 /* reseed the PRNG */
s_fortuna_reseed(prng_state * prng)96 static int s_fortuna_reseed(prng_state *prng)
97 {
98 unsigned char tmp[MAXBLOCKSIZE];
99 hash_state md;
100 ulong64 reset_cnt;
101 int err, x;
102
103 #ifdef LTC_FORTUNA_RESEED_RATELIMIT_TIMED
104 ulong64 now = s_fortuna_current_time();
105 if (now == prng->u.fortuna.wd) {
106 return CRYPT_OK;
107 }
108 #else
109 if (++prng->u.fortuna.wd < LTC_FORTUNA_WD) {
110 return CRYPT_OK;
111 }
112 #endif
113
114 /* new K == LTC_SHA256(K || s) where s == LTC_SHA256(P0) || LTC_SHA256(P1) ... */
115 sha256_init(&md);
116 if ((err = sha256_process(&md, prng->u.fortuna.K, 32)) != CRYPT_OK) {
117 sha256_done(&md, tmp);
118 return err;
119 }
120
121 reset_cnt = prng->u.fortuna.reset_cnt + 1;
122
123 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
124 if (x == 0 || ((reset_cnt >> (x-1)) & 1) == 0) {
125 /* terminate this hash */
126 if ((err = sha256_done(&prng->u.fortuna.pool[x], tmp)) != CRYPT_OK) {
127 sha256_done(&md, tmp);
128 return err;
129 }
130 /* add it to the string */
131 if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
132 sha256_done(&md, tmp);
133 return err;
134 }
135 /* reset this pool */
136 if ((err = sha256_init(&prng->u.fortuna.pool[x])) != CRYPT_OK) {
137 sha256_done(&md, tmp);
138 return err;
139 }
140 } else {
141 break;
142 }
143 }
144
145 /* finish key */
146 if ((err = sha256_done(&md, prng->u.fortuna.K)) != CRYPT_OK) {
147 return err;
148 }
149 if ((err = rijndael_setup(prng->u.fortuna.K, 32, 0, &prng->u.fortuna.skey)) != CRYPT_OK) {
150 return err;
151 }
152 s_fortuna_update_iv(prng);
153
154 /* reset/update internals */
155 prng->u.fortuna.pool0_len = 0;
156 #ifdef LTC_FORTUNA_RESEED_RATELIMIT_TIMED
157 prng->u.fortuna.wd = now;
158 #else
159 prng->u.fortuna.wd = 0;
160 #endif
161 prng->u.fortuna.reset_cnt = reset_cnt;
162
163
164 #ifdef LTC_CLEAN_STACK
165 zeromem(&md, sizeof(md));
166 zeromem(tmp, sizeof(tmp));
167 #endif
168
169 return CRYPT_OK;
170 }
171
172 /**
173 "Update Seed File"-compliant update of K
174
175 @param in The PRNG state
176 @param inlen Size of the state
177 @param prng The PRNG to import
178 @return CRYPT_OK if successful
179 */
fortuna_update_seed(const unsigned char * in,unsigned long inlen,prng_state * prng)180 int fortuna_update_seed(const unsigned char *in, unsigned long inlen, prng_state *prng)
181 {
182 int err;
183 unsigned char tmp[MAXBLOCKSIZE];
184 hash_state md;
185
186 LTC_MUTEX_LOCK(&prng->lock);
187 /* new K = LTC_SHA256(K || in) */
188 sha256_init(&md);
189 if ((err = sha256_process(&md, prng->u.fortuna.K, 32)) != CRYPT_OK) {
190 sha256_done(&md, tmp);
191 goto LBL_UNLOCK;
192 }
193 if ((err = sha256_process(&md, in, inlen)) != CRYPT_OK) {
194 sha256_done(&md, tmp);
195 goto LBL_UNLOCK;
196 }
197 /* finish key */
198 if ((err = sha256_done(&md, prng->u.fortuna.K)) != CRYPT_OK) {
199 goto LBL_UNLOCK;
200 }
201 s_fortuna_update_iv(prng);
202
203 LBL_UNLOCK:
204 LTC_MUTEX_UNLOCK(&prng->lock);
205 #ifdef LTC_CLEAN_STACK
206 zeromem(&md, sizeof(md));
207 #endif
208
209 return err;
210 }
211
212 /**
213 Start the PRNG
214 @param prng [out] The PRNG state to initialize
215 @return CRYPT_OK if successful
216 */
fortuna_start(prng_state * prng)217 int fortuna_start(prng_state *prng)
218 {
219 int err, x, y;
220 unsigned char tmp[MAXBLOCKSIZE];
221
222 LTC_ARGCHK(prng != NULL);
223 prng->ready = 0;
224
225 /* initialize the pools */
226 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
227 if ((err = sha256_init(&prng->u.fortuna.pool[x])) != CRYPT_OK) {
228 for (y = 0; y < x; y++) {
229 sha256_done(&prng->u.fortuna.pool[y], tmp);
230 }
231 return err;
232 }
233 }
234 prng->u.fortuna.pool_idx = prng->u.fortuna.pool0_len = 0;
235 prng->u.fortuna.reset_cnt = prng->u.fortuna.wd = 0;
236
237 /* reset bufs */
238 zeromem(prng->u.fortuna.K, 32);
239 if ((err = rijndael_setup(prng->u.fortuna.K, 32, 0, &prng->u.fortuna.skey)) != CRYPT_OK) {
240 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
241 sha256_done(&prng->u.fortuna.pool[x], tmp);
242 }
243 return err;
244 }
245 zeromem(prng->u.fortuna.IV, 16);
246
247 LTC_MUTEX_INIT(&prng->lock)
248
249 return CRYPT_OK;
250 }
251
s_fortuna_add(unsigned long source,unsigned long pool,const unsigned char * in,unsigned long inlen,prng_state * prng)252 static int s_fortuna_add(unsigned long source, unsigned long pool, const unsigned char *in, unsigned long inlen, prng_state *prng)
253 {
254 unsigned char tmp[2];
255 int err;
256
257 /* ensure inlen <= 32 */
258 if (inlen > 32) {
259 inlen = 32;
260 }
261
262 /* add s || length(in) || in to pool[pool_idx] */
263 tmp[0] = (unsigned char)source;
264 tmp[1] = (unsigned char)inlen;
265
266 if ((err = sha256_process(&prng->u.fortuna.pool[pool], tmp, 2)) != CRYPT_OK) {
267 return err;
268 }
269 if ((err = sha256_process(&prng->u.fortuna.pool[pool], in, inlen)) != CRYPT_OK) {
270 return err;
271 }
272 if (pool == 0) {
273 prng->u.fortuna.pool0_len += inlen;
274 }
275 return CRYPT_OK; /* success */
276 }
277
278 /**
279 Add random event to the PRNG state as proposed by the original paper.
280 @param source The source this random event comes from (0 .. 255)
281 @param pool The pool where to add the data to (0 .. LTC_FORTUNA_POOLS)
282 @param in The data to add
283 @param inlen Length of the data to add
284 @param prng PRNG state to update
285 @return CRYPT_OK if successful
286 */
fortuna_add_random_event(unsigned long source,unsigned long pool,const unsigned char * in,unsigned long inlen,prng_state * prng)287 int fortuna_add_random_event(unsigned long source, unsigned long pool, const unsigned char *in, unsigned long inlen, prng_state *prng)
288 {
289 int err;
290
291 LTC_ARGCHK(prng != NULL);
292 LTC_ARGCHK(in != NULL);
293 LTC_ARGCHK(inlen > 0);
294 LTC_ARGCHK(source <= 255);
295 LTC_ARGCHK(pool < LTC_FORTUNA_POOLS);
296
297 LTC_MUTEX_LOCK(&prng->lock);
298
299 err = s_fortuna_add(source, pool, in, inlen, prng);
300
301 LTC_MUTEX_UNLOCK(&prng->lock);
302
303 return err;
304 }
305
306 /**
307 Add entropy to the PRNG state
308 @param in The data to add
309 @param inlen Length of the data to add
310 @param prng PRNG state to update
311 @return CRYPT_OK if successful
312 */
fortuna_add_entropy(const unsigned char * in,unsigned long inlen,prng_state * prng)313 int fortuna_add_entropy(const unsigned char *in, unsigned long inlen, prng_state *prng)
314 {
315 int err;
316
317 LTC_ARGCHK(prng != NULL);
318 LTC_ARGCHK(in != NULL);
319 LTC_ARGCHK(inlen > 0);
320
321 LTC_MUTEX_LOCK(&prng->lock);
322
323 err = s_fortuna_add(0, prng->u.fortuna.pool_idx, in, inlen, prng);
324
325 if (err == CRYPT_OK) {
326 ++(prng->u.fortuna.pool_idx);
327 prng->u.fortuna.pool_idx %= LTC_FORTUNA_POOLS;
328 }
329
330 LTC_MUTEX_UNLOCK(&prng->lock);
331
332 return err;
333 }
334
335 /**
336 Make the PRNG ready to read from
337 @param prng The PRNG to make active
338 @return CRYPT_OK if successful
339 */
fortuna_ready(prng_state * prng)340 int fortuna_ready(prng_state *prng)
341 {
342 int err;
343 LTC_ARGCHK(prng != NULL);
344
345 LTC_MUTEX_LOCK(&prng->lock);
346 /* make sure the reseed doesn't fail because
347 * of the chosen rate limit */
348 #ifdef LTC_FORTUNA_RESEED_RATELIMIT_TIMED
349 prng->u.fortuna.wd = s_fortuna_current_time() - 1;
350 #else
351 prng->u.fortuna.wd = LTC_FORTUNA_WD;
352 #endif
353 err = s_fortuna_reseed(prng);
354 prng->ready = (err == CRYPT_OK) ? 1 : 0;
355
356 LTC_MUTEX_UNLOCK(&prng->lock);
357 return err;
358 }
359
360 /**
361 Read from the PRNG
362 @param out Destination
363 @param outlen Length of output
364 @param prng The active PRNG to read from
365 @return Number of octets read
366 */
fortuna_read(unsigned char * out,unsigned long outlen,prng_state * prng)367 unsigned long fortuna_read(unsigned char *out, unsigned long outlen, prng_state *prng)
368 {
369 unsigned char tmp[16];
370 unsigned long tlen = 0;
371
372 if (outlen == 0 || prng == NULL || out == NULL) return 0;
373
374 LTC_MUTEX_LOCK(&prng->lock);
375
376 if (!prng->ready) {
377 goto LBL_UNLOCK;
378 }
379
380 /* do we have to reseed? */
381 if (prng->u.fortuna.pool0_len >= 64) {
382 if (s_fortuna_reseed(prng) != CRYPT_OK) {
383 goto LBL_UNLOCK;
384 }
385 }
386
387 /* ensure that one reseed happened before allowing to read */
388 if (prng->u.fortuna.reset_cnt == 0) {
389 goto LBL_UNLOCK;
390 }
391
392 /* now generate the blocks required */
393 tlen = outlen;
394
395 /* handle whole blocks without the extra XMEMCPY */
396 while (outlen >= 16) {
397 /* encrypt the IV and store it */
398 rijndael_ecb_encrypt(prng->u.fortuna.IV, out, &prng->u.fortuna.skey);
399 out += 16;
400 outlen -= 16;
401 s_fortuna_update_iv(prng);
402 }
403
404 /* left over bytes? */
405 if (outlen > 0) {
406 rijndael_ecb_encrypt(prng->u.fortuna.IV, tmp, &prng->u.fortuna.skey);
407 XMEMCPY(out, tmp, outlen);
408 s_fortuna_update_iv(prng);
409 }
410
411 /* generate new key */
412 rijndael_ecb_encrypt(prng->u.fortuna.IV, prng->u.fortuna.K , &prng->u.fortuna.skey);
413 s_fortuna_update_iv(prng);
414
415 rijndael_ecb_encrypt(prng->u.fortuna.IV, prng->u.fortuna.K+16, &prng->u.fortuna.skey);
416 s_fortuna_update_iv(prng);
417
418 if (rijndael_setup(prng->u.fortuna.K, 32, 0, &prng->u.fortuna.skey) != CRYPT_OK) {
419 tlen = 0;
420 }
421
422 LBL_UNLOCK:
423 #ifdef LTC_CLEAN_STACK
424 zeromem(tmp, sizeof(tmp));
425 #endif
426 LTC_MUTEX_UNLOCK(&prng->lock);
427 return tlen;
428 }
429
430 /**
431 Terminate the PRNG
432 @param prng The PRNG to terminate
433 @return CRYPT_OK if successful
434 */
fortuna_done(prng_state * prng)435 int fortuna_done(prng_state *prng)
436 {
437 int err, x;
438 unsigned char tmp[32];
439
440 LTC_ARGCHK(prng != NULL);
441
442 LTC_MUTEX_LOCK(&prng->lock);
443 prng->ready = 0;
444
445 /* terminate all the hashes */
446 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
447 if ((err = sha256_done(&(prng->u.fortuna.pool[x]), tmp)) != CRYPT_OK) {
448 goto LBL_UNLOCK;
449 }
450 }
451 /* call cipher done when we invent one ;-) */
452 err = CRYPT_OK; /* success */
453
454 LBL_UNLOCK:
455 #ifdef LTC_CLEAN_STACK
456 zeromem(tmp, sizeof(tmp));
457 #endif
458 LTC_MUTEX_UNLOCK(&prng->lock);
459 LTC_MUTEX_DESTROY(&prng->lock);
460 return err;
461 }
462
463 /**
464 Export the PRNG state
465 @param out [out] Destination
466 @param outlen [in/out] Max size and resulting size of the state
467 @param prng The PRNG to export
468 @return CRYPT_OK if successful
469 */
LTC_PRNG_EXPORT(fortuna)470 LTC_PRNG_EXPORT(fortuna)
471
472 /**
473 Import a PRNG state
474 @param in The PRNG state
475 @param inlen Size of the state
476 @param prng The PRNG to import
477 @return CRYPT_OK if successful
478 */
479 int fortuna_import(const unsigned char *in, unsigned long inlen, prng_state *prng)
480 {
481 int err;
482
483 LTC_ARGCHK(in != NULL);
484 LTC_ARGCHK(prng != NULL);
485
486 if (inlen < (unsigned long)fortuna_desc.export_size) {
487 return CRYPT_INVALID_ARG;
488 }
489
490 if ((err = fortuna_start(prng)) != CRYPT_OK) {
491 return err;
492 }
493
494 if ((err = fortuna_update_seed(in, inlen, prng)) != CRYPT_OK) {
495 return err;
496 }
497
498 return err;
499 }
500
501 /**
502 PRNG self-test
503 @return CRYPT_OK if successful, CRYPT_NOP if self-testing has been disabled
504 */
fortuna_test(void)505 int fortuna_test(void)
506 {
507 #ifndef LTC_TEST
508 return CRYPT_NOP;
509 #else
510 int err;
511
512 if ((err = sha256_test()) != CRYPT_OK) {
513 return err;
514 }
515 return rijndael_test();
516 #endif
517 }
518
519 #endif
520
521