/*	$NetBSD$	*/

/*-
 * Copyright (c) 2019 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.
 */

/*
 * Entropy pool based on a sponge duplex.
 *
 *	- Samples are length-delimited with 8-bit length.
 *	- The most significant octet is reserved for padding, to
 *	  distinguish stirring samples from stirring outputs.
 *	- Output is not buffered: callers should draw 32 bytes and
 *	  expand with a stream cipher.
 *
 * On top of the underlying sponge state, an entropy pool maintains an
 * integer i in [0, RATE-1] indicating where to write the next byte in
 * the input buffer.  Zeroing an entropy pool initializes it.
 */

#ifdef _KERNEL
#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD$");
#endif

#include "entpool.h"

#ifdef _KERNEL
#include <sys/types.h>
#include <lib/libkern/libkern.h>
#define	ASSERT		KASSERT
#else
#include <sys/cdefs.h>
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#define	ASSERT		assert
#define	CTASSERT	__CTASSERT
#endif

#define	secret	/* must not use in variable-time operations; should zero */
#define	arraycount(A)	(sizeof(A)/sizeof((A)[0]))
#define	MIN(X,Y)	((X) < (Y) ? (X) : (Y))

#define	RATE		ENTPOOL_RATE

/*
 * stir(P)
 *
 *	Internal subroutine to apply the sponge permutation to the
 *	state in P.  Resets P->i to 0 to indicate that the input buffer
 *	is empty.
 */
static void
stir(struct entpool *P)
{
	size_t i;

	/*
	 * Switch to the permutation's byte order, if necessary, apply
	 * permutation, and then switch back.  This way we can data in
	 * and out byte by byte, but get the same answers out of test
	 * vectors.
	 */
	for (i = 0; i < arraycount(P->s.w); i++)
		P->s.w[i] = ENTPOOL_WTOH(P->s.w[i]);
	ENTPOOL_PERMUTE(P->s.w);
	for (i = 0; i < arraycount(P->s.w); i++)
		P->s.w[i] = ENTPOOL_HTOW(P->s.w[i]);

	/* Reset the input buffer.  */
	P->i = 0;
}

/*
 * entpool_enter(P, buf, len)
 *
 *	Enter len bytes from buf into the entropy pool P, stirring as
 *	needed.
 */
void
entpool_enter(struct entpool *P, const void *buf, size_t len)
{
	const uint8_t *p = buf;
	size_t n = len;

	/* Length is encoded in 8 bits, so samples are at most 255 bytes.  */
	ASSERT(len <= ENTPOOL_MAXENTER);
	CTASSERT(ENTPOOL_MAXENTER == 255);

	/* Sanity-check P->i.  */
	ASSERT(P->i <= RATE-1);

	/* If the input buffer is full, stir.  */
	if (P->i == RATE-1)
		stir(P);
	ASSERT(P->i < RATE-1);

	/*
	 * Enter the sample with 1-byte length delimiter, stirring as
	 * needed.
	 */
	P->s.u8[P->i++] ^= len;
	while (n --> 0) {
		if (P->i == RATE-1)
			stir(P);
		ASSERT(P->i < RATE-1);
		P->s.u8[P->i++] ^= *p++;
	}

	/* If we filled the input buffer exactly, stir once more.  */
	if (P->i == RATE-1)
		stir(P);
	ASSERT(P->i < RATE-1);
}

/*
 * entpool_enter_nostir(P, buf, len)
 *
 *	Enter as many bytes as possible, up to len, from buf into the
 *	entropy pool P.
 *
 *	Return true if the sample was consumed in its entirety, or true
 *	if the sample was truncated so the caller should arrange to
 *	call entpool_stir when it is next convenient to do so.
 */
bool
entpool_enter_nostir(struct entpool *P, const void *buf, size_t len)
{
	const uint8_t *p = buf;
	size_t n0, n;

	/* Can't enter more than a 1-block sample, with length byte.  */
	ASSERT(len <= ENTPOOL_MAXENTER_NOSTIR);
	CTASSERT(ENTPOOL_MAXENTER_NOSTIR == MIN(255, RATE-1 - 1));

	/* Sanity-check P->i.  */
	ASSERT(P->i <= RATE-1);

	/* If the input buffer is full, fail.  */
	if (P->i == RATE-1)
		return false;
	ASSERT(P->i < RATE-1);

	/* Truncate the sample and enter it with 1-byte length encoding.  */
	n = n0 = MIN(len, RATE-1 - P->i - 1);
	P->s.u8[P->i++] ^= n;
	while (n --> 0)
		P->s.u8[P->i++] ^= *p++;

	/* Can't guarantee anything better than 0 <= i <= RATE-1.  */
	ASSERT(P->i <= RATE-1);

	/* Return true if all done, false if truncated and in need of stir.  */
	return (n0 == len);
}

