Re: rand() is broken
On Sun, 2 Feb 2003, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: Why not? Arc4 is a) deterministic and b) good for all bits. If you mean arc4random() function - not, because it use true randomness, if you mean RC4 algorithm, probably yes, but we should compare its distribution with our current variant and be sure that speed is acceptable. What form RC4 distribution have? arc4 is the non-encumbered name for rc4 that is not derived from RSA code -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, 2 Feb 2003 [EMAIL PROTECTED] wrote: In message [EMAIL PROTECTED], Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 19:32:50 +0100, [EMAIL PROTECTED] wrote: Anyway, last time we discussed this, I think we stuck with the rand() we had because we feared that people were using it's repeatable well documented sequence of random numbers in regression testing. As documented, it must be repeatable across the calls for same seed, that is all. It not means repeatable accross platforms or across different OS versions. In fact it is already not repeatable across different OS'es, so regression is limited. Also, regression must not stop bugs fixing progress in anycase. Our manual pages do not comprehensively list all compatibility concerns or concessions, waving our manpage about does not address the concern. As I said, I don't know how big a concern this is. But last time it was enough of a concern to make us keep rand() as it was. man srand on another system (for what its worth) says: The rand() function uses a multiplicative congruential random-number generator with period 2**32 that returns suc- cessive pseudo-random numbers in the range of 0 to RAND_MAX (defined in stdlib.h). The srand() function uses the argument seed as a seed for a new sequence of pseudo-random numbers to be returned by sub- sequent calls to rand(). If srand() is then called with the same seed value, the sequence of pseudo-random numbers will be repeated. If rand() is called before any calls to srand() have been made, the same sequence will be generated as when srand() is first called with a seed value of 1. Please surf the mail-archives to find the discussion, it contained a lot of good arguments from both sides, arguments which should be thought about before changing rand(). -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, 2 Feb 2003, Juli Mallett wrote: * De: David Malone [EMAIL PROTECTED] [ Data: 2003-02-02 ] [ Subjecte: Re: rand() is broken ] On Sun, Feb 02, 2003 at 02:37:25PM -0800, Steve Kargl wrote: FreeBSD Redhat SunOS 660787754660787754645318364 FWIW - AIX aggrees with Solaris. Endiannes, or an SVR4 implementation difference? Not endianess, unless they did something really gross to the routine on Solatis/x86 -- Juli Mallett [EMAIL PROTECTED] AIM: BSDFlata -- IRC: juli on EFnet OpenDarwin, Mono, FreeBSD Developer ircd-hybrid Developer, EFnet addict FreeBSD on MIPS-Anything on FreeBSD To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Mon, Feb 03, 2003 at 21:40:20 -0800, David Schultz wrote: followed by a 5 or 6. There is a similar pattern for 'e a 7'. I think this pretty much demonstrates that the algorithm isn't good enough to generate high-quality randomness with respect to different seed values. I'm not suggesting that it absolutely must be replaced, since most rand() implementations aren't very good in the first place, but I'm pointing out that to do a good job of fixing it once and for all is harder than you might think. I don't try to make rand() good for high-quality pseudo-randomness, because it can be done by price of speed and, more important, big state size. Due to rand_r() restriction state size can be one word only, so we can choose rand() algorithm only from those which pass this restrictions. So, if you define USE_WEAK_SEEDING and re-compile rand.c, you'll get even worse results from your test. It means current variant is better then previous. If you know even better algorithm wich pass restrictions above, just tell and we consider switching to it. Returning to current algorithm, I am interested in good NSHUFF value in the range 100-2000. Do you have any findings there? -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: Returning to current algorithm, I am interested in good NSHUFF value in the range 100-2000. Do you have any findings there? Apparently 100 is not enough too, I see repeated pattern in your program. I'll try other values... -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: So, if you define USE_WEAK_SEEDING and re-compile rand.c, you'll get even worse results from your test. It means current variant is better then previous. If you know even better algorithm wich pass restrictions above, just tell and we consider switching to it. Here is result from your test for USE_WEAK_SEEDING, i.e. for old algorithm. As we can see, it even worse than current one. It means that returning to old algoritm as Kris means (maybe?) is not an option. 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 1 e b 8 5 2 f c 9 6 3 0 d a 7 4 -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 12:58:40 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 12:46:59 +0300, Andrey A. Chernov wrote: Returning to current algorithm, I am interested in good NSHUFF value in the range 100-2000. Do you have any findings there? Apparently 100 is not enough too, I see repeated pattern in your program. I'll try other values... Well, I find that bigger values are not better, it means that algorithm limit is reached, so just 100 is good enough... -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Thus spake Andrey A. Chernov [EMAIL PROTECTED]: On Mon, Feb 03, 2003 at 21:40:20 -0800, David Schultz wrote: I don't try to make rand() good for high-quality pseudo-randomness, because it can be done by price of speed and, more important, big state size. Due to rand_r() restriction state size can be one word only, so we can choose rand() algorithm only from those which pass this restrictions. You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The section on LCGs suggests that the multiplier FreeBSD uses (7^5) is not particularly good, and points out some better values suggested by Knuth. I can't find the original discussion in TAOCP vol. 2, but I take N. Wagner's word that the numbers have been blessed by the holy hand of Knuth. I'm sure you can find more information if you search the literature. I apologize, but I don't have time to help you right now, and rand() isn't really a concern to me. Returning to current algorithm, I am interested in good NSHUFF value in the range 100-2000. Do you have any findings there? Well, if 0 doesn't work, and 10 doesn't work, and 100 doesn't work, then I'm not too hopeful about 2000. I appeal to Asimov's zero, one, infinity law. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 03:52:37 -0800, David Schultz wrote: You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The section on LCGs suggests that the multiplier FreeBSD uses (7^5) is not particularly good, and points out some better values suggested by Knuth. I can't find the original discussion in TAOCP vol. 2, but Thank for your pointer, I'll look at later. Well, if 0 doesn't work, and 10 doesn't work, and 100 doesn't work, then I'm not too hopeful about 2000. I appeal to Asimov's zero, one, infinity law. I found that f.e. 50 is worse than 100, but 200 isn't better. 100 is better than 0 because remove monotonically increased sequence. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 15:07:30 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 03:52:37 -0800, David Schultz wrote: You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The section on LCGs suggests that the multiplier FreeBSD uses (7^5) is not particularly good, and points out some better values suggested by Knuth. I can't find the original discussion in TAOCP vol. 2, but Two variants looks interesting from that paper: m=2^31-1, k=48271 m=2^31-1, k=62089911 Do you know any comparison of them with what we currently have, i.e. m=2^31-1, k=16807 -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
David Schultz [EMAIL PROTECTED] writes:
You can do better than the present generator with 32 bits of state.
See the following page by Neal Wagner (not to be confused with David Wagner):
http://www.cs.utsa.edu/~wagner/laws/rng.html
The attached patch, based on one of the m/k pairs suggested on that
page, results in the following:
des@des ~/src% ./rndtest | head
0 b 5 f 8 5 2 c 8 5 1 8 4 9 7 b d 9 e a d 3 8 8 5 9 2 3 e a c f
7 a d b f 0 1 3 6 7 4 f 0 6 0 1 2 3 1 c b a 6 1 e 0 9 c f 7 c 6
6 1 a a d b 3 e b a a 0 e d a f 8 6 3 f f 9 3 7 6 6 d 7 f 6 8 d
b d 6 2 b f 2 2 b 1 7 4 4 3 5 5 2 9 6 4 e 1 9 4 7 b f 6 f 7 8 c
1 5 7 e 3 5 d b 8 c c 4 d 1 3 6 e 0 3 3 3 2 e 5 3 b 5 e 7 b c a
0 a 3 2 d 5 f c 9 f c 3 9 a 1 f 3 f 2 c 5 9 4 6 2 d 2 3 e 2 7 5
a 8 8 1 5 7 0 5 4 e c f 6 3 b 0 8 4 d 2 a 8 0 5 7 b 2 1 4 e e 9
7 1 5 5 6 f f e 6 f a 4 e 5 a f 8 d f 7 b 3 8 d e 3 f 5 4 0 2 e
5 c a f 5 a e 5 0 9 4 6 0 0 9 f d 9 6 4 b f 8 2 3 5 e 4 5 9 9 a
d 3 4 5 5 0 f 9 9 1 8 6 7 a 5 0 2 0 5 8 b 6 1 6 7 f a 9 a 6 6 d
Note that my patch assumes that RAND_MAX fits in 32 bits, which should
be acceptable for FreeBSD since it always uses 32-bit ints (all our
32-bit platforms are ILP32, and I believe all our 64-bit platforms are
I32LP64) and RAND_MAX is uniformly defined to 0x7fff.
DES
--
Dag-Erling Smorgrav - [EMAIL PROTECTED]
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 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:37:03 -
@@ -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 += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = *ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)RAND_MAX);
+ 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()
Re: rand() is broken
On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: David Schultz [EMAIL PROTECTED] writes: You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The attached patch, based on one of the m/k pairs suggested on that page, results in the following: I just think about 62089911 and 48271 too :-) There is one bug in your patch: 0 is still illegal, so my fix required. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:10:06 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: David Schultz [EMAIL PROTECTED] writes: You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The attached patch, based on one of the m/k pairs suggested on that page, results in the following: I just think about 62089911 and 48271 too :-) There is one bug in your patch: 0 is still illegal, so my fix required. The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. The next is not the bug but portability thing alowing different RAND_MAX: you need to assign *ctx first and return it % RAND_MAX + 1 next, not assign *ctx % RAND_MAX + 1 like you currently does. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:17:48 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 16:10:06 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 14:00:27 +0100, Dag-Erling Smorgrav wrote: David Schultz [EMAIL PROTECTED] writes: You can do better than the present generator with 32 bits of state. See the following page by Neal Wagner (not to be confused with David Wagner): http://www.cs.utsa.edu/~wagner/laws/rng.html The attached patch, based on one of the m/k pairs suggested on that page, results in the following: I just think about 62089911 and 48271 too :-) There is one bug in your patch: 0 is still illegal, so my fix required. The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. The next is not the bug but portability thing alowing different RAND_MAX: you need to assign *ctx first and return it % RAND_MAX + 1 next, not assign *ctx % RAND_MAX + 1 like you currently does. And the next bug is 32bit overflow there: tmp = *ctx * 62089911; must be tmp = (uint64_t) *ctx * 62089911; I'll produce working variant based on your patch... -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov [EMAIL PROTECTED] writes:
There is one bug in your patch: 0 is still illegal, so my fix required.
I believe that's a feature. All linear congruence generator have a
fixed point. 0 is a far better fixed point than any other because it
is more obviously unsuited (for some values of obviously) as a
seed value. (but see below)
The next bug is that there is % RAND_MAX + 1, not % RAND_MAX.
No, using modulo 0x8000 instead of modulo 0x7fff breaks the
algorithm. (but see below)
The next is not the bug but portability thing alowing different RAND_MAX:
you need to assign *ctx first and return it % RAND_MAX + 1 next, not
assign *ctx % RAND_MAX + 1 like you currently does.
Changing RAND_MAX affects the algorithm in such a way that you should
not do so without giving serious thought to revising the algorithm
itself. In fact, RAND_MAX should be considered a characteristic of
the algorithm rather than a parameter that regulates it. For that
reason, and to make the algorithm more transparent to the reader, I've
replaced RAND_MAX with 0x7fff in the attached patch.
All that being said, adding 1 to *ctx before returning it (see patch)
adresses both of your objections: a seed of 0 will not cause the LCG
to get stuck, and the result of rand() will range between 0 and
RAND_MAX inclusive.
des@des ~/src% ./rndtest| head
2 0 1 7 1 7 f 2 5 3 f 6 a d 6 a 3 b 5 2 f 8 6 3 d 9 6 1 f 0 2 3
4 4 1 a f 3 b 5 4 2 a 6 f 0 0 6 9 5 1 7 c f 6 9 1 7 7 a 7 8 1 b
0 a c 7 a c 7 3 9 f 4 2 d 3 d 9 d 4 4 a 3 0 c f 7 6 2 5 9 2 3 7
5 b 7 7 f 9 9 b d 1 d c 5 2 b 6 7 c c 5 8 4 3 b 2 1 6 f 6 c 2 2
5 6 5 e a b b 8 e e 4 9 1 9 4 2 3 4 d b 3 5 3 a d 4 3 5 b 7 4 a
c 1 2 4 e 5 d 9 0 6 6 8 b 7 f 8 8 2 6 1 c d 1 c f f 0 9 1 3 4 c
5 6 8 b 8 9 a 8 5 d b 8 8 d 7 e 7 0 c 2 c 8 0 6 5 8 f 8 9 6 0 c
9 d 4 7 0 8 5 2 c b 8 e 5 f 5 c d 1 c c b 3 8 8 f f 1 2 a 5 c f
0 5 f 2 4 e 9 0 1 1 9 2 5 f 0 0 2 2 d f b f 7 0 2 a 2 4 7 a 2 f
9 0 f 1 c 8 e 2 f c f 2 8 c d 5 7 0 f 2 b a 2 a 4 d 8 b c 4 0 4
DES
--
Dag-Erling Smorgrav - [EMAIL PROTECTED]
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 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:33:30 -
@@ -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 += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = *ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)0x7fff + 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()
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:28:45 +0300, Andrey A. Chernov wrote:
I'll produce working variant based on your patch...
When all done correctly, there is repeated pattern still, so some NSHUFF
drop required too:
1 7 e 4 a 0 7 d 3 a 0 6
See attached patch based on -current sources.
--
Andrey A. Chernov
http://ache.pp.ru/
--- /usr/src/lib/libc/stdlib/rand.c Tue Feb 4 14:24:08 2003
+++ ./rand.cTue Feb 4 16:40:24 2003
@@ -51,10 +51,8 @@
#include stdio.h
#endif /* TEST */
-#define NSHUFF 100 /* to drop part of seed - 1st value correlation */
-
static int
-do_rand(unsigned long *ctx)
+do_rand(uint32_t *ctx)
{
#ifdef USE_WEAK_SEEDING
/*
@@ -65,24 +63,25 @@
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;
/* Can't be initialized with 0, so use another value. */
if (*ctx == 0)
*ctx = 123459876;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
- x = 16807 * lo - 2836 * hi;
- if (x 0)
- x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = ((uint64_t)*ctx * 62089911) % 2147483647;
+ return ((*ctx = tmp) % ((uint32_t)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
}
@@ -90,7 +89,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;
@@ -98,7 +97,7 @@
}
-static u_long next = 1;
+static uint32_t next = 1;
int
rand()
@@ -110,11 +109,7 @@
srand(seed)
u_int seed;
{
- int i;
-
next = seed;
- for (i = 0; i NSHUFF; i++)
- (void)do_rand(next);
}
Re: rand() is broken
Andrey A. Chernov [EMAIL PROTECTED] 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 - [EMAIL PROTECTED]
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 - 1.11
+++ lib/libc/stdlib/rand.c 4 Feb 2003 13:44:52 -
@@ -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 += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ tmp = (uint64_t)*ctx * 62089911;
+ *ctx = (uint32_t)(tmp % (uint64_t)0x7fff + 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()
Re: rand() is broken
On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: I believe that's a feature. All linear congruence generator have a fixed point. 0 is a far better fixed point than any other because it is more obviously unsuited (for some values of obviously) as a seed value. (but see below) It is implementation details. rand() manpage says nothing about linear congruence generator and not suppose special meaning of 0 which means that application stuck at this point. We should not relay on that. The next bug is that there is % RAND_MAX + 1, not % RAND_MAX. No, using modulo 0x8000 instead of modulo 0x7fff breaks the algorithm. (but see below) Yes, but manpage says about range from 0 to RAND_MAX inclusive. It means that RAND_MAX clipping must be not part of algorithm and be applied only at later stage. Changing RAND_MAX affects the algorithm in such a way that you should not do so without giving serious thought to revising the algorithm Changing RAND_MAX should NOT affect algorithm at all, because RAND_MAX is not part of it. All that being said, adding 1 to *ctx before returning it (see patch) adresses both of your objections: a seed of 0 will not cause the LCG to get stuck, and the result of rand() will range between 0 and RAND_MAX inclusive. Adding +1 you break algorithm formulae badly from math point of view, something else then given formulae not allowed here. You can change 'a' parameter to anything you want, but not add something at the end. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 16:47:14 +0300, Andrey A. Chernov wrote: On Tue, Feb 04, 2003 at 16:28:45 +0300, Andrey A. Chernov wrote: I'll produce working variant based on your patch... When all done correctly, there is repeated pattern still, so some NSHUFF drop required too: 1 7 e 4 a 0 7 d 3 a 0 6 See attached patch based on -current sources. With NSHUFF 100 situation not changed much, so I beleive that stated problem is common for this type PRNGs, so we gains nothing changing formulae to Knuth-recommended values. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov [EMAIL PROTECTED] writes: With NSHUFF 100 situation not changed much, so I beleive that stated problem is common for this type PRNGs, so we gains nothing changing formulae to Knuth-recommended values. Yes we do. We get a better sequence for any given seed, i.e. we get less correlation between n and x(n) for any given x(0). I don't think it changes much for long sequences, but we get a better distribution for short sequences (including short subsequences of long sequences). As for patterns in the lower bits, we should try with a != 0 and see how that affects the results. I believe the purpose of a in the LCG algorithm is to scramble the lower bits. DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov [EMAIL PROTECTED] writes: On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: All that being said, adding 1 to *ctx before returning it (see patch) adresses both of your objections: a seed of 0 will not cause the LCG to get stuck, and the result of rand() will range between 0 and RAND_MAX inclusive. Adding +1 you break algorithm formulae badly from math point of view, something else then given formulae not allowed here. You can change 'a' parameter to anything you want, but not add something at the end. Do the math - adding 1 after the modulo operation is equivalent to setting a == k. DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 15:23:28 +0100, Dag-Erling Smorgrav wrote: Andrey A. Chernov [EMAIL PROTECTED] writes: On Tue, Feb 04, 2003 at 14:43:57 +0100, Dag-Erling Smorgrav wrote: All that being said, adding 1 to *ctx before returning it (see patch) adresses both of your objections: a seed of 0 will not cause the LCG to get stuck, and the result of rand() will range between 0 and RAND_MAX inclusive. Adding +1 you break algorithm formulae badly from math point of view, something else then given formulae not allowed here. You can change 'a' parameter to anything you want, but not add something at the end. Do the math - adding 1 after the modulo operation is equivalent to setting a == k. Repeated k may affect distribution. Better variant will be with a != k. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 15:22:03 +0100, Dag-Erling Smorgrav wrote: Yes we do. We get a better sequence for any given seed, i.e. we get less correlation between n and x(n) for any given x(0). I don't think it changes much for long sequences, but we get a better distribution for short sequences (including short subsequences of long sequences). Maybe, I am not sure here, we need to ask expert. As for patterns in the lower bits, we should try with a != 0 and see how that affects the results. I believe the purpose of a in the LCG algorithm is to scramble the lower bits. a != 0 eliminates 0 stuck problem, no additional visible effects. Even with a != 0 values are monotonically increased, I try with a == 123459876 0: 123459876 1: 185549787 2: 247639698 3: 309729609 4: 371819520 5: 433909431 6: 495999342 7: 558089253 8: 620179164 9: 682269075 -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Tue, Feb 04, 2003 at 17:36:04 +0300, Andrey A. Chernov wrote: with a != 0 values are monotonically increased, I try with a == 123459876 With your a == 62089911 (i.e. +1) the same: 0: 62089911 1: 124179822 2: 186269733 3: 248359644 4: 310449555 5: 372539466 6: 434629377 7: 496719288 8: 558809199 9: 620899110 With a == 0 the same: 0: 0 1: 62089911 2: 124179822 3: 186269733 4: 248359644 5: 310449555 6: 372539466 7: 434629377 8: 496719288 9: 558809199 Where is improvement? -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
FWIW - AIX aggrees with Solaris.
Endiannes, or an SVR4 implementation difference?
OS X agrees with FreeBSD i386. In fact, FreeBSD sparc64 and FreeBSD
alpha are all the same too, so it seems the code isn't too sensitive
to byteorder or wordsize.
Bakul's comments on who agrees with BSD 4.{2,3,4}-* probably explain
the differences.
David.
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
* De: David Malone [EMAIL PROTECTED] [ Data: 2003-02-03 ]
[ Subjecte: Re: rand() is broken ]
FWIW - AIX aggrees with Solaris.
Endiannes, or an SVR4 implementation difference?
OS X agrees with FreeBSD i386. In fact, FreeBSD sparc64 and FreeBSD
alpha are all the same too, so it seems the code isn't too sensitive
to byteorder or wordsize.
Bakul's comments on who agrees with BSD 4.{2,3,4}-* probably explain
the differences.
*Nod* when I saw that message, I got it :)
--
Juli Mallett [EMAIL PROTECTED]
AIM: BSDFlata -- IRC: juli on EFnet
OpenDarwin, Mono, FreeBSD Developer
ircd-hybrid Developer, EFnet addict
FreeBSD on MIPS-Anything on FreeBSD
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 16:26:39 -0800, David Schultz wrote: The correlation is still present with your patch and NSHUFF set to 10. For instance, try seeding rand() with contiguous monotonically increasing integers, and observe the four lowest-order bits. Since you already have running framework for that, could you please test it with NSHUFF picked from 100-2000 range? -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
At 4:41 PM -0800 2003/02/02, Terry Lambert wrote: Donald Knuth seemed to like them well enough to publish the algorithm, as part of his discussion on randomness. He *didn't* publish RC4, in that same discussion. RC stands for Ron's Code. This stuff came after the work that Diffie Hellman did, for which the patent expired a little while ago. Did RC4 even exist at the time that Don published that book? -- Brad Knowles, [EMAIL PROTECTED] They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. -Benjamin Franklin, Historical Review of Pennsylvania. GCS/IT d+(-) s:+(++): a C++(+++)$ UMBSHI$ P+++ L+ !E-(---) W+++(--) N+ !w--- O- M++ V PS++(+++) PE- Y+(++) PGP+++ t+(+++) 5++(+++) X++(+++) R+(+++) tv+(+++) b+() DI+() D+(++) G+() e++ h--- r---(+++)* z(+++) To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
FWIW - AIX aggrees with Solaris. OSF1 .. V5.1 732 alpha HP-UX . B.11.00 U 9000/800 agree with Solaris -- Alexander Pohoyda [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
Andrey A. Chernov writes: If I understand correctly, this still doesn't solve the problem, because any PRNG sequence that hits the magic value will still get stuck there forever. It was true for the first patch I post which just move problem to another= place (this is commonly spreaded method for this PRNG). It is false for the last patch I post which not stuck with any given seed. How do you _know_ that your newly chosen magic number isn't going to cause some kind of recurring (and too-short) sequence of numbers? Will it recur after 5 iterations? 100? 1000? 100? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: How do you _know_ that your newly chosen magic number isn't going to cause some kind of recurring (and too-short) sequence of numbers? I run simple test for it, it is not too short. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 14:08:41 +0300, Andrey A. Chernov wrote: On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: How do you _know_ that your newly chosen magic number isn't going to cause some kind of recurring (and too-short) sequence of numbers? I run simple test for it, it is not too short. To be more specific - it never returns to 0 from this value at least in 2**31 iterations. You can test it by yourself, the code is obvious: srand(0) ... loop ... if (rand() == 0) print iteration number -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
Andrey A. Chernov writes: On Mon, Feb 03, 2003 at 10:55:42 +, Mark Murray wrote: How do you _know_ that your newly chosen magic number isn't going to cause some kind of recurring (and too-short) sequence of numbers? I run simple test for it, it is not too short. simple test? How long did you check for? random() is documented to not repeat before some number of outputs; how do you know that this fix does not significantly shorten that? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 11:19:17 +, Mark Murray wrote: simple test? How long did you check for? See my another message with details. random() is documented to not repeat before some number of outputs; how do you know that this fix does not significantly shorten that? random(3) is not affected to to its hashing nature. We talk about rand(3). -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for 0 problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 14:26:00 +0300, Andrey A. Chernov wrote: random(3) is not affected to to its hashing nature. We talk about rand(3). to to = due to -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Final fix for correlation problem (was Re: rand() is broken)
This is final fix for 1st value correlation problem. Somebody with
math statistic knowledge please run some test to be sure that NSHUFF is
good enough for this simple PRNG (i.e. not 100% good, but good for average
quality PRNG we have). My simple test shown that 100 is enough, but I
am not PRNG math expert. Maybe increasing NSHUFF up too 2000 required.
Similar patch is needed for random(3) TYPE_0 too, I'll produce it when we
find good NSHUFF.
--- stdlib/rand.c.bak Mon Feb 3 13:22:12 2003
+++ stdlib/rand.c Mon Feb 3 14:03:58 2003
@@ -51,6 +51,8 @@
#include stdio.h
#endif /* TEST */
+#define NSHUFF 100 /* to drop seed - 1st value correlation */
+
static int
do_rand(unsigned long *ctx)
{
@@ -108,7 +110,11 @@
srand(seed)
u_int seed;
{
+ int i;
+
next = seed;
+ for (i = 0; i NSHUFF; i++)
+ (void)do_rand(next);
}
@@ -137,7 +143,7 @@
unsigned long junk;
gettimeofday(tv, NULL);
- next = (getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk;
+ srand((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk);
}
}
--
Andrey A. Chernov
http://ache.pp.ru/
msg51666/pgp0.pgp
Description: PGP signature
Re: Final fix for correlation problem (was Re: rand() is broken)
I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? I have worked with programs that depend on exactly that behavior. That is, given the same input seed - I expect to see the same random sequence again. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... Please, oh please, don't change that behavior in srand()/rand(). - Dave Rivers - -- [EMAIL PROTECTED]Work: (919) 676-0847 Get your mainframe programming tools at http://www.dignus.com To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 07:01:50 -0500, Thomas David Rivers wrote: Please, oh please, don't change that behavior in srand()/rand(). This subject is not discussed (again). We already discuss it long time ago and agrees that changes are allowed especially when they fix bugs. Search mailing lists for exact arguments. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
On Mon, Feb 03, 2003 at 07:01:50AM -0500, Thomas David Rivers wrote: I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? That understanding is mistaken. I have worked with programs that depend on exactly that behavior. Then those programs have a bug. If you need every execution of the program to use the exact same sequence of pseudo-random numbers then the program need to implement its own RNG. That is, given the same input seed - I expect to see the same random sequence again. You will - if you generate both sequences during the same program execution. There are no guarantees (and has never been) that srand()/rand() will give the same sequence after an OS update or on a different system or even between two different runs of the same program. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... a) srand()/rand() does use different algorithms on different systems so depending on some particular algorithm is inherently unportable. b) random() was not introduced because the sequence from rand() couldn't be changed. It was rather because the calling interface for srand()/rand() puts constraints on the implementation that result in rand() by necessity being a rather poor RNG. random() was introduced so one could have a RNG with better statistical properties. c) I believe the algorithm used by rand() *was* changed in -CURRENT about two years ago. (And pretty the same discussion ensued back then.) This change was done because the old algorithm used was particularly poor and it was possible to do better. Now some defect in the new algorithm has apparently been discovered which is why it needs to be modified again. Please, oh please, don't change that behavior in srand()/rand(). - Dave Rivers - -- Insert your favourite quote here. Erik Trulsson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: Final fix for correlation problem (was Re: rand() is broken)
Thus spake Thomas David Rivers [EMAIL PROTECTED]: I'm afraid I don't understand the fix... and how it seems to affect the historical behaviour of srand()/rand(). How does it address the understanding that if I use srand(28), I will get exactly the same sequence of numbers srand(28) produced yesterday, last week, last year? I have worked with programs that depend on exactly that behavior. That is, given the same input seed - I expect to see the same random sequence again. This requirement would seem to indicate that changing srand()/rand() isn't really possible... And, also, I believe, why random() was introduced... Please, oh please, don't change that behavior in srand()/rand(). There are two sides to this argument. One side says that rand() should always produce the same sequence for a given seed no matter what. This argument is bogus, because if you need exact reproducability across all platforms for all time, you should be using your own PRNG. The other side says that rand() should be a reasonably good RNG for most applications. It would be nice if things worked out that way, but there are enough broken rand() implementations out there that most people don't rely upon them. So I'd be inclined to call this argument bogus as well, except that I know someone who has been burned by a bad rand() while trying to test a randomized graph algorithm in C. My final thoughts are that having a better rand() implementation is a Good Thing, but it isn't that big a deal, and it certainly isn't worth all of this bickering. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah [EMAIL PROTECTED] writes: Guys, please realize that random() is also used in generating simulation inputs (or timing or whatever). If you go change the underlying algorithm or its parameters one can't generate the same sequence from the same seed when repeating a test. Some chip bug symptoms show up after hours/days of simulation time and only with specific inputs so repeatablity is a requirement. Go to URL:http://stat.fsu.edu/pub/diehard/cdrom/ for free download of up to 480,000,000 random bits, which ought to be enough for most simulations. DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Brad Knowles wrote: At 4:41 PM -0800 2003/02/02, Terry Lambert wrote: Donald Knuth seemed to like them well enough to publish the algorithm, as part of his discussion on randomness. He *didn't* publish RC4, in that same discussion. RC stands for Ron's Code. This stuff came after the work that Diffie Hellman did, for which the patent expired a little while ago. Did RC4 even exist at the time that Don published that book? Not the original edition, but yes, for the revised edition, which is only a couple of years old, and, in fact, includes some new algorithms, based on the fact that Fermat's last Theorem has been proved, proving the Taniyama-Shimura Conjecture as a side effect, etc.. -- Terry To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Thus spake Andrey A. Chernov [EMAIL PROTECTED]:
On Sun, Feb 02, 2003 at 16:26:39 -0800, David Schultz wrote:
The correlation is still present with your patch and NSHUFF set to
10. For instance, try seeding rand() with contiguous monotonically
increasing integers, and observe the four lowest-order bits.
Since you already have running framework for that, could you please
test it with NSHUFF picked from 100-2000 range?
Rather than me showing you more semi-meaningful numbers from
Marsaglia's tests, why don't you look at the following sequence,
which I get by taking the lowest four bits of the 201st number in
the rand() sequence for seeds of (0, 1, 2, ...).
f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9
6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f
c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5
2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b
8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1
e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7
4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d
a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3
0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9
6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f
Notice that 'f c 9' repeats in regular intervals and is always
followed by a 5 or 6. There is a similar pattern for 'e a 7'. I
think this pretty much demonstrates that the algorithm isn't good
enough to generate high-quality randomness with respect to
different seed values. I'm not suggesting that it absolutely must
be replaced, since most rand() implementations aren't very good in
the first place, but I'm pointing out that to do a good job of
fixing it once and for all is harder than you might think.
The program to generate this sequence follows. I ran this on a
several-month-old -CURRENT system with the new generator, but
without your latest patches.
#include stdio.h
#include stdlib.h
int main() {
int i, j;
for (i = 0; ; i++) {
srand(i);
for (j = 0; j 200; j++)
rand();
printf(%x , rand() 0x0f);
if (i % 32 == 31)
putchar('\n');
}
}
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
David Schultz ([EMAIL PROTECTED]) wrote: Rather than me showing you more semi-meaningful numbers from Marsaglia's tests, why don't you look at the following sequence, which I get by taking the lowest four bits of the 201st number in the rand() sequence for seeds of (0, 1, 2, ...). f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f Notice that 'f c 9' repeats in regular intervals and is always followed by a 5 or 6. There is a similar pattern for 'e a 7'. I think this pretty much demonstrates that the algorithm isn't good enough to generate high-quality randomness with respect to different seed values. I'm not suggesting that it absolutely must be replaced, since most rand() implementations aren't very good in the first place, but I'm pointing out that to do a good job of fixing it once and for all is harder than you might think. A littele modification shows just how similar these sequences are :) -- Eric Hodel - [EMAIL PROTECTED] - http://segment7.net All messages signed with fingerprint: FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04 msg51721/pgp0.pgp Description: PGP signature
Re: rand() is broken
Thus spake Eric Hodel [EMAIL PROTECTED]: David Schultz ([EMAIL PROTECTED]) wrote: Rather than me showing you more semi-meaningful numbers from Marsaglia's tests, why don't you look at the following sequence, which I get by taking the lowest four bits of the 201st number in the rand() sequence for seeds of (0, 1, 2, ...). f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e b 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 6 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 1 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f c 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 7 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f c 9 5 2 f b 8 5 2 e b 8 4 1 e a 7 4 0 d a 6 3 0 d 9 6 3 f Notice that 'f c 9' repeats in regular intervals and is always followed by a 5 or 6. There is a similar pattern for 'e a 7'. I think this pretty much demonstrates that the algorithm isn't good enough to generate high-quality randomness with respect to different seed values. I'm not suggesting that it absolutely must be replaced, since most rand() implementations aren't very good in the first place, but I'm pointing out that to do a good job of fixing it once and for all is harder than you might think. A littele modification shows just how similar these sequences are :) Yeah, I saw the periodicity when I asked less(1) to select particular subsequences. I guess it's a bit more impressive when you select the right modulus. ;-) To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
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.
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 */
+#define NSHUFF 3
+
static int
do_rand(unsigned long *ctx)
{
@@ -103,7 +105,11 @@
srand(seed)
u_int seed;
{
+ int i;
+
next = seed;
+ for (i = 0; i NSHUFF; i++)
+ (void)do_rand(next);
}
@@ -117,7 +123,7 @@
void
sranddev()
{
- int fd, done;
+ int fd, done, i;
done = 0;
fd = _open(/dev/random, O_RDONLY, 0);
@@ -133,6 +139,8 @@
gettimeofday(tv, NULL);
next = (getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk;
+ for (i = 0; i NSHUFF; i++)
+ (void)do_rand(next);
}
}
--
Andrey A. Chernov
http://ache.pp.ru/
msg51491/pgp0.pgp
Description: PGP signature
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:04:22PM +0300, Andrey A. Chernov wrote: 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. 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. Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). It looks like a lot more validation of this PRNG is needed. Kris msg51493/pgp0.pgp Description: PGP signature
Re: rand() is broken
On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). It looks like a lot more validation of this PRNG is needed. Don't have an idea about this thing yet, maybe some sign or variable size change fix required. BTW, note that new formulae also used in the kernel (by BSD developers) and taken from there - libkern/random.c - so all you say is true there too. -- Andrey A. Chernov http://ache.pp.ru/ msg51495/pgp0.pgp Description: PGP signature
Re: rand() is broken
In message [EMAIL PROTECTED], Andrey A. Chernov writes: --SUOF0GtieIMvvwua Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: =20 Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). =20 It looks like a lot more validation of this PRNG is needed. Don't have an idea about this thing yet, maybe some sign or variable size= =20 change fix required. BTW, note that new formulae also used in the kernel (by BSD developers) and taken from there - libkern/random.c - so all you say is true there too. It should be nuked from the kernel, and arc4random() used instead. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
[EMAIL PROTECTED] writes: BTW, note that new formulae also used in the kernel (by BSD developers) and taken from there - libkern/random.c - so all you say is true there too. It should be nuked from the kernel, and arc4random() used instead. I agree. If no-one objects, I'll do this? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 01:11:06 -0800, Kris Kennaway wrote: Another problem (noticed by tjr) is that once the sequence hits '0' it jumps to INT_MAX and stays there forever. For example, seeding with srand(0) produces nothing but INT_MAX from rand(). It looks like a lot more validation of this PRNG is needed. As I see searching through various sources, this is not simple overlook but fundamental feature of this formulae - it can't be initialized with zero and BSD developers try to deal with that fact by simple adding of INT_MAX in zero case (which is not in the original formulae), but gain nothing this way. Workaround I find so far is something like that #define MASK 123459876 seed ^= MASK; ... calculate value ... seed ^= MASK; Which just add another magick value, but fix zero. I am still searching... -- Andrey A. Chernov http://ache.pp.ru/ msg51498/pgp0.pgp Description: PGP signature
Re: rand() is broken
Thus spake Andrey A. Chernov [EMAIL PROTECTED]: 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. 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. Throwing away the first 10 numbers is probably not good enough to eliminate randomness with respect to the initial seed. Knuth suggests throwing away the first 2000, but he is conservative.[1] But no amount of throwing away the initial sequence will help as long as the generator itself doesn't look very random. Specifically, rand() isn't very interesting in the lower-order bits, and it spectacularly fails nearly all of Marsaglia's randomness tests.[2] If rand() is a concern to someone, they should either find LCG parameters that produce better behavior, or research a replacement algorithm. [1] His PRNG is available from http://www-cs-faculty.stanford.edu/~knuth/programs/rng.c [2] http://stat.fsu.edu/~geo/diehard.html (you need ports/lang/f2c) To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 03:48:17 -0800, David Schultz wrote: Specifically, rand() isn't very interesting in the lower-order bits, and it spectacularly fails nearly all of Marsaglia's It seems that you speak about old formulae, we use new one (which intended to fix low-ordered bits), see our rand.c source. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote:
Workaround I find so far is something like that
#define MASK 123459876
I found nothing better. Here is fix for 0 problem I plan to commit:
--- stdlib/rand.c.old Sat Jan 4 20:39:19 2003
+++ stdlib/rand.c Sun Feb 2 14:43:42 2003
@@ -70,14 +70,18 @@
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/
+#define SHIFT_MASK 123459876
long hi, lo, x;
- hi = *ctx / 127773;
- lo = *ctx % 127773;
+ /* Can't be initialized with 0, so use shifting mask. */
+ x = *ctx ^ SHIFT_MASK;
+ hi = x / 127773;
+ lo = x % 127773;
x = 16807 * lo - 2836 * hi;
- if (x = 0)
+ if (x 0)
x += 0x7fff;
- return ((*ctx = x) % ((u_long)RAND_MAX + 1));
+ *ctx = x ^ SHIFT_MASK;
+ return (x % ((u_long)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
}
@@ -86,8 +90,10 @@
rand_r(unsigned int *ctx)
{
u_long val = (u_long) *ctx;
- *ctx = do_rand(val);
- return (int) *ctx;
+ int r = do_rand(val);
+
+ *ctx = (unsigned int) val;
+ return (r);
}
--- stdlib/random.c.old Sun Mar 24 23:42:48 2002
+++ stdlib/random.c Sun Feb 2 15:24:38 2003
@@ -142,6 +142,10 @@
*/
#defineMAX_TYPES 5 /* max number of types above */
+#ifndef USE_WEAK_SEEDING
+#define SHIFT_MASK 123459876
+#endif
+
static long degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
static long seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
@@ -171,12 +175,12 @@
0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
0x27fb47b9,
#else /* !USE_WEAK_SEEDING */
- 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
+ 0x52a59789, 0x43164b1c, 0x7be52a82, 0x748ef343, 0x642a8923, 0x6ade1cd8,
+ 0x1ae76e27, 0x24b915ee, 0x2c42f326, 0x12ab3ee1, 0x4679af03, 0x876d19a0,
+ 0xe9e535ba, 0xad2471c8, 0x710262f8, 0xe1c16494, 0x29224bcc, 0x9710c348,
+ 0x7347f8e4, 0xe01ef1b4, 0x2030c33f, 0xd465e38, 0x925375aa, 0x6091d15d,
+ 0x467ee7d7, 0x92713312, 0x32346127, 0x8350e834, 0x3dadc6ea, 0x391364f2,
+ 0x8226561c,
#endif /* !USE_WEAK_SEEDING */
};
@@ -236,12 +240,14 @@
*/
long hi, lo;
+ /* Can't be initialized with 0, so use shifting mask. */
+ x ^= SHIFT_MASK;
hi = x / 127773;
lo = x % 127773;
x = 16807 * lo - 2836 * hi;
- if (x = 0)
+ if (x 0)
x += 0x7fff;
- return (x);
+ return (x ^ SHIFT_MASK); /* return state, not value */
#endif /* !USE_WEAK_SEEDING */
}
@@ -473,7 +479,12 @@
if (rand_type == TYPE_0) {
i = state[0];
- state[0] = i = (good_rand(i)) 0x7fff;
+ state[0] = good_rand(i);
+#ifndef USE_WEAK_SEEDING
+ i = state[0] ^ SHIFT_MASK;
+#else
+ i = state[0] 0x7fff;
+#endif
} else {
/*
* Use local variables rather than static variables for speed.
--
Andrey A. Chernov
http://ache.pp.ru/
msg51505/pgp0.pgp
Description: PGP signature
Re: rand() is broken
On Sun, 2 Feb 2003, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote: Workaround I find so far is something like that #define MASK 123459876 I found nothing better. Here is fix for 0 problem I plan to commit: I think it's worthwhile to wait till we get a chance to try arc4random(). Also, have you run the code you're proposing through the tests in the post that David Schultz just made? Before leaping ahead with another band-aid it would be nice to give this some serious thought. Doug -- If it's moving, encrypt it. If it's not moving, encrypt it till it moves, then encrypt it some more. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 04:38:53 -0800, Doug Barton wrote: I think it's worthwhile to wait till we get a chance to try arc4random(). This is libc's rand/random, it can't be fixed with arc4random() as designed. Also, have you run the code you're proposing through the tests in the post that David Schultz just made? This is fix form problem with 0, not for seed - 1st value correlation. I can't deal with two problems with same time, lets be sequental. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 03:30:35PM +0300, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 13:26:21 +0300, Andrey A. Chernov wrote: Workaround I find so far is something like that #define MASK 123459876 I found nothing better. Here is fix for 0 problem I plan to commit: --- stdlib/rand.c.old Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2 14:43:42 2003 @@ -70,14 +70,18 @@ * Park and Miller, Communications of the ACM, vol. 31, no. 10, * October 1988, p. 1195. */ +#define SHIFT_MASK 123459876 long hi, lo, x; - hi = *ctx / 127773; - lo = *ctx % 127773; + /* Can't be initialized with 0, so use shifting mask. */ + x = *ctx ^ SHIFT_MASK; + hi = x / 127773; + lo = x % 127773; x = 16807 * lo - 2836 * hi; - if (x = 0) + if (x 0) x += 0x7fff; - return ((*ctx = x) % ((u_long)RAND_MAX + 1)); + *ctx = x ^ SHIFT_MASK; + return (x % ((u_long)RAND_MAX + 1)); #endif /* !USE_WEAK_SEEDING */ } I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Tim To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is possible for this formulae and this is documented in algorithm, some value must be excluded. Excluding 0 is bad only because srand(0) is commonly used and srand(123459876) is not. Ragarding to old formulae, the question is: what is worse, generate non-random lover bits everytime (old variant) or exclude one seed value (new variant)? Of course formulae can be changed to some another algorithm, but keep in mind that rand() must be simple and speedy. Now used variant is most simpler, others are much more complex. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 16:42:25 +0300, Andrey A. Chernov wrote: On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is possible for this formulae and this is documented in algorithm, some value must be excluded. Excluding 0 is bad only because srand(0) is commonly used and srand(123459876) is not. This workaround can be improved more, to make generator not stuck ever with 123459876 by simple way: if (seed == 123459876) seed = 123459877; It can be done even with original variant using more simpler patch: if (seed == 0) seed = 123459876; I'll produce and send it a bit later. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 17:02:23 +0300, Andrey A. Chernov wrote:
I'll produce and send it a bit later.
Here it is.
--- stdlib/rand.c.old Sat Jan 4 20:39:19 2003
+++ stdlib/rand.c Sun Feb 2 17:06:08 2003
@@ -72,10 +72,13 @@
*/
long hi, lo, x;
+ /* Can't be initialized with 0, so use another value. */
+ if (*ctx == 0)
+ *ctx = 123459876;
hi = *ctx / 127773;
lo = *ctx % 127773;
x = 16807 * lo - 2836 * hi;
- if (x = 0)
+ if (x 0)
x += 0x7fff;
return ((*ctx = x) % ((u_long)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
@@ -86,8 +89,10 @@
rand_r(unsigned int *ctx)
{
u_long val = (u_long) *ctx;
- *ctx = do_rand(val);
- return (int) *ctx;
+ int r = do_rand(val);
+
+ *ctx = (unsigned int) val;
+ return (r);
}
--- stdlib/random.c.old Sun Mar 24 23:42:48 2002
+++ stdlib/random.c Sun Feb 2 17:09:19 2003
@@ -236,10 +236,13 @@
*/
long hi, lo;
+ /* Can't be initialized with 0, so use another value. */
+ if (x == 0)
+ x = 123459876;
hi = x / 127773;
lo = x % 127773;
x = 16807 * lo - 2836 * hi;
- if (x = 0)
+ if (x 0)
x += 0x7fff;
return (x);
#endif /* !USE_WEAK_SEEDING */
--
Andrey A. Chernov
http://ache.pp.ru/
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Final fix for 0 problem (was Re: rand() is broken)
So far, this is final variant for 0 problem fixing ready for committing. Any objections? --- stdlib/rand.c.old Sat Jan 4 20:39:19 2003 +++ stdlib/rand.c Sun Feb 2 17:34:34 2003 @@ -72,10 +72,13 @@ */ long hi, lo, x; + /* Can't be initialized with 0, so use another value. */ + if (*ctx == 0) + *ctx = 123459876; hi = *ctx / 127773; lo = *ctx % 127773; x = 16807 * lo - 2836 * hi; - if (x = 0) + if (x 0) x += 0x7fff; return ((*ctx = x) % ((u_long)RAND_MAX + 1)); #endif /* !USE_WEAK_SEEDING */ --- stdlib/random.c.old Sun Mar 24 23:42:48 2002 +++ stdlib/random.c Sun Feb 2 17:09:19 2003 @@ -236,10 +236,13 @@ */ long hi, lo; + /* Can't be initialized with 0, so use another value. */ + if (x == 0) + x = 123459876; hi = x / 127773; lo = x % 127773; x = 16807 * lo - 2836 * hi; - if (x = 0) + if (x 0) x += 0x7fff; return (x); #endif /* !USE_WEAK_SEEDING */ -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
David Schultz [EMAIL PROTECTED] writes: [2] http://stat.fsu.edu/~geo/diehard.html (you need ports/lang/f2c) There's a native C version on Marsaglia's random number CD: http://stat.fsu.edu/pub/diehard/cdrom/die.c/ DES -- Dag-Erling Smorgrav - [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Jeroen C. van Gelderen writes: Wouldn't it be a good idea to change the name at the same time? Or should it be retained for compatibility reasons with other BSDs? Currently the name needlessly exposes implementation detail. Callers expect good, cheap, non-blocking randomness but don't give a hoot if that is actually provided trough use of RC4 or not. I see no reason why the implementation could be changed if the contract is maintained. Good point. We can re-implement random() internally with arc4rand(). Objections? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 15:32:32 +, Mark Murray wrote: Jeroen C. van Gelderen writes: Wouldn't it be a good idea to change the name at the same time? Or should it be retained for compatibility reasons with other BSDs? Currently the name needlessly exposes implementation detail. Callers expect good, cheap, non-blocking randomness but don't give a hoot if that is actually provided trough use of RC4 or not. I see no reason why the implementation could be changed if the contract is maintained. Good point. We can re-implement random() internally with arc4rand(). Objections? We can't, simple because sequence must be repeated for the same seed across the calls. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 04:38:53 -0800, Doug Barton wrote: I think it's worthwhile to wait till we get a chance to try arc4random(). This is libc's rand/random, it can't be fixed with arc4random() as designed. Why not? Arc4 is a) deterministic and b) good for all bits. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov writes: On Mon, Feb 03, 2003 at 00:17:35 +1100, Tim Robbins wrote: I believe that this change just moves the bad seed to 123459876; after calling srand() with that seed, each call to rand() returns 0. Yes. Nothing better is possible for this formulae and this is documented in algorithm, some value must be excluded. Excluding 0 is bad only because srand(0) is commonly used and srand(123459876) is not. This means that this routine has a chance of failing spectacularly. We should not use it. Ragarding to old formulae, the question is: what is worse, generate non-random lover bits everytime (old variant) or exclude one seed value (new variant)? Neither. New RNG is needed. Of course formulae can be changed to some another algorithm, but keep in mind that rand() must be simple and speedy. Now used variant is most simpler, others are much more complex. RC4 is fast. RC4 is simple. Any objections? :-) M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov writes: Objections? We can't, simple because sequence must be repeated for the same seed across the calls. RC4 is repeatable. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: Why not? Arc4 is a) deterministic and b) good for all bits. If you mean arc4random() function - not, because it use true randomness, if you mean RC4 algorithm, probably yes, but we should compare its distribution with our current variant and be sure that speed is acceptable. What form RC4 distribution have? -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 17:34:19 +, Mark Murray wrote: Andrey A. Chernov writes: Objections? We can't, simple because sequence must be repeated for the same seed across the calls. RC4 is repeatable. It seems we mean different things saying arc4random(), see my answer in the thread. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 21:20:09 +0300, Andrey A. Chernov wrote: On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: Why not? Arc4 is a) deterministic and b) good for all bits. If you mean arc4random() function - not, because it use true randomness, if you mean RC4 algorithm, probably yes, but we should compare its distribution with our current variant and be sure that speed is acceptable. What form RC4 distribution have? BTW, if we ever think about replacing our current variant with such complex and unknown (at least to me) thing as RC4-based PseudoRNG, I simpatize more to Knuth variant mentioned by David Schultz: http://www-cs-faculty.stanford.edu/~knuth/programs/rng.c RC4 is good for hashing existen randomness, but is it good as PseudoRNG? -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
In message [EMAIL PROTECTED], Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: Why not? Arc4 is a) deterministic and b) good for all bits. If you mean arc4random() function - not, because it use true randomness, if you mean RC4 algorithm, probably yes, but we should compare its distribution with our current variant and be sure that speed is acceptable. What form RC4 distribution have? RC4 can be implemented in about 4 lines of C. Anyway, last time we discussed this, I think we stuck with the rand() we had because we feared that people were using it's repeatable well documented sequence of random numbers in regression testing. This is still a valid concern, but I don't know how significant a concern it is. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 19:32:50 +0100, [EMAIL PROTECTED] wrote: Anyway, last time we discussed this, I think we stuck with the rand() we had because we feared that people were using it's repeatable well documented sequence of random numbers in regression testing. As documented, it must be repeatable across the calls for same seed, that is all. It not means repeatable accross platforms or across different OS versions. In fact it is already not repeatable across different OS'es, so regression is limited. Also, regression must not stop bugs fixing progress in anycase. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 17:30:48 +, Mark Murray wrote: Why not? Arc4 is a) deterministic and b) good for all bits. If you mean arc4random() function - not, because it use true randomness, if you mean RC4 algorithm, probably yes, but we should compare its distribution with our current variant and be sure that speed is acceptable. What form RC4 distribution have? (I have read the whole thread) I think we need four things. 1) void srandom(int arg) which uses the argument to seed. 2) void srandomdev(void) which uses system entropy to seed. 3) int random(void) which returns a number statistically random in all bits. 4) something else which returns as many bytes of randomness (statistically random in all bits) as the caller asks for. We have most of this, and RC4 can deliver. RC4's licence is fine. Call it ArCFour and there is no problem. The code is small, fast and repeatable, and meets conditions 1-4 above. Coding is Junior-high-school level, given the spec. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
In message [EMAIL PROTECTED], Andrey A. Chernov writes: On Sun, Feb 02, 2003 at 19:32:50 +0100, [EMAIL PROTECTED] wrote: Anyway, last time we discussed this, I think we stuck with the rand() we had because we feared that people were using it's repeatable well documented sequence of random numbers in regression testing. As documented, it must be repeatable across the calls for same seed, that is all. It not means repeatable accross platforms or across different OS versions. In fact it is already not repeatable across different OS'es, so regression is limited. Also, regression must not stop bugs fixing progress in anycase. Our manual pages do not comprehensively list all compatibility concerns or concessions, waving our manpage about does not address the concern. As I said, I don't know how big a concern this is. But last time it was enough of a concern to make us keep rand() as it was. Please surf the mail-archives to find the discussion, it contained a lot of good arguments from both sides, arguments which should be thought about before changing rand(). -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
In message [EMAIL PROTECTED], Mark Murray wr ites: We have most of this, and RC4 can deliver. RC4's licence is fine. Call it ArCFour and there is no problem. The code is small, fast and repeatable, and meets conditions 1-4 above. There are some concerns about RC4's strength and predictability. In cases were we just want trivial randomness, this doesn't matter, but when we start to seed it with /dev/random to get good randomness we to be more careful. Maybe we should spend an AES on it, just in case ? -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Good point. We can re-implement random() internally with arc4rand(). Objections? Guys, please realize that random() is also used in generating simulation inputs (or timing or whatever). If you go change the underlying algorithm or its parameters one can't generate the same sequence from the same seed when repeating a test. Some chip bug symptoms show up after hours/days of simulation time and only with specific inputs so repeatablity is a requirement. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has a pretty long cycle and enough randomness to be very useful and it *is* used. *Please* don't change random() -- if you do that you will break existing tests. It is not a matter of just rewriting tests since there is no easy way to predict which input triggers a certain bug -- one can try to use the same binaries but that prevents fixing of bugs in the test generation code itself. If you think random() is not random enough for your purposes, go create a new function with a *new* name. [I see from his latest email that PHK remembered the old discussion!] -- bakul To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 19:43:44 +0100, [EMAIL PROTECTED] wrote: Please surf the mail-archives to find the discussion, it contained a lot of good arguments from both sides, arguments which should be thought about before changing rand(). I remember well that we decide to allow it be changed in that discussion, moreover we already change it once. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 19:47:12 +0100, [EMAIL PROTECTED] wrote: In message [EMAIL PROTECTED], Mark Murray wr ites: We have most of this, and RC4 can deliver. RC4's licence is fine. Call it ArCFour and there is no problem. The code is small, fast and repeatable, and meets conditions 1-4 above. There are some concerns about RC4's strength and predictability. Yes. That why I say we need to run some tests to compare RC4 distribution and other vital parameters with our current variant. The worst case will be if we replace good PRNG with bad. F.e. Knuth variant I already mention already proven as better than what we currently have, so don't have such problem as RC4-based PRNG probably have. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
[EMAIL PROTECTED] writes: In message [EMAIL PROTECTED], Mark Murray wr ites: We have most of this, and RC4 can deliver. RC4's licence is fine. Call it ArCFour and there is no problem. The code is small, fast and repeatable, and meets conditions 1-4 above. There are some concerns about RC4's strength and predictability. Not here. We are talking statistical randomness, not cryptographic. RC4 is jst fine. In cases were we just want trivial randomness, this doesn't matter, but when we start to seed it with /dev/random to get good randomness we to be more careful. Sure. srandomdev() needs to burn some output. Maybe we should spend an AES on it, just in case ? Hold that thought. The moral equivalent of 'dd if=random() of=/dev/null bs=1 count=4096' is enough for now. Any problems, and I'll be right with you! M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
As I said, I don't know how big a concern this is. But last time it was enough of a concern to make us keep rand() as it was. [I know you are talking about rand() but Mark Murray's earlier email about wanting to re-implement random() really concerned me so I want to make sure my point gets across] Not changing random() was of real concern to me when I was doing chip simulations. ASIC design verification folks won't be happy if the rug is pulled out from under them. In general crypto and simulation needs are different and I don't trust the crypto guys to look out for the simulation guys! I don't care any more if rand() is changed but _please_ leave random() alone! And it would be nice to indicate *why* in the source code for the next time this discussion comes up. Thanks! -- bakul To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah writes: Good point. We can re-implement random() internally with arc4rand(). Objections? Guys, please realize that random() is also used in generating simulation inputs (or timing or whatever). If you go change the underlying algorithm or its parameters one can't generate the same sequence from the same seed when repeating a test. Some chip bug symptoms show up after hours/days of simulation time and only with specific inputs so repeatablity is a requirement. RC4 is _utterly_ repeatable, given a particular seed/key. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has a pretty long cycle and enough randomness to be very useful and it *is* used. Yes. And it breaks, and we have a complainant. *Please* don't change random() -- if you do that you will break existing tests. It is not a matter of just rewriting tests since there is no easy way to predict which input triggers a certain bug -- one can try to use the same binaries but that prevents fixing of bugs in the test generation code itself. Heisenbug. Which tests do we break? Tests for specific output, or tests for more general cases? The random() function in libc is documented to give the same pseudo-random output for a particular seed. if you link your program against a _different_ libc, you cannot expect your results to follow a particular number sequence. We have to be able to fix bugs, and a bug has been identified. If you want a stable generator here, link statically, and keep a set of compatiblity libraries around. If you think random() is not random enough for your purposes, go create a new function with a *new* name. Any supporters of this request? [I see from his latest email that PHK remembered the old discussion!] So did I! M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah writes: Not changing random() was of real concern to me when I was doing chip simulations. ASIC design verification folks won't be happy if the rug is pulled out from under them. In general crypto and simulation needs are different and I don't trust the crypto guys to look out for the simulation guys! Are you a Verilog guy ar a VRML guy? Something else maybe? M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 07:08:47PM +, Mark Murray wrote: RC4 is _utterly_ repeatable, given a particular seed/key. I presume it also produces reasonably uniform output for most seeds too. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has a pretty long cycle and enough randomness to be very useful and it *is* used. Yes. And it breaks, and we have a complainant. I thought the complaint was about rand, not random? If you think random() is not random enough for your purposes, go create a new function with a *new* name. Any supporters of this request? I'd support that. People who are using rand and random for crypto type randomness are deceiving themselves, as neither are portably suitable for that use. Lots of people are using rand, random and the rand48 suite for simulation or games, and this type of randomness has different requirements (as Bakul points out - repeatability being a useful one). I'd suggest we ammend the rand and random man pages saying that sequences produced from either cannot be expected to be suitable for cryptographic purposes, but are should be OK for simulation and games. (I guess a couple of numbers produced after calling srandomdev might be safe, but I wouldn't like to bet on them being that safe...) The man page can refer people on to arc4random, the apropriate OpenSSL pages, uuidgen and so on. As different consumers have different, sometimes contradictory, requirements for randomness it seems foolish to try to lump them all into one group of functions. David. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sunday 02 February 2003 6:48 pm, Bakul Shah wrote: Guys, please realize that random() is also used in generating simulation inputs (or timing or whatever). If you go change the underlying algorithm or its parameters one can't generate the same sequence from the same seed when repeating a test. Maybe I missed something, but why cannot you just rip random() from libc, rename it to bakul_shah_random() and use that in your testing code? Then you are safe from any changes to random(), and indeed have a portable RNG if your host OS changes. Regards, Edward. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
David Malone writes: On Sun, Feb 02, 2003 at 07:08:47PM +, Mark Murray wrote: RC4 is _utterly_ repeatable, given a particular seed/key. I presume it also produces reasonably uniform output for most seeds too. Yes. Modulo the requirement to burn a bit of output after a reseed. The old 16 bit rand() was broken enough that it didn't matter much (read: _I_ don't care) if its behavior got changed but random() has a pretty long cycle and enough randomness to be very useful and it *is* used. Yes. And it breaks, and we have a complainant. I thought the complaint was about rand, not random? Erm, yes. Similar difference though. PRNGs are _trouble_ unless designed properly. If you think random() is not random enough for your purposes, go create a new function with a *new* name. Any supporters of this request? I'd support that. People who are using rand and random for crypto type randomness are deceiving themselves, as neither are portably suitable for that use. Lots of people are using rand, random and the rand48 suite for simulation or games, and this type of randomness has different requirements (as Bakul points out - repeatability being a useful one). Repeatability is fine. Is convergence-to-constant OK? I'd suggest we ammend the rand and random man pages saying that sequences produced from either cannot be expected to be suitable for cryptographic purposes, but are should be OK for simulation and games. (I guess a couple of numbers produced after calling srandomdev might be safe, but I wouldn't like to bet on them being that safe...) I'm fine with this. The man page can refer people on to arc4random, the apropriate OpenSSL pages, uuidgen and so on. As different consumers have different, sometimes contradictory, requirements for randomness it seems foolish to try to lump them all into one group of functions. Yes. We should separately document (or at least clarify) the differences between cryptographic randomness and statistical randomness. We should also make sure that both are bug-free. Cast-in-stone algorithms are dumb, but if you really want those, its probably best to put them in your own code. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
RC4 is _utterly_ repeatable, given a particular seed/key. May be but it is not the same as the current random(). Also, I know you will want to change it the next time some one points out a problem with RC4. Yes. And it breaks, and we have a complainant. So create a new function! Or use a different function to generate or initialize the seed. I think one has to treat a behavior bug very carefully. If enough people are depending on it, it pretty much has to get enshrined as part of the spec -- sort of like the timeout arg to select(). The random() function in libc is documented to give the same pseudo-random output for a particular seed. if you link your program against a _different_ libc, you cannot expect your results to follow a particular number sequence. There is an expectation that on subsequent releases of the same OS things continue to work. Historically rand() and random() under unix have been used the most for simulation. [aside: Earl T. Cohen (the author of random(3)) also has had a lot to do in this area] Why not totally separate all uses of crypto related random number generator uses from the traditional simulation use? That way you can change crypto_random to your heart's content as the crypto needs change (as they will). -- bakul To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
I presume it also produces reasonably uniform output for most seeds too. Yes. Modulo the requirement to burn a bit of output after a reseed. I guess the crypto guys would have junked it otherwise ;-) I thought the complaint was about rand, not random? Erm, yes. Similar difference though. PRNGs are _trouble_ unless designed properly. I thought random was relatively carefully designed, though I don't know what the design goals were. I guess we should find out so we can do a fair comparison. I'd support that. People who are using rand and random for crypto type randomness are deceiving themselves, as neither are portably suitable for that use. Lots of people are using rand, random and the rand48 suite for simulation or games, and this type of randomness has different requirements (as Bakul points out - repeatability being a useful one). Repeatability is fine. Is convergence-to-constant OK? While we have no obligation to keep our implimantation constant accross between versions of libc, it may be a pain for users if we change the implimentation. We should just consider that before we decide to make a change. If it our change really is an improvement for most users, then it may be worth making anyway. [I presume you mean our rand* implimentation is slowly converging-to-constant code ;-] The man page can refer people on to arc4random, the apropriate OpenSSL pages, uuidgen and so on. As different consumers have different, sometimes contradictory, requirements for randomness it seems foolish to try to lump them all into one group of functions. Yes. We should separately document (or at least clarify) the differences between cryptographic randomness and statistical randomness. We should also make sure that both are bug-free. Good idea - though it might make a better paper than a man page! Cast-in-stone algorithms are dumb, but if you really want those, its probably best to put them in your own code. Indeed, that's what I've done when I really want portable repeatibility. Infact the old crappy rand() implimentation had some interesting interactions when used when one of the MSc students here used it to test some of the AES candidates. [It may be mentioned in that document that I sent you recently.] David. To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Maybe I missed something, but why cannot you just rip random() from libc, rename it to bakul_shah_random() and use that in your testing code? Then you are safe from any changes to random(), and indeed have a portable RNG if your host OS changes. Yes, *I* can do it but I don't work at every place they do simulation! If in the extreme you are suggesting that a portable application shouldn't rely on any OS features, you are of course right but that kind of makes mockery of any claims of compatibility. The point of compatibility is to not break interfaces unless there is a significant benefit. -- bakul To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sunday 02 February 2003 8:06 pm, Bakul Shah wrote: Maybe I missed something, but why cannot you just rip random() from libc, rename it to bakul_shah_random() and use that in your testing code? Then you are safe from any changes to random(), and indeed have a portable RNG if your host OS changes. Yes, *I* can do it but I don't work at every place they do simulation! If in the extreme you are suggesting that a portable application shouldn't rely on any OS features, No, that wasn't what I meant; yes, there are things should be able to rely on not changing between platforms, however ... The point of compatibility is to not break interfaces unless there is a significant benefit. ... I think there is more than one level of 'compatibility'; I for one would not expect random() to return the same results across platforms, certainly, or even between seperate releases of one platform, even though its API may be the same. For two reasons, mainly, the first that you know someone will change it somewhere anyway ;-), and second I think that's placing too much of a restriction on the OS. If FreeBSD makes random2() using RC4 to avoid changing rand() or random(), will people then start relying on random2()'s behaviour, and when someone finds a problem in RC4, then the next will be random3()? If you require x implementation of random(), then I don't think that it's so bad that you should be expected to provide it yourself, rather than assuming this is what the OS uses. But then maybe this comes down to difference of opinion. Would you have a problem with changes in the TCP/IP stack changing the content of packets sent out when you connect(), if it breaks your TCP/IP simulations? Regards, Edward. (PS: Even though it's rand(), not random() being changed, I think this issue applies to both..) To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah writes:
RC4 is _utterly_ repeatable, given a particular seed/key.
May be but it is not the same as the current random(). Also,
I know you will want to change it the next time some one
points out a problem with RC4.
Yes. This is called fixing bugs. We (OS maintainers) reserve that
right. If you need something more predictable, please maintain your
own code.
Yes. And it breaks, and we have a complainant.
So create a new function! Or use a different function to
generate or initialize the seed. I think one has to treat a
behavior bug very carefully. If enough people are depending
on it, it pretty much has to get enshrined as part of the
spec -- sort of like the timeout arg to select().
The documented behaviour is rand(3)/random(3). No guarantee
of lifelong repeatability is provided.
Would you prefer that we defined random() as
int
random(void)
{
static int retval = 0;
return retval++;
}
and worked on statistical randomness somewhere else?
The random() function in libc is documented to give the same
pseudo-random output for a particular seed. If you link your
program against a _different_ libc, you cannot expect your
results to follow a particular number sequence.
There is an expectation that on subsequent releases of the
same OS things continue to work.
Where is that expectation guaranteed?
Where is that expectation supported?
Historically rand() and random() under unix have been used
the most for simulation. [aside: Earl T. Cohen (the author
of random(3)) also has had a lot to do in this area]
Why not totally separate all uses of crypto related random
number generator uses from the traditional simulation use?
That way you can change crypto_random to your heart's content
as the crypto needs change (as they will).
The two are related topics.
Consider the (joking reference to) elephant-free biology. :-)
M
--
Mark Murray
iumop ap!sdn w,I idlaH
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah writes: Yes, *I* can do it but I don't work at every place they do simulation! If in the extreme you are suggesting that a portable application shouldn't rely on any OS features, you are of course right but that kind of makes mockery of any claims of compatibility. The point of compatibility is to not break interfaces unless there is a significant benefit. We are not proposing interface breaks. M -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 20:05:29 +, David Malone wrote: I presume it also produces reasonably uniform output for most seeds too. Yes. Modulo the requirement to burn a bit of output after a reseed. I guess the crypto guys would have junked it otherwise ;-) Notice that it will happens _each_ time for rand() due to rand_r() requirement 1) to output the same sequence as rand() and to 2) to store one word seed value each time. I.e. it will be reseed on each call. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
a restriction on the OS. If FreeBSD makes random2() using RC4 to avoid
changing rand() or random(), will people then start relying on random2()'s
behaviour, and when someone finds a problem in RC4, then the next will be
random3()?
What I am suggesting is to leave random() as it is and
guarantee its behavior won't change and add cryto_random() or
whatever, and indicate it *may* change.
Would you have a problem with changes in the TCP/IP stack changing the
content of packets sent out when you connect(), if it breaks your TCP/IP
simulations?
This is not a similar situation.
Note that it is rand() that is broken, not random() as can be
seen by modifying Kris Kennaways' test so I don't see why
Mark Murray was talking about changing it in the first place.
#include stdlib.h
#include stdio.h
int main() {
int i;
for(i = 1; i = 1000; i++) {
srandom(i);
printf(%d: %d\n, i, random());
}
}
1: 1804289383
2: 1505335290
3: 1205554746
4: 1968078301
5: 590011675
6: 290852541
7: 1045618677
8: 757547896
9: 54915
10: 1215069295
11: 1989311423
12: 1687063760
13: 1358590890
14: 2146406683
15: 762299093
16: 462648444
17: 1227918265
...
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:39:50 -0800, Bakul Shah wrote: Note that it is rand() that is broken, not random() as can be seen by modifying Kris Kennaways' test so I don't see why Mark Murray was talking about changing it in the first place. About correlation bug: it is srand() which is broken, not rand(). It is common practice for this type of PRNGs to throw out N values after seeding to remove correlation and srand() not follow this. My first patch fix this. -- Andrey A. Chernov http://ache.pp.ru/ To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:06:56PM -0800, Bakul Shah wrote: Maybe I missed something, but why cannot you just rip random() from libc, rename it to bakul_shah_random() and use that in your testing code? Then you are safe from any changes to random(), and indeed have a portable RNG if your host OS changes. Yes, *I* can do it but I don't work at every place they do simulation! If in the extreme you are suggesting that a portable application shouldn't rely on any OS features, you are of course right but that kind of makes mockery of any claims of compatibility. The point of compatibility is to not break interfaces unless there is a significant benefit. If your program depends on the exact algorithm used by random() (or rand() for that matter) to not change between OS updates (not to mention between different systems) then that is a bug in your program. The interface will not change just because a different algorithm is used. The exact sequence of random numbers produced is not a part of the interface but rather an implementation detail that portable programs should not depend on. It might also be worth noting that if a good PRNG is needed then one should not use random() or rand() since on some systems their output is not very random. -- Insert your favourite quote here. Erik Trulsson [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 11:55:25AM -0800, Bakul Shah wrote: RC4 is _utterly_ repeatable, given a particular seed/key. May be but it is not the same as the current random(). Also, I know you will want to change it the next time some one points out a problem with RC4. Since you keep talking about random(), I must conclude you're knee-jerking, since we're not discussing that function. Please stay on-topic :-) Kris msg51577/pgp0.pgp Description: PGP signature
Re: rand() is broken
Would you prefer that we defined random() as
int
random(void)
{
static int retval = 0;
return retval++;
}
No because that would be a change from the exisiting random()
behavior :-)
As I indicated in my earlier email random() is not broken,
srand() is (as corrected by Andrey Chernov) so you won't be
fixing any bugs by changing random(). If you guys had left
the original rand() alone we wouldn't be discussing any of
this
random(3) also provides an initstate() call which presumably
allows you to change the amount of randomnes. So here is
another suggestion: why not fold your algorithm change in
that function? For example,
initstate(seed, RC4, 3);
changes the algorithm to RC4. Yes, this is a change in the
interface but one I am sure most people can live with.
There is an expectation that on subsequent releases of the
same OS things continue to work.
Where is that expectation guaranteed?
Where is that expectation supported?
This expectation is a reasonable one. Most commerical OSes
do a good job of maintaining compatibility. IRIX certainly
did a pretty good job of it. FreeBSD also does a pretty good
job on the whole.
The two are related topics.
Yes, but not the same.
Consider the (joking reference to) elephant-free biology. :-)
The way things are going we will be there pretty soon :-(
To Unsubscribe: send mail to [EMAIL PROTECTED]
with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Since you keep talking about random(), I must conclude you're knee-jerking, since we're not discussing that function. Please stay on-topic :-) Read through the thread. In particular see Mark's message [EMAIL PROTECTED] where he says Good point. We can re-implement random() internally with arc4rand(). To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
Bakul Shah writes: Note that it is rand() that is broken, not random() as can be seen by modifying Kris Kennaways' test so I don't see why Mark Murray was talking about changing it in the first place. rand(3) says: STANDARDS The rand() and srand() functions conform to ISO/IEC 9899:1990 (``ISO C89''). rand(3) does not specify an exact algorithm (the man page does, but not the standard). random(3) has no such standardisation. Any code that assumes particular constants is _broken_[1]. If it has been recompiled or if it is dynamically linked against a shared library other than the one it was tested aginst, different results are a _feature_. M [1] no nitpicking on INT_MAX, please. -- Mark Murray iumop ap!sdn w,I idlaH To Unsubscribe: send mail to [EMAIL PROTECTED] with unsubscribe freebsd-current in the body of the message
Re: rand() is broken
On Sun, Feb 02, 2003 at 12:57:45PM -0800, Bakul Shah wrote: Since you keep talking about random(), I must conclude you're knee-jerking, since we're not discussing that function. Please stay on-topic :-) Read through the thread. In particular see Mark's message [EMAIL PROTECTED] where he says Good point. We can re-implement random() internally with arc4rand(). I assume he transposed and meant rand() internally with arc4random(). Kris msg51582/pgp0.pgp Description: PGP signature
