packages feed

crypton-2.3.0: cbits/crypton_sysdrg.c

/*
 * The generator behind MonadRandom IO.
 *
 * A ChaCha20 DRBG per operating system thread, seeded straight from the
 * system: getrandom(2) or getentropy(3).  There is no process-wide generator
 * in between (#350); glibc, Go, BoringSSL and Rust's ThreadRng do without one
 * too, and it saved one system call per thread per mebibyte.
 *
 * Per operating system thread and not per Haskell thread: a forkIO thread
 * moves between capabilities, so state kept against it would be shared by
 * threads running at the same time.  That is why the state is here and
 * reached through pthread_getspecific rather than held in Haskell.
 *
 * Two modes (#352).  Per draw, the default, keeps no state: every draw takes
 * a fresh key from the system and expands it, so a copy of the process
 * restored from a saved image -- a VM snapshot, a CRIU checkpoint -- has
 * nothing of its own to repeat.  Per thread keeps the generator described
 * above, which is faster, and reseeds it when
 *
 *   - the thread has produced CRYPTON_THREAD_RESEED bytes,
 *   - the reseed interval has passed since the last seed,
 *   - realtime has moved against the monotonic clock since then
 *     (with an interval of 0, neither clock check is made),
 *   - the process has forked,
 *   - the program has called crypton_sysdrg_reseed.
 *
 * A child inherits its parent's state, and so does every copy of a restored
 * image.  A fork and crypton_sysdrg_reseed bump the generation counter
 * below, and every generator compares against it before it answers.  A
 * restore keeps the monotonic clock running on from the image, so the
 * interval does not see one: CRIU puts the process in a time namespace and
 * a hypervisor rewinds the guest's counter.  Under CRIU realtime jumps by
 * the time the image was away, which the clock check catches on the first
 * draw.  A restored VM moves neither clock until NTP steps it, and nothing
 * here sees it: per draw, or crypton_sysdrg_reseed, is the answer there.
 */

#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "crypton_chacha.h"
#include "crypton_sha512.h"

#ifdef _WIN32
#include <windows.h>
#else
#include <pthread.h>
#include <unistd.h>
#endif

/* from crypton_sysrandom.c */
int crypton_sysrandom_available(void);
int crypton_sysrandom_bytes(uint8_t *buf, int len);

#define CHACHA_ROUNDS      20
#define SEED_KEY           32
#define SEED_IV             8
#define SEED_LEN           (SEED_KEY + SEED_IV)

#define CRYPTON_THREAD_RESEED  (1u << 20)

#define MODE_PER_DRAW      0
#define MODE_PER_THREAD    1
#define DEFAULT_INTERVAL_MS 10
/* How far realtime may move against the monotonic clock before it counts
 * as a restore: well above an NTP slew between reseeds, well below any
 * time an image spends away. */
#define OFFSET_SLACK_MS     1000

typedef struct {
	crypton_chacha_context ctx;
	uint64_t used;
	uint64_t seeded_at;
	int64_t offset_at;
	size_t generation;
	int seeded;
} drg_t;

/* Set from any thread at any time, so atomic, and 32 bits so that no
 * platform needs libatomic for it.  The interval is in milliseconds; 0
 * turns the time limit off. */
static int sysdrg_mode = MODE_PER_DRAW;
static uint32_t reseed_interval_ms = DEFAULT_INTERVAL_MS;
#define MODE() __atomic_load_n(&sysdrg_mode, __ATOMIC_RELAXED)
#define INTERVAL_MS() __atomic_load_n(&reseed_interval_ms, __ATOMIC_RELAXED)

/* Read by every draw, and bumped from any thread or a signal handler by
 * crypton_sysdrg_reseed, so it is atomic and takes no lock.  size_t is 64
 * bits wherever that needs no libatomic, so it does not wrap back. */
static size_t generation_count = 0;
#define GENERATION() __atomic_load_n(&generation_count, __ATOMIC_ACQUIRE)

#ifdef _WIN32
/* Fls and not Tls: TlsAlloc has no destructor, so the state of every thread
 * that ever drew a byte would be left allocated and unscrubbed when the
 * thread ended.  FlsAlloc takes the callback that pthread_key_create does. */
static DWORD thread_slot;
static INIT_ONCE init_once = INIT_ONCE_STATIC_INIT;
#else
static pthread_key_t thread_slot;
static pthread_once_t init_once = PTHREAD_ONCE_INIT;
#endif

static void scrub(void *p, size_t n)
{
	volatile uint8_t *q = (volatile uint8_t *) p;
	while (n--) *q++ = 0;
}

/*
 * Seed material for a thread's DRBG.
 *
 * What the system gives goes through SHA-512 rather than into the key
 * directly, so that the key is a fixed size whatever the call returns, and
 * so that a second source could be added without any of this changing shape.
 * There is one source today and the note below says why.
 */
