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