From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 04:25:32 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 4378230C for ; Tue, 17 Mar 2015 04:25:32 +0000 (UTC) Received: from nm34-vm2.bullet.mail.bf1.yahoo.com (nm34-vm2.bullet.mail.bf1.yahoo.com [72.30.239.74]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id EDD36AAB for ; Tue, 17 Mar 2015 04:25:31 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426566182; bh=u0FLXjzJDZcnSTsid2Hmig18Howrg29Nro3Wm6NfCJs=; h=From:Subject:Date:To:From:Subject; b=LNdgbhEETX0jg5j5yWrSAd/gW8m9b8dTc8MODFYjN2JAlvFSMhP8d6IYmt7t56GE15kGD2Czxaqa8KXQgDToJQnn4yk3xymEJ4EfBQayORkBHl+LgclQ4hlNo0XWGCXF5+gUdc5+thkWLj3LO8PrVDgjHyjyI9u+ePpoYjB5t8yd08BWnwIyV24LUOPSve562dv1nYCd3yQr3TV9nHYFQ344/41/1Hp4VwYvutI3nNj4DNNT8r0iM4m8XY0G544YtSD+Cnks9gpQIAAlE2sq58hl8TqTkSuuCACB9SeE4qExwZHOjMJ6XKpJJCLdOgLc4bIP4lC1XkMVGxIESDUf3w== Received: from [66.196.81.170] by nm34.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 04:23:02 -0000 Received: from [98.139.211.160] by tm16.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 04:23:02 -0000 Received: from [127.0.0.1] by smtp217.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 04:23:02 -0000 X-Yahoo-Newman-Id: 631154.9897.bm@smtp217.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: .JkPre0VM1kYFH6W_V3Apl1vObUiXoPylzPf6ck..sj9Aku w08SPr.bK6Nkh_s_5kGEMFnHq8YEhrCg4CuIaNzoQWvBHLPcv7NLnVvBI3iL kUjAbE8Ra05bnrkorzRnbrv87AkCMoBj6_BMxPdMNcPquWjHNrxJkCv_ygFy wDC32nsG83BYZiWEWQg7QsbhzVUL8lNWd4nVzjTbToCx7yQwDxjEYMTbZgL. 16JiXEFrQust7lDSmVp.9LEEtv.vNk4_psDq0H1esqS.nGZt_L3pkC1xMVCQ BbDqx5GTHkSF8fMZ9bFJusB0Waiw0vL2Lr4IW0DRPk86anUm3A9ePy6aMrPd 7J0qxT_m2w3PDXWSus7E5W8COC_VW5or2.ebYaTI05NSKVHZJaulrCZrr1ZH oKO11v60iGTYCIYuFPVPIo3HqaC3MUbjvjzFGSwzqZAQNfk7_NZ_Ch9WcNX7 yBZs5dmrzuXvIscGdOOSJfIM086YUFl.Wdtn2ZrbxlWDfuPSdAErQoeZztaH t6hcYfdzcJHujmJ3AXH0XTnN.X.gcBAVuF9Vrjh_StxSzBM.wQOKy0mTWQvt CMr7_1pfj77nrd4Cha0b_JE7C49p5EMfbgk3jFo_xPNynS8Id4XskR7enkB5 gq6.mx9SzLDQembEg10O5.a_klIadCgsqBGVDgy8UmYkBRZY53U3BQw9_kPN IvDRTkftvK3dPP5NULk7ncX0Cv7nA.NS1sIzMh1S5fZaO0zTcQRfSGyZ0f6C Fb0XfCfFGMrfOxDZ2Aq983O.tHNbKBc8uXg-- X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf From: Pedro Giffuni Subject: Random number generators Message-Id: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> Date: Mon, 16 Mar 2015 23:22:31 -0500 To: freebsd-numerics@FreeBSD.org Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) X-Mailer: Apple Mail (2.2070.6) Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.18-1 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 04:25:32 -0000 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=E2=80=99t be adapted for the C API) in = their applications. OpenBSD did something drastic about it [1], breaking standards and = compatibility and whatnot. I wouldn=E2=80=99t go there and I don=E2=80=99t think there is any real = =E2=80=9Csolution=E2=80=9D 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=3D20d01d83b5a13c77805976e7c5= 20f566244ba3ff = 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 From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 06:03:19 2015 Return-Path: Delivered-To: freebsd-numerics@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id BF1F11B4; Tue, 17 Mar 2015 06:03:19 +0000 (UTC) Received: from troutmask.apl.washington.edu (troutmask.apl.washington.edu [128.95.76.21]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 6F0683B6; Tue, 17 Mar 2015 06:03:16 +0000 (UTC) Received: from troutmask.apl.washington.edu (localhost [127.0.0.1]) by troutmask.apl.washington.edu (8.14.9/8.14.9) with ESMTP id t2H63A3D022045 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Mon, 16 Mar 2015 23:03:10 -0700 (PDT) (envelope-from sgk@troutmask.apl.washington.edu) Received: (from sgk@localhost) by troutmask.apl.washington.edu (8.14.9/8.14.9/Submit) id t2H63AMV022044; Mon, 16 Mar 2015 23:03:10 -0700 (PDT) (envelope-from sgk) Date: Mon, 16 Mar 2015 23:03:10 -0700 From: Steve Kargl To: Pedro Giffuni Subject: Re: Random number generators Message-ID: <20150317060310.GA21975@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> User-Agent: Mutt/1.5.23 (2014-03-12) Cc: freebsd-numerics@FreeBSD.org 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 06:03:19 -0000 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 > > 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. 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. -- Steve From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 12:10:56 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 1CDA091C for ; Tue, 17 Mar 2015 12:10:56 +0000 (UTC) Received: from nm14-vm0.bullet.mail.bf1.yahoo.com (nm14-vm0.bullet.mail.bf1.yahoo.com [98.139.213.164]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id C7B19609 for ; Tue, 17 Mar 2015 12:10:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426594248; bh=pM/RzuNzOHAXpTYQ3cf1W60sBiszFC7ZBooDt+EWs9o=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From:Subject; b=C5v30Ya21z5FjBzkZIez+cX11GOQYrC/Jhg+fvSyet+rA6cKJ1PIeKepXOK+U35Uue+te950t01jnvFaYWJm3SC9q6Y5p8dC3NqYRGmhz40yginLj98r3k+X6atyJskbfS2Ue8vuopR8PbMVk4QUUjcJuUURiSxseWTt84paFtD0udZ//xqU6I/zt9EQDrTSLRBf9OsHvL93cLwUF2K1UaFzv7aWPOJuj37Iwd8rC0YRMbkdvLPdxDzhs6dOHgCJtr0iKIin0GUPQj8ic3oYDvsIWA0KLp/Jkxzx5PZYg83Evedgjlrh/ZbRZBO4BSrw8h56Kez/gHHOTdp73p449w== Received: from [66.196.81.174] by nm14.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 Received: from [68.142.230.64] by tm20.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 Received: from [127.0.0.1] by smtp221.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 12:10:48 -0000 X-Yahoo-Newman-Id: 652752.87660.bm@smtp221.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: bXf2rgMVM1kCw7ohrs4pK11Gf6QBGegKoN13.kdV32znkma bfsuJvQ8vNz2ZLrwS1HalmhRjEfLUsNIg0wnUNh81Tepr__28mFMDm2dAIvq 3cWKQmYG_FjFl0BFQpAZH9vqwQz77umgMpzWREyeuB5Y3_DJqPfscoyxXT5C 0jfTnYvMnb2Ds7fHoHaduAv6mqoORpcHMIS6x12pDgSlKM05yuL9Qsjl1q.l .hV6GAQlKYwyROD35WsFXHR9Va8eEF56FzD56ZQ5iimFiEELx7qTyMuKWVjD MS1TwrRyVm8mnEhG.Sg7PNXaVWNjEwRJA5U8iKAMEHjLLI4o3FyRmAiEefKD OV55a7o4jghbUXMl5Ll8_tbYiT9ApLV_d.eJzrIwTfIBnJdndDWwFSjzoZe7 MMwpHu2UXw_FVas0R4kRUGdPtxg1_uGUiHx2KFA6xl3MBJdNaLSIQnfIrOiK 1d2ws22Tpv.Qmwau62AHiYqKBcrDCx9Jap5thdSuKmqa25FPpav.QYrLnr9T .LMQ6hJuhVqPEmPHt6GWgColpLxpDKZe.l7CwJt0_uk9kqUtS1eXD7LunL6H DH_fmd5BXpVWq3J96MMLzbORXW_osI213pX_B8Asy7yqTafXy0IsFbsvkPu4 eiU8_HN9xo8jaE.1yF5gc.1nmp2.FycvbRrfxTjkQ_Vq3qjUK55WIbtEBzi3 oXmlF7HeymXJlHWdIfsbbSP3NTjJB8X6ZRH5WMZ49RAlh0Hkt5DDDkzOxyBA NksrcozaSXOzbdBxweTGQOhFQJZNBqcGOrg-- X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) Subject: Re: Random number generators From: Pedro Giffuni In-Reply-To: <20150317060310.GA21975@troutmask.apl.washington.edu> Date: Tue, 17 Mar 2015 07:10:46 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> To: Steve Kargl X-Mailer: Apple Mail (2.2070.6) Cc: freebsd-numerics@FreeBSD.org 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 12:10:56 -0000 > 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=3D20d01d83b5a13c77805976e7c5= 20f566244ba3ff = >>=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. From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 17:07:39 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 D33D3FA4; Tue, 17 Mar 2015 17:07:39 +0000 (UTC) Received: from troutmask.apl.washington.edu (troutmask.apl.washington.edu [128.95.76.21]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id B47C3AE4; Tue, 17 Mar 2015 17:07:39 +0000 (UTC) Received: from troutmask.apl.washington.edu (localhost [127.0.0.1]) by troutmask.apl.washington.edu (8.14.9/8.14.9) with ESMTP id t2HH7bwk024868 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Tue, 17 Mar 2015 10:07:37 -0700 (PDT) (envelope-from sgk@troutmask.apl.washington.edu) Received: (from sgk@localhost) by troutmask.apl.washington.edu (8.14.9/8.14.9/Submit) id t2HH7bCq024867; Tue, 17 Mar 2015 10:07:37 -0700 (PDT) (envelope-from sgk) Date: Tue, 17 Mar 2015 10:07:37 -0700 From: Steve Kargl To: Pedro Giffuni Subject: Re: Random number generators Message-ID: <20150317170737.GA24682@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) Cc: freebsd-numerics@FreeBSD.org 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:07:39 -0000 On Tue, Mar 17, 2015 at 07:10:46AM -0500, Pedro Giffuni wrote: > > > 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). > GM's kiss generator has a period of 2**123. The manpage for random(3) claims a period of about 2**35. The rand(3) manpage does not give a period, but I suspect it is well short of 2**123. The code that follows my sig uses. a Lehmer LCG generator to provide the 4 seeds needed for kiss. The Lehmer LCG takes a single 32 bit seed. If reseed() is not called prior to calling kiss(), then a default set of seeds is used. If the argument to reseed() is 0 or 1, then the default set of seeds is used. It should be straight forward to map reseed() to srand() and kiss() to rand(). Do note that range kiss() is (0,UINT_MAX], so one needs to subtract 1 to get [0,UINT_MAX-1) if 0 needs to be in the range. To use this code in preference to random(3) (and in violation of POSIX?), initstate() and setstate() would need to muck with the internal state of kiss(). This is certainly possible, but I don't do it below. -- Steve #include #include #include #include #include /* * The KISS generator requires 4 seeds. Use a simple Lehmer linear * congruential generator (LCG) that requires only a single seed to * generate the 4 KISS seeds. */ static uint64_t lcg_seed = 0; /* Need to remember the state of LCG. */ static uint32_t lehmer_lcg(uint32_t a) { return ((uint64_t)a * 279470273UL) % 4294967291UL; } /* * If reseed() is not called or it is called with an argument of 0 or 1, * then use DEFAULT_SEED as the set of seeds for kiss(). */ #define DEFAULT_SEED {123456789, 362436069, 521288629, 916191069} static const uint32_t default_seed[4] = DEFAULT_SEED; static uint32_t seed[4] = DEFAULT_SEED; uint32_t reseed(uint32_t s) { int i; uint32_t kiss_seed; /* Copy seed given by user. */ lcg_seed = s; if (lcg_seed == 0 || lcg_seed == 1) { for (i = 0; i < 4; i++) seed[i] = default_seed[i]; } else { kiss_seed = lcg_seed; for (i = 0; i < 4; i++) { kiss_seed = lehmer_lcg(kiss_seed); seed[i] = kiss_seed; } } return (lcg_seed); } /* * kiss() returns an integer value in the range of (0, 2**32-1]. The * distribution of pseudorandom numbers should be uniform. The overall * perdiod for this generator exceeds 2**123. */ #define LEFT(k, n) ((k)^((k)<<(n))) #define RGHT(k, n) ((k)^((k)>>(n))) uint32_t kiss(void) { seed[0] = 69069 * seed[0] + 1327217885; seed[1] = LEFT(RGHT(LEFT(seed[1],13),17),5); seed[2] = 18000 * (seed[2] & 65535) + (seed[2] >> 16); seed[3] = 30903 * (seed[3] & 65535) + (seed[3] >> 16); return (seed[0] + seed[1] + (seed[2] << 16) + seed[3]); } #define NUM 5 int main(void) { int i; uint32_t n; struct rusage t0, t1; /* Default seeds. */ printf("Default seeds used.\n"); for (i = 0; i < NUM; i++) printf("%u\n", kiss()); n = reseed(42); printf("\nseed = %u\n", n); for (i = 0; i < NUM; i++) printf("%u\n", kiss()); /* Default seeds. */ n = reseed(0); printf("\nseed = %u\n", n); for (i = 0; i < NUM; i++) printf("%u\n", kiss()); n = reseed(12345); printf("\nseed = %u\n", n); for (i = 0; i < NUM; i++) printf("%u\n", kiss()); /* Default seeds. */ n = reseed(1); printf("\nseed = %u\n", n); for (i = 0; i < NUM; i++) printf("%u\n", kiss()); getrusage(RUSAGE_SELF, &t0); for (i = 0; i < 1000000; i++) n = kiss(); getrusage(RUSAGE_SELF, &t1); { double u; u = (t1.ru_utime.tv_sec - t0.ru_utime.tv_sec); u += (t1.ru_stime.tv_sec - t0.ru_stime.tv_sec); u += 1.e-6*(t1.ru_utime.tv_usec - t0.ru_utime.tv_usec); u += 1.e-6*(t1.ru_stime.tv_usec - t0.ru_stime.tv_usec); printf("\n%u\n", n); printf("%.2f ms for 1 million values\n", n, 1000 * u); } return 0; } 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" From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:12:42 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 A051EDD8 for ; Tue, 17 Mar 2015 18:12:42 +0000 (UTC) Received: from nm41-vm4.bullet.mail.bf1.yahoo.com (nm41-vm4.bullet.mail.bf1.yahoo.com [216.109.114.159]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 45AE02B5 for ; Tue, 17 Mar 2015 18:12:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426615831; bh=fPvGuo81LepHOUWrgMrUK9vNuRvXE6gPouKNNptsbSs=; h=Date:From:To:Subject:References:In-Reply-To:From:Subject; b=lV80IahzMcXtH/OCd/E8GMX2yqedayogIxcXQsFK701szCtA9gUf5r3LeNGHuieGLGgE7nFmkL9j7kPhmQPkDylvauMxoQrAuhVrNxZZXuKRd9vudpYrR/t3QepcrqGeTxpl9909OD64Xi0VAVRzwnNzblSp8UCgKM4uVs9rltGAtPHMWOcfnzRuJvEepIEdWFeJfxy8UiraNmYSYGMTbL5Y2AKJc/2nQB4TwL7rB1HUnP34zrapOvb6pjCoMb0gCQxpQIRCopCNzYLBAnVLoCz2mlafd/9857uyo62iLVGIP7lrsR5vaLc1hbrOBqnrYYjGIXt9bbfvn1vYpyy6ag== Received: from [98.139.170.182] by nm41.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:10:31 -0000 Received: from [98.139.211.201] by tm25.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:10:31 -0000 Received: from [127.0.0.1] by smtp210.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:10:31 -0000 X-Yahoo-Newman-Id: 756745.93646.bm@smtp210.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: TyuzyhMVM1lqKqVhs2LiX7TookCYXzGvn9HPgyqSj48uIGx TDlm8I9dcyWtxxKJcXoUYRkU.AgM9my9TlscN55bdXJ97ZRs9SPsXADrwpaH KBN8HYkIh1OlQF5okI2zGqaiug.jr7ddmhGPMuleJSgsFs7uBcfpiqdDeDrY wOhw6_uwtOfF8Fw2Zip5sSlFHXKbCupFWQkjqPsi_X.20V04aW9T_ZbJHzEb 62P_hRk95DGu7Pd.Scp.Njv0OaSsg_o3USg_AT8VNX1D8AmtVBISOQOPk7fg EwUO.mC4JbLy9mJajaNitpE5iR8S1RZyjmL1NqYEXafNeVbebb7p0Iq3KhT5 6zRrcykC6EKq7FchjpGrLb6wWzDbxft1_CIxlAPNwtA.arh1kowlp3FA0cYu rau51kuF1onHYB9nCVGnOn50d30g_fiUlBF2cfvhBNyltKcjlwo8XXrDRewr 2L1AueL15IOtmgO.MqfHlhvakxTnwC1Rfp_Xp1A0sk36TWM6GGKXfBX_6.Fn wR8K5ucn9e1K6nFEeGkkl4osyuIPc7TvW1VZyyD8aGSskdLVjzReZSyWwWJC 7t3kaCT2TO4JGoxKilyRgth8IbINUSx3CHkpmh7_Wa9Fgo7aWTp2RI85VLqX 6sK3NL0S1kxy94lpiQAp4aatjrYxRVqQ4vSEEuw-- X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Message-ID: <55086E2D.9080806@FreeBSD.org> Date: Tue, 17 Mar 2015 13:10:53 -0500 From: Pedro Giffuni User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: dennis.hamilton@acm.org, freebsd-numerics@FreeBSD.org Subject: Re: Random number generators References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> In-Reply-To: <00a001d060d7$0077f100$0167d300$@acm.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit 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 18:12:42 -0000 Hi Dennis; 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, . 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. > > 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. 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. From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:18:52 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 4A143F5D; Tue, 17 Mar 2015 18:18:52 +0000 (UTC) Received: from mail-yh0-x22f.google.com (mail-yh0-x22f.google.com [IPv6:2607:f8b0:4002:c01::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 023A8309; Tue, 17 Mar 2015 18:18:52 +0000 (UTC) Received: by yhpt93 with SMTP id t93so6440648yhp.0; Tue, 17 Mar 2015 11:18:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=c3jSrks2owBMUrfKx+Tm0E3MZe/XadOLveiZ4LjOYEo=; b=z799y+9dhd+kJ26fUjqzcSucmlGZtjvx7srqfLUWh3ED9LudaQyojZ9Y6hEOYo0PLo x4Exozq/FKYryZgVLl3pjWZxnwDzk2z9MJA0TlvFXRFbMxlI8ag7Q7JYn5PvXPvSID1Y D7Itute8Mjm4lJiyiMOMuQWEuzutaslzP7/RqVSOR2gWe9jo0phxVuOBClAMLeJV8e7m +/57BsMvtw8OByu1ApP3Exd17NBzjIGDGtzpG7EVDIuPGZSueTFtZiUj0qhSGQAh71Kc bZeZnyw8NEohBS2Hs6qnrwKKX8utqpTZyoKeVFmmEkWiuomJ1xMzDf4CyE1Y7XUGaJ9B qWpQ== MIME-Version: 1.0 X-Received: by 10.170.37.141 with SMTP id 135mr57011939ykf.94.1426616331117; Tue, 17 Mar 2015 11:18:51 -0700 (PDT) Received: by 10.170.60.69 with HTTP; Tue, 17 Mar 2015 11:18:51 -0700 (PDT) In-Reply-To: <55086E2D.9080806@FreeBSD.org> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <55086E2D.9080806@FreeBSD.org> Date: Tue, 17 Mar 2015 11:18:51 -0700 Message-ID: Subject: Re: Random number generators From: Mehmet Erol Sanliturk To: Pedro Giffuni Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.18-1 Cc: dennis.hamilton@acm.org, freebsd-numerics@freebsd.org 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 18:18:52 -0000 On Tue, Mar 17, 2015 at 11:10 AM, Pedro Giffuni wrote: > Hi Dennis; > > 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: >> 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. >> >> 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. >> > > 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 . Thank you very much . Mehmet Erol Sanliturk From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:32:08 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id D1466190 for ; Tue, 17 Mar 2015 18:32:08 +0000 (UTC) Received: from nm9-vm0.bullet.mail.bf1.yahoo.com (nm9-vm0.bullet.mail.bf1.yahoo.com [98.139.213.154]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 874E36AD for ; Tue, 17 Mar 2015 18:32:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426617121; bh=OpG+3HnjCtRUGp0a0hxwjcpGwZJYcusMu80UQTmyGi0=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=YdjeeuvWBGTFahrXk5zGh6za3uP1cJtkSX30vk/MUVakpP0dE1dQUpPVALj1oQxdc9xLobf3rk7JpIu8fnUYUot5TNZV2fNixa46KPngHs/izXG5PCWcgsK6s4I9qqIv2pI4wBb1PRoI4O7OylsTIZYF0TnjpvJVABN3LIUCDZDJieTFldSuO2HcK/Xu/fCAJM36XlofErSx3z0fLMduRu8k4gM652sRoadjgXnIe3FB/5T40PF9sdI9Gfm7kzCCM0+I7HasUYO/6OjMaRHB2nQJNntTa/o/doDe7ioB1Y7+y2DvGnlmdszviN9xtHHhkfWO8IoyiZ2ef3PsbUfvvA== Received: from [66.196.81.173] by nm9.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:32:01 -0000 Received: from [98.139.211.198] by tm19.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:32:01 -0000 Received: from [127.0.0.1] by smtp207.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:31:57 -0000 X-Yahoo-Newman-Id: 594839.31495.bm@smtp207.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: CEKAuWMVM1meLbndl5aXIqHtQcRGV7m5MmWi.PrI9FKl4EJ G4JWFDikstGcnwiIdUrc0RitD9W3DBFTyeGciWLWU0oSVVt4c9Jr.ZeJ9u._ U0Tsir548ZrwCz3odSp4SWYmRVltOZ0o7CoPwqpT8tVQ0CnHsfGyJsXWB18S sRSmIZhb3p35rSOWn_a0g6dUuFtPxN.OIXqn0LjtEYq_NdxrvkZBPZXA_XWg 5UMg9OcP1Ewc9rREIVtsMjO9BjhDChe0gfNkfKu6EMlujHKUe5.8enSEPgwB ei_Nhl6a8XRHFeiyJ5ycwArP49kF68x3QQaT6JPi4VK.WzHyVqKu1Uk8eSlj xmhMf.qLD8JHYWD3VFV3XhSJCNmsD8ZCj2v_LEJUJVM.2xN.lWgsipH8VErU 23c4HMtQrMmoDeEqCIHojdGqAynfhm0rli59iU0ribvvHZoEsyvtbN_bhYcB 9jwF5lv4rrxS6mUzQ5rlAWzsfU2yhaiv_493egrDE_YT0GLNyyRgfmZuBLzM L7_m.srPx6jxXe3xmO9Btxl0srYbTv3om X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Message-ID: <55087331.4060709@FreeBSD.org> Date: Tue, 17 Mar 2015 13:32:17 -0500 From: Pedro Giffuni User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Steve Kargl Subject: Re: Random number generators References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <20150317170737.GA24682@troutmask.apl.washington.edu> In-Reply-To: <20150317170737.GA24682@troutmask.apl.washington.edu> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-numerics@FreeBSD.org 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 18:32:09 -0000 On 03/17/15 12:07, Steve Kargl wrote: > On Tue, Mar 17, 2015 at 07:10:46AM -0500, Pedro Giffuni wrote: >>> 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). >> > GM's kiss generator has a period of 2**123. The manpage > for random(3) claims a period of about 2**35. The rand(3) > manpage does not give a period, but I suspect it is well > short of 2**123. I just started to look at the original KISS. It appears to be a combination of three different pseudo random generators. In particular it uses static unsigned long Q[4194304] and seeds it with CNG+XS. I am tempted to just seed it with a crypto random source instead of using an LCG. This is not for libc, just for entertainment purposes though :). > The code that follows my sig uses. a Lehmer LCG generator to > provide the 4 seeds needed for kiss. The Lehmer LCG takes a > single 32 bit seed. If reseed() is not called prior to calling > kiss(), then a default set of seeds is used. If the argument > to reseed() is 0 or 1, then the default set of seeds is used. > It should be straight forward to map reseed() to srand() and > kiss() to rand(). Do note that range kiss() is (0,UINT_MAX], > so one needs to subtract 1 to get [0,UINT_MAX-1) if 0 needs > to be in the range. > > To use this code in preference to random(3) (and in violation of > POSIX?), initstate() and setstate() would need to muck with the > internal state of kiss(). This is certainly possible, but I > don't do it below. > Interesting. I don't really want to break POSIX but we have 3 pseudo random generators: rand(), random() and rand48(). It would be really nice if we could change one to be modern (and fast) although not crypto friendly. FWIW, the Playstation 4 carries Mersenne Twister in their credits along with FreeBSD's libc and kernel so someone has a use for a faster pseudo-random generator and a better period than those we carry in libc. Pedro. From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:44:26 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id DDDC8654 for ; Tue, 17 Mar 2015 18:44:26 +0000 (UTC) Received: from nm16.bullet.mail.bf1.yahoo.com (nm16.bullet.mail.bf1.yahoo.com [98.139.212.175]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 8F2D1868 for ; Tue, 17 Mar 2015 18:44:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426617545; bh=KzuLTdQSCB5Ea78B4DynnOHFeZWmCVcgceDcO81okwM=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=kTuDMVAWgzg97n4VD+DT74hPMMhlanCdTZAPxAt+IJavDKOStVUT0CORVDLV4qW9dYb8HERxTEsXZwB5kghHy3MGLybphPe2ZvcT8gsp8gPHuniv+RLv1XlNr7CXusGxkBIFvTYa9L74x3B/UK2pGfONqJkqL+zC2Z9uU0wAqiojiLKwwvH1yoZ7D3XukP6ZaQ1HYS9YVEbZfYvLGcrcm5Mg97ga49KcM5DGuLiSkWONbgrI/BB+W3sSJxfFk3jHM3mnir6ZsJuTc2/d/kOjCRYJ7yJWBnXkvEXN4sdFmsTTMJ6BwBFHenTHn1dEMSaeoJ5yMLbIAGJ2AA5StkBlfA== Received: from [98.139.170.182] by nm16.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:39:05 -0000 Received: from [98.139.211.205] by tm25.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:39:05 -0000 Received: from [127.0.0.1] by smtp214.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 18:39:05 -0000 X-Yahoo-Newman-Id: 546457.53950.bm@smtp214.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: k3ItqBkVM1k9.IgL47AovhHAqmEZ4tqIBucHyLYgKITb_JC CuvV7tScE_L9v2EZimGDMJexBT7J.Jjw1zzykTMTt1pAfP0TCQCUbO_irEAp wYJ1FXr85TmN_ExtA6yLl7Kg0ldkmkB2v_EYHQ21Swo5TD4WNDwp6zhfXpuL KCCWJbrdFOVxOQcKgORd1sQ4D_HZab_RCW58sc9PEDK.L8zEmOHLRrev7krj 81vddC0zVIjAfIyiEJYAvMgKZ7Wcwt8eKl2auweHl.P6poFTbERKMLaK68go dYIGOcxzsWyLOkMn3lVvy2pSUyk_rC35YfZ.cKL23IGHH8CQgQx4NtFjtjW4 x0wZK_t8nyWO0rVAnBdq33KfHKw3Wb.YRmn1MhSUAKrpUJbtLEHq0p4F27k0 a4ToSNrA5SQw0yRbVzNdX5VKyQXGgFHqSp.8ADMy470hZAXdG5.kL33GDQBi cAP695xY_5U961ppfxwBrIPkRIuC_YSoYikAGjYvp0vnoODYqYOdzUrpay3y rAG_BUqeHBPWJaFSiaqghxboLCCpA.wjo0gO_czwkUkX.DnYtHK_DRjk6rZD CRMtmuWY9HvWVis.wSIaE8bi6VBmri4iPeFWbc2gjJ4Y.sW8SZhb7ix3K0WZ Qk_7XeXQX0bqiHBTtjrpAiYzXbTyd.EvbpQH_6Q-- X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Message-ID: <550874DE.3060700@FreeBSD.org> Date: Tue, 17 Mar 2015 13:39:26 -0500 From: Pedro Giffuni User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Mehmet Erol Sanliturk Subject: Re: Random number generators References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <55086E2D.9080806@FreeBSD.org> In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Content-Filtered-By: Mailman/MimeDel 2.1.18-1 Cc: dennis.hamilton@acm.org, freebsd-numerics@freebsd.org 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 18:44:27 -0000 Hi; On 03/17/15 13:18, Mehmet Erol Sanliturk wrote: > > > On Tue, Mar 17, 2015 at 11:10 AM, Pedro Giffuni > wrote: > > Hi Dennis; > > 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, . 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. > > 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. > > > 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"?) It may be worth considering though. Pedro. From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:46:23 2015 Return-Path: Delivered-To: freebsd-numerics@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 7A509693; Tue, 17 Mar 2015 18:46:23 +0000 (UTC) Received: from troutmask.apl.washington.edu (troutmask.apl.washington.edu [128.95.76.21]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "troutmask", Issuer "troutmask" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 55C37880; Tue, 17 Mar 2015 18:46:23 +0000 (UTC) Received: from troutmask.apl.washington.edu (localhost [127.0.0.1]) by troutmask.apl.washington.edu (8.14.9/8.14.9) with ESMTP id t2HIkJRQ025248 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Tue, 17 Mar 2015 11:46:19 -0700 (PDT) (envelope-from sgk@troutmask.apl.washington.edu) Received: (from sgk@localhost) by troutmask.apl.washington.edu (8.14.9/8.14.9/Submit) id t2HIkJkT025247; Tue, 17 Mar 2015 11:46:19 -0700 (PDT) (envelope-from sgk) Date: Tue, 17 Mar 2015 11:46:18 -0700 From: Steve Kargl To: "Dennis E. Hamilton" Subject: Re: Random number generators Message-ID: <20150317184618.GA24951@troutmask.apl.washington.edu> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <00a001d060d7$0077f100$0167d300$@acm.org> User-Agent: Mutt/1.5.23 (2014-03-12) Cc: freebsd-numerics@FreeBSD.org, '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 18:46:23 -0000 On Tue, Mar 17, 2015 at 10:22:51AM -0700, Dennis E. Hamilton wrote: > > 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. > I intrepeted Pedro's original email to mean something better than rand(3) and random(3). Neither is appropriate for crypto, and I'm certainly not claiming KISS by GM is suitable for crypto either. In fact, others have shown KISS isn't a good source for crypto (http://eprint.iacr.org/2011/007.pdf). For crypto randomness, as Pedro stated, use arc4random(3). kiss(), as I posted here, is good enough to deal cards and to do monte carlo simulations in various fields of physics. -- Steve From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 18:55:33 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 EF8A6975; Tue, 17 Mar 2015 18:55:33 +0000 (UTC) Received: from mail-yh0-x22e.google.com (mail-yh0-x22e.google.com [IPv6:2607:f8b0:4002:c01::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id A561696F; Tue, 17 Mar 2015 18:55:33 +0000 (UTC) Received: by yhct68 with SMTP id t68so6762389yhc.2; Tue, 17 Mar 2015 11:55:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=UT/hTJBlvaDIYMj/RBAp2/pvrCPCvShUR+f3i/i6TWw=; b=tnlW3mA0pMFqB3XPGvTd+1Sni5yN5fvAgMbSexsSApFzFXC3LW4BtI2Ajb2YB5hlSQ mws91b3EELDz+rpn34mm9p6EJdiEJGNuj/7mJB5l68lFiW4zKQtYmznAArjyLdyBEme0 dk75gtDC4QCzqpmzoAopiqJ7zbdpRYUeREvQOsY+Q3vENGCTw7xZ0KrmHx4CXVgvg4lq 2MSeNd7AuKZF1OgRF8hdZWdLsQ4K0gWRC+JGp0HP1C2tyesmt/qC4VavtJe7MLg8gtuo 7XMkvW618vucl5xKd2RyswNmFLxf2Flz8A3EfiaQCjyxTVXTSi7w1uXrJ7eVEEjLIfn4 FGEQ== MIME-Version: 1.0 X-Received: by 10.170.180.66 with SMTP id w63mr57790260ykd.39.1426618532866; Tue, 17 Mar 2015 11:55:32 -0700 (PDT) Received: by 10.170.60.69 with HTTP; Tue, 17 Mar 2015 11:55:32 -0700 (PDT) In-Reply-To: <550874DE.3060700@FreeBSD.org> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <55086E2D.9080806@FreeBSD.org> <550874DE.3060700@FreeBSD.org> Date: Tue, 17 Mar 2015 11:55:32 -0700 Message-ID: Subject: Re: Random number generators From: Mehmet Erol Sanliturk To: Pedro Giffuni Content-Type: text/plain; charset=UTF-8 X-Content-Filtered-By: Mailman/MimeDel 2.1.18-1 Cc: dennis.hamilton@acm.org, freebsd-numerics@freebsd.org 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 18:55:34 -0000 On Tue, Mar 17, 2015 at 11:39 AM, Pedro Giffuni wrote: > Hi; > > On 03/17/15 13:18, Mehmet Erol Sanliturk wrote: > > > > On Tue, Mar 17, 2015 at 11:10 AM, Pedro Giffuni wrote: > >> Hi Dennis; >> >> 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, >>> . 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. >>> >>> 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. >>> >> >> 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"?) > > It may be worth considering though. > > Pedro. > There is the following page : http://csrc.nist.gov/groups/ST/toolkit/rng/index.html random number generation ( Software is in Public Domain ) I do not know whether it may be useful or not for this thread . Thank you very much . Mehmet Erol Sanliturk From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 20:43:34 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 110FFD29 for ; Tue, 17 Mar 2015 20:43:34 +0000 (UTC) Received: from barracuda.supercp.com (barracuda.supercp.com [216.234.124.51]) by mx1.freebsd.org (Postfix) with ESMTP id C7EA7946 for ; Tue, 17 Mar 2015 20:43:33 +0000 (UTC) X-ASG-Debug-ID: 1426625010-0798da1d4f4b85b90001-ljoQne Received: from a2s42.a2hosting.com (a2s42.a2hosting.com [216.119.133.2]) by barracuda.supercp.com with ESMTP id EecBc0prsYpZhzKf for ; Tue, 17 Mar 2015 16:43:30 -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]:33229 helo=Astraendo2) by a2s42.a2hosting.com with esmtpa (Exim 4.82) (envelope-from ) id 1YXyKm-001qzp-O2 for freebsd-numerics@freebsd.org; Tue, 17 Mar 2015 16:43:29 -0400 Reply-To: From: "Dennis E. Hamilton" To: References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <55086E2D.9080806@FreeBSD.org> <550874DE.3060700@FreeBSD.org> In-Reply-To: <550874DE.3060700@FreeBSD.org> Subject: RE: Random number generators Date: Tue, 17 Mar 2015 13:43:27 -0700 X-ASG-Orig-Subj: RE: Random number generators Organization: NuovoDoc Message-ID: <014301d060f3$06388070$12a98150$@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: AQH32Py7Ohz5iRyKYdk0RcO8dKEfnwHlGiR6AYuy88UAwAV03wE/WwDZAitxe8MBerg5zJyJfKyQ 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: 1426625010 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_SPF_SOFTFAIL X-Barracuda-Spam-Report: Code version 3.2, rules version 3.2.3.16821 Rule breakdown below pts rule name description ---- ---------------------- -------------------------------------------------- 0.00 BSF_SPF_SOFTFAIL Custom Rule SPF Softfail 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 20:43:34 -0000 You need to look at the explanations on other PCG pages to see what the = criteria are. Also this narrative is helpful: = . At the bottom of that page, PCG is also considered and it is not = recommended as of cryptographic quality because it has not been tested = and challenged enough. In non-cryptographic use it may also be important to understand that = reseeding or mixing that involves capturing "more entropy" may be = delayed because of exhaustion of a periodic source, and one has to wait = for more bits, making attempted cryptographic quality even slower.=20 -----Original Message----- From: owner-freebsd-numerics@freebsd.org = [mailto:owner-freebsd-numerics@freebsd.org] On Behalf Of Pedro Giffuni Sent: Tuesday, March 17, 2015 11:39 To: Mehmet Erol Sanliturk Cc: dennis.hamilton@acm.org; freebsd-numerics@freebsd.org Subject: Re: Random number generators [ ... ] It just came up here. It looks like PCG compares favorably with=20 ChaCha20, but this is PCG's page and the comparison is not very clear ("Secure" vs=20 "Challenging"?) It may be worth considering though. 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" From owner-freebsd-numerics@FreeBSD.ORG Tue Mar 17 21:24:57 2015 Return-Path: Delivered-To: freebsd-numerics@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 52467BB7 for ; Tue, 17 Mar 2015 21:24:57 +0000 (UTC) Received: from nm38-vm4.bullet.mail.bf1.yahoo.com (nm38-vm4.bullet.mail.bf1.yahoo.com [72.30.239.20]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id EC12BE2A for ; Tue, 17 Mar 2015 21:24:56 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1426627315; bh=SUmQ2y2fFfP7jKCcEqv6DdZ6Aaq9Te7Pff5XcfAfzc4=; h=Date:From:To:CC:Subject:References:In-Reply-To:From:Subject; b=aE3WGKU8j9xR1fSZA0d7kkfhwcWMRlWRj2kaHVHRF7TEhI+pFD8S2mVg2XZ6g+LNlc/+wWxuuPV8Kj2pXbSbC0sXLWlY8Nz/d4hi2XKqc/gXxSX05S0nHH8WVg/j4tJPJ00+MZuwBHLR8B/o6XFq/WskF4ryp6mzd0JJ00vpWxurM562ipk729m2+QVLUnFMrCKvcA+X+8UtILtr1pCfB/4ffFBc9ZZu5dYtnzsZIpJ+d54bmKn5yWfn3bYN0voiykCeVinbqivb921uD2QJeQHjOH6oNXNDdWiYrUXyrIS6+QzUJl3J11l0RY6WL7GEoWgzzMSV9Y/vR2NKMnfc/A== Received: from [98.139.215.143] by nm38.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 21:21:55 -0000 Received: from [98.139.211.207] by tm14.bullet.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 21:21:55 -0000 Received: from [127.0.0.1] by smtp216.mail.bf1.yahoo.com with NNFMP; 17 Mar 2015 21:21:55 -0000 X-Yahoo-Newman-Id: 927753.93401.bm@smtp216.mail.bf1.yahoo.com X-Yahoo-Newman-Property: ymail-3 X-YMail-OSG: S_068A0VM1lLok2HufVfazH1LFmlBVpv86tVlMVm6mCSk6o KXLco6yqoQoPPKGM5RwHbFV81eSFUnAXvtEPjKwSa1zPongsHbFkPgKGG0Rt wgyLNg5BT0lgE7fzLEi9tytvGWbga1JYjt9U8as5H6THj2_HDV0awQAgl.5T rRqZMo0XjScR7aP9rxqhETkuJLHNHcY3nx1SJLCBnH3XNZfukuKXnlanFADH 0COxI7F0Za6l.5eBMevh0ypQwMA3i.yBi_p5rlrYzlRl933OZFd5_yy8mfwy JEMDWpJBDpvFgq5GIHYW_Ht.54VoVORDOWp_CQCYn7AifiuPdGZ83ZgUU3T4 8HPhKRuefG_aqqtP14VD4e7jQD0YYzlXwuOMT3GYsy8bxLeBd.F0celGrCDh bpTOFsjkVtdeZMpoNgPgFMtny1q7XfhLCk4BMrDeUUt6N_0ezRLs5vzCNvol wWd6j05O5dlrGYZQkbDLtpr6h3IPJh3SUd20LsxeRwrp2cNoirVlMpAiVF0m Z2sDUUCCoK8CpQM82Fd2VEjF7F0h3wu3W X-Yahoo-SMTP: xcjD0guswBAZaPPIbxpWwLcp9Unf Message-ID: <55089B08.4020501@FreeBSD.org> Date: Tue, 17 Mar 2015 16:22:16 -0500 From: Pedro Giffuni User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0 MIME-Version: 1.0 To: Steve Kargl , "Dennis E. Hamilton" Subject: Re: Random number generators References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <20150317184618.GA24951@troutmask.apl.washington.edu> In-Reply-To: <20150317184618.GA24951@troutmask.apl.washington.edu> Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-numerics@FreeBSD.org 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 21:24:57 -0000 On 03/17/15 13:46, Steve Kargl wrote: > On Tue, Mar 17, 2015 at 10:22:51AM -0700, Dennis E. Hamilton wrote: >> 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. >> > I intrepeted Pedro's original email to mean something better > than rand(3) and random(3). You interpreted right. Unfortunately I don't see us changing the POSIX behavior in libc (specially not in the brutal way OpenBSD did), and even if we were to change it, we would still have to carry the old version for compatibility through symbol versioning so the only choice for interested parties is to add their own implementation, and live with the bloat of existing versions. It was really nice to learn about kiss() though. Pedro. From owner-freebsd-numerics@FreeBSD.ORG Wed Mar 18 18:41:46 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 A6E6D7E9; Wed, 18 Mar 2015 18:41:46 +0000 (UTC) Received: from gold.funkthat.com (gate2.funkthat.com [208.87.223.18]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "gold.funkthat.com", Issuer "gold.funkthat.com" (not verified)) by mx1.freebsd.org (Postfix) with ESMTPS id 797A67B9; Wed, 18 Mar 2015 18:41:46 +0000 (UTC) Received: from gold.funkthat.com (localhost [127.0.0.1]) by gold.funkthat.com (8.14.5/8.14.5) with ESMTP id t2IIRlJb052061 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 18 Mar 2015 11:27:47 -0700 (PDT) (envelope-from jmg@gold.funkthat.com) Received: (from jmg@localhost) by gold.funkthat.com (8.14.5/8.14.5/Submit) id t2IIRkx4052060; Wed, 18 Mar 2015 11:27:46 -0700 (PDT) (envelope-from jmg) Date: Wed, 18 Mar 2015 11:27:46 -0700 From: John-Mark Gurney To: Pedro Giffuni Subject: Re: Random number generators Message-ID: <20150318182746.GI51048@funkthat.com> References: <7CBD7758-9472-4A2E-8065-EC6E68EE8DAB@FreeBSD.org> <20150317060310.GA21975@troutmask.apl.washington.edu> <00a001d060d7$0077f100$0167d300$@acm.org> <55086E2D.9080806@FreeBSD.org> <550874DE.3060700@FreeBSD.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <550874DE.3060700@FreeBSD.org> X-Operating-System: FreeBSD 9.1-PRERELEASE amd64 X-PGP-Fingerprint: 54BA 873B 6515 3F10 9E88 9322 9CB1 8F74 6D3F A396 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ X-Resume: http://resnet.uoregon.edu/~gurney_j/resume.html X-TipJar: bitcoin:13Qmb6AeTgQecazTWph4XasEsP7nGRbAPE X-to-the-FBI-CIA-and-NSA: HI! HOW YA DOIN? can i haz chizburger? User-Agent: Mutt/1.5.21 (2010-09-15) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.2.7 (gold.funkthat.com [127.0.0.1]); Wed, 18 Mar 2015 11:27:47 -0700 (PDT) Cc: freebsd-numerics@FreeBSD.org, dennis.hamilton@acm.org 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: Wed, 18 Mar 2015 18:41:46 -0000 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 > > 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, . 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. > > > > 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."