Random number generators

Dennis E. Hamilton dennis.hamilton at acm.org
Tue Mar 17 17:38:18 UTC 2015


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.


 -- Dennis E. Hamilton
    orcmid at apache.org
    dennis.hamilton at acm.org    +1-206-779-9430
    https://keybase.io/orcmid  PGP F96E 89FF D456 628A
    X.509 certs used and requested for signed e-mail

-----Original Message-----
From: owner-freebsd-numerics at freebsd.org [mailto:owner-freebsd-numerics at freebsd.org] On Behalf Of Pedro Giffuni
Sent: Tuesday, March 17, 2015 05:11
To: Steve Kargl
Cc: freebsd-numerics at FreeBSD.org
Subject: Re: Random number generators


> Il giorno 17/mar/2015, alle ore 01:03, Steve Kargl <sgk at troutmask.apl.washington.edu> ha scritto:
> 
> On Mon, Mar 16, 2015 at 11:22:31PM -0500, Pedro Giffuni wrote:
>> Hi;
>> 
>> FreeBSD libc random functions are not too bad but in general I was having some thoughts about how the random generator functions in libc are slow and predictable and how just about every application nowadays is including "Mersenne Twister"  or similar algorithms (which are fast and better in every way but can?t be adapted for the C API) in their applications.
>> 
>> OpenBSD did something drastic about it [1], breaking standards and compatibility and whatnot.
>> I wouldn?t go there and I don?t think there is any real ?solution? for this. The musl libc guys tried something interesting though. They took the tempering function from MT:
>> 
>> http://git.musl-libc.org/cgit/musl/commit/?id=20d01d83b5a13c77805976e7c520f566244ba3ff <http://git.musl-libc.org/cgit/musl/commit/?id=20d01d83b5a13c77805976e7c520f566244ba3ff>
>> 
>> It should be something relatively easy to try on our implementation too, if someone feels like running the tests and measuring if there is a difference.
>> 
>> Pedro.
>> 
>> [1[ http://www.tedunangst.com/flak/post/random-in-the-wild
>> 
>> 
> 
> I suppose it depends on what you want to accomplish.  MT
> can be a horrible thing to use.  See the history of 
> libgfortran/intrinsics/random.c (svn r82443) where I ripped
> MT out many years ago in favor of George Marsaglia's KISS generator.
> The KISS generator that I used was his 32-bit version.  GM has
> a 64-bit generator as well.  The 32-bit version passed all
> of GM's diehard tests.  I haven't read a report on the
> 64-bit generator's diehard result. 
> 

Oh, absolutely, I am considering something like this for OpenOffice.
Apache OpenOffice (and LibreOffice, I think) is using MT (from Boost)
but the seeding is not done properly.

[ ... ]

> One big issue is saving internal state.  IIRC, MT requires 623-bit
> of internal state.  KISS requires 4 32-bit int.  Thus, if
> you want to reseed the generator, KISS requires far less effort.
> 

Yes, the problem is the that libc requires a single 32 (or 31) bit seed.
Given that restriction, our existing generator is not bad. Enforcing something
better breaks the API and is not really practical to get crypto-grade randomness
for stuff like refreshing a slide in a presentation anyways.

The musl libc approach seemed reasonable but I haven’t looked at the
base random generator there (I’ve heard the glibc one is not good at all).

Pedro.


_______________________________________________
freebsd-numerics at freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-numerics
To unsubscribe, send any mail to "freebsd-numerics-unsubscribe at freebsd.org"



More information about the freebsd-numerics mailing list