1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis
3 * LibTomCrypt is a library that provides various cryptographic
4 * algorithms in a highly modular and flexible manner.
6 * The library is free for all purposes without any express
13 Fortuna PRNG, Tom St Denis
16 /* Implementation of Fortuna by Tom St Denis
18 We deviate slightly here for reasons of simplicity [and to fit in the API]. First all "sources"
19 in the AddEntropy function are fixed to 0. Second since no reliable timer is provided
20 we reseed automatically when len(pool0) >= 64 or every LTC_FORTUNA_WD calls to the read function */
24 /* requries LTC_SHA256 and AES */
25 #if !(defined(LTC_RIJNDAEL) && defined(LTC_SHA256))
26 #error LTC_FORTUNA requires LTC_SHA256 and LTC_RIJNDAEL (AES)
29 #ifndef LTC_FORTUNA_POOLS
30 #warning LTC_FORTUNA_POOLS was not previously defined (old headers?)
31 #define LTC_FORTUNA_POOLS 32
34 #if LTC_FORTUNA_POOLS < 4 || LTC_FORTUNA_POOLS > 32
35 #error LTC_FORTUNA_POOLS must be in [4..32]
38 const struct ltc_prng_descriptor fortuna_desc = {
40 (32 * LTC_FORTUNA_POOLS), /* default: 1024 */
52 static void _fortuna_update_iv(prng_state *prng)
57 IV = prng->fortuna.IV;
58 for (x = 0; x < 16; x++) {
59 IV[x] = (IV[x] + 1) & 255;
60 if (IV[x] != 0) break;
65 static int _fortuna_reseed(prng_state *prng)
67 unsigned char tmp[MAXBLOCKSIZE];
73 /* new K == LTC_SHA256(K || s) where s == LTC_SHA256(P0) || LTC_SHA256(P1) ... */
75 if ((err = sha256_process(&md, prng->fortuna.K, 32)) != CRYPT_OK) {
76 sha256_done(&md, tmp);
80 reset_cnt = prng->fortuna.reset_cnt + 1;
82 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
83 if (x == 0 || ((reset_cnt >> (x-1)) & 1) == 0) {
84 /* terminate this hash */
85 if ((err = sha256_done(&prng->fortuna.pool[x], tmp)) != CRYPT_OK) {
86 sha256_done(&md, tmp);
89 /* add it to the string */
90 if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
91 sha256_done(&md, tmp);
95 if ((err = sha256_init(&prng->fortuna.pool[x])) != CRYPT_OK) {
96 sha256_done(&md, tmp);
105 if ((err = sha256_done(&md, prng->fortuna.K)) != CRYPT_OK) {
108 if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
111 _fortuna_update_iv(prng);
113 /* reset/update internals */
114 prng->fortuna.pool0_len = 0;
115 prng->fortuna.wd = 0;
116 prng->fortuna.reset_cnt = reset_cnt;
119 #ifdef LTC_CLEAN_STACK
120 zeromem(&md, sizeof(md));
121 zeromem(tmp, sizeof(tmp));
128 "Update Seed File"-compliant update of K
130 @param in The PRNG state
131 @param inlen Size of the state
132 @param prng The PRNG to import
133 @return CRYPT_OK if successful
135 static int _fortuna_update_seed(const unsigned char *in, unsigned long inlen, prng_state *prng)
138 unsigned char tmp[MAXBLOCKSIZE];
141 LTC_MUTEX_LOCK(&prng->lock);
142 /* new K = LTC_SHA256(K || in) */
144 if ((err = sha256_process(&md, prng->fortuna.K, 32)) != CRYPT_OK) {
145 sha256_done(&md, tmp);
148 if ((err = sha256_process(&md, in, inlen)) != CRYPT_OK) {
149 sha256_done(&md, tmp);
153 if ((err = sha256_done(&md, prng->fortuna.K)) != CRYPT_OK) {
156 _fortuna_update_iv(prng);
159 LTC_MUTEX_UNLOCK(&prng->lock);
160 #ifdef LTC_CLEAN_STACK
161 zeromem(&md, sizeof(md));
169 @param prng [out] The PRNG state to initialize
170 @return CRYPT_OK if successful
172 int fortuna_start(prng_state *prng)
175 unsigned char tmp[MAXBLOCKSIZE];
177 LTC_ARGCHK(prng != NULL);
180 /* initialize the pools */
181 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
182 if ((err = sha256_init(&prng->fortuna.pool[x])) != CRYPT_OK) {
183 for (y = 0; y < x; y++) {
184 sha256_done(&prng->fortuna.pool[y], tmp);
189 prng->fortuna.pool_idx = prng->fortuna.pool0_len = prng->fortuna.wd = 0;
190 prng->fortuna.reset_cnt = 0;
193 zeromem(prng->fortuna.K, 32);
194 if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
195 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
196 sha256_done(&prng->fortuna.pool[x], tmp);
200 zeromem(prng->fortuna.IV, 16);
202 LTC_MUTEX_INIT(&prng->lock)
208 Add entropy to the PRNG state
209 @param in The data to add
210 @param inlen Length of the data to add
211 @param prng PRNG state to update
212 @return CRYPT_OK if successful
214 int fortuna_add_entropy(const unsigned char *in, unsigned long inlen, prng_state *prng)
216 unsigned char tmp[2];
219 LTC_ARGCHK(prng != NULL);
220 LTC_ARGCHK(in != NULL);
221 LTC_ARGCHK(inlen > 0);
223 /* ensure inlen <= 32 */
228 /* add s || length(in) || in to pool[pool_idx] */
230 tmp[1] = (unsigned char)inlen;
232 LTC_MUTEX_LOCK(&prng->lock);
233 if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], tmp, 2)) != CRYPT_OK) {
236 if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], in, inlen)) != CRYPT_OK) {
239 if (prng->fortuna.pool_idx == 0) {
240 prng->fortuna.pool0_len += inlen;
242 if (++(prng->fortuna.pool_idx) == LTC_FORTUNA_POOLS) {
243 prng->fortuna.pool_idx = 0;
245 err = CRYPT_OK; /* success */
248 LTC_MUTEX_UNLOCK(&prng->lock);
253 Make the PRNG ready to read from
254 @param prng The PRNG to make active
255 @return CRYPT_OK if successful
257 int fortuna_ready(prng_state *prng)
260 LTC_ARGCHK(prng != NULL);
262 LTC_MUTEX_LOCK(&prng->lock);
263 err = _fortuna_reseed(prng);
264 prng->ready = (err == CRYPT_OK) ? 1 : 0;
266 LTC_MUTEX_UNLOCK(&prng->lock);
272 @param out Destination
273 @param outlen Length of output
274 @param prng The active PRNG to read from
275 @return Number of octets read
277 unsigned long fortuna_read(unsigned char *out, unsigned long outlen, prng_state *prng)
279 unsigned char tmp[16];
280 unsigned long tlen = 0;
282 if (outlen == 0 || prng == NULL || out == NULL) return 0;
284 LTC_MUTEX_LOCK(&prng->lock);
290 /* do we have to reseed? */
291 if ((++prng->fortuna.wd == LTC_FORTUNA_WD) && (prng->fortuna.pool0_len >= 64)) {
292 if (_fortuna_reseed(prng) != CRYPT_OK) {
297 /* ensure that one reseed happened before allowing to read */
298 if (prng->fortuna.reset_cnt == 0) {
302 /* now generate the blocks required */
305 /* handle whole blocks without the extra XMEMCPY */
306 while (outlen >= 16) {
307 /* encrypt the IV and store it */
308 rijndael_ecb_encrypt(prng->fortuna.IV, out, &prng->fortuna.skey);
311 _fortuna_update_iv(prng);
314 /* left over bytes? */
316 rijndael_ecb_encrypt(prng->fortuna.IV, tmp, &prng->fortuna.skey);
317 XMEMCPY(out, tmp, outlen);
318 _fortuna_update_iv(prng);
321 /* generate new key */
322 rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K , &prng->fortuna.skey);
323 _fortuna_update_iv(prng);
325 rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K+16, &prng->fortuna.skey);
326 _fortuna_update_iv(prng);
328 if (rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey) != CRYPT_OK) {
333 #ifdef LTC_CLEAN_STACK
334 zeromem(tmp, sizeof(tmp));
336 LTC_MUTEX_UNLOCK(&prng->lock);
342 @param prng The PRNG to terminate
343 @return CRYPT_OK if successful
345 int fortuna_done(prng_state *prng)
348 unsigned char tmp[32];
350 LTC_ARGCHK(prng != NULL);
352 LTC_MUTEX_LOCK(&prng->lock);
355 /* terminate all the hashes */
356 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
357 if ((err = sha256_done(&(prng->fortuna.pool[x]), tmp)) != CRYPT_OK) {
361 /* call cipher done when we invent one ;-) */
362 err = CRYPT_OK; /* success */
365 #ifdef LTC_CLEAN_STACK
366 zeromem(tmp, sizeof(tmp));
368 LTC_MUTEX_UNLOCK(&prng->lock);
369 LTC_MUTEX_DESTROY(&prng->lock);
374 Export the PRNG state
375 @param out [out] Destination
376 @param outlen [in/out] Max size and resulting size of the state
377 @param prng The PRNG to export
378 @return CRYPT_OK if successful
380 int fortuna_export(unsigned char *out, unsigned long *outlen, prng_state *prng)
384 unsigned long len = fortuna_desc.export_size;
386 LTC_ARGCHK(out != NULL);
387 LTC_ARGCHK(outlen != NULL);
388 LTC_ARGCHK(prng != NULL);
390 LTC_MUTEX_LOCK(&prng->lock);
397 /* we'll write bytes for s&g's */
400 err = CRYPT_BUFFER_OVERFLOW;
404 md = XMALLOC(sizeof(hash_state));
410 /* to emit the state we copy each pool, terminate it then hash it again so
411 * an attacker who sees the state can't determine the current state of the PRNG
413 for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
415 XMEMCPY(md, &(prng->fortuna.pool[x]), sizeof(*md));
418 if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
423 if ((err = sha256_init(md)) != CRYPT_OK) {
426 if ((err = sha256_process(md, out+x*32, 32)) != CRYPT_OK) {
429 if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
437 #ifdef LTC_CLEAN_STACK
438 zeromem(md, sizeof(*md));
442 LTC_MUTEX_UNLOCK(&prng->lock);
448 @param in The PRNG state
449 @param inlen Size of the state
450 @param prng The PRNG to import
451 @return CRYPT_OK if successful
453 int fortuna_import(const unsigned char *in, unsigned long inlen, prng_state *prng)
457 LTC_ARGCHK(in != NULL);
458 LTC_ARGCHK(prng != NULL);
460 if (inlen < (unsigned long)fortuna_desc.export_size) {
461 return CRYPT_INVALID_ARG;
464 if ((err = fortuna_start(prng)) != CRYPT_OK) {
468 if ((err = _fortuna_update_seed(in, inlen, prng)) != CRYPT_OK) {
477 @return CRYPT_OK if successful, CRYPT_NOP if self-testing has been disabled
479 int fortuna_test(void)
486 if ((err = sha256_test()) != CRYPT_OK) {
489 return rijndael_test();
496 /* ref: $Format:%D$ */
497 /* git commit: $Format:%H$ */
498 /* commit time: $Format:%ai$ */