pd.if.org Git - zpackage/blob - libtomcrypt/src/prngs/fortuna.c

   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 #include "tomcrypt.h"
  10
  11 /**
  12   @file fortuna.c
  13   Fortuna PRNG, Tom St Denis
  14 */
  15
  16 /* Implementation of Fortuna by Tom St Denis
  17
  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 */
  21
  22 #ifdef LTC_FORTUNA
  23
  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)
  27 #endif
  28
  29 #ifndef LTC_FORTUNA_POOLS
  30    #warning LTC_FORTUNA_POOLS was not previously defined (old headers?)
  31    #define LTC_FORTUNA_POOLS 32
  32 #endif
  33
  34 #if LTC_FORTUNA_POOLS < 4 || LTC_FORTUNA_POOLS > 32
  35    #error LTC_FORTUNA_POOLS must be in [4..32]
  36 #endif
  37
  38 const struct ltc_prng_descriptor fortuna_desc = {
  39     "fortuna",
  40     (32 * LTC_FORTUNA_POOLS), /* default: 1024 */
  41     &fortuna_start,
  42     &fortuna_add_entropy,
  43     &fortuna_ready,
  44     &fortuna_read,
  45     &fortuna_done,
  46     &fortuna_export,
  47     &fortuna_import,
  48     &fortuna_test
  49 };
  50
  51 /* update the IV */
  52 static void _fortuna_update_iv(prng_state *prng)
  53 {
  54    int            x;
  55    unsigned char *IV;
  56    /* update IV */
  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;
  61    }
  62 }
  63
  64 /* reseed the PRNG */
  65 static int _fortuna_reseed(prng_state *prng)
  66 {
  67    unsigned char tmp[MAXBLOCKSIZE];
  68    hash_state    md;
  69    ulong64       reset_cnt;
  70    int           err, x;
  71
  72
  73    /* new K == LTC_SHA256(K || s) where s == LTC_SHA256(P0) || LTC_SHA256(P1) ... */
  74    sha256_init(&md);
  75    if ((err = sha256_process(&md, prng->fortuna.K, 32)) != CRYPT_OK) {
  76       sha256_done(&md, tmp);
  77       return err;
  78    }
  79
  80    reset_cnt = prng->fortuna.reset_cnt + 1;
  81
  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);
  87              return err;
  88           }
  89           /* add it to the string */
  90           if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
  91              sha256_done(&md, tmp);
  92              return err;
  93           }
  94           /* reset this pool */
  95           if ((err = sha256_init(&prng->fortuna.pool[x])) != CRYPT_OK) {
  96              sha256_done(&md, tmp);
  97              return err;
  98           }
  99        } else {
 100           break;
 101        }
 102    }
 103
 104    /* finish key */
 105    if ((err = sha256_done(&md, prng->fortuna.K)) != CRYPT_OK) {
 106       return err;
 107    }
 108    if ((err = rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey)) != CRYPT_OK) {
 109       return err;
 110    }
 111    _fortuna_update_iv(prng);
 112
 113    /* reset/update internals */
 114    prng->fortuna.pool0_len = 0;
 115    prng->fortuna.wd        = 0;
 116    prng->fortuna.reset_cnt = reset_cnt;
 117
 118
 119 #ifdef LTC_CLEAN_STACK
 120    zeromem(&md, sizeof(md));
 121    zeromem(tmp, sizeof(tmp));
 122 #endif
 123
 124    return CRYPT_OK;
 125 }
 126
 127 /**
 128   "Update Seed File"-compliant update of K
 129
 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
 134 */
 135 static int _fortuna_update_seed(const unsigned char *in, unsigned long inlen, prng_state *prng)
 136 {
 137    int           err;
 138    unsigned char tmp[MAXBLOCKSIZE];
 139    hash_state    md;
 140
 141    LTC_MUTEX_LOCK(&prng->lock);
 142    /* new K = LTC_SHA256(K || in) */
 143    sha256_init(&md);
 144    if ((err = sha256_process(&md, prng->fortuna.K, 32)) != CRYPT_OK) {
 145       sha256_done(&md, tmp);
 146       goto LBL_UNLOCK;
 147    }
 148    if ((err = sha256_process(&md, in, inlen)) != CRYPT_OK) {
 149       sha256_done(&md, tmp);
 150       goto LBL_UNLOCK;
 151    }
 152    /* finish key */
 153    if ((err = sha256_done(&md, prng->fortuna.K)) != CRYPT_OK) {
 154       goto LBL_UNLOCK;
 155    }
 156    _fortuna_update_iv(prng);
 157
 158 LBL_UNLOCK:
 159    LTC_MUTEX_UNLOCK(&prng->lock);
 160 #ifdef LTC_CLEAN_STACK
 161    zeromem(&md, sizeof(md));
 162 #endif
 163
 164    return err;
 165 }
 166
 167 /**
 168   Start the PRNG
 169   @param prng     [out] The PRNG state to initialize
 170   @return CRYPT_OK if successful
 171 */
 172 int fortuna_start(prng_state *prng)
 173 {
 174    int err, x, y;
 175    unsigned char tmp[MAXBLOCKSIZE];
 176
 177    LTC_ARGCHK(prng != NULL);
 178    prng->ready = 0;
 179
 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);
 185           }
 186           return err;
 187        }
 188    }
 189    prng->fortuna.pool_idx = prng->fortuna.pool0_len = prng->fortuna.wd = 0;
 190    prng->fortuna.reset_cnt = 0;
 191
 192    /* reset bufs */
 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);
 197       }
 198       return err;
 199    }
 200    zeromem(prng->fortuna.IV, 16);
 201
 202    LTC_MUTEX_INIT(&prng->lock)
 203
 204    return CRYPT_OK;
 205 }
 206
 207 /**
 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
 213 */
 214 int fortuna_add_entropy(const unsigned char *in, unsigned long inlen, prng_state *prng)
 215 {
 216    unsigned char tmp[2];
 217    int           err;
 218
 219    LTC_ARGCHK(prng != NULL);
 220    LTC_ARGCHK(in != NULL);
 221    LTC_ARGCHK(inlen > 0);
 222
 223    /* ensure inlen <= 32 */
 224    if (inlen > 32) {
 225       inlen = 32;
 226    }
 227
 228    /* add s || length(in) || in to pool[pool_idx] */
 229    tmp[0] = 0;
 230    tmp[1] = (unsigned char)inlen;
 231
 232    LTC_MUTEX_LOCK(&prng->lock);
 233    if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], tmp, 2)) != CRYPT_OK) {
 234       goto LBL_UNLOCK;
 235    }
 236    if ((err = sha256_process(&prng->fortuna.pool[prng->fortuna.pool_idx], in, inlen)) != CRYPT_OK) {
 237       goto LBL_UNLOCK;
 238    }
 239    if (prng->fortuna.pool_idx == 0) {
 240       prng->fortuna.pool0_len += inlen;
 241    }
 242    if (++(prng->fortuna.pool_idx) == LTC_FORTUNA_POOLS) {
 243       prng->fortuna.pool_idx = 0;
 244    }
 245    err = CRYPT_OK; /* success */
 246
 247 LBL_UNLOCK:
 248    LTC_MUTEX_UNLOCK(&prng->lock);
 249    return err;
 250 }
 251
 252 /**
 253   Make the PRNG ready to read from
 254   @param prng   The PRNG to make active
 255   @return CRYPT_OK if successful
 256 */
 257 int fortuna_ready(prng_state *prng)
 258 {
 259    int err;
 260    LTC_ARGCHK(prng != NULL);
 261
 262    LTC_MUTEX_LOCK(&prng->lock);
 263    err = _fortuna_reseed(prng);
 264    prng->ready = (err == CRYPT_OK) ? 1 : 0;
 265
 266    LTC_MUTEX_UNLOCK(&prng->lock);
 267    return err;
 268 }
 269
 270 /**
 271   Read from the PRNG
 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
 276 */
 277 unsigned long fortuna_read(unsigned char *out, unsigned long outlen, prng_state *prng)
 278 {
 279    unsigned char tmp[16];
 280    unsigned long tlen = 0;
 281
 282    if (outlen == 0 || prng == NULL || out == NULL) return 0;
 283
 284    LTC_MUTEX_LOCK(&prng->lock);
 285
 286    if (!prng->ready) {
 287       goto LBL_UNLOCK;
 288    }
 289
 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) {
 293          goto LBL_UNLOCK;
 294       }
 295    }
 296
 297    /* ensure that one reseed happened before allowing to read */
 298    if (prng->fortuna.reset_cnt == 0) {
 299       goto LBL_UNLOCK;
 300    }
 301
 302    /* now generate the blocks required */
 303    tlen = outlen;
 304
 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);
 309       out += 16;
 310       outlen -= 16;
 311       _fortuna_update_iv(prng);
 312    }
 313
 314    /* left over bytes? */
 315    if (outlen > 0) {
 316       rijndael_ecb_encrypt(prng->fortuna.IV, tmp, &prng->fortuna.skey);
 317       XMEMCPY(out, tmp, outlen);
 318       _fortuna_update_iv(prng);
 319    }
 320
 321    /* generate new key */
 322    rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K   , &prng->fortuna.skey);
 323    _fortuna_update_iv(prng);
 324
 325    rijndael_ecb_encrypt(prng->fortuna.IV, prng->fortuna.K+16, &prng->fortuna.skey);
 326    _fortuna_update_iv(prng);
 327
 328    if (rijndael_setup(prng->fortuna.K, 32, 0, &prng->fortuna.skey) != CRYPT_OK) {
 329       tlen = 0;
 330    }
 331
 332 LBL_UNLOCK:
 333 #ifdef LTC_CLEAN_STACK
 334    zeromem(tmp, sizeof(tmp));
 335 #endif
 336    LTC_MUTEX_UNLOCK(&prng->lock);
 337    return tlen;
 338 }
 339
 340 /**
 341   Terminate the PRNG
 342   @param prng   The PRNG to terminate
 343   @return CRYPT_OK if successful
 344 */
 345 int fortuna_done(prng_state *prng)
 346 {
 347    int           err, x;
 348    unsigned char tmp[32];
 349
 350    LTC_ARGCHK(prng != NULL);
 351
 352    LTC_MUTEX_LOCK(&prng->lock);
 353    prng->ready = 0;
 354
 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) {
 358           goto LBL_UNLOCK;
 359        }
 360    }
 361    /* call cipher done when we invent one ;-) */
 362    err = CRYPT_OK; /* success */
 363
 364 LBL_UNLOCK:
 365 #ifdef LTC_CLEAN_STACK
 366    zeromem(tmp, sizeof(tmp));
 367 #endif
 368    LTC_MUTEX_UNLOCK(&prng->lock);
 369    LTC_MUTEX_DESTROY(&prng->lock);
 370    return err;
 371 }
 372
 373 /**
 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
 379 */
 380 int fortuna_export(unsigned char *out, unsigned long *outlen, prng_state *prng)
 381 {
 382    int         x, err;
 383    hash_state *md;
 384    unsigned long len = fortuna_desc.export_size;
 385
 386    LTC_ARGCHK(out    != NULL);
 387    LTC_ARGCHK(outlen != NULL);
 388    LTC_ARGCHK(prng   != NULL);
 389
 390    LTC_MUTEX_LOCK(&prng->lock);
 391
 392    if (!prng->ready) {
 393       err = CRYPT_ERROR;
 394       goto LBL_UNLOCK;
 395    }
 396
 397    /* we'll write bytes for s&g's */
 398    if (*outlen < len) {
 399       *outlen = len;
 400       err = CRYPT_BUFFER_OVERFLOW;
 401       goto LBL_UNLOCK;
 402    }
 403
 404    md = XMALLOC(sizeof(hash_state));
 405    if (md == NULL) {
 406       err = CRYPT_MEM;
 407       goto LBL_UNLOCK;
 408    }
 409
 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
 412     */
 413    for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
 414       /* copy the PRNG */
 415       XMEMCPY(md, &(prng->fortuna.pool[x]), sizeof(*md));
 416
 417       /* terminate it */
 418       if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
 419          goto LBL_ERR;
 420       }
 421
 422       /* now hash it */
 423       if ((err = sha256_init(md)) != CRYPT_OK) {
 424          goto LBL_ERR;
 425       }
 426       if ((err = sha256_process(md, out+x*32, 32)) != CRYPT_OK) {
 427          goto LBL_ERR;
 428       }
 429       if ((err = sha256_done(md, out+x*32)) != CRYPT_OK) {
 430          goto LBL_ERR;
 431       }
 432    }
 433    *outlen = len;
 434    err = CRYPT_OK;
 435
 436 LBL_ERR:
 437 #ifdef LTC_CLEAN_STACK
 438    zeromem(md, sizeof(*md));
 439 #endif
 440    XFREE(md);
 441 LBL_UNLOCK:
 442    LTC_MUTEX_UNLOCK(&prng->lock);
 443    return err;
 444 }
 445
 446 /**
 447   Import a PRNG state
 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
 452 */
 453 int fortuna_import(const unsigned char *in, unsigned long inlen, prng_state *prng)
 454 {
 455    int           err;
 456
 457    LTC_ARGCHK(in    != NULL);
 458    LTC_ARGCHK(prng  != NULL);
 459
 460    if (inlen < (unsigned long)fortuna_desc.export_size) {
 461       return CRYPT_INVALID_ARG;
 462    }
 463
 464    if ((err = fortuna_start(prng)) != CRYPT_OK) {
 465       return err;
 466    }
 467
 468    if ((err = _fortuna_update_seed(in, inlen, prng)) != CRYPT_OK) {
 469       return err;
 470    }
 471
 472    return err;
 473 }
 474
 475 /**
 476   PRNG self-test
 477   @return CRYPT_OK if successful, CRYPT_NOP if self-testing has been disabled
 478 */
 479 int fortuna_test(void)
 480 {
 481 #ifndef LTC_TEST
 482    return CRYPT_NOP;
 483 #else
 484    int err;
 485
 486    if ((err = sha256_test()) != CRYPT_OK) {
 487       return err;
 488    }
 489    return rijndael_test();
 490 #endif
 491 }
 492
 493 #endif
 494
 495
 496 /* ref:         $Format:%D$ */
 497 /* git commit:  $Format:%H$ */
 498 /* commit time: $Format:%ai$ */