problems with RANDOM in subshells

problems with RANDOM in subshells

[Clint Adams]

One can work around the problem described below by doing

: $RANDOM ; (echo $RANDOM) | cat

Should the random-seeding behavior be changed for subshells?

----- Forwarded message from Falk Hueffner <falk@debian.org> -----

For each subshell, $RANDOM gets initialized to the same value, which
leads to the same sequence of random numbers.  This makes
e. g. playlist shuffling functions way boring, and is generally not
what one would expect.

falk@borkum:~% (echo $RANDOM) | cat
12042
falk@borkum:~% (echo $RANDOM) | cat
12042
falk@borkum:~% (echo $RANDOM) | cat
12042

	Falk

-- System Information
Debian Release: 3.0
Architecture: alpha
Kernel: Linux borkum 2.4.16 #1 Sat Dec 1 23:02:59 CET 2001 alpha
Locale: LANG=C, LC_CTYPE=de_DE

Versions of packages zsh depends on:
ii  libc6.1                  2.2.4-7         GNU C Library: Shared libraries an
ii  libcap1                  1:1.10-12       support for getting/setting POSIX.
ii  libncurses5              5.2.20020112a-2 Shared libraries for terminal hand


----- End forwarded message -----

Re: problems with RANDOM in subshells

[Zefram]

Clint Adams wrote:
>Should the random-seeding behavior be changed for subshells?

No.  We define $RANDOM to be a PRNG; zshparam(1) speaks of seeding it
(by writing to $RANDOM).  Opening a subshell should not interfere with
the PRNG sequence, which one might be relying on to be reproducible.
That is, we should maintain this useful behaviour:

	% RANDOM=1234; echo $RANDOM; echo $RANDOM
	8718
	31363
	% RANDOM=1234; echo $RANDOM; (echo $RANDOM)
	8718
	31363
	% RANDOM=1234; (echo $RANDOM; echo $RANDOM)
	8718
	31363
	% (RANDOM=1234; echo $RANDOM; echo $RANDOM)
	8718
	31363

Where one requires unpredictability rather than reproducibility, it is
well known (see Knoth vol. 2, et al) that one must take extra steps.
For example, in an application that forks off subshells and needs a new
random number in each subshell, one must at minimum step the PRNG between
subshells.  (Either each subshell uses the next random number generated
by the main program, or each runs the PRNG itself, duplicating a random
number that the main program generates and throws away.)  To get wildly
different random *sequences* in each subshell, rather than just a single
random number, one can kink the PRNG sequence by doing "RANDOM=$RANDOM"
between subshells.

(In my interactive zsh setup, I step the PRNG with ": $RANDOM" in precmd.
This largely solves the problem for interactive use of $RANDOM --
subshells started at different prompts get different (albeit overlapping)
$RANDOM sequences.)

For zsh-workers:

It may be useful to add, separately from the PRNG, an entropy collection
module.  This would generate moderate-quality *unpredictable* numbers
on demand; unlike the $RANDOM PRNG its output would be irreproducible.
The shell is probably a good place to put an entropy collector; on systems
like Linux that have /dev/random we can just use the kernel device,
but on other systems the shell is still in a position to see a lot of
unpredictable timing data, so we can make randomness reliably available
to shell scripts on all Unices.  (Does Perl have such a module yet?)

-zefram

Re: problems with RANDOM in subshells

[Bart Schaefer]

On Jan 31,  3:46am, Zefram wrote:
} Subject: Re: problems with RANDOM in subshells
}
} The shell is probably a good place to put an entropy collector; on systems
} like Linux that have /dev/random we can just use the kernel device,
} but on other systems the shell is still in a position to see a lot of
} unpredictable timing data, so we can make randomness reliably available
} to shell scripts on all Unices.  (Does Perl have such a module yet?)

According to search.cpan.org:

Statistics-MaxEntropy-0.9 by Hugo WL ter Doest Released 26th November 1998


-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Zsh: http://www.zsh.org | PHPerl Project: http://phperl.sourceforge.net   

Re: problems with RANDOM in subshells

[Bart Schaefer]

On Jan 31,  4:03am, Bart Schaefer wrote:
}
} According to search.cpan.org:
} 
} Statistics-MaxEntropy-0.9 by Hugo WL ter Doest Released 26th November 1998

Sorry, that turns out not to be what I at first thought.

Crypt::Random looks like a better choice, or Math-TrulyRandom-1.0.

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Zsh: http://www.zsh.org | PHPerl Project: http://phperl.sourceforge.net   

Re: problems with RANDOM in subshells

[Peter Stephenson]

Zefram wrote:
> Clint Adams wrote:
> >Should the random-seeding behavior be changed for subshells?
> 
> No.  We define $RANDOM to be a PRNG; zshparam(1) speaks of seeding it
> (by writing to $RANDOM).  Opening a subshell should not interfere with
> the PRNG sequence, which one might be relying on to be reproducible.

bash has the zsh behaviour, but ksh 88 handles subshells specially.
POSIX/SUS doesn't defined RANDOM, but we probably ought to get this
specified for David Korn's enhanced shell proposal, given that all three
shells under discussion already have RANDOM.

