← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dropbear/utopic-proposed

« back to all changes in this revision

Viewing changes to libtomcrypt/src/prngs/fortuna.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2005-12-08 19:20:21 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051208192021-nyp9rwnt77nsg6ty
Tags: 0.47-1
* New upstream release.
* SECURITY: Fix incorrect buffer sizing.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.org
 
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
 
 
20
We deviate slightly here for reasons of simplicity [and to fit in the API].  First all "sources"
 
21
in the AddEntropy function are fixed to 0.  Second since no reliable timer is provided 
 
22
we 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
 
 
40
const 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 */
 
53
static 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 */
 
66
static 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
      return err;
 
78
   }
 
79
 
 
80
   for (x = 0; x < FORTUNA_POOLS; x++) {
 
81
       if (x == 0 || ((prng->fortuna.reset_cnt >> (x-1)) & 1) == 0) { 
 
82
          /* terminate this hash */
 
83
          if ((err = sha256_done(&prng->fortuna.pool[x], tmp)) != CRYPT_OK) {
 
84
             return err; 
 
85
          }
 
86
          /* add it to the string */
 
87
          if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
 
88
             return err;
 
89
          }
 
90
          /* reset this pool */
 
91
          sha256_init(&prng->fortuna.pool[x]);
 
92
       } else {
 
93
          break;
 
94
       }
 
95
   }
 
96
 
 
97
   /* finish key */
 
98
   if ((err = sha256_done(&md, prng->fortuna.K)) != CRYPT_OK) {
 
99
      return err; 
 
100
   }
 
101
   if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
 
102
      return err;
 
103
   }
 
104
   fortuna_update_iv(prng);
 
105
 
 
106
   /* reset pool len */
 
107
   prng->fortuna.pool0_len = 0;
 
108
   prng->fortuna.wd        = 0;
 
109
 
 
110
 
 
111
#ifdef LTC_CLEAN_STACK
 
112
   zeromem(&md, sizeof(md));
 
113
   zeromem(tmp, sizeof(tmp));
 
114
#endif
 
115
 
 
116
   return CRYPT_OK;
 
117
}
 
118
 
 
119
/**
 
120
  Start the PRNG
 
121
  @param prng     [out] The PRNG state to initialize
 
122
  @return CRYPT_OK if successful
 
123
*/  
 
124
int fortuna_start(prng_state *prng)
 
125
{
 
126
   int err, x;
 
127
 
 
128
   LTC_ARGCHK(prng != NULL);
 
129
   
 
130
   /* initialize the pools */
 
131
   for (x = 0; x < FORTUNA_POOLS; x++) {
 
132
       sha256_init(&prng->fortuna.pool[x]);
 
133
   }
 
134
   prng->fortuna.pool_idx = prng->fortuna.pool0_len = prng->fortuna.reset_cnt = 
 
135
   prng->fortuna.wd = 0;
 
136
 
 
137
   /* reset bufs */
 
138
   zeromem(prng->fortuna.K, 32);
 
139
   if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
 
140
      return err;
 
141
   }
 
142
   zeromem(prng->fortuna.IV, 16);
 
143
 
 
144
   return CRYPT_OK;
 
145
}
 
146
 
 
147
/**
 
148
  Add entropy to the PRNG state
 
149
  @param in       The data to add
 
150
  @param inlen    Length of the data to add
 
151
  @param prng     PRNG state to update
 
152
  @return CRYPT_OK if successful
 
153
*/  
 
154
int fortuna_add_entropy(const unsigned char *in, unsigned long inlen, prng_state *prng)
 
155
{
 
156
   unsigned char tmp[2];
 
157
   int           err;
 
158
 
 
159
   LTC_ARGCHK(in  != NULL);
 
160
   LTC_ARGCHK(prng != NULL);
 
161
 
 
162
   /* ensure inlen <= 32 */
 
163
   if (inlen > 32) {
 
164
      return CRYPT_INVALID_ARG;
 
165
   }
 
166
 
 
167
   /* add s || length(in) || in to pool[pool_idx] */
 
168
   tmp[0] = 0;
 
169
   tmp[1] = inlen;
 
170
   if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], tmp, 2)) != CRYPT_OK) {
 
171
      return err;
 
172
   }
 