static int seed_from_system(uint8_t out[SEED_LEN])
{
	struct sha512_ctx h;
	uint8_t buf[64];
	uint8_t digest[64];
	int got;

	crypton_sha512_init(&h);

	/*
	 * The system call only.  Where there is none -- an old kernel, a BSD
	 * this does not know -- seeding fails and the caller keeps the path
	 * it has, rather than this file growing a second copy of the device
	 * reading that Crypto.Random.Entropy.Unix already does.
	 *
	 * And RDRAND is not mixed in beside it, which it was until
	 * @vdukhovni pointed out that it cannot add anything: every system
	 * this code runs on already feeds RDRAND into the pool the call below
	 * draws from.  Linux does that whatever random.trust_cpu says -- that
	 * setting decides whether the contribution is *credited*, not whether
	 * it is mixed -- so the instruction's output is in this buffer
	 * already.
	 *
	 * The argument for keeping it was defence in depth against that pool
	 * having gone wrong.  It does not survive the above: a pool that has
	 * gone wrong has gone wrong with RDRAND already in it, so asking the
	 * instruction a second time covers only the case where the kernel's
	 * mixing is broken and the instruction is not.  That is not worth a
	 * second code path, a flag, and the standing invitation to read this
	 * as a second source when it is the same one twice.
	 */
	got = crypton_sysrandom_available() ? crypton_sysrandom_bytes(buf, 64) : 0;
	/* all 64 or nothing: a short read is a call that failed part way */
	if (got != 64) {
		/* Nothing else here is a seed on its own, so there is nothing to
		 * go on with: return before drawing anything that would only be
		 * thrown away. */
		scrub(&h, sizeof h);
		scrub(buf, sizeof buf);
		return 0;
	}
	crypton_sha512_update(&h, buf, (uint32_t) got);


	crypton_sha512_finalize(&h, digest);
	memcpy(out, digest, SEED_LEN);

	scrub(&h, sizeof h);
	scrub(buf, sizeof buf);
	scrub(digest, sizeof digest);
	return 1;
}

/* generation is the counter as it was before the seed was drawn: read after,
 * a reseed in between would be recorded as met by a seed from before it */
static void drg_seed(drg_t *d, const uint8_t seed[SEED_LEN], size_t generation,
                     uint64_t now, int64_t offset)
{
	crypton_chacha_init(&d->ctx, CHACHA_ROUNDS, SEED_KEY, seed,
	                    SEED_IV, seed + SEED_KEY);
	d->used = 0;
	d->seeded_at = now;
	d->offset_at = offset;
	d->generation = generation;
	d->seeded = 1;
}

/*
 * Forget the key that produced the bytes just handed out.
 *
 * Without this the key stands until the next reseed, and anyone who reads a
 * generator's state can wind the counter back and reproduce everything it
 * has issued since -- up to CRYPTON_THREAD_RESEED bytes that were meant to
 * be secret.  Taking the next forty bytes of keystream as the new key and
 * nonce, and dropping the old ones, puts that out of reach one step after
 * it is issued: ChaCha20 does not run backwards, and the key that would
 * have been needed is gone.  It is what arc4random does.
 *
 * crypton_chacha_init memsets the whole context, so the counter returns to
 * zero and the tail of a part-used block goes with the old key rather than
 * being handed out under the new one.
 *
 * d->used is not touched.  It counts what callers were given, which is what
 * the reseed interval is written in terms of; these forty bytes are the
 * cost of the rekey and not an answer to anybody.
 */
static void drg_rekey(drg_t *d)
{
	uint8_t next[SEED_LEN];

	crypton_chacha_generate(next, &d->ctx, SEED_LEN);
	crypton_chacha_init(&d->ctx, CHACHA_ROUNDS, SEED_KEY, next,
	                    SEED_IV, next + SEED_KEY);
	scrub(next, sizeof next);
}

/* Milliseconds of a monotonic clock that is cheap to read; its resolution
 * of a few milliseconds is why the interval is not offered in anything
 * finer.  It carries on from the image across a restore; see the top. */
static uint64_t now_ms(void)
{
#if defined(_WIN32)
	return (uint64_t) GetTickCount64();
#else
	struct timespec t;
#if defined(CLOCK_MONOTONIC_COARSE)
	clock_gettime(CLOCK_MONOTONIC_COARSE, &t);
#elif defined(CLOCK_MONOTONIC_FAST)
	clock_gettime(CLOCK_MONOTONIC_FAST, &t);
#elif defined(CLOCK_MONOTONIC_RAW_APPROX)
	clock_gettime(CLOCK_MONOTONIC_RAW_APPROX, &t);
#else
	clock_gettime(CLOCK_MONOTONIC, &t);
#endif
	return (uint64_t) t.tv_sec * 1000 + (uint64_t) t.tv_nsec / 1000000;
#endif
}

