Random number generators

[John-Mark Gurney]

Pedro Giffuni wrote this message on Tue, Mar 17, 2015 at 13:39 -0500:
> On 03/17/15 13:18, Mehmet Erol Sanliturk wrote:
> >
> > On Tue, Mar 17, 2015 at 11:10 AM, Pedro Giffuni <pfg at freebsd.org 
> > <mailto:pfg at freebsd.org>> wrote:
> >
> >     On 03/17/15 12:22, Dennis E. Hamilton wrote:
> >
> >         There is a lot of discussion about qualities of Random Number
> >         generators on cryptography lists.  MT is not a good choice for
> >         that, but it might not need to be important for other
> >         applications.
> >
> >         There has been some recent work, PCG, that has attracted some
> >         attention, <http://www.pcg-random.org/>. There are good videos
> >         explaining what the approach is about as well.  PCG also has
> >         implementations in C.  (It is under the Apache License 2.0
> >         too: <https://github.com/imneme/pcg-c-basic> for a minimal
> >         family and <https://github.com/imneme/pcg-c> for ones with
> >         extended capabilities.)
> >
> >         The analysis of what does and doesn't work, and how passing
> >         diehard is too easy, is also valuable.
> >
> >         If you are serious about crypto grade randomness, libc is
> >         probably not the answer.  Generally, I don't think reliance on
> >         a single generator for general purpose use and for
> >         cryptographic quality is going to work well. This is a very
> >         context-sensitive situation and addressing specific threat
> >         models against cryptographic PRGs is a very different matter
> >         from wanting unpredictable and good quality pseudo-randoms for
> >         simulations and other purposes.

This is a statement I wholely agree with...

If you need an RNG for repeatable simulations, then you should
understand what you are getting, which means you won't be using random
OS's random(3) call.. If you don't really care about repeatablility,
then using the OS's CSPRNG should be just fine...

> >     The pcg-random link seems to be down now but for crypto, we have
> >     arc4random(3) which is pretty good and about to be improved further.
> >
> >     Pedro.
> >
> >     _______________________________________________
> >
> >
> >
> > Three of the above links are accessible from here at Izmir , in Turkey .
> >
> 
> It just came up here. It looks like PCG compares favorably with 
> ChaCha20, but
> this is PCG's page and the comparison is not very clear ("Secure" vs 
> "Challenging"?)

i.e. it's not secure, which means it MUST NOT be used for nonces and
key material...  Which makes it unsuitable for a replacement for
any arc4rand* function, be it userland or kernel...

The table on the page is incorrect...  ChaCha20 MUST ALWAYS be
Reproducible otherwise it isn't secure, same goes for arc4random...
They said not always reproducible, but that's just because it is
seeded differently, and implementations don't allow you to provide
a seed manually...  Most implementations automatically get their seed
from another secure PRNG, usually the kernel..  If someone were to
use their own implementation which allowed a custom seed (which this
page seems to require) then it is reproducible..

I find it funny that they consider it a problem w/ arc4random that it
can't be used w/ a user provided seed... That's a feature for what
arc4random is documented as being used for...  It would be a major
security issue if it was easy for a program to make arc4random to
return predictable numbers...  (See recent problem when arc4random
was being used w/ a possibly predictable seed.)

I would like to know what they think the period of ChaCha20... In one
place they list it as being huge, but in the negatives they say: "Has
a much smaller period than might be inferred from the size of the
generator state."  I don't know how they can predict the period of
ChaCha20..  If they mean you never reseed/stir it, then it's by
definition 2^69 as that is the counter roll over (each counter generates
64 bytes of output, so +2^5), or maybe 2^133 bytes if you include the
IV as part of the counter, but if you reseed/stir, then the period
would be very long, possibly effectively infinite if you use an
external source for seeding...

As someone who worked on a program that pretty much was just:
	if (customrandom() % 4)
		dominorwork();

and where customrandom was aes256-ctr, I still only saw something like
10-20% of the program's time generating randomness...  And this was a
pure software implementation of aes256, not AES-NI accelerated..  Yes,
having fast random numbers for simulations can be important, but is very
different problem than the one I'm addressing...

It's a shame they didn't just list MB/sec under the time performance
column...

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."