4 ms·

The Security of the Fortuna PRNG

40 points by edwintorok 13y ago

andrewcooke 13y ago
exercise for the reader. compare the information density in this paper to the months and months of useless pissing in the wind on this subject in cryptography@metzdowd.com
- tptacek 13y ago
  I don't read that list (my understanding is, it's all pissing in the wind) --- is it amusing? Can you give us a capsule summary?
  - andrewcooke 13y ago
    no, not amusing at all. do you have any suggestions for something better (i mainly lurk unless i can answer something obvious)?
  - pbsd 13y ago
    If you find CFRG infuriating at times, don't even bother with the metzdowd list -- it's an order of magnitude worse.
TillE 13y ago
I see Yarrow and Fortuna are quite popular, but is there any reason that people shouldn't use stream ciphers like Salsa20 (or RC4 in OpenBSD, I guess) as a CSPRNG? They're designed for nearly identical purposes, and some of them have been pretty well analyzed.
- delinka 13y ago
  RC4 has shown weaknesses over time [1] that should make any user wary. I'm sure RC4 has its place, but probably not as the sole source of randomness in a Real Security Application®. 1 - https://en.wikipedia.org/wiki/RC4#Biased_outputs_of_the_RC4 https://en.wikipedia.org/wiki/RC4#Biased_outputs_of_the_RC4
  - edwintorok 13y ago
    In fact OpenBSD will use Chacha20 in the next version for its arc4random implementation: http://marc.info/?l=openbsd-cvs&m=138065251627052 http://marc.info/?l=openbsd-cvs&m=138065251627052 And I think FreeBSD might follow and switch its implementation too.
    - tptacek 13y ago
      Its implementation of arc4random, you mean; not its /dev/random, right?
      - clarry 13y ago
        replace rc4 with ChaCha20 here, too; ok djm, tedu, deraadt http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c.diff?r1=1.144;r2=1.145 http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c.diff... http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c
      - throwaway2048 13y ago
        it is now both /dev/random and /dev/urandom on openbsd
        clarry 13y ago
        Right, there used to be a number of different random devices, including random, arandom, urandom, prandom, and srandom. Prandom was killed quite some time ago, and as of 2011 all the rest are unified. Four /dev nodes still exist for compatibility, but they all behave identical; so there's really just one random device. The principle being that there's good randomness and there's good randomness. The system does its best to provide good randomness. You can't choose the wrong device.
- TallGuyShort 13y ago
  Much of the Fortuna design is concerned with accumulating and using entropy effectively - there's more to it than just the random output generator.
delinka 13y ago
This is what I like about Schneier. He makes things, knows they need analysis by other people, and when the analysis comes in negative, he accepts it. No quibbling, no weaseling, just a "that's the way it is" attitude.
- gjm11 13y ago
  The analysis didn't come in negative. It describes the key idea in Yarrow and Fortuna as "simple but brilliant", and finds that Fortuna does its job rather well. It corrects a couple of (not very large) errors in the paper that introduced Fortuna and presents a modified version that does better. None of that makes either Schneier or Fortuna look substantially bad. Accordingly, there's nothing very surprising or impressive in the fact that he's prepared to accept it. (For the avoidance of doubt, I am not -- at all -- making any criticism of Schneier. Just saying that Schneier's response to this paper isn't anything special.) [EDITED to add: Perhaps you were thinking that the paper's presentation of the "premature next" problem amounts to demonstrating a weakness in Fortuna? No -- dealing with the "premature next" problem was a key design goal of Fortuna, and it did it rather well. The paper just shows how to do it even better.]
TallGuyShort 13y ago
This reminds me, in my undergraduate I implemented Fortuna in C and used it for a project in my statistics class. I seeded the generator and provided entropy from different sources, then scored the output according to the NIST's "Statistical Test Suite". I found that poor sources of entropy very consistently caused a statistically significant drop in the test suite's score. It's hardly as rigorous an analysis as this paper, and I had forgotten about it (what's more, I'm sure my implementation had a few flaws of its own). If anybody would be interested in the results I'll see if I can dig them out from an old backup... edit: I've found the code, data and paper from that project. It includes a bunch of software and papers released by the US Federal government, so I won't post the link here, but if anyone is interested let me know and I'll try figure out what I can and cannot redistribute.
clarry 13y ago
How likely a scenario RNG compromise is really?
- tptacek 13y ago
  That doesn't compromise more important aspects of the target? Very unlikely. Still, it's something you want covered. Note that the paper doesn't say Fortuna is worthless against compromised state; just that optimization techniques can be used to build an RNG that handles the problem better.
- edwintorok 13y ago
  It might be a problem if your device doesn't have enough entropy sources early on when it generates its SSH host keys, like a router for example, although there were some improvements in random number generation on MIPS lately: https://factorable.net/ https://factorable.net/