/*
 * entpool_stir(P)
 *
 *	Stir the entropy pool after entpool_enter_nostir fails.
 */
void
entpool_stir(struct entpool *P)
{

	/* Sanity-check P->i.  */
	ASSERT(P->i <= RATE-1);

	/* If the input buffer is full, stir.  */
	if (P->i == RATE-1)
		stir(P);
	ASSERT(P->i < RATE-1);
}

/*
 * entpool_extract(P, buf, len)
 *
 *	Extract len bytes from the entropy pool P into buf.
 */
void
entpool_extract(struct entpool *P, secret void *buf, size_t len)
{
	uint8_t *p = buf;
	size_t n = len;

	/* Keep the output length reasonably bounded.  */
	ASSERT(len <= ENTPOOL_MAXEXTRACT);

	/* Sanity-check P->i.  */
	ASSERT(P->i <= RATE-1);

	/* If input buffer is not empty, stir.  */
	if (P->i != 0)
		stir(P);
	ASSERT(P->i == 0);

	/*
	 * Copy out and zero (RATE-1)-sized chunks at a time, stirring
	 * with a bit set to distinguish this from inputs.
	 */
	while (n > RATE-1) {
		memcpy(p, P->s.u8, RATE-1);
		memset(P->s.u8, 0, RATE-1);
		P->s.u8[RATE-1] ^= 0x80;
		stir(P);
		p += RATE-1;
		n -= RATE-1;
	}

	/*
	 * If there's anything left, copy out a partial rate's worth
	 * and zero the entire rate's worth, stirring with a bit set to
	 * distinguish this from inputs.
	 */
	if (n) {
		ASSERT(n <= RATE-1);
		memcpy(p, P->s.u8, n);
		memset(P->s.u8, 0, RATE-1);
		P->s.u8[RATE-1] ^= 0x80;
		stir(P);
	}
}

#if ENTPOOL_SMALL

#define	KATLEN	15

/* Gimli */
static const uint8_t known_answers[][KATLEN] = {
	[0] = {
		0xf3,0x8a,0xa8,0x58,0x2a,0xc2,0x90,0x73,
		0x7c,0x8f,0x28,0x1e,0xd9,0x07,0x6a,
	},
	[1] = {
		0x68,0x8c,0x47,0xa7,0xa1,0x65,0xe8,0xdd,
		0xf9,0x15,0x63,0x57,0xa2,0x1e,0x0d,
	},
	[2] = {
		0x09,0x53,0x9b,0xc9,0x0b,0x67,0x0a,0x70,
		0xda,0x62,0x8f,0xda,0x1c,0xde,0x78,
	},
	[3] = {
		0x09,0x53,0x9b,0xc9,0x0b,0x67,0x0a,0x70,
		0xda,0x62,0x8f,0xda,0x1c,0xde,0x78,
	},
	[4] = {
		0xf3,0x8a,0xa8,0x58,0x2a,0xc2,0x90,0x73,
		0x7c,0x8f,0x28,0x1e,0xd9,0x07,0x6a,
	},
	[5] = {
		0xaa,0xa8,0x00,0xf0,0xf7,0x50,0x8c,0xa8,
		0xef,0x2b,0xd2,0x80,0xee,0xd1,0xa2,
	},
	[6] = {
		0xab,0x30,0x8a,0xb5,0x3c,0xb0,0x69,0x3f,
		0x30,0xd8,0xfd,0x34,0x39,0x27,0x15,
	},
	[7] = {
		0x09,0x53,0x9b,0xc9,0x0b,0x67,0x0a,0x70,
		0xda,0x62,0x8f,0xda,0x1c,0xde,0x78,
	},
	[8] = {
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,
	},
	[9] = {
		0xf3,0x8a,0xa8,0x58,0x2a,0xc2,0x90,0x73,
		0x7c,0x8f,0x28,0x1e,0xd9,0x07,0x6a,
	},
	[10] = {
		0xab,0x30,0x8a,0xb5,0x3c,0xb0,0x69,0x3f,
		0x30,0xd8,0xfd,0x34,0x39,0x27,0x15,
	},
	[11] = {
		0x4f,0xfd,0x99,0x18,0x4e,0x8d,0x7d,0xcb,
		0x2f,0x24,0x3a,0xe3,0xdb,0xb8,0x15,
	},
	[12] = {
		0xcc,0x4f,0x3f,0x7a,0x22,0xd8,0xdd,0xf3,
		0x21,0xf3,0x9d,0x88,0xe7,0xb7,0xe1,
	},
};

