Date: Tue, 04 Feb 2003 14:47:24 +0100 From: Dag-Erling Smorgrav <des@ofug.org> To: "Andrey A. Chernov" <ache@nagual.pp.ru> Cc: David Schultz <dschultz@uclink.Berkeley.EDU>, Kris Kennaway <kris@obsecurity.org>, current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <xzpu1fkuphv.fsf@flood.ping.uio.no> In-Reply-To: <20030204132845.GA92674@nagual.pp.ru> ("Andrey A. Chernov"'s message of "Tue, 4 Feb 2003 16:28:45 %2B0300") References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204094659.GA87303@nagual.pp.ru> <20030204115237.GA6483@HAL9000.homeunix.com> <xzpfzr4b3pw.fsf@flood.ping.uio.no> <20030204131006.GB92301@nagual.pp.ru> <20030204131748.GA92510@nagual.pp.ru> <20030204132845.GA92674@nagual.pp.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
--=-=-=
"Andrey A. Chernov" <ache@nagual.pp.ru> writes:
> And the next bug is 32bit overflow there:
>
> tmp = *ctx * 62089911;
Ack, I thought the type promotion was automatic. Updated patch is
attached.
DES
--
Dag-Erling Smorgrav - des@ofug.org
--=-=-=
Content-Type: text/x-patch
Content-Disposition: attachment; filename=rand.diff
Index: lib/libc/stdlib/rand.c
===================================================================
RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v
retrieving revision 1.11
diff -u -r1.11 rand.c
--- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 -0000 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:44:52 -0000
@@ -52,7 +52,7 @@
#endif /* TEST */
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -63,21 +63,23 @@
return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
/*
- * Compute x = (7^5 * x) mod (2^31 - 1)
- * wihout overflowing 31 bits:
- * (2^31 - 1) = 127773 * (7^5) + 2836
- * 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.
+ * New algorithm derived from
+ * The Laws of Cryptography: Pseudo-random Number Generation
+ * by Neal R. Wagner
+ * http://www.cs.utsa.edu/~wagner/laws/rng.html
+ * which itself is derived from work by Donald E. Knuth.
+ *
+ * This is a linear congruence generator using the equation
+ *
+ * x(n+1) = (k * x(n) + a) mod m
+ *
+ * where m is 2^31 - 1, k is 62089911 and a is 0.
*/
- long hi, lo, x;
+ uint64_t tmp;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x <= 0)
- x += 0x7fffffff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = (uint64_t)*ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)0x7fffffff + 1);
+ return (*ctx);
#endif /* !USE_WEAK_SEEDING */
}
@@ -85,7 +87,7 @@
int
rand_r(unsigned int *ctx)
{
- u_long val = (u_long) *ctx;
+ uint32_t val = (uint32_t) *ctx;
int r = do_rand(&val);
*ctx = (unsigned int) val;
@@ -93,7 +95,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
--=-=-=--
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?xzpu1fkuphv.fsf>