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;
}