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 (at) 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 */ 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 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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