#else  /* !ENTPOOL_SMALL */

#define	KATLEN	16

/* Keccak-p[1600, 24] */
static const uint8_t known_answers[][KATLEN] = {
	[0] = {
		0x48,0xe0,0x3c,0x48,0x1f,0x6e,0xc5,0x8c,
		0x86,0x1f,0x0d,0x76,0x73,0x9e,0xbf,0x27,
	},
	[1] = {
		0x5f,0x58,0x57,0xde,0xd1,0x69,0x39,0x70,
		0x83,0xa5,0x2d,0x41,0x71,0xc3,0x53,0xdf,
	},
	[2] = {
		0x05,0x80,0x05,0x8f,0x0f,0x8d,0xb4,0x35,
		0xa3,0x9f,0x82,0x9f,0x31,0x6b,0x0e,0xca,
	},
	[3] = {
		0x05,0x80,0x05,0x8f,0x0f,0x8d,0xb4,0x35,
		0xa3,0x9f,0x82,0x9f,0x31,0x6b,0x0e,0xca,
	},
	[4] = {
		0x48,0xe0,0x3c,0x48,0x1f,0x6e,0xc5,0x8c,
		0x86,0x1f,0x0d,0x76,0x73,0x9e,0xbf,0x27,
	},
	[5] = {
		0x14,0x45,0xe1,0x6d,0x05,0x38,0xd4,0x55,
		0x6c,0xbc,0x69,0x8c,0xaf,0xd2,0xa6,0xd3,
	},
	[6] = {
		0xac,0xb6,0x0b,0x91,0xff,0xa7,0x5e,0x9b,
		0xb0,0xbf,0xc1,0xa0,0xf0,0xaa,0xdf,0xb7,
	},
	[7] = {
		0x05,0x80,0x05,0x8f,0x0f,0x8d,0xb4,0x35,
		0xa3,0x9f,0x82,0x9f,0x31,0x6b,0x0e,0xca,
	},
	[8] = {
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
		0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
	},
	[9] = {
		0x48,0xe0,0x3c,0x48,0x1f,0x6e,0xc5,0x8c,
		0x86,0x1f,0x0d,0x76,0x73,0x9e,0xbf,0x27,
	},
	[10] = {
		0xac,0xb6,0x0b,0x91,0xff,0xa7,0x5e,0x9b,
		0xb0,0xbf,0xc1,0xa0,0xf0,0xaa,0xdf,0xb7,
	},
	[11] = {
		0xd2,0x2f,0x9a,0x00,0xbe,0xd2,0x7f,0xb2,
		0xdf,0x7a,0xcd,0xec,0x53,0xc5,0xf4,0x9c,
	},
	[12] = {
		0x8d,0x9a,0x61,0x76,0x65,0xc1,0xcc,0xf0,
		0xb9,0x98,0x39,0x31,0x62,0x40,0xf1,0x42,
	},
};

#endif

#define	KAT_BEGIN(P)	memset(P, 0, sizeof(*(P)))
#define	KAT_END(P, n)	do						      \
{									      \
	uint8_t actual[KATLEN];						      \
									      \
	entpool_extract(P, actual, KATLEN);				      \
	if (memcmp(actual, known_answers[n], KATLEN))			      \
		return -1;						      \
} while (0)

