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
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 */
fortuna_update_iv(prng_state * prng)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 */
fortuna_reseed(prng_state * 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 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 */
fortuna_start(prng_state * prng)130 int 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 */
fortuna_add_entropy(const unsigned char * in,unsigned long inlen,prng_state * prng)171 int 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 */
fortuna_ready(prng_state * prng)214 int 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 */
fortuna_read(unsigned char * out,unsigned long outlen,prng_state * prng)226 unsigned 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 */
fortuna_done(prng_state * prng)284 int 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 */
fortuna_export(unsigned char * out,unsigned long * outlen,prng_state * prng)316 int 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
366 LBL_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 */
fortuna_import(const unsigned char * in,unsigned long inlen,prng_state * prng)382 int 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 */
fortuna_test(void)408 int 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