Mercurial > dropbear

comparison libtomcrypt/src/prngs/fortuna.c @ 285:1b9e69c058d2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
propagate from branch 'au.asn.ucc.matt.ltc.dropbear' (head 20dccfc09627970a312d77fb41dc2970b62689c3) to branch 'au.asn.ucc.matt.dropbear' (head fdf4a7a3b97ae5046139915de7e40399cceb2c01)
author Matt Johnston <matt@ucc.asn.au>
date Wed, 08 Mar 2006 13:23:58 +0000
parents
children 0cbe8f6dbf9e
comparison
equal deleted inserted replaced
281:997e6f7dc01e 285:1b9e69c058d2
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
387
388 /* $Source: /cvs/libtom/libtomcrypt/src/prngs/fortuna.c,v $ */
389 /* $Revision: 1.3 $ */
390 /* $Date: 2005/05/05 14:35:59 $ */