Page MenuHomeFreeBSD
Differential D10048 Diff 27475 head/sys/libkern/arc4random.c

Changeset View

Standalone View

View Options

head/sys/libkern/arc4random.c

/*- /*-
* THE BEER-WARE LICENSE * Copyright (c) 2017 The FreeBSD Foundation
* All rights reserved.
* *
* <dan@FreeBSD.ORG> wrote this file. As long as you retain this notice you * Redistribution and use in source and binary forms, with or without
* can do whatever you want with this stuff. If we meet some day, and you * modification, are permitted provided that the following conditions
* think this stuff is worth it, you can buy me a beer in return. * are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer
* in this position and unchanged.
* 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.
* *
* Dan Moschuk * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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/cdefs.h> #include <sys/cdefs.h>
__FBSDID("$FreeBSD$"); __FBSDID("$FreeBSD$");
#include <sys/types.h> #include <sys/types.h>
#include <sys/param.h> #include <sys/param.h>
#include <sys/kernel.h> #include <sys/kernel.h>
#include <sys/random.h>
#include <sys/libkern.h> #include <sys/libkern.h>
#include <sys/linker.h>
#include <sys/lock.h> #include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/mutex.h> #include <sys/mutex.h>
#include <sys/time.h> #include <sys/random.h>
#include <sys/smp.h> #include <sys/smp.h>
#include <sys/malloc.h> #include <sys/time.h>
#define ARC4_RESEED_BYTES 65536 #include <crypto/chacha20/chacha.h>
#define ARC4_RESEED_SECONDS 300
#define ARC4_KEYBYTES 256
#define CHACHA20_RESEED_BYTES 65536
#define CHACHA20_RESEED_SECONDS 300
#define CHACHA20_KEYBYTES 32
#define CHACHA20_BUFFER_SIZE 64
CTASSERT(CHACHA20_KEYBYTES*8 >= CHACHA_MINKEYLEN);
int arc4rand_iniseed_state = ARC4_ENTR_NONE; int arc4rand_iniseed_state = ARC4_ENTR_NONE;
MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures"); MALLOC_DEFINE(M_CHACHA20RANDOM, "chacha20random", "chacha20random structures");
struct arc4_s { struct chacha20_s {
struct mtx mtx; struct mtx mtx;
u_int8_t i, j; int numbytes;
int numruns; int first_time_done;
u_int8_t sbox[256];
time_t t_reseed; time_t t_reseed;
u_int8_t m_buffer[CHACHA20_BUFFER_SIZE];
struct chacha_ctx ctx;
} __aligned(CACHE_LINE_SIZE); } __aligned(CACHE_LINE_SIZE);
static struct arc4_s *arc4inst = NULL; static struct chacha20_s *chacha20inst = NULL;
#define ARC4_FOREACH(_arc4) \ #define CHACHA20_FOREACH(_chacha20) \
for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++) for (_chacha20 = &chacha20inst[0]; \
_chacha20 <= &chacha20inst[mp_maxid]; \
_chacha20++)
static u_int8_t arc4_randbyte(struct arc4_s *arc4);
static __inline void
arc4_swap(u_int8_t *a, u_int8_t *b)
{
u_int8_t c;
c = *a;
*a = *b;
*b = c;
}
/* /*
* Stir our S-box. * Mix up the current context.
*/ */
static void static void
arc4_randomstir(struct arc4_s* arc4) chacha20_randomstir(struct chacha20_s* chacha20)
{ {
u_int8_t key[ARC4_KEYBYTES];
int n;
struct timeval tv_now; struct timeval tv_now;
size_t n, size;
u_int8_t key[CHACHA20_KEYBYTES], *data;
caddr_t keyfile;
/* /*
* XXX: FIX!! This isn't brilliant. Need more confidence. * This is making the best of what may be an insecure
* This returns zero entropy before random(4) is seeded. * Situation. If the loader(8) did not have an entropy
* stash from the previous shutdown to load, then we will
* be improperly seeded. The answer is to make sure there
* is an entropy stash at shutdown time.
*/ */
(void)read_random(key, ARC4_KEYBYTES); (void)read_random(key, CHACHA20_KEYBYTES);
getmicrouptime(&tv_now); if (!chacha20->first_time_done) {
mtx_lock(&arc4->mtx); keyfile = preload_search_by_type(RANDOM_CACHED_BOOT_ENTROPY_MODULE);
for (n = 0; n < 256; n++) { if (keyfile != NULL) {
arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256; data = preload_fetch_addr(keyfile);
arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]); size = MIN(preload_fetch_size(keyfile), CHACHA20_KEYBYTES);
for (n = 0; n < size; n++)
key[n] ^= data[n];
explicit_bzero(data, size);
if (bootverbose)
printf("arc4random: read %zu bytes from preloaded cache\n", size);
} else
printf("arc4random: no preloaded entropy cache\n");
chacha20->first_time_done = 1;
} }
arc4->i = arc4->j = 0; getmicrouptime(&tv_now);
mtx_lock(&chacha20->mtx);
chacha_keysetup(&chacha20->ctx, key, CHACHA20_KEYBYTES*8);
chacha_ivsetup(&chacha20->ctx, (u_char *)&tv_now.tv_sec, (u_char *)&tv_now.tv_usec);
/* Reset for next reseed cycle. */ /* Reset for next reseed cycle. */
arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS; chacha20->t_reseed = tv_now.tv_sec + CHACHA20_RESEED_SECONDS;
arc4->numruns = 0; chacha20->numbytes = 0;
/* mtx_unlock(&chacha20->mtx);
* Throw away the first N words of output, as suggested in the
* paper "Weaknesses in the Key Scheduling Algorithm of RC4"
* by Fluher, Mantin, and Shamir. (N = 768 in our case.)
*
* http://dl.acm.org/citation.cfm?id=646557.694759
*/
for (n = 0; n < 768*4; n++)
arc4_randbyte(arc4);
mtx_unlock(&arc4->mtx);
} }
/* /*
* Initialize our S-box to its beginning defaults. * Initialize the contexts.
*/ */
static void static void
arc4_init(void) chacha20_init(void)
{ {
struct arc4_s *arc4; struct chacha20_s *chacha20;
int n;
arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s), chacha20inst = malloc((mp_maxid + 1) * sizeof(struct chacha20_s),
M_ARC4RANDOM, M_NOWAIT | M_ZERO); M_CHACHA20RANDOM, M_NOWAIT | M_ZERO);
KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error")); KASSERT(chacha20inst != NULL, ("chacha20_init: memory allocation error"));
ARC4_FOREACH(arc4) { CHACHA20_FOREACH(chacha20) {
mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF); mtx_init(&chacha20->mtx, "chacha20_mtx", NULL, MTX_DEF);
chacha20->t_reseed = -1;
arc4->i = arc4->j = 0; chacha20->numbytes = 0;
for (n = 0; n < 256; n++) chacha20->first_time_done = 0;
arc4->sbox[n] = (u_int8_t) n; explicit_bzero(chacha20->m_buffer, CHACHA20_BUFFER_SIZE);
explicit_bzero(&chacha20->ctx, sizeof(chacha20->ctx));
arc4->t_reseed = -1;
arc4->numruns = 0;
} }
} }
SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL); SYSINIT(chacha20, SI_SUB_LOCK, SI_ORDER_ANY, chacha20_init, NULL);
static void static void
arc4_uninit(void) chacha20_uninit(void)
{ {
struct arc4_s *arc4; struct chacha20_s *chacha20;
ARC4_FOREACH(arc4) { CHACHA20_FOREACH(chacha20)
mtx_destroy(&arc4->mtx); mtx_destroy(&chacha20->mtx);
free(chacha20inst, M_CHACHA20RANDOM);
} }
SYSUNINIT(chacha20, SI_SUB_LOCK, SI_ORDER_ANY, chacha20_uninit, NULL);
free(arc4inst, M_ARC4RANDOM);
}
SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL);
/* /*
* Generate a random byte.
*/
static u_int8_t
arc4_randbyte(struct arc4_s *arc4)
{
u_int8_t arc4_t;
arc4->i = (arc4->i + 1) % 256;
arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256;
arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]);
arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256;
return arc4->sbox[arc4_t];
}
/*
* MPSAFE * MPSAFE
*/ */
void void
arc4rand(void *ptr, u_int len, int reseed) arc4rand(void *ptr, u_int len, int reseed)
{ {
u_char *p; struct chacha20_s *chacha20;
struct timeval tv; struct timeval tv;
struct arc4_s *arc4; u_int length;
u_int8_t *p;
if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state, if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_HAVE, ARC4_ENTR_SEED))
ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) { CHACHA20_FOREACH(chacha20)
ARC4_FOREACH(arc4) chacha20_randomstir(chacha20);
arc4_randomstir(arc4);
}
arc4 = &arc4inst[curcpu]; chacha20 = &chacha20inst[curcpu];
getmicrouptime(&tv); getmicrouptime(&tv);
if ((arc4->numruns > ARC4_RESEED_BYTES) || /* We may get unlucky and be migrated off this CPU, but that is expected to be infrequent */
(tv.tv_sec > arc4->t_reseed)) if ((chacha20->numbytes > CHACHA20_RESEED_BYTES) || (tv.tv_sec > chacha20->t_reseed))
arc4_randomstir(arc4); chacha20_randomstir(chacha20);
mtx_lock(&arc4->mtx); mtx_lock(&chacha20->mtx);
arc4->numruns += len;
p = ptr; p = ptr;
while (len--) while (len) {
*p++ = arc4_randbyte(arc4); length = MIN(CHACHA20_BUFFER_SIZE, len);
mtx_unlock(&arc4->mtx); chacha_encrypt_bytes(&chacha20->ctx, chacha20->m_buffer, p, length);
p += length;
len -= length;
chacha20->numbytes += length;
if (chacha20->numbytes > CHACHA20_RESEED_BYTES) {
mtx_unlock(&chacha20->mtx);
chacha20_randomstir(chacha20);
mtx_lock(&chacha20->mtx);
} }
}
mtx_unlock(&chacha20->mtx);
}
uint32_t uint32_t
arc4random(void) arc4random(void)
{ {
uint32_t ret; uint32_t ret;
arc4rand(&ret, sizeof ret, 0); arc4rand(&ret, sizeof(ret), 0);
return ret; return ret;
}
void
arc4random_buf(void *ptr, size_t len)
{
arc4rand(ptr, len, 0);
} }