#ifdef CRYPTON_SYSDRG_TESTING
static int64_t test_realtime_shift_ms = 0;
#endif

/* Realtime minus the monotonic clock of now_ms, in milliseconds. */
static int64_t clock_offset_ms(uint64_t mono)
{
	int64_t real;
#if defined(_WIN32)
	FILETIME ft;
	ULARGE_INTEGER u;
	GetSystemTimeAsFileTime(&ft);
	u.LowPart = ft.dwLowDateTime;
	u.HighPart = ft.dwHighDateTime;
	real = (int64_t) (u.QuadPart / 10000);
#else
	struct timespec t;
#if defined(CLOCK_REALTIME_COARSE)
	clock_gettime(CLOCK_REALTIME_COARSE, &t);
#elif defined(CLOCK_REALTIME_FAST)
	clock_gettime(CLOCK_REALTIME_FAST, &t);
#else
	clock_gettime(CLOCK_REALTIME, &t);
#endif
	real = (int64_t) t.tv_sec * 1000 + (int64_t) t.tv_nsec / 1000000;
#endif
#ifdef CRYPTON_SYSDRG_TESTING
	real += test_realtime_shift_ms;
#endif
	return real - (int64_t) mono;
}

/* interval 0 turns off both clock checks, and the clocks are not read. */
static int drg_stale(const drg_t *d, uint64_t limit, uint64_t interval,
                     uint64_t now, int64_t offset)
{
	int64_t moved = offset - d->offset_at;

	if (!d->seeded || d->used >= limit || d->generation != GENERATION())
		return 1;
	return interval != 0
	    && (now - d->seeded_at >= interval
	        || moved >= OFFSET_SLACK_MS || moved <= -OFFSET_SLACK_MS);
}

#ifdef _WIN32
static void WINAPI thread_free(void *p)
#else
static void thread_free(void *p)
#endif
{
	if (p) {
		scrub(p, sizeof(drg_t));
		free(p);
	}
}

#ifndef _WIN32
static void after_fork_in_child(void)
{
	__atomic_add_fetch(&generation_count, 1, __ATOMIC_RELEASE);
}
#endif

#ifdef CRYPTON_SYSDRG_TESTING
/* For cbits/tests/sysdrg and nothing else.  Nothing outside that test
 * declares these, and the library is never built with this defined. */
static drg_t *this_thread(void);

/* The calling thread's ChaCha key, which is d[4..11] of the state.  A test
 * uses it to ask whether the key that produced a draw is still there
 * afterwards; see "a draw replaces the key that made it" in
 * cbits/tests/sysdrg. */
void crypton_sysdrg_test_key(uint8_t out[32]);

void crypton_sysdrg_test_key(uint8_t out[32])
{
	drg_t *d = this_thread();
	int i;

	if (!d)
		return;
	for (i = 0; i < 8; i++) {
		uint32_t w = d->ctx.st.d[4 + i];
		out[i * 4 + 0] = (uint8_t) (w);
		out[i * 4 + 1] = (uint8_t) (w >> 8);
		out[i * 4 + 2] = (uint8_t) (w >> 16);
		out[i * 4 + 3] = (uint8_t) (w >> 24);
	}
}

/* Copy the calling thread's generator and the generation out and back in,
 * as a saved image and a restore from it would: a test draws, restores, and
 * draws again, which is two copies of one image. */
static struct {
	drg_t thread;
	size_t generation;
} saved_image;

void crypton_sysdrg_test_save(void);
void crypton_sysdrg_test_restore(void);
void crypton_sysdrg_test_shift_realtime(int64_t ms);

/* Move realtime against the monotonic clock, as a CRIU restore does. */
void crypton_sysdrg_test_shift_realtime(int64_t ms)
{
	test_realtime_shift_ms += ms;
}

void crypton_sysdrg_test_save(void)
{
	drg_t *d = this_thread();

	if (d)
		saved_image.thread = *d;
	saved_image.generation = GENERATION();
}

void crypton_sysdrg_test_restore(void)
{
	drg_t *d = this_thread();

	if (d)
		*d = saved_image.thread;
	__atomic_store_n(&generation_count, saved_image.generation, __ATOMIC_RELEASE);
}
#endif

#ifdef _WIN32
static BOOL CALLBACK init_slot(PINIT_ONCE o, PVOID p, PVOID *c)
{
	(void) o; (void) p; (void) c;
	thread_slot = FlsAlloc(thread_free);
	return TRUE;
}
#else
static void init_slot(void)
{
	pthread_key_create(&thread_slot, thread_free);
	pthread_atfork(NULL, NULL, after_fork_in_child);
}
#endif

