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