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

[Taylor R Campbell <campbell+netbsd-tech-crypto%mumble.net@localhost>]

> Date: Sun, 25 Jun 2017 15:21:54 +0700
> From: Robert Elz <kre%munnari.OZ.AU@localhost>
> 
> 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.)

Attached is a self-contained example (a) algorithm to use that
provides a strong security model like arc4random(3), (b) shrandom API
you could use inside the /bin/sh implementation, and (c) trivial test
program to demonstrate it.

% make shrandom
cc -O2   -o shrandom shrandom.c
% ./shrandom
deterministic
29234 32575 8779 20450
nondeterministic
855 17187 3659 9030

Should be pretty self-explanatory.  Let me know if you want to extend
it past potential 16-bit outputs, and if so, how far you want to
extend it (32-bit? 64-bit? whatever fits in memory? -- probably not a
good idea to allow setting RANDOM_BITS=100000000000 have the effect of
DoSing $RANDOM).

It is certainly not the fastest way to get this (a single ChaCha core
to get 15 bits of output is tremendous overkill), but it was fifteen
minutes to write from parts on hand and should be very easy to audit;
it's hard to imagine that shell $RANDOM will be a bottleneck; and it's
easy to increase the throughput (simply buffer outputs from ChaCha).

> 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.)

/dev/urandom is the correct choice here, or sysctl kern.arandom, but
you can just get 32 bytes from arc4random(3) instead with less code
and likely negligible cost.

/*-
 * Copyright (c) 2017 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Taylor R. Campbell.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/types.h>
#include <sys/endian.h>

#include <sha2.h>
#include <string.h>

/* explicit_memset -- not needed for >=netbsd7 */

void *(*volatile shrandom_explicit_memset_impl)(void *, int, size_t) = memset;
void *
shrandom_explicit_memset(void *buf, int c, size_t len)
{

	return (*shrandom_explicit_memset_impl)(buf, c, len);
}
#define	explicit_memset	shrandom_explicit_memset

/* ChaCha core */

#define	crypto_core_OUTPUTBYTES	64
#define	crypto_core_INPUTBYTES	16
#define	crypto_core_KEYBYTES	32
#define	crypto_core_CONSTBYTES	16

#define	crypto_core_ROUNDS	20

static uint32_t
rotate(uint32_t u, unsigned c)
{

	return (u << c) | (u >> (32 - c));
}

#define	QUARTERROUND(a, b, c, d) do {					      \
	(a) += (b); (d) ^= (a); (d) = rotate((d), 16);			      \
	(c) += (d); (b) ^= (c); (b) = rotate((b), 12);			      \
	(a) += (b); (d) ^= (a); (d) = rotate((d),  8);			      \
	(c) += (d); (b) ^= (c); (b) = rotate((b),  7);			      \
} while (/*CONSTCOND*/0)

const uint8_t crypto_core_constant32[16] = "expand 32-byte k";

static void
crypto_core(uint8_t *out, const uint8_t *in, const uint8_t *k,
    const uint8_t *c)
{
	uint32_t x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15;
	uint32_t j0,j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12,j13,j14,j15;
	int i;

	j0 = x0 = le32dec(c + 0);
	j1 = x1 = le32dec(c + 4);
	j2 = x2 = le32dec(c + 8);
	j3 = x3 = le32dec(c + 12);
	j4 = x4 = le32dec(k + 0);
	j5 = x5 = le32dec(k + 4);
	j6 = x6 = le32dec(k + 8);
	j7 = x7 = le32dec(k + 12);
	j8 = x8 = le32dec(k + 16);
	j9 = x9 = le32dec(k + 20);
	j10 = x10 = le32dec(k + 24);
	j11 = x11 = le32dec(k + 28);
	j12 = x12 = le32dec(in + 0);
	j13 = x13 = le32dec(in + 4);
	j14 = x14 = le32dec(in + 8);
	j15 = x15 = le32dec(in + 12);

	for (i = crypto_core_ROUNDS; i > 0; i -= 2) {
		QUARTERROUND( x0, x4, x8,x12);
		QUARTERROUND( x1, x5, x9,x13);
		QUARTERROUND( x2, x6,x10,x14);
		QUARTERROUND( x3, x7,x11,x15);
		QUARTERROUND( x0, x5,x10,x15);
		QUARTERROUND( x1, x6,x11,x12);
		QUARTERROUND( x2, x7, x8,x13);
		QUARTERROUND( x3, x4, x9,x14);
	}

	le32enc(out + 0, x0 + j0);
	le32enc(out + 4, x1 + j1);
	le32enc(out + 8, x2 + j2);
	le32enc(out + 12, x3 + j3);
	le32enc(out + 16, x4 + j4);
	le32enc(out + 20, x5 + j5);
	le32enc(out + 24, x6 + j6);
	le32enc(out + 28, x7 + j7);
	le32enc(out + 32, x8 + j8);
	le32enc(out + 36, x9 + j9);
	le32enc(out + 40, x10 + j10);
	le32enc(out + 44, x11 + j11);
	le32enc(out + 48, x12 + j12);
	le32enc(out + 52, x13 + j13);
	le32enc(out + 56, x14 + j14);
	le32enc(out + 60, x15 + j15);
}

