tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: randomness (crypto?) code example wanted please?



On 25.06.2017 10:21, Robert Elz wrote:
> 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!
> 

There is a libc function for this kind of tasks: arc4random_uniform(3).

I was evaluation at some point whether this could be done differently,
with a dedicated userland random(1) program, that would be standalone
and independent from a shell. It could accept arguments of type of
randomness, ranges etc. Portable programs would use this external
utility. I would certainly depend on it in a case of a portable shell
scripts, on the other hand there is Perl/Python that would ship it
natively..

I was trying to generate these numbers in a shell with awk(1), but this
approach was imperfect.

Attachment: signature.asc
Description: OpenPGP digital signature



Home | Main Index | Thread Index | Old Index