sortix-mirror/kernel/random.cpp
Jonas 'Sortie' Termansen e4f18b8049 Collect entropy.
2024-10-10 13:24:16 +02:00

295 lines
10 KiB
C++

/*
* Copyright (c) 2014, 2015, 2016, 2024 Jonas 'Sortie' Termansen.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
* random.cpp
* Kernel entropy gathering.
*/
#include <sys/mman.h>
#include <assert.h>
#include <errno.h>
#include <sha2.h>
#include <stdlib.h>
#include <string.h>
#include <timespec.h>
#include <sortix/clock.h>
#include <sortix/limits.h>
#include <sortix/kernel/addralloc.h>
#include <sortix/kernel/copy.h>
#include <sortix/kernel/kernel.h>
#include <sortix/kernel/kthread.h>
#include <sortix/kernel/memorymanagement.h>
#include <sortix/kernel/random.h>
#include <sortix/kernel/syscall.h>
#include <sortix/kernel/time.h>
#include "multiboot.h"
// This is the entropy collection subsystem.
//
// Potentially weak and hostile entropy sources (such as the previous boot's
// entropy seed, hardware details and serial numbers, interrupt timing data and
// details, peripheral input, network checksums, registers on preemption, etc.)
// are mixed together into an entropy stream where an attacker cannot guess all
// of the data especially as the entropy collects over time.
//
// Incoming source data is written to its channel's ring buffer. If the buffer
// is full, then the new data is XOR'd into the buffer.
//
// Channels are mixed together by replacing each block in the channel buffer
// with its SHA256 digest and then XOR'ing together all of the channel buffers
// into a single entropy buffer.
//
// Random numbers are provided using the arc4random(3) functions which uses the
// entropy collected here. New entropy is stired together and used whenever:
//
// - No entropy has ever been provided.
// - getentropy(2) is being called and new entropy is available in any channel.
// - Any channel has new entropy whose buffer has never filled.
// - New entropy is available and one second has passed since the last stir.
//
// The random number generator is available immediately after boot, although it
// won't be strong until the random seed is mixed in, and if none is provided,
// then it will take some system activity for entropy to collect. The goal is
// to have strong entropy by the time a fresh interactive system installation is
// completed.
namespace Sortix {
namespace Random {
struct Channel
{
unsigned char entropy[GETENTROPY_MAX];
size_t collected;
size_t offset;
size_t total;
};
static Channel channels[SOURCE_MAX];
static kthread_mutex_t entropy_lock = KTHREAD_MUTEX_INITIALIZER;
static bool want_stir;
static bool has_any_entropy;
static bool has_new_record;
static struct timespec last_stir_at;
void Init(multiboot_info_t* bootinfo)
{
// Mix in the random seed if provided as a kernel module.
// TODO: This assumes the multiboot structures are accessible. That
// assumption is wrong in general and we should map them ourselves in
// manner that cannot fail.
struct multiboot_mod_list* modules =
(struct multiboot_mod_list*) (uintptr_t) bootinfo->mods_addr;
for ( uint32_t i = 0; i < bootinfo->mods_count; i++ )
{
struct multiboot_mod_list* module = &modules[i];
// TODO: This assumes module is mapped.
size_t mod_size = module->mod_end - module->mod_start;
const char* cmdline = (const char*) (uintptr_t) module->cmdline;
// TODO: This assumes cmdline is mapped.
if ( strcmp(cmdline, "--random-seed") != 0 )
continue;
// TODO: Make an early map facility that cannot fail and use it to map
// the random seed.
// TODO: AllocateKernelAddress might invoke randomness in some way in
// future.
addralloc_t addralloc;
if ( !AllocateKernelAddress(&addralloc, mod_size) )
PanicF("Random::Init AllocateKernelAddress failed: %m");
addr_t physfrom = module->mod_start;
addr_t mapat = addralloc.from;
for ( size_t i = 0; i < mod_size; i += Page::Size() )
{
if ( !Memory::Map(physfrom + i, mapat + i, PROT_KREAD | PROT_KWRITE) )
PanicF("Random::Init Memory::Map failed: %m");
}
Memory::Flush();
unsigned char* seed = (unsigned char*) addralloc.from;
Mix(SOURCE_SEED, seed, mod_size);
explicit_bzero(seed, mod_size);
for ( size_t i = 0; i < mod_size; i += Page::Size() )
Memory::Unmap(mapat + i);
Memory::Flush();
FreeKernelAddress(&addralloc);
}
}
int GetFallbackStatus()
{
ScopedLock lock(&entropy_lock);
if ( channels[SOURCE_SEED].collected == 0 )
return 1;
else if ( channels[SOURCE_SEED].collected < GETENTROPY_MAX )
return 2;
else
return 0;
}
void Mix(enum Source source, const void* ptr, size_t size)
{
bool in_interrupt =
source == SOURCE_PREEMPTION || source == SOURCE_INTERRUPT;
const unsigned char* buffer = (const unsigned char*) ptr;
Channel* channel = &channels[source];
// TODO: Use a spin lock and rethink SOURCE_PREEMPTION when ready for SMP.
bool locked = true;
if ( in_interrupt )
locked = kthread_mutex_trylock(&entropy_lock);
else
kthread_mutex_lock(&entropy_lock);
size_t done = 0;
// Repeatedly mix in the data into the ring buffer.
while ( done < size )
{
size_t left = size - done;
size_t available = sizeof(channel->entropy) - channel->offset;
size_t count = left < available ? left : available;
// XOR the new data into the ring buffer to preserve entropy already
// there with fresh data that may be weak and hostile (but wouldn't know
// the internal state of the channels).
for ( size_t i = 0; i < count; i++ )
{
unsigned char input = channel->entropy[channel->offset + i];
unsigned char seed = buffer[done + i];
unsigned char output = input ^ seed;
channel->entropy[channel->offset + i] = output;
}
channel->offset += count;
// Stir the entropy if the channel is starting up and has new data.
if ( locked && channel->collected < channel->offset )
{
channel->collected = channel->offset;
has_new_record = true;
}
if ( channel->offset == sizeof(channel->entropy) )
channel->offset = 0;
channel->total += count;
done += count;
}
if ( locked )
{
if ( done )
has_any_entropy = true;
kthread_mutex_unlock(&entropy_lock);
}
}
void MixNow(enum Source source)
{
// The exact uptime and estimated realtime of an event may not be known,
// and whether the event occurred, but it largely may be guessed. Mixing in
// enough of these slight unknowns will exponentially increase the
// possibilities. The uptime is used here since it might not be public,
// meanwhile the realtime is public, but the network time estimation will be
// somewhat inaccurate. The lower bits of tv_nsec are likely to be the most
// random and the higher bits of tv_sec rarely changed, so mix it together
// into a 32-bit hash to avoid filling the channel with repetitive data.
struct timespec rt = Time::Get(CLOCK_REALTIME);
struct timespec bt = Time::Get(CLOCK_BOOTTIME);
struct timespec sum = timespec_add(rt, bt);
uint32_t hash = sum.tv_nsec ^ (sum.tv_sec >> 32) ^ sum.tv_sec;
Mix(source, &hash, sizeof(hash));
}
bool HasEntropy(size_t amount)
{
ScopedLock lock(&entropy_lock);
// Stir fresh entropy for arc4random(3) on the conditions documented above.
return amount <= GETENTROPY_MAX &&
has_any_entropy &&
(want_stir ||
has_new_record ||
timespec_le(timespec_make(1, 0),
timespec_sub(Time::Get(CLOCK_BOOTTIME), last_stir_at)));
}
void GetEntropy(void* result, size_t size)
{
unsigned char* output = (unsigned char*) result;
// The channel ring buffer size must be a multiple of the SHA2 block size.
assert(size <= GETENTROPY_MAX);
static_assert(SHA256_DIGEST_LENGTH < GETENTROPY_MAX,
"SHA256_DIGEST_LENGTH < GETENTROPY_MAX");
static_assert(GETENTROPY_MAX % SHA256_DIGEST_LENGTH == 0,
"GETENTROPY_MAX % SHA256_DIGEST_LENGTH == 0");
// Mix all of the channels together into a single entropy buffer.
unsigned char entropy[GETENTROPY_MAX];
SHA2_CTX ctx;
kthread_mutex_lock(&entropy_lock);
for ( size_t i = 0; i < SOURCE_MAX; i++ )
{
Channel* channel = &channels[i];
// SHA256 digest each block in the channel's buffer and replace the
// block with the digest. This digest massively mixes the bits together
// so they don't have obvious patterns, unlike the weak data presently
// in the buffer. The newly hashed data remains in the buffer and will
// be fit-flipped with XOR by new data being mixed in later.
for ( size_t b = 0; b < GETENTROPY_MAX / SHA256_DIGEST_LENGTH; b++ )
{
size_t offset = b * SHA256_DIGEST_LENGTH;
SHA256Init(&ctx);
SHA256Update(&ctx, channel->entropy + offset, SHA256_DIGEST_LENGTH);
SHA256Final(channel->entropy + offset, &ctx);
}
// XOR the combined entropy buffer with the channel's digested entropy.
for ( size_t n = 0; n < GETENTROPY_MAX; n++ )
entropy[n] ^= channel->entropy[n];
}
last_stir_at = Time::Get(CLOCK_BOOTTIME);
has_any_entropy = false;
has_new_record = false;
want_stir = false;
kthread_mutex_unlock(&entropy_lock);
// Copy the entropy to the caller. Too much entropy was probably generated,
// so repeatedly XOR the remaining entropy into the caller's buffer, so the
// excess entropy isn't lost.
memcpy(result, entropy, size);
for ( size_t i = size, o = 0; i < GETENTROPY_MAX; i++ )
{
output[o++] ^= entropy[i];
if ( o == size )
o = 0;
}
explicit_bzero(&entropy, sizeof(entropy));
explicit_bzero(&ctx, sizeof(ctx));
}
} // namespace Random
} // namespace Sortix
namespace Sortix {
int sys_getentropy(void* user_buffer, size_t size)
{
unsigned char buffer[GETENTROPY_MAX];
if ( sizeof(buffer) < size )
return errno = EIO, -1;
// Always stir in new entropy if any is available, since this syscall may be
// called on system shutdown to get the best entropy gathered so far, so it
// can be stored for the next boot.
kthread_mutex_lock(&Random::entropy_lock);
Random::want_stir = true;
kthread_mutex_unlock(&Random::entropy_lock);
arc4random_buf(buffer, size);
if ( !CopyToUser(user_buffer, buffer, size) )
return -1;
return 0;
}
} // namespace Sortix