2
$\begingroup$

I have both Yarrow and Fortuna implemented as number generators. I ran 100 complete DieHarder (entropy tester) tests for each implementation using the same entropy source. The results were surprising: Fortuna doesn't perform as well as Yarrow.

The results show marginally worse results when generating with Fortuna.

Is the purpose of using the Fortuna PRNG more about security and preventing a 'seed leakage' than it is about the 'quality' of its generated random values?

As requested, here are the results from 100 samples:

Fortuna
Test Name                                    PASSED    WEAK    POOR    FAILED
-----------------------------------------  --------  ------  ------  --------
RGB Bit Distribution Test                        97       3       0         0
RGB Bit Distribution Test                        96       3       1         0
RGB Bit Distribution Test                        98       2       0         0
RGB Bit Distribution Test                        98       2       0         0
RGB Bit Distribution Test                        97       3       0         0
RGB Bit Distribution Test                        97       3       0         0
RGB Bit Distribution Test                        95       3       2         0
RGB Bit Distribution Test                        97       2       1         0
RGB Bit Distribution Test                        97       3       0         0
RGB Bit Distribution Test                        98       1       1         0
RGB Bit Distribution Test                        94       6       0         0
RGB Bit Distribution Test                        87       8       5         0
Diehard(er) Birthdays Test                       95       3       2         0
Diehard OPERM5 Test                              17      18      45        20
Diehard 32x32 Binary Rank Test                  100       0       0         0
Diehard 6x8 Binary Rank Test                     89      10       1         0
Diehard Bitstream Test                            2       7      61        30
Diehard OPSO                                     77      14       8         1
Diehard OQSO Test                                96       4       0         0
Diehard DNA Test                                 78      16       6         0
Diehard Count the 1s (stream) Test               91       6       3         0
Diehard Count the 1s Test (byte)                 94       4       2         0
Diehard Parking Lot Test                         96       3       1         0
Diehard Minimum Distance (2d Circle) Test        96       3       1         0
Diehard 3d Sphere (Minimum Distance) Test        95       5       0         0
Example Dieharder Test                           94       6       0         0
Diehard Sums Test                                 0       0       0       100
Diehard Runs Test                                96       3       1         0
Diehard Runs Test                                97       3       0         0
Diehard(er) Craps Test                           99       1       0         0
Diehard(er) Craps Test                           97       3       0         0
Marsaglia and Tsang GCD Test                     99       1       0         0
Marsaglia and Tsang GCD Test                     99       1       0         0
STS Monobit Test                                 97       3       0         0
STS Runs Test                                    98       1       1         0
Example Dieharder Test                           98       1       1         0

