randomness (crypto?) code example wanted please?

[Robert Elz <kre%munnari.OZ.AU@localhost>]

Hi,

I am (sometime not to far away) planning to add $RANDOM to
the NetBSD shell (for !SMALL shells so not for install media) - part
of keeping up with the Jones's, as just about every other shell has it,
even our /bin/ksh.

Its default will be to return random values 15 bite wide (0..32767)
just because that is what everyone else does (from ancient history)
but I will also add a mechanism to allow the user to select how
many bits to return (probably a "RANDOM_BITS" variable, which would
default to 15 if not set, unless someone has a better suggestion.)

What I am lacking at the minute is a method to produce good random
numbers (in the 15 bit, or any other, range), so I am seeking advice
(in the form of code fragments, either in the form of code in e-mail,
or a pointer to where in the NetBSD src tree I can find a good example.)

I'd prefer not references off into pkgsrc land, or even worse, www,
but if that's all that is possible...  What's more, this really needs
to use only what is available in libc to avoid requiring linking
against more libraries, and slowing sh startup time.

Since this is for in-tree code I will not be copying, or using, anything
GPL'd or similarly restricted.

The definition of RANDOM is that users can assign to it to set the
seed, so we need a method whereby if an integer of some arbitrary
number of bits is assigned by the user/script we can use that to
generate a repeatable sequence of "random" numbers.   (Remember the shell
works with char *'s so the "integer" here is just a string of digits,
it has no inherent max value, though we can limit what we use any way we like.)

I am planning to extend that so that if a null string is assigned to
RANDOM (which will be its initial value at sh start) then the seed
gets fetched from /dev/urandom (or /dev/random if someone can convince
me why that would be better.)   Suggestions on how many bits to read
from there in order to make whatever randomness algorithm you suggest
work well are also needed.   (As you will see below, sh (my internal version)
currently just sets the seed to 0 - but that is explicit in the current code,
not a side effect.)  (Note all this happens when $RANDOM is expanded, if
it has been assigned a value by the script, before being referenced,
/dev/*random will not be used, unless later, RANDOM='' is executed,
and then $RANDOM referenced.)

We can also look for a leading 0x (or some other indicator, like ',' or ':'
chars in the value) and interpret the seed value any way that is useful
in that case.

Note: I will only be implementing one algorithm, not dozens with some
way for the user to select!

I have implemented the underlying mechanism in the shell to make all this
happen, but as you will see when I show some examples below, the current
code will not pass anyone's idea of what is a random number...  (it will
never be released in this form).   [Ugh: that sounds grandiose - it is
just a few lines of code, took far less time than writing this message,
and is so simple it worked first time.]

So, please help.

But if your answer will be: "Just use rand(3) - it returns 15 bit values"
then don't bother sending it, thanks all the same.

Alternatively, if your answer is "random(3) is good enough for this" then
there is no need to send code (or pointers to code) - I know how to use
random(3) (I just haven't yet, as I suspect that would be wasted effort,
I have a feeling I will be told to use something better).   If this is
the answer however, please suggest how big the state table should be, and
whether, after shell startup, it ever needs to be reinitialised, and if
so when? (Whenever the seed is explicitly set?  Every hour?  Every 100 refs?)

In any case, if you plan on replying only to tech-crypto, please explicitly
cc me, I'm not on that list (if you also reply to tech-userlevel, then there
is no need to include me, I will see those replies, but there is also no
harm done including my addr as well, duplicate messages do not bother me.)

Thanks,

kre

And now, here, from initial shell startup state, is a demo of the
current implementation:

$ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
1 2 3 4 
$ RANDOM=100
$ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
101 102 103 104 
$ RANDOM=$(date +%s)
$ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
25913 25914 25915 25916 
$ RANDOM=
$ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
1 2 3 4 
$ RANDOM=32766
$ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
32767 0 1 2 

I suspect you can all guess the current "randomness" algorithm!