/* ChaCha self-test */

/*
 * http://tools.ietf.org/html/draft-strombergson-chacha-test-vectors-00
 */

__CTASSERT(crypto_core_ROUNDS == 20);
static const uint8_t crypto_core_selftest_vector[64] = {
	0x76,0xb8,0xe0,0xad,0xa0,0xf1,0x3d,0x90,
	0x40,0x5d,0x6a,0xe5,0x53,0x86,0xbd,0x28,
	0xbd,0xd2,0x19,0xb8,0xa0,0x8d,0xed,0x1a,
	0xa8,0x36,0xef,0xcc,0x8b,0x77,0x0d,0xc7,
	0xda,0x41,0x59,0x7c,0x51,0x57,0x48,0x8d,
	0x77,0x24,0xe0,0x3f,0xb8,0xd8,0x4a,0x37,
	0x6a,0x43,0xb8,0xf4,0x15,0x18,0xa1,0x1c,
	0xc3,0x87,0xb6,0x69,0xb2,0xee,0x65,0x86,
};

static int
crypto_core_selftest(void)
{
	const uint8_t nonce[crypto_core_INPUTBYTES] = {0};
	const uint8_t key[crypto_core_KEYBYTES] = {0};
	uint8_t block[64];
	unsigned i;

	crypto_core(block, nonce, key, crypto_core_constant32);
	for (i = 0; i < 64; i++) {
		if (block[i] != crypto_core_selftest_vector[i])
			return -1;
	}

	return 0;
}

/* shrandom: 15-bit outputs for shell $RANDOM */

struct shrandom {
	uint8_t	shr_key[crypto_core_KEYBYTES];
};

int
shrandom_selftest(void)
{

	/* XXX exercise for reader: check known output on some fixed seed */
	return crypto_core_selftest();
}

void
shrandom_init(struct shrandom *shr, const void *seed, size_t len)
{
	SHA256_CTX sha256;

	__CTASSERT(crypto_core_KEYBYTES == 32);
	SHA256_Init(&sha256);
	SHA256_Update(&sha256, seed, len);
	SHA256_Final(shr->shr_key, &sha256);
}

uint16_t
shrandom_next(struct shrandom *shr)
{
	const uint8_t input[crypto_core_INPUTBYTES] = {0};
	uint8_t output[crypto_core_OUTPUTBYTES];
	uint16_t r;

	/* output := chacha(output, input, key, constant) */
	crypto_core(output, input, shr->shr_key, crypto_core_constant32);

	/* key := output[0..31] */
	__CTASSERT(crypto_core_KEYBYTES <= crypto_core_OUTPUTBYTES + 2);
	memcpy(shr->shr_key, output, crypto_core_KEYBYTES);

	/* r := output[32] + 2^16 output[33] */
	r = le16dec(output + crypto_core_KEYBYTES);

	/* erase key */
	explicit_memset(output, 0, sizeof output);

	return r & 0x7fff;
}

void
shrandom_fini(struct shrandom *shr)
{

	explicit_memset(shr, 0, sizeof(*shr));
}

/* Test program */

#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char **argv)
{
	uint8_t buf[32];
	struct shrandom shr;
	unsigned i;

	(void)argc;
	(void)argv;

	if (shrandom_selftest() != 0)
		abort();

	printf("deterministic\n");
	shrandom_init(&shr, "hello", 6);
	for (i = 0; i < 4; i++)
		printf("%hu%s", shrandom_next(&shr), i < 3? " " : "\n");
	shrandom_fini(&shr);

	printf("nondeterministic\n");
	arc4random_buf(&buf, sizeof buf);
	shrandom_init(&shr, buf, sizeof buf);
	for (i = 0; i < 4; i++)
		printf("%hu%s", shrandom_next(&shr), i < 3? " " : "\n");
	shrandom_fini(&shr);

	return 0;
}