Yarrow
Test Name                                    PASSED    WEAK    POOR    FAILED
-----------------------------------------  --------  ------  ------  --------
RGB Bit Distribution Test                        98       1       1         0
RGB Bit Distribution Test                        95       5       0         0
RGB Bit Distribution Test                        98       2       0         0
RGB Bit Distribution Test                        98       2       0         0
RGB Bit Distribution Test                        96       2       2         0
RGB Bit Distribution Test                       100       0       0         0
RGB Bit Distribution Test                        98       1       1         0
RGB Bit Distribution Test                        97       3       0         0
RGB Bit Distribution Test                        95       5       0         0
RGB Bit Distribution Test                        99       1       0         0
RGB Bit Distribution Test                        98       2       0         0
RGB Bit Distribution Test                        97       3       0         0
Diehard(er) Birthdays Test                       95       5       0         0
Diehard OPERM5 Test                              15      20      51        14
Diehard 32x32 Binary Rank Test                   97       2       1         0
Diehard 6x8 Binary Rank Test                     91       6       3         0
Diehard Bitstream Test                            4       8      57        31
Diehard OPSO                                     76      16       8         0
Diehard OQSO Test                                98       2       0         0
Diehard DNA Test                                 81      13       4         2
Diehard Count the 1s (stream) Test               94       3       3         0
Diehard Count the 1s Test (byte)                 92       4       4         0
Diehard Parking Lot Test                         97       2       1         0
Diehard Minimum Distance (2d Circle) Test        94       6       0         0
Diehard 3d Sphere (Minimum Distance) Test        95       4       1         0
Example Dieharder Test                           99       1       0         0
Diehard Sums Test                                 0       0       0       100
Diehard Runs Test                                95       4       1         0
Diehard Runs Test                                98       1       1         0
Diehard(er) Craps Test                           97       3       0         0
Diehard(er) Craps Test                           98       2       0         0
Marsaglia and Tsang GCD Test                     97       2       1         0
Marsaglia and Tsang GCD Test                     96       3       1         0
STS Monobit Test                                 98       2       0         0
STS Runs Test                                    95       4       1         0
Example Dieharder Test                           98       2       0         0
$\endgroup$
  • 1
    $\begingroup$ Fortuna uses AES in CTR mode (usually) to generate the output, which is a widely accepted method to generate a pseudorandom bitstream. Chances are you just had bad luck there and Fortuna performed slightly worse (this happens statistically seen) when running the statistic tests. $\endgroup$ – SEJPM Sep 28 '16 at 14:29
  • 2
    $\begingroup$ To round off this question properly, you absolutely need to quantify "marginally". Randomness is only a statistical effect based on percentages, and human acceptance of random changes with time. It would be useful to know some of your experimental percentages /outputs. $\endgroup$ – Paul Uszak Sep 28 '16 at 14:45
  • 3
    $\begingroup$ Going through the results you have listed, I don't see any statistically significant difference. If Fortuna was listed as failing Diehard OPERM5 Test 20 times, while Yarrow is listed as failing the same test 14 times, that is within the expected range due to randomness (and that OPERM5 test detects more than 1 failure over 100 runs more likely shows more that the Diehard test is bad, rather than these RNGs are) $\endgroup$ – poncho Sep 28 '16 at 16:36
  • 2
    $\begingroup$ @Whome: As you're guessing, it's not "better" because the output is any more random. It's better because it's more robust against some kinds of attack. I.e., the improvements are only in the context of an active attacker trying to defeat the RNG. $\endgroup$ – Luis Casillas Sep 28 '16 at 18:04
  • 2
    $\begingroup$ @poncho it depends on the threat /evaluation model you're considering for your RNG. A common one I've encountered is that the attacker is given the internal state at one point and then it's measured at which point the RNG has re-gained a reasonable amount of entropy. That's the whole point of the Fortuna construction: recover from (punctual) state leaks more relieably than all previous CSPRNGs. $\endgroup$ – SEJPM Sep 28 '16 at 19:21
7
$\begingroup$

Is the purpose of using the Fortuna PRNG more about security and preventing a 'seed leakage' than it is about the 'quality' of its generated random values?

No. It's not about the 'quality' of generated random values. It's about DieHarder being very paranoic about things that are indeed good quality. Just because your RNG gave you zero three times in a row, it doesn't really mean it's a bad RNG-- this is expected to happen. DieHarder has a known history in failing every RNG in existence from time to time. Your results are simply random; next time you could get opposite results.

If the test result deltas can be attributed to randomness, how can Fortuna be evaluated as a better PRNG?

DieHarder only decides if output is random-looking or not. It's a blackbox approach. This can only find major mistakes in RNG quality, and DieHarder pushing the limits also detects good RNGs as poor. Cryptographers have a whitebox approach, which gives more details about the cipher, how secure it is etc. Essentially, we want the attacker with the most details/data/attack points given failing an attack (which DieHarder can't simulate well). Yarrow has a less clear approach with trying to determine input quality. Fortuna simplifies this because it uses more randomness pools (and also avoids some problems this way). Also, Yarrow uses algorithms which are now deprecated, and some are broken (not to even mention minor flaws like being inefficient): SHA-1 and 3DES. Those can be changed, but why bother when we have new a standard that uses unbroken algorithms?

Simply said: Fortuna is simpler to implement, uses better primitives out-of-the-box and is generally considered better (because Yarrow has some mistakes that Fortuna fixes). All that with having bigger security margins and better efficiency. There is no reason to consider Yarrow if Fortuna is available.

$\endgroup$

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.