It does seem to me that it's unnecessarily hard for a user to take avoiding
action in a subshell.  At least providing the PID of the subshell process
as separate parameter might give them the start, e.g. make $ZSH_REALPID map
directly to getpid() --- obviously not with a very high degree of
randomness, but I don't think that was a problem in this case.  (The
advantage over providing a real `random' number is that it takes a minute
to write instead of a day.)

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR Ltd., Science Park, Milton Road,
Cambridge, CB4 0WH, UK                          Tel: +44 (0)1223 392070


**********************************************************************
The information transmitted is intended only for the person or
entity to which it is addressed and may contain confidential 
and/or privileged material. 
Any review, retransmission, dissemination or other use of, or
taking of any action in reliance upon, this information by 
persons or entities other than the intended recipient is 
prohibited.  
If you received this in error, please contact the sender and 
delete the material from any computer.
**********************************************************************

Re: problems with RANDOM in subshells

[Peter Stephenson]

[-- Attachment #1: Type: text/plain, Size: 1582 bytes --]

Guess what?  Forgot to change the `To:' line again.

"Bart Schaefer" wrote:
> On Jan 31,  4:03am, Bart Schaefer wrote:
> }
> } According to search.cpan.org:
> } 
> } Statistics-MaxEntropy-0.9 by Hugo WL ter Doest Released 26th November 1998
> 
> Sorry, that turns out not to be what I at first thought.
> 
> Crypt::Random looks like a better choice, or Math-TrulyRandom-1.0.

Crypt::Random simply uses /dev/random.  However, Math-TrulyRandom is based
on a short C program which has a nice, simple copyright, so we could simply
include it.  It may need some work porting to other UNIX variants.

There's no encryption involved, so I don't think the warning about export
controls is applicable.  On the other hand, we don't have a built-in MD5 or
DES to run on it.  The nearest we have is the hashing function.

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR Ltd., Science Park, Milton Road,
Cambridge, CB4 0WH, UK                          Tel: +44 (0)1223 392070


**********************************************************************
The information transmitted is intended only for the person or
entity to which it is addressed and may contain confidential 
and/or privileged material. 
Any review, retransmission, dissemination or other use of, or
taking of any action in reliance upon, this information by 
persons or entities other than the intended recipient is 
prohibited.  
If you received this in error, please contact the sender and 
delete the material from any computer.
**********************************************************************

[-- Attachment #2: RNG C code --]
[-- Type: text/plain, Size: 2905 bytes --]

/*
 *	Physically random numbers (very nearly uniform)
 *	D. P. Mitchell
 *	Modified by Matt Blaze 2/95
 */
/*
 * The authors of this software are Don Mitchell and Matt Blaze.
 *              Copyright (c) 1995 by AT&T.
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * This software may be subject to United States export controls.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

/*
 * WARNING: depending on the particular platform, truerand() output may
 * be biased or correlated.  In general, you can expect about 16 bits of
 * "pseudo-entropy" out of each 32 bit word returned by truerand(),
 * but it may not be uniformly diffused.  You should therefore run
 * the output through some post-whitening function (like MD5 or DES or
 * whatever) before using it to generate key material.  (RSAREF's
 * random package does this for you when you feed truerand() bits to the
 * seed input function.)
 *
 * Test these assumptions on your own platform before fielding a system
 * based on this software or these techniques.
 *
 * This software seems to work well (at 16 bits per truerand() call) on
 * a Sun Sparc-20 under SunOS 4.1.3 and on a P100 under BSDI 2.0.  You're
 * on your own elsewhere.
 */

#include <signal.h>
#include <setjmp.h>
#include <sys/time.h>
#include <math.h>
#include <stdio.h>

#include "truerand.h"

static jmp_buf env;
static unsigned count;
static unsigned ocount;
static unsigned buffer;

static int
tick()
{
	struct itimerval it, oit;

	timerclear(&it.it_interval);
	it.it_value.tv_sec = 0;
	it.it_value.tv_usec = 16665;
	if (setitimer(ITIMER_REAL, &it, &oit) < 0)
		perror("tick");
}

static void
interrupt()
{
	if (count)
		longjmp(env, 1);
	(void) signal(SIGALRM, interrupt);
	tick();
}

static unsigned long
roulette()
{

	if (setjmp(env)) {
		count ^= (count>>3) ^ (count>>6) ^ ocount;
		count &= 0x7;
		ocount=count;
		buffer = (buffer<<3) ^ count;
		return buffer;
	}
	(void) signal(SIGALRM, interrupt);
	count = 0;
	tick();
	for (;;)
		count++;	/* about 1 MHz on VAX 11/780 */
}

unsigned long
truerand()
{

	count=0;
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	(void) roulette();
	return roulette();
}

int
n_truerand(n)
int n;
{
	int slop, v;

	slop = 0x7FFFFFFF % n;
	do {
		v = truerand() >> 1;
	} while (v <= slop);
	return v % n;
}