From owner-freebsd-current Sun Feb 2 1: 4:29 2003 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 7037837B401 for ; Sun, 2 Feb 2003 01:04:26 -0800 (PST) Received: from nagual.pp.ru (pobrecita.freebsd.ru [194.87.13.42]) by mx1.FreeBSD.org (Postfix) with ESMTP id D3C7443F43 for ; Sun, 2 Feb 2003 01:04:24 -0800 (PST) (envelope-from ache@pobrecita.freebsd.ru) Received: from pobrecita.freebsd.ru (ache@localhost [127.0.0.1]) by nagual.pp.ru (8.12.6/8.12.6) with ESMTP id h1294Nd6060036; Sun, 2 Feb 2003 12:04:23 +0300 (MSK) (envelope-from ache@pobrecita.freebsd.ru) Received: (from ache@localhost) by pobrecita.freebsd.ru (8.12.6/8.12.6/Submit) id h1294MDF060035; Sun, 2 Feb 2003 12:04:22 +0300 (MSK) (envelope-from ache) Date: Sun, 2 Feb 2003 12:04:22 +0300 From: "Andrey A. Chernov" To: Kris Kennaway Cc: current@FreeBSD.org Subject: Re: rand() is broken Message-ID: <20030202090422.GA59750@nagual.pp.ru> References: <20030202070644.GA9987@rot13.obsecurity.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="9jxsPFA5p3P2qPhR" Content-Disposition: inline In-Reply-To: <20030202070644.GA9987@rot13.obsecurity.org> User-Agent: Mutt/1.5.1i Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG --9jxsPFA5p3P2qPhR Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Feb 01, 2003 at 23:06:50 -0800, Kris Kennaway wrote: > FreeBSD's rand() implementation has been broken for the past 23 > months, since the following commit: > i.e. the first value returned from rand() is correlated with the seed > given to srand(). This is a big problem unless your seed is randomly > chosen over its entire integer range. I noticed this because awk > exhibits the same problem, and the script seeds the generator with a > PID. The script works fine under 4.x since the rand() implementation > does not have this "feature". Yes, first value correlation is there, but old formulae have even worse effect "The random sequences do not vary much with the seed", as source file comments and whole discussion about old RNG bad effects shown. I.e. = =20 for different time+PID sequence, especially increased monotonically, like in common practice, you'l got the same random sequence with old formulae (which can't be called "works fine" because this fine work was the main reason for change). So, returning to old formulae is not an option. The real problem is not in formulae, but in srand() funclion. This simple patch can fix first value correlation, and I plan to commit it, if we all agree. I not find better value for NSHUFF right now, but think that something like 10 will be enough to fight corellation completely. Some generating picture tests needed. --- stdlib/rand.c.bak Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2 11:56:01 2003 @@ -51,6 +51,8 @@ #include #endif /* TEST */ =20 +#define NSHUFF 3 + static int do_rand(unsigned long *ctx) { @@ -103,7 +105,11 @@ srand(seed) u_int seed; { + int i; + next =3D seed; + for (i =3D 0; i < NSHUFF; i++) + (void)do_rand(&next); } =20 =20 @@ -117,7 +123,7 @@ void sranddev() { - int fd, done; + int fd, done, i; =20 done =3D 0; fd =3D _open("/dev/random", O_RDONLY, 0); @@ -133,6 +139,8 @@ =20 gettimeofday(&tv, NULL); next =3D (getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk; + for (i =3D 0; i < NSHUFF; i++) + (void)do_rand(&next); } } =20 --=20 Andrey A. Chernov http://ache.pp.ru/ --9jxsPFA5p3P2qPhR Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.0 (FreeBSD) iQCVAwUBPjzfFuJgpPLZnQjrAQGjNAP+Lrf+q4WX8JMLAznPY33Fjt/cvq5O3i0K +vbYYhHh1elr3NKRZMQGJmPj3im+sJMtn6vlBMVEVeRtU5UHLKWE70Fh7CkwlzrT Et8ZyWwsmWG6v6N/g854+fFOeNoO9xM9kj/ughWbZG8u/z4VWHXs0xJ04vp3Q5ms TJWwG3lO7Fk= =ZJVn -----END PGP SIGNATURE----- --9jxsPFA5p3P2qPhR-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message