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