173
   if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], in, inlen)) != CRYPT_OK) {
 
174
      return err;
 
175
   }
 
176
   if (prng->fortuna.pool_idx == 0) {
 
177
      prng->fortuna.pool0_len += inlen;
 
178
   }
 
179
   if (++(prng->fortuna.pool_idx) == FORTUNA_POOLS) {
 
180
      prng->fortuna.pool_idx = 0;
 
181
   }
 
182
 
 
183
   return CRYPT_OK;
 
184
}
 
185
 
 
186
/**
 
187
  Make the PRNG ready to read from
 
188
  @param prng   The PRNG to make active
 
189
  @return CRYPT_OK if successful
 
190
*/  
 
191
int fortuna_ready(prng_state *prng)
 
192
{
 
193
   return fortuna_reseed(prng);
 
194
}
 
195
 
 
196
/**
 
197
  Read from the PRNG
 
198
  @param out      Destination
 
199
  @param outlen   Length of output
 
200
  @param prng     The active PRNG to read from
 
201
  @return Number of octets read
 
202
*/  
 
203
unsigned long fortuna_read(unsigned char *out, unsigned long outlen, prng_state *prng)
 
204
{
 
205
   unsigned char tmp[16];
 
206
   int           err;
 
207
   unsigned long tlen;
 
208
 
 
209
   LTC_ARGCHK(out  != NULL);
 
210
   LTC_ARGCHK(prng != NULL);
 
211
 
 
212
   /* do we have to reseed? */
 
213
   if (++prng->fortuna.wd == FORTUNA_WD || prng->fortuna.pool0_len >= 64) {
 
214
      if ((err = fortuna_reseed(prng)) != CRYPT_OK) {
 
215
         return 0;
 
216
      }
 
217
   }
 
218
 
 
219
   /* now generate the blocks required */
 
220
   tlen = outlen;
 
221
 
 
222
   /* handle whole blocks without the extra memcpy */
 
223
   while (outlen >= 16) {
 
224
      /* encrypt the IV and store it */
 
225
      rijndael_ecb_encrypt(prng->fortuna.IV, out, &prng->fortuna.skey);
 
226
      out += 16;
 
227
      outlen -= 16;
 
228
      fortuna_update_iv(prng);
 
229
   }
 
230
 
 
231
   /* left over bytes? */
 
232
   if (outlen > 0) {
 
233
      rijndael_ecb_encrypt(prng->fortuna.IV, tmp, &prng->fortuna.skey);
 
234
      XMEMCPY(out, tmp, outlen);
 
235
      fortuna_update_iv(prng);
 
236
   }
 
237
       
 
238
   /* generate new key */
 
239
   rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K   , &prng->fortuna.skey); fortuna_update_iv(prng);
 
240
   rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K+16, &prng->fortuna.skey); fortuna_update_iv(prng);
 
241
   if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
 
242
      return 0;
 
243
   }
 
244
 
 
245
#ifdef LTC_CLEAN_STACK
 
246
   zeromem(tmp, sizeof(tmp));
 
247
#endif
 
248
   return tlen;
 
249
}   
 
250
 
 
251
/**
 
252
  Terminate the PRNG
 
253
  @param prng   The PRNG to terminate
 
254
  @return CRYPT_OK if successful
 
255
*/  
 
256
int fortuna_done(prng_state *prng)
 
257
{
 
258
   int           err, x;
 
259
   unsigned char tmp[32];
 
260
 
 
261
   LTC_ARGCHK(prng != NULL);
 
262
 
 
263
   /* terminate all the hashes */
 
264
   for (x = 0; x < FORTUNA_POOLS; x++) {
 
265
       if ((err = sha256_done(&(prng->fortuna.pool[x]), tmp)) != CRYPT_OK) {
 
266
          return err; 
 
267
       }
 
268
   }
 
269
   /* call cipher done when we invent one ;-) */
 
270
 
 
271
#ifdef LTC_CLEAN_STACK
 
272
   zeromem(tmp, sizeof(tmp));
 
273
#endif
 
274
 
 
275
   return CRYPT_OK;
 
276
}
 
