Date: Tue, 17 Mar 2015 10:22:51 -0700 From: "Dennis E. Hamilton" <dennis.hamilton@acm.org> To: <freebsd-numerics@FreeBSD.org> Cc: 'Pedro Giffuni' <pfg@FreeBSD.org> Subject: RE: Random number generators Message-ID: <00a001d060d7$0077f100$0167d300$@acm.org> In-Reply-To: <F6137E2C-FDF2-46B3-BFC2-1975AFA40951@FreeBSD.org> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <F6137E2C-FDF2-46B3-BFC2-1975AFA40951@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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. =20 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@apache.org dennis.hamilton@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@freebsd.org = [mailto:owner-freebsd-numerics@freebsd.org] On Behalf Of Pedro Giffuni Sent: Tuesday, March 17, 2015 05:11 To: Steve Kargl Cc: freebsd-numerics@FreeBSD.org Subject: Re: Random number generators > Il giorno 17/mar/2015, alle ore 01:03, Steve Kargl = <sgk@troutmask.apl.washington.edu> ha scritto: >=20 > On Mon, Mar 16, 2015 at 11:22:31PM -0500, Pedro Giffuni wrote: >> Hi; >>=20 >> 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. >>=20 >> 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: >>=20 >> = http://git.musl-libc.org/cgit/musl/commit/?id=3D20d01d83b5a13c77805976e7c= 520f566244ba3ff = <http://git.musl-libc.org/cgit/musl/commit/?id=3D20d01d83b5a13c77805976e7= c520f566244ba3ff> >>=20 >> 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. >>=20 >> Pedro. >>=20 >> [1[ http://www.tedunangst.com/flak/post/random-in-the-wild >>=20 >>=20 >=20 > I suppose it depends on what you want to accomplish. MT > can be a horrible thing to use. See the history of=20 > 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.=20 >=20 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. >=20 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=E2=80=99t looked at = the base random generator there (I=E2=80=99ve heard the glibc one is not = good at all). Pedro. _______________________________________________ freebsd-numerics@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-numerics To unsubscribe, send any mail to = "freebsd-numerics-unsubscribe@freebsd.org"
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?00a001d060d7$0077f100$0167d300$>