Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've implemented LibTomCrypt's version of fortuna and am wondering about the pool resetting after a reseed. In fortuna.c in libtomcrypt we have the following (which is that part that adds the entropy from the pools into the key),

for (x = 0; x < LTC_FORTUNA_POOLS; x++) {
  if (x == 0 || ((prng->fortuna.reset_cnt >> (x-1)) & 1) == 0) { 
      /* terminate this hash */
      if ((err = sha256_done(&prng->fortuna.pool[x], tmp)) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err; 
      }
      /* add it to the string */
      if ((err = sha256_process(&md, tmp, 32)) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err;
      }
      /* reset this pool */
      if ((err = sha256_init(&prng->fortuna.pool[x])) != CRYPT_OK) {
         sha256_done(&md, tmp);
         return err;
      }
   } else {
      break;
   }
}

Once the pool has been added to the key, it is reset, why is that? I realise that at that point the entropy has been included in the key, so it has been used, but why not just keep adding entropy to the pool and have it keep all the entropy from the beginning of time? Is there any disadvantage if the pools are not reset?

share|improve this question
1  
Well, the question here is more about whether the pools should or shouldn't be reset, based on an example implementation which does reset them. What I want to know is whether the algorithm requires the pools to be reset and what the reasons are for that. –  Duncan Drennan Apr 7 at 9:36
2  
You can download the paper from schneier.com/fortuna.pdf . Regarding the reset you are talking about: it does appear in the paper. I don't know the rationale behind it, but I suppose it has to do with avoiding poisoning of the pools. But the paper is very terse and does not give much reasons about the decisions made :-(. –  izaera Apr 7 at 10:43
add comment

2 Answers 2

up vote 2 down vote accepted

As noted by izaera, that reset of the pool is explicitly specified in Fortuna, and not an implementation artifact.

The pools in Fortuna are SHA-256 hashes. By definition, in order to obtain a pool's result, the SHA-256 hash must be obtained (in the present code, that's the job of sha256_done). With a standard SHA-256 implementation, there is no way to continue a hash after obtaining its result (e.g. sha256_process could fail after sha256_done until another sha256_init has been performed). I have not checked if it is the case in LibTomCrypt, but it would be the case with the equivalent in java.security.MessageDigest.

This provides an incentive for a "reset of the pool": restarting the pool/SHA-256 from scratch is the simplest option compatible with obtaining the hash and making the pool able to collect entropy again, that allows to use standard SHA-256 libraries.

It would be possible to reenter the collected entropy (here, tmp returned by sha256_done). That would be more complex, and slower. Most importantly, it is not necessary for the security rationale of Fortuna, which has a large enough state beyond the pools.


Another argument on the same line of thought: with standard SHA-256 libraries, there is no way to save and restore the state of a hash (except by saving the whole input), when we might want to save the state of Fortuna (as compactly as possible).

share|improve this answer
1  
Thanks! The explanation about restarting SHA256 makes perfect sense, so that helps it fall into place correctly in my mind - much appreciated. –  Duncan Drennan Apr 8 at 10:33
add comment

If nothing else, it makes the output of the pool irrecoverable. One of Fortuna's goals is to make prior Fortuna outputs safe from a compromise (the discovery of all of Fortuna's current data by an adversary). If the pool continued on without a reset, with little or no entropy added before the compromise took place, the adversary could more easily calculate the past contents of the master pool.

Edit: Per M. Grieu (Merci!), let's make that "more easily verify guesses of past inputs to the master pool".

Also, I believe the OP's question is less about LibTomCrypt than about the Fortuna algorithm itself.

share|improve this answer
    
Discounting the counter, the master state evolves per $K←\text{SHA}_d\text{-256}(K||s)$ where $s$ is built from the pool outputs. That makes it computationally impossible to calculate the past contents of master state from current contents of master state and pools, even if that fully revealed past pool outputs. However, indeed, a reset of a pool after use makes it harder to verify a guess of the past contents of the master state from current contents of master state and pools. –  fgrieu Apr 10 at 5:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.