I have implemented the Fortuna random number generator as described in chapter 10 of "Practical Cryptography" (Ferguson and Schneier, Wiley, 2003), the result can be found at http://www.seehuhn.de/pages/fortuna .

My question: How can I test my implementation? Or more specifically:

  • Are there any known-correct test vectors for the Fortuna generator available?
  • Are there automated tests for the cryptographic properties of the output? (I know how to test the statistical properties of the output, but I don't know how to test the cryptographic properties.)
  • Any other testing methodologies I should consider?
  • $\begingroup$ Take a look at Fourmilab, it seems to have what you need. $\endgroup$ – rath Jul 24 '13 at 12:19
  • $\begingroup$ @rath, thanks for your suggestion. I have tried the tool from Fourmilab, and my generator passes without problems; results are now on my Fortuna web page. Slightly worryingly, the tests still pass when I deliberately break my code by disabling the rekeying (which is prescribed to happen after every megabyte of output). $\endgroup$ – jochen Jul 24 '13 at 13:39
  • $\begingroup$ Although not the best thing to ask for (because results are completly dependant on 'ent' and this is getting too localized) could you also post the results of the control data? $\endgroup$ – rath Jul 24 '13 at 14:18
  • 1
    $\begingroup$ @rath, I am not quite sure what you mean by "control data". Assuming you mean the output of ent for the generator without rekeying, I've put this up at gist.github.com/seehuhn/6071391 now. $\endgroup$ – jochen Jul 24 '13 at 15:03
  • 1
    $\begingroup$ Related: how-to-prove-the-security-of-the-prng $\endgroup$ – Cryptographeur Dec 3 '13 at 10:46

Robert Brown of Duke University has an excellent test suite called "Dieharder". Supposedly this is the most stringent battery of PRG tests available. I have never used it but it will be worth your while to check it out.

  • 1
    $\begingroup$ The answer wasn't quite what I had hoped for (the tests are mostly for the statistical properties of the output), but this being the only answer it's clearly also the best answer, so I have accepted it now :) $\endgroup$ – jochen Aug 27 '13 at 22:30
  • $\begingroup$ @jochen: If you want to test the cryptographic properties you have to see if anyone can "break the generator" by using the output bits to find the secret key. $\endgroup$ – William Hird Aug 27 '13 at 22:59

Perhaps obvious, but couldn't you download other implementations, design a test set of your own, and run it through multiple implementations to verify the same results?

There are these implementations:

If system entropy is an issue, you might be able to tweak all implementations to fudge the updates to be equal.

  • 1
    $\begingroup$ That's what I did in the end: the test vectors at seehuhn.de/pages/fortuna#sec:4.1.0 are generated using the Python Cryptography Toolkit and I managed to make the output of my implementation match with this. Many implementations are subtly different from Schneier's version (e.g. using a different number of entropy buffers), so I didn't get agreement with any other implementations. $\endgroup$ – jochen Dec 3 '13 at 19:12

Testing properly implemented Fortuna is little different than testing any alleged cryptographically secure random number generator. The fundamental problem is a philosophical one, as well as a practical one. For simulation it may be sufficient to choose digits from pi, which is universally believed to be randomly distributed. But, as a cryptographic key or initialization vector or most anything else cryptographic, this would be a spectacularly bad choice. Any attacker who suspected you of using pi digits has broken your system -- everybody knows those digits or can compute them with little effort.

Random requires that no attacker can predict, and given that some attackers will have half a brain, this is much more difficult than random for some simulation model.

Fortuna has the virtue that a great many practical issues have been addressed to maximize the entropy in the pool from which numbers are drawn. And, furthermore, Fortuna can be so configured to make this approach closer than for the usual random generator.

Knuth (vol 2) concluded, and no one has been able to do any better really, that the best you can do with any random number generator is to apply lots of statistical tests looking for patterns (he suggests many) and abandon any that show any patterns. Thase that are left are about as good as one can do.

A reading of a good account of information theory (originally Shannon) will give you much to think about in regard to entropy and the provision therefor.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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