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

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--aKWQFNBslk0RXsKqBPaLGF6tu84OQEtN2
Content-Type: multipart/mixed; boundary="NtutoPrklPauoofIgeIP1nMISX8cjMpE2";
 protected-headers="v1"
From: Kamil Rytarowski <[email protected]>
To: Robert Elz <[email protected]>, [email protected],
 [email protected]
Message-ID: <[email protected]>
Subject: Re: randomness (crypto?) code example wanted please?
References: <[email protected]>
In-Reply-To: <[email protected]>

--NtutoPrklPauoofIgeIP1nMISX8cjMpE2
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: quoted-printable

On 25.06.2017 10:21, Robert Elz wrote:
> Hi,
>=20
> 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.
>=20
> 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.)
>=20
> 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.=
)
>=20
> 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.
>=20
> Since this is for in-tree code I will not be copying, or using, anythin=
g
> GPL'd or similarly restricted.
>=20
> 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 she=
ll
> 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 w=
e like.)
>=20
> 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 ve=
rsion)
> 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, i=
f
> it has been assigned a value by the script, before being referenced,
> /dev/*random will not be used, unless later, RANDOM=3D'' is executed,
> and then $RANDOM referenced.)
>=20
> 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.
>=20
> Note: I will only be implementing one algorithm, not dozens with some
> way for the user to select!
>=20
> I have implemented the underlying mechanism in the shell to make all th=
is
> happen, but as you will see when I show some examples below, the curren=
t
> code will not pass anyone's idea of what is a random number...  (it wil=
l
> 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.]
>=20
> So, please help.
>=20
> But if your answer will be: "Just use rand(3) - it returns 15 bit value=
s"
> then don't bother sending it, thanks all the same.
>=20
> Alternatively, if your answer is "random(3) is good enough for this" th=
en
> 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, a=
nd
> 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?)
>=20
> In any case, if you plan on replying only to tech-crypto, please explic=
itly
> 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 n=
o
> harm done including my addr as well, duplicate messages do not bother m=
e.)
>=20
> Thanks,
>=20
> kre
>=20
> And now, here, from initial shell startup state, is a demo of the
> current implementation:
>=20
> $ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
> 1 2 3 4=20
> $ RANDOM=3D100
> $ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
> 101 102 103 104=20
> $ RANDOM=3D$(date +%s)
> $ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
> 25913 25914 25915 25916=20
> $ RANDOM=3D
> $ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
> 1 2 3 4=20
> $ RANDOM=3D32766
> $ for f in a b c d; do printf '%s ' ${RANDOM}; done; printf '\n'
> 32767 0 1 2=20
>=20
> I suspect you can all guess the current "randomness" algorithm!
>=20

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.


--NtutoPrklPauoofIgeIP1nMISX8cjMpE2--

--aKWQFNBslk0RXsKqBPaLGF6tu84OQEtN2
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCAAGBQJZT6QnAAoJEEuzCOmwLnZsRQoP/Ag/FB4jSd1WgVxXX6OYNKHA
PQ5bNrwO3UiC46o8phdQmhix8sI3neTbic4k6y+9C2vFLFBYvfnzCqGJnrri4+sT
2xiY18ojhqv2z1zfLonVXx5YewBm0Fe0fOtVMsWyE+ib0BoMsDVVDgKr67J7HyjK
fETbyYyNBR+pKO2DdcvVHZDorp7fvmD7wZwK7ZYfxLwIlL/zeAiCpvTPj1ryZ67L
vdPEq75iFEgCLfCXQUxXMaCBBLLkIWRlVgYjrYXNlAYTf1Tvtbv0eQ/21VBMCgTK
EO44IAL58J4VZPynuNcsreLkm2nFv+pkh7Z4dqWucwtXGZR37Ua5lB1B8+wMlv94
HIRqS0GIBSgFozLZslN92yItL3xbOiNbj6UPjhARUMsZvZkwrPn5hges/SMfNxE9
fjX0hTwzRasssVYyrddm9xMpfxKnUPV5gXXLqKfVBP3aLur5L1JSnEo0dyCSMsCI
tbna+yt4fUhgbON1yiJ1BMxcKh3IOcMXB+x0X+C+hucbrgHd2d6VLn0XJrPbR+H3
yGK2OP0o/X+/D9R1TM7zCO0vdPtjUDL2v2zmY1H2VE4kCZaONC9p/e2cg3wPa94f
Y/d8jNCcpH6SBNWxa+tP7WJ5hiv1VcHngQo91HE3hvHE03WoBi75GmQ/XkZol/wW
PUqbUhaGQ8X+WqAjnyik
=Upbz
-----END PGP SIGNATURE-----

--aKWQFNBslk0RXsKqBPaLGF6tu84OQEtN2--