int
entpool_selftest(void)
{
	struct entpool pool, *P = &pool;
	uint8_t sample[1] = {0xff};
	uint8_t scratch[ENTPOOL_MAXEXTRACT];
	const uint8_t zero[ENTPOOL_MAXENTER] = {0};

	CTASSERT(ENTPOOL_MAXENTER <= 255);
	CTASSERT(KATLEN <= ENTPOOL_MAXEXTRACT);

	/* Test entpool_enter with empty buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 0);

	/* Test entpool_enter with partial buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_enter(P, zero, RATE-3);
	entpool_stir(P);	/* noop */
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 1);

	/* Test entpool_enter with full buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, zero, RATE-2))
		return -1;
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 2);

	/* Test entpool_enter with full buffer after stir.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, zero, RATE-2))
		return -1;
	entpool_stir(P);
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 3);

	/* Test entpool_enter_nostir with empty buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, sample, 1))
		return -1;
	entpool_stir(P);	/* noop */
	KAT_END(P, 4);

	/* Test entpool_enter_nostir with partial buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_enter(P, zero, RATE-3);
	entpool_stir(P);	/* noop */
	if (entpool_enter_nostir(P, sample, 1))
		return -1;
	entpool_stir(P);
	KAT_END(P, 5);

	/* Test entpool_enter_nostir with full buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, zero, RATE-2))
		return -1;
	if (entpool_enter_nostir(P, sample, 1))
		return -1;
	entpool_stir(P);
	KAT_END(P, 6);

	/* Test entpool_enter_nostir with full buffer after stir.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, zero, RATE-2))
		return -1;
	entpool_stir(P);
	if (!entpool_enter_nostir(P, sample, 1))
		return -1;
	entpool_stir(P);	/* noop */
	KAT_END(P, 7);

	/* Test entpool_extract with empty input buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	KAT_END(P, 8);

	/* Test entpool_extract with nonempty input buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 9);

	/* Test entpool_extract with full input buffer.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	if (!entpool_enter_nostir(P, zero, RATE-2))
		return -1;
	KAT_END(P, 10);

	/* Test entpool_extract with iterated output.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_extract(P, scratch, RATE-1 + 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 11);

	/* Test extract, enter, extract.  */
	KAT_BEGIN(P);
	entpool_stir(P);	/* noop */
	entpool_extract(P, scratch, 1);
	entpool_stir(P);	/* noop */
	entpool_enter(P, sample, 1);
	entpool_stir(P);	/* noop */
	KAT_END(P, 12);

	return 0;
}

#if ENTPOOL_GENKAT

#include <stdio.h>

struct event {
	enum { IN, OUT, STOP } t;
	uint8_t b[RATE-1];
};

/* Cases correspond to entpool_selftest above.  */
static const struct event *const cases[] = {
	[0] = (const struct event[]) {
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[1] = (const struct event[]) {
		{IN, {RATE-3, [RATE-2] = 1}},
		{IN, {0xff}},
		{STOP, {0}},
	},
	[2] = (const struct event[]) {
		{IN, {RATE-2}},
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[3] = (const struct event[]) {
		{IN, {RATE-2}},
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[4] = (const struct event[]) {
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[5] = (const struct event[]) {
		{IN, {RATE-3, [RATE-2] = 0 /* truncated length */}},
		{STOP, {0}},
	},
	[6] = (const struct event[]) {
		{IN, {RATE-2}},
		{STOP, {0}},
	},
	[7] = (const struct event[]) {
		{IN, {RATE-2}},
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[8] = (const struct event[]) {
		{STOP, {0}},
	},
	[9] = (const struct event[]) {
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
	[10] = (const struct event[]) {
		{IN, {RATE-2}},
		{STOP, {0}},
	},
	[11] = (const struct event[]) {
		{OUT, {0}},
		{OUT, {0}},
		{STOP, {0}},
	},
	[12] = (const struct event[]) {
		{OUT, {0}},
		{IN, {1, 0xff}},
		{STOP, {0}},
	},
};

static void
compute(uint8_t output[KATLEN], const struct event *events)
{
	union {
		uint8_t b[ENTPOOL_SIZE];
		ENTPOOL_WORD w[ENTPOOL_SIZE/sizeof(ENTPOOL_WORD)];
	} u;
	unsigned i, j, k;

	memset(&u.b, 0, sizeof u.b);
	for (i = 0;; i++) {
		if (events[i].t == STOP)
			break;
		for (j = 0; j < sizeof(events[i].b); j++)
			u.b[j] ^= events[i].b[j];
		if (events[i].t == OUT) {
			memset(u.b, 0, RATE-1);
			u.b[RATE-1] ^= 0x80;
		}

		for (k = 0; k < arraycount(u.w); k++)
			u.w[k] = ENTPOOL_WTOH(u.w[k]);
		ENTPOOL_PERMUTE(u.w);
		for (k = 0; k < arraycount(u.w); k++)
			u.w[k] = ENTPOOL_HTOW(u.w[k]);
	}

	for (j = 0; j < KATLEN; j++)
		output[j] = u.b[j];
}

int
main(void)
{
	uint8_t output[KATLEN];
	unsigned i, j;

	printf("static const uint8_t known_answers[][KATLEN] = {\n");
	for (i = 0; i < arraycount(cases); i++) {
		printf("\t[%u] = {\n", i);
		compute(output, cases[i]);
		for (j = 0; j < KATLEN; j++) {
			if (j % 8 == 0)
				printf("\t\t");
			printf("0x%02hhx,", output[j]);
			if (j % 8 == 7)
				printf("\n");
		}
		printf("\t},\n");
	}
	printf("};\n");

	fflush(stdout);
	return ferror(stdout);
}

#endif