Date: Sun, 2 Feb 2003 12:04:22 +0300 From: "Andrey A. Chernov" <ache@nagual.pp.ru> To: Kris Kennaway <kris@obsecurity.org> Cc: current@FreeBSD.org Subject: Re: rand() is broken Message-ID: <20030202090422.GA59750@nagual.pp.ru> In-Reply-To: <20030202070644.GA9987@rot13.obsecurity.org> References: <20030202070644.GA9987@rot13.obsecurity.org>
next in thread | previous in thread | raw e-mail | index | archive | help
--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 <stdio.h>
#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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030202090422.GA59750>