static drg_t *this_thread(void)
{
	drg_t *d;

#ifdef _WIN32
	InitOnceExecuteOnce(&init_once, init_slot, NULL, NULL);
	if (thread_slot == FLS_OUT_OF_INDEXES)
		return NULL;
	d = (drg_t *) FlsGetValue(thread_slot);
#else
	pthread_once(&init_once, init_slot);
	d = (drg_t *) pthread_getspecific(thread_slot);
#endif
	if (!d) {
		d = (drg_t *) calloc(1, sizeof(drg_t));
		if (!d)
			return NULL;
#ifdef _WIN32
		if (!FlsSetValue(thread_slot, d)) {
			free(d);
			return NULL;
		}
#else
		if (pthread_setspecific(thread_slot, d) != 0) {
			free(d);
			return NULL;
		}
#endif
	}
	return d;
}

/* Per draw: a key and nonce straight from the system, expanded and dropped.
 * The system's bytes go into the key as they are; there is nothing to fix
 * the size of, and a call that comes back short is a failure. */
static int per_draw_bytes(uint8_t *out, int len)
{
	crypton_chacha_context ctx;
	uint8_t seed[SEED_LEN];

	if (crypton_sysrandom_bytes(seed, SEED_LEN) != SEED_LEN) {
		scrub(seed, sizeof seed);
		return 0;
	}
	crypton_chacha_init(&ctx, CHACHA_ROUNDS, SEED_KEY, seed,
	                    SEED_IV, seed + SEED_KEY);
	crypton_chacha_generate(out, &ctx, (uint32_t) len);
	scrub(seed, sizeof seed);
	scrub(&ctx, sizeof ctx);
	return len;
}

/* Choose the mode and the interval.  A change bumps the generation, so a
 * thread that comes back to per-thread mode starts from a fresh seed rather
 * than from a state it left some time ago. */
void crypton_sysdrg_set_mode(int mode, uint32_t interval_ms)
{
	__atomic_store_n(&reseed_interval_ms, interval_ms, __ATOMIC_RELAXED);
	__atomic_store_n(&sysdrg_mode,
	                 mode == MODE_PER_THREAD ? MODE_PER_THREAD : MODE_PER_DRAW,
	                 __ATOMIC_RELAXED);
	__atomic_add_fetch(&generation_count, 1, __ATOMIC_RELEASE);
}

int crypton_sysdrg_get_mode(void)
{
	return MODE();
}

uint32_t crypton_sysdrg_get_interval(void)
{
	return INTERVAL_MS();
}

/* Returns the number of bytes written, which is len unless there was no
 * seed to be had -- and then it is 0, so that the caller can say so rather
 * than hand back a buffer it cannot vouch for. */
int crypton_sysdrg_bytes(uint8_t *out, int len)
{
	drg_t *d;
	uint64_t interval, now;
	int64_t offset;

	if (len < 0)
		return 0;
	if (MODE() == MODE_PER_DRAW)
		return per_draw_bytes(out, len);
	d = this_thread();
	if (!d)
		return 0;

	interval = INTERVAL_MS();
	now = interval != 0 ? now_ms() : 0;
	offset = interval != 0 ? clock_offset_ms(now) : 0;
	if (drg_stale(d, CRYPTON_THREAD_RESEED, interval, now, offset)) {
		uint8_t seed[SEED_LEN];
		size_t g = GENERATION();
		int ok = seed_from_system(seed);
		if (ok)
			drg_seed(d, seed, g, now, offset);
		scrub(seed, sizeof seed);
		if (!ok)
			return 0;
	}

	crypton_chacha_generate(out, &d->ctx, (uint32_t) len);
	d->used += (uint64_t) len;
	drg_rekey(d);
	return len;
}

/*
 * Make every thread's generator reseed from the system before it answers
 * again, as after a fork.  For a program that knows it has been restored
 * from a saved image, which no generator can see for itself.  It only bumps
 * the generation, so it takes no lock and is async-signal-safe.
 */
void crypton_sysdrg_reseed(void)
{
	__atomic_add_fetch(&generation_count, 1, __ATOMIC_RELEASE);
}

/* For the tests: how many times the generators have been told to reseed,
 * by a fork or by crypton_sysdrg_reseed. */
uint32_t crypton_sysdrg_generation(void)
{
	return (uint32_t) GENERATION();
}

/* For the tests: bytes this thread's generator has produced since it was
 * last seeded.  A generator shared between threads would carry the first
 * thread's count into the second; a per-thread one starts again at zero,
 * and that is the only way from outside to tell the two apart. */
uint64_t crypton_sysdrg_thread_used(void)
{
	drg_t *d = this_thread();
	return d ? d->used : 0;
}