40 points by edwintorok 13y ago

exercise for the reader. compare the information density in this paper to the months and months of useless pissing in the wind on this subject in cryptography@metzdowd.com

tptacek 13y ago
I don't read that list (my understanding is, it's all pissing in the wind) --- is it amusing? Can you give us a capsule summary?
- andrewcooke 13y ago
  no, not amusing at all. do you have any suggestions for something better (i mainly lurk unless i can answer something obvious)?
- pbsd 13y ago
  If you find CFRG infuriating at times, don't even bother with the metzdowd list -- it's an order of magnitude worse.

TillE 13y ago

I see Yarrow and Fortuna are quite popular, but is there any reason that people shouldn't use stream ciphers like Salsa20 (or RC4 in OpenBSD, I guess) as a CSPRNG? They're designed for nearly identical purposes, and some of them have been pretty well analyzed.

delinka 13y ago
RC4 has shown weaknesses over time [1] that should make any user wary. I'm sure RC4 has its place, but probably not as the sole source of randomness in a Real Security Application®. 1 - https://en.wikipedia.org/wiki/RC4#Biased_outputs_of_the_RC4 https://en.wikipedia.org/wiki/RC4#Biased_outputs_of_the_RC4
- edwintorok 13y ago
  In fact OpenBSD will use Chacha20 in the next version for its arc4random implementation: http://marc.info/?l=openbsd-cvs&m=138065251627052 http://marc.info/?l=openbsd-cvs&m=138065251627052 And I think FreeBSD might follow and switch its implementation too.
  - tptacek 13y ago
    Its implementation of arc4random, you mean; not its /dev/random, right?
    - clarry 13y ago
      replace rc4 with ChaCha20 here, too; ok djm, tedu, deraadt http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c.diff?r1=1.144;r2=1.145 http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c.diff... http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c http://www.openbsd.org/cgi-bin/cvsweb/src/sys/dev/rnd.c
    - throwaway2048 13y ago
      it is now both /dev/random and /dev/urandom on openbsd
      - clarry 13y ago
        Right, there used to be a number of different random devices, including random, arandom, urandom, prandom, and srandom. Prandom was killed quite some time ago, and as of 2011 all the rest are unified. Four /dev nodes still exist for compatibility, but they all behave identical; so there's really just one random device. The principle being that there's good randomness and there's good randomness. The system does its best to provide good randomness. You can't choose the wrong device.
TallGuyShort 13y ago
Much of the Fortuna design is concerned with accumulating and using entropy effectively - there's more to it than just the random output generator.

delinka 13y ago

This is what I like about Schneier. He makes things, knows they need analysis by other people, and when the analysis comes in negative, he accepts it. No quibbling, no weaseling, just a "that's the way it is" attitude.

gjm11 13y ago
The analysis didn't come in negative. It describes the key idea in Yarrow and Fortuna as "simple but brilliant", and finds that Fortuna does its job rather well. It corrects a couple of (not very large) errors in the paper that introduced Fortuna and presents a modified version that does better. None of that makes either Schneier or Fortuna look substantially bad. Accordingly, there's nothing very surprising or impressive in the fact that he's prepared to accept it. (For the avoidance of doubt, I am not -- at all -- making any criticism of Schneier. Just saying that Schneier's response to this paper isn't anything special.) [EDITED to add: Perhaps you were thinking that the paper's presentation of the "premature next" problem amounts to demonstrating a weakness in Fortuna? No -- dealing with the "premature next" problem was a key design goal of Fortuna, and it did it rather well. The paper just shows how to do it even better.]

TallGuyShort 13y ago

This reminds me, in my undergraduate I implemented Fortuna in C and used it for a project in my statistics class. I seeded the generator and provided entropy from different sources, then scored the output according to the NIST's "Statistical Test Suite". I found that poor sources of entropy very consistently caused a statistically significant drop in the test suite's score. It's hardly as rigorous an analysis as this paper, and I had forgotten about it (what's more, I'm sure my implementation had a few flaws of its own). If anybody would be interested in the results I'll see if I can dig them out from an old backup... edit: I've found the code, data and paper from that project. It includes a bunch of software and papers released by the US Federal government, so I won't post the link here, but if anyone is interested let me know and I'll try figure out what I can and cannot redistribute.

clarry 13y ago

How likely a scenario RNG compromise is really?

tptacek 13y ago
That doesn't compromise more important aspects of the target? Very unlikely. Still, it's something you want covered. Note that the paper doesn't say Fortuna is worthless against compromised state; just that optimization techniques can be used to build an RNG that handles the problem better.
edwintorok 13y ago
It might be a problem if your device doesn't have enough entropy sources early on when it generates its SSH host keys, like a router for example, although there were some improvements in random number generation on MIPS lately: https://factorable.net/ https://factorable.net/