277
 
 
278
/**
 
279
  Export the PRNG state
 
280
  @param out       [out] Destination
 
281
  @param outlen    [in/out] Max size and resulting size of the state
 
282
  @param prng      The PRNG to export
 
283
  @return CRYPT_OK if successful
 
284
*/  
 
285
int fortuna_export(unsigned char *out, unsigned long *outlen, prng_state *prng)
 
286
{
 
287
   int         x, err;
 
288
   hash_state *md;
 
289
 
 
290
   LTC_ARGCHK(out    != NULL);
 
291
   LTC_ARGCHK(outlen != NULL);
 
292
   LTC_ARGCHK(prng   != NULL);
 
293
 
 
294
   /* we'll write bytes for s&g's */
 
295
   if (*outlen < 32*FORTUNA_POOLS) {
 
296
      return CRYPT_BUFFER_OVERFLOW;
 
297
   }
 
298
 
 
299
   md = XMALLOC(sizeof(hash_state));
 
300
   if (md == NULL) {
 
301
      return CRYPT_MEM;
 
302
   }
 
303
 
 
304
   /* to emit the state we copy each pool, terminate it then hash it again so 
 
305
    * an attacker who sees the state can't determine the current state of the PRNG 
 
306
    */   
 
307
   for (x = 0; x < FORTUNA_POOLS; x++) {
 
308
      /* copy the PRNG */
 
309
      XMEMCPY(md, &(prng->fortuna.pool[x]), sizeof(*md));
 
310
 
 
311
      /* terminate it */
 
312
      if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
 
313
         goto LBL_ERR;
 
314
      }
 
315
 
 
316
      /* now hash it */
 
317
      if ((err = sha256_init(md)) != CRYPT_OK) {
 
318
         goto LBL_ERR;
 
319
      }
 
320
      if ((err = sha256_process(md, out+x*32, 32)) != CRYPT_OK) {
 
321
         goto LBL_ERR;
 
322
      }
 
323
      if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
 
324
         goto LBL_ERR;
 
325
      }
 
326
   }
 
327
   *outlen = 32*FORTUNA_POOLS;
 
328
   err = CRYPT_OK;
 
329
 
 
330
LBL_ERR:
 
331
#ifdef LTC_CLEAN_STACK
 
332
   zeromem(md, sizeof(*md));
 
333
#endif
 
334
   XFREE(md);
 
335
   return err;
 
336
}
 
337
 
 
338
/**
 
339
  Import a PRNG state
 
340
  @param in       The PRNG state
 
341
  @param inlen    Size of the state
 
342
  @param prng     The PRNG to import
 
343
  @return CRYPT_OK if successful
 
344
*/  
 
345
int fortuna_import(const unsigned char *in, unsigned long inlen, prng_state *prng)
 
346
{
 
347
   int err, x;
 
348
 
 
349
   LTC_ARGCHK(in   != NULL);
 
350
   LTC_ARGCHK(prng != NULL);
 
351
 
 
352
   if (inlen != 32*FORTUNA_POOLS) {
 
353
      return CRYPT_INVALID_ARG;
 
354
   }
 
355
 
 
356
   if ((err = fortuna_start(prng)) != CRYPT_OK) {
 
357
      return err;
 
358
   }
 
359
   for (x = 0; x < FORTUNA_POOLS; x++) {
 
360
      if ((err = fortuna_add_entropy(in+x*32, 32, prng)) != CRYPT_OK) {
 
361
         return err;
 
362
      }
 
363
   }
 
364
   return err;
 
365
}
 
366
 
 
367
/**
 
368
  PRNG self-test
 
369
  @return CRYPT_OK if successful, CRYPT_NOP if self-testing has been disabled
 
370
*/  
 
371
int fortuna_test(void)
 
372
{
 
373
#ifndef LTC_TEST
 
374
   return CRYPT_NOP;
 
375
#else
 
376
   int err;
 
377
 
 
378
   if ((err = sha256_test()) != CRYPT_OK) {
 
379
      return err;
 
380
   }
 
381
   return rijndael_test();
 
382
#endif
 
383
}
 
384
 
 
385
#endif
 
386
 
 
387
 
 
388
/* $Source: /cvs/libtom/libtomcrypt/src/prngs/fortuna.c,v $ */
 
389
/* $Revision: 1.3 $ */
 
390
/* $Date: 2005/05/05 14:35:59 $ */