comparison src/prngs/fortuna.c @ 191:1c15b283127b libtomcrypt-orig

Import of libtomcrypt 1.02 with manual path rename rearrangement etc
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 13:23:02 +0000
parents
children 39d5d58461d6
comparison
equal deleted inserted replaced
143:5d99163f7e32 191:1c15b283127b
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, [email protected], 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