From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 17:38:17 2015 Return-Path: Delivered-To: freebsd-numerics@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id D7261809 for ; Tue, 17 Mar 2015 17:38:17 +0000 (UTC) Received: from barracuda.supercp.com (barracuda.supercp.com [216.234.124.51]) by mx1.freebsd.org (Postfix) with ESMTP id 9A74FE77 for ; Tue, 17 Mar 2015 17:38:17 +0000 (UTC) X-ASG-Debug-ID: 1426612974-0798da1d4f4b5cd20001-eff8eK Received: from a2s42.a2hosting.com (a2s42.a2hosting.com [216.119.133.2]) by barracuda.supercp.com with ESMTP id XnB8huYDbEXoYUTq; Tue, 17 Mar 2015 13:22:54 -0400 (EDT) X-Barracuda-Envelope-From: dennis.hamilton@acm.org X-Barracuda-Apparent-Source-IP: 216.119.133.2 Received: from 75-165-123-152.tukw.qwest.net ([75.165.123.152]:33362 helo=Astraendo2) by a2s42.a2hosting.com with esmtpa (Exim 4.82) (envelope-from ) id 1YXvCf-0009NT-Dw; Tue, 17 Mar 2015 13:22:53 -0400 Reply-To: From: "Dennis E. Hamilton" To: References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> In-Reply-To: Subject: RE: Random number generators Date: Tue, 17 Mar 2015 10:22:51 -0700 X-ASG-Orig-Subj: RE: Random number generators Organization: NuovoDoc Message-ID: <00a001d060d7$0077f100$0167d300$@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-Mailer: Microsoft Outlook 15.0 Thread-Index: AQH32Py7Ohz5iRyKYdk0RcO8dKEfnwHlGiR6AYuy88Wctm3QAA== Content-Language: en-us X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - a2s42.a2hosting.com X-AntiAbuse: Original Domain - freebsd.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - acm.org X-Get-Message-Sender-Via: a2s42.a2hosting.com: authenticated_id: himself+orcmid.com/only user confirmed/virtual account not confirmed X-Barracuda-Connect: a2s42.a2hosting.com[216.119.133.2] X-Barracuda-Start-Time: 1426612974 X-Barracuda-URL: https://216.234.124.51:443/cgi-mod/mark.cgi Received-SPF: softfail (supercp.com: domain of transitioning dennis.hamilton@acm.org does not designate 75.165.123.152 as permitted sender) X-Virus-Scanned: by bsmtpd at supercp.com X-Barracuda-BRTS-Status: 1 X-Barracuda-Spam-Score: 0.00 X-Barracuda-Spam-Status: No, SCORE=0.00 using per-user scores of TAG_LEVEL=1000.0 QUARANTINE_LEVEL=4.0 KILL_LEVEL=5.0 tests=BSF_SC0_MISMATCH_TO, BSF_SPF_SOFTFAIL X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.16814 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.00 BSF_SC0_MISMATCH_TO Envelope rcpt doesn't match header 0.00 BSF_SPF_SOFTFAIL Custom Rule SPF Softfail Cc: 'Pedro Giffuni' X-BeenThere: freebsd-numerics@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: "Discussions of high quality implementation of libm functions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 17 Mar 2015 17:38:18 -0000 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, = . 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: = for a minimal family and = 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 = 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 = >>=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"