NetBSD Problem Report #22853

Received: (qmail 27083 invoked by uid 605); 19 Sep 2003 12:13:05 -0000
Message-Id: <200309191212.h8JCCsZJ002808@smtp01.mem.interq.net>
Date: Fri, 19 Sep 2003 21:12:54 +0900 (JST)
From: deton@m1.interq.or.jp
Sender: gnats-bugs-owner@NetBSD.org
Reply-To: deton@m1.interq.or.jp
To: gnats-bugs@gnats.netbsd.org
Subject: srandom(3)'s weak seeding: random sequence do not vary with seed
X-Send-Pr-Version: 3.95

>Number:         22853
>Category:       lib
>Synopsis:       srandom(3)'s weak seeding: random sequence do not vary with seed
>Confidential:   no
>Severity:       non-critical
>Priority:       medium
>Responsible:    jdolecek
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Sep 19 12:14:00 +0000 2003
>Closed-Date:    Wed Nov 26 20:45:49 +0000 2003
>Last-Modified:  Wed Nov 26 20:45:49 +0000 2003
>Originator:     KIHARA Hideto
>Release:        NetBSD 1.6U
>Organization:
>Environment:
System: NetBSD ayame.deton.private 1.6U NetBSD 1.6U (JORNADA720) #0: Sat Jun 28 14:16:46 UTC 2003 autobuild@tgm.daemon.org:/autobuild/HEAD/hpcarm/OBJ/autobuild/HEAD/src/sys/arch/hpcarm/compile/JORNADA720 hpcarm
Architecture: arm
Machine: hpcarm
>Description:
srandom(3)'s seeding is very weak; the random sequence do not
vary much with the seed.
This problem is fixed on FreeBSD and OpenBSD at 1996 (on glibc at 1995).

problem detail and discussion on FreeBSD-current ML:
http://www.geocrawler.com/archives/3/147/1996/10/1000/665915/

OpenBSD fix:
http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/random.c#rev1.2

FreeBSD fix:
http://www.freebsd.org/cgi/cvsweb.cgi/src/lib/libc/stdlib/random.c#rev1.4

glibc fix:
http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/stdlib/random.c?cvsroot=glibc#rev1.5

>How-To-Repeat:
The following program in the above article
generates a PBM image of streams of random numbers
from different starting seeds.
The result SHOULD be white noise, but it does not.

#include <stdio.h>
#include <stdlib.h>

#define LOOP 200
#define ITER 200

main()
{
        int i,l;
        int seed=0;

        printf("P1\n%d %d\n",ITER,LOOP);
        for (l=0; l<LOOP; l++) {
                srandom(seed); seed+=1;
                for (i=0; i<ITER; i++) {
                        int b=random()&1;
                        printf("%d\n",b);
                }
        }
}
>Fix:
The change in srandom_unlocked() is from src/sys/lib/libkern/random.c.
--- src/lib/libc/stdlib/random.c.1.22	2003-09-13 18:15:07.000000000 +0900
+++ src/lib/libc/stdlib/random.c	2003-09-13 22:19:36.000000000 +0900
@@ -181,17 +181,17 @@ static const int seps[MAX_TYPES] =	{ SEP
 /* LINTED */
 static int randtbl[DEG_3 + 1] = {
 	TYPE_3,
-	0x9a319039, 0x32d9c024, 0x9b663182,
-	0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
-	0xf103bc02, 0x48f340fb, 0x7449e56b,
-	0xbeb1dbb0, 0xab5c5918, 0x946554fd,
-	0x8c2e680f, 0xeb3d799f, 0xb11ee0b7,
-	0x2d436b86, 0xda672e2a, 0x1588ca88,
-	0xe369735d, 0x904f35f7, 0xd7158fd6,
-	0x6fa6f051, 0x616e6b96, 0xac94efdc,
-	0x36413f93, 0xc622c298, 0xf5a42ab8,
-	0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
-	0x27fb47b9,
+	0x991539b1, 0x16a5bce3, 0x6774a4cd,
+	0x3e01511e, 0x4e508aaa, 0x61048c05,
+	0xf5500617, 0x846b7115, 0x6a19892c,
+	0x896a97af, 0xdb48f936, 0x14898454,
+	0x37ffd106, 0xb58bff9c, 0x59e17104,
+	0xcf918a49, 0x09378c83, 0x52c7a471,
+	0x8d293ea9, 0x1f4fc301, 0xc3db71be,
+	0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
+	0x19edc328, 0x87bf4bdd, 0xc9b240e5,
+	0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
+	0xf3bec5da,
 };

 /*
@@ -249,8 +249,23 @@ srandom_unlocked(x)
 		state[0] = x;
 	else {
 		state[0] = x;
-		for (i = 1; i < rand_deg; i++)
-			state[i] = 1103515245 * state[i - 1] + 12345;
+		for (i = 1; i < rand_deg; i++) {
+			long x, hi, lo, t;
+
+			/*
+			 * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
+			 * From "Random number generators: good ones are hard to find",
+			 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
+			 * October 1988, p. 1195.
+			 */
+			x = state[i - 1];
+			hi = x / 127773;
+			lo = x % 127773;
+			t = 16807 * lo - 2836 * hi;
+			if (t <= 0)
+				t += 0x7fffffff;
+			state[i] = t;
+		}
 		fptr = &state[rand_sep];
 		rptr = &state[0];
 		for (i = 0; i < 10 * rand_deg; i++)
>Release-Note:
>Audit-Trail:
Responsible-Changed-From-To: lib-bug-people->jdolecek 
Responsible-Changed-By: jdolecek 
Responsible-Changed-When: Sat Sep 20 05:11:35 EDT 2003 
Responsible-Changed-Why:  
I'd look at this. 
State-Changed-From-To: open->closed 
State-Changed-By: jdolecek 
State-Changed-When: Wed Nov 26 20:45:14 UTC 2003 
State-Changed-Why:  
Proposed change committed. Thanks for quality report and patch! 
>Unformatted:

Home	PR Database Search