Changeset View
Changeset View
Standalone View
Standalone View
lib/libc/gen/arc4random.c
- This file was copied to lib/libc/gen/arc4random_uniform.c.
Property | Old Value | New Value |
---|---|---|
svn:mime-type | null | text/plain \ No newline at end of property |
/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */ | /* $OpenBSD: arc4random.c,v 1.54 2015/09/13 08:31:47 guenther Exp $ */ | ||||
/* | /* | ||||
* Copyright (c) 1996, David Mazieres <dm@uun.org> | * Copyright (c) 1996, David Mazieres <dm@uun.org> | ||||
* Copyright (c) 2008, Damien Miller <djm@openbsd.org> | * Copyright (c) 2008, Damien Miller <djm@openbsd.org> | ||||
* Copyright (c) 2013, Markus Friedl <markus@openbsd.org> | |||||
* Copyright (c) 2014, Theo de Raadt <deraadt@openbsd.org> | |||||
* | * | ||||
* Permission to use, copy, modify, and distribute this software for any | * Permission to use, copy, modify, and distribute this software for any | ||||
* purpose with or without fee is hereby granted, provided that the above | * purpose with or without fee is hereby granted, provided that the above | ||||
* copyright notice and this permission notice appear in all copies. | * copyright notice and this permission notice appear in all copies. | ||||
* | * | ||||
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | ||||
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | ||||
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | ||||
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | ||||
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | ||||
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | ||||
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | ||||
*/ | */ | ||||
/* | /* | ||||
* Arc4 random number generator for OpenBSD. | * ChaCha based random number generator for OpenBSD. | ||||
* | |||||
* This code is derived from section 17.1 of Applied Cryptography, | |||||
* second edition, which describes a stream cipher allegedly | |||||
* compatible with RSA Labs "RC4" cipher (the actual description of | |||||
* which is a trade secret). The same algorithm is used as a stream | |||||
* cipher called "arcfour" in Tatu Ylonen's ssh package. | |||||
* | |||||
* RC4 is a registered trademark of RSA Laboratories. | |||||
*/ | */ | ||||
#include <sys/cdefs.h> | #include <sys/cdefs.h> | ||||
__FBSDID("$FreeBSD$"); | __FBSDID("$FreeBSD$"); | ||||
#include "namespace.h" | #include "namespace.h" | ||||
#include <fcntl.h> | #include <fcntl.h> | ||||
#include <limits.h> | #include <limits.h> | ||||
#include <pthread.h> | |||||
#include <signal.h> | |||||
#include <stdint.h> | |||||
#include <stdlib.h> | #include <stdlib.h> | ||||
#include <string.h> | |||||
#include <unistd.h> | #include <unistd.h> | ||||
#include <sys/param.h> | #include <sys/types.h> | ||||
#include <sys/sysctl.h> | |||||
#include <sys/time.h> | #include <sys/time.h> | ||||
#include <pthread.h> | |||||
#include "libc_private.h" | #include "libc_private.h" | ||||
#include "un-namespace.h" | #include "un-namespace.h" | ||||
#ifdef __GNUC__ | #define KEYSTREAM_ONLY | ||||
#include "chacha_private.h" | |||||
#define minimum(a, b) ((a) < (b) ? (a) : (b)) | |||||
cem: `MIN()`? | |||||
delphijAuthorUnsubmitted Done Inline ActionsThe goal is to minimize changes to this file and not diverge from OpenBSD. Their reasoning was at https://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random.c?rev=1.53&content-type=text/x-cvsweb-markup . delphij: The goal is to minimize changes to this file and not diverge from OpenBSD. Their reasoning was… | |||||
cemUnsubmitted Done Inline ActionsMIN() is a different name than min(), and regardless we don't build FreeBSD with MSVC. cem: MIN() is a different name than min(), and regardless we don't build FreeBSD with MSVC. | |||||
#if defined(__GNUC__) || defined(_MSC_VER) | |||||
#define inline __inline | #define inline __inline | ||||
#else /* !__GNUC__ */ | #else /* __GNUC__ || _MSC_VER */ | ||||
#define inline | #define inline | ||||
#endif /* !__GNUC__ */ | #endif /* !__GNUC__ && !_MSC_VER */ | ||||
cemUnsubmitted Done Inline ActionsWhat is this trying to accomplish? cem: What is this trying to accomplish? | |||||
cemUnsubmitted Not Done Inline ActionsHm, I'm still not sure what the inline ifdefs are for. cem: Hm, I'm still not sure what the inline ifdefs are for. | |||||
struct arc4_stream { | #define KEYSZ 32 | ||||
u_int8_t i; | #define IVSZ 8 | ||||
u_int8_t j; | #define BLOCKSZ 64 | ||||
u_int8_t s[256]; | #define RSBUFSZ (16*BLOCKSZ) | ||||
}; | |||||
static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; | /* Marked MAP_INHERIT_ZERO, so zero'd out in fork children. */ | ||||
devnexen_gmail.comUnsubmitted Done Inline ActionsINHERIT_ZERO devnexen_gmail.com: INHERIT_ZERO | |||||
static struct _rs { | |||||
size_t rs_have; /* valid bytes at end of rs_buf */ | |||||
size_t rs_count; /* bytes till reseed */ | |||||
} *rs; | |||||
#define KEYSIZE 128 | /* Maybe be preserved in fork children, if _rs_allocate() decides. */ | ||||
#define _ARC4_LOCK() \ | static struct _rsx { | ||||
do { \ | chacha_ctx rs_chacha; /* chacha context for random keystream */ | ||||
if (__isthreaded) \ | u_char rs_buf[RSBUFSZ]; /* keystream blocks */ | ||||
_pthread_mutex_lock(&arc4random_mtx); \ | } *rsx; | ||||
} while (0) | |||||
#define _ARC4_UNLOCK() \ | static inline int _rs_allocate(struct _rs **, struct _rsx **); | ||||
do { \ | static inline void _rs_forkdetect(void); | ||||
if (__isthreaded) \ | #include "arc4random.h" | ||||
cemUnsubmitted Done Inline ActionsThis is a very odd pattern. Why is any of the contents of arc4random.h in a header instead of in this file? cem: This is a very odd pattern. Why is any of the contents of arc4random.h in a header instead of… | |||||
_pthread_mutex_unlock(&arc4random_mtx); \ | |||||
} while (0) | |||||
static int rs_initialized; | static inline void _rs_rekey(u_char *dat, size_t datlen); | ||||
static struct arc4_stream rs; | |||||
static pid_t arc4_stir_pid; | |||||
static int arc4_count; | |||||
extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, | |||||
void *newp, size_t newlen); | |||||
static inline u_int8_t arc4_getbyte(void); | |||||
static void arc4_stir(void); | |||||
static inline void | static inline void | ||||
arc4_init(void) | _rs_init(u_char *buf, size_t n) | ||||
{ | { | ||||
int n; | if (n < KEYSZ + IVSZ) | ||||
return; | |||||
for (n = 0; n < 256; n++) | if (rs == NULL) { | ||||
rs.s[n] = n; | if (_rs_allocate(&rs, &rsx) == -1) | ||||
rs.i = 0; | abort(); | ||||
rs.j = 0; | |||||
} | } | ||||
static inline void | chacha_keysetup(&rsx->rs_chacha, buf, KEYSZ * 8, 0); | ||||
arc4_addrandom(u_char *dat, int datlen) | chacha_ivsetup(&rsx->rs_chacha, buf + KEYSZ); | ||||
{ | |||||
int n; | |||||
u_int8_t si; | |||||
rs.i--; | |||||
for (n = 0; n < 256; n++) { | |||||
rs.i = (rs.i + 1); | |||||
si = rs.s[rs.i]; | |||||
rs.j = (rs.j + si + dat[n % datlen]); | |||||
rs.s[rs.i] = rs.s[rs.j]; | |||||
rs.s[rs.j] = si; | |||||
} | } | ||||
rs.j = rs.i; | |||||
} | |||||
size_t | static void | ||||
__arc4_sysctl(u_char *buf, size_t size) | _rs_stir(void) | ||||
{ | { | ||||
int mib[2]; | u_char rnd[KEYSZ + IVSZ]; | ||||
size_t len, done; | |||||
mib[0] = CTL_KERN; | if (getentropy(rnd, sizeof rnd) == -1) | ||||
mib[1] = KERN_ARND; | _getentropy_fail(); | ||||
done = 0; | |||||
do { | if (!rs) | ||||
len = size; | _rs_init(rnd, sizeof(rnd)); | ||||
if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) | else | ||||
return (done); | _rs_rekey(rnd, sizeof(rnd)); | ||||
done += len; | explicit_bzero(rnd, sizeof(rnd)); /* discard source seed */ | ||||
buf += len; | |||||
size -= len; | |||||
} while (size > 0); | |||||
return (done); | /* invalidate rs_buf */ | ||||
rs->rs_have = 0; | |||||
memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf)); | |||||
rs->rs_count = 1600000; | |||||
} | } | ||||
static void | static inline void | ||||
arc4_stir(void) | _rs_stir_if_needed(size_t len) | ||||
{ | { | ||||
u_char rdat[KEYSIZE]; | _rs_forkdetect(); | ||||
int i; | if (!rs || rs->rs_count <= len) | ||||
_rs_stir(); | |||||
if (!rs_initialized) { | if (rs->rs_count <= len) | ||||
arc4_init(); | rs->rs_count = 0; | ||||
rs_initialized = 1; | else | ||||
rs->rs_count -= len; | |||||
} | } | ||||
if (__arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) { | |||||
/* | |||||
* The sysctl cannot fail. If it does fail on some FreeBSD | |||||
* derivative or after some future change, just abort so that | |||||
* the problem will be found and fixed. abort is not normally | |||||
* suitable for a library but makes sense here. | |||||
*/ | |||||
abort(); | |||||
} | |||||
arc4_addrandom(rdat, KEYSIZE); | static inline void | ||||
_rs_rekey(u_char *dat, size_t datlen) | |||||
/* | |||||
* Discard early keystream, as per recommendations in: | |||||
* "(Not So) Random Shuffles of RC4" by Ilya Mironov. | |||||
*/ | |||||
for (i = 0; i < 3072; i++) | |||||
(void)arc4_getbyte(); | |||||
arc4_count = 1600000; | |||||
} | |||||
static void | |||||
arc4_stir_if_needed(void) | |||||
{ | { | ||||
pid_t pid = getpid(); | #ifndef KEYSTREAM_ONLY | ||||
memset(rsx->rs_buf, 0, sizeof(rsx->rs_buf)); | |||||
#endif | |||||
/* fill rs_buf with the keystream */ | |||||
chacha_encrypt_bytes(&rsx->rs_chacha, rsx->rs_buf, | |||||
rsx->rs_buf, sizeof(rsx->rs_buf)); | |||||
/* mix in optional user provided data */ | |||||
if (dat) { | |||||
size_t i, m; | |||||
if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) { | m = minimum(datlen, KEYSZ + IVSZ); | ||||
arc4_stir_pid = pid; | for (i = 0; i < m; i++) | ||||
arc4_stir(); | rsx->rs_buf[i] ^= dat[i]; | ||||
} | } | ||||
/* immediately reinit for backtracking resistance */ | |||||
_rs_init(rsx->rs_buf, KEYSZ + IVSZ); | |||||
memset(rsx->rs_buf, 0, KEYSZ + IVSZ); | |||||
rs->rs_have = sizeof(rsx->rs_buf) - KEYSZ - IVSZ; | |||||
} | } | ||||
static inline u_int8_t | static inline void | ||||
arc4_getbyte(void) | _rs_random_buf(void *_buf, size_t n) | ||||
{ | { | ||||
u_int8_t si, sj; | u_char *buf = (u_char *)_buf; | ||||
u_char *keystream; | |||||
size_t m; | |||||
rs.i = (rs.i + 1); | _rs_stir_if_needed(n); | ||||
si = rs.s[rs.i]; | while (n > 0) { | ||||
rs.j = (rs.j + si); | if (rs->rs_have > 0) { | ||||
sj = rs.s[rs.j]; | m = minimum(n, rs->rs_have); | ||||
rs.s[rs.i] = sj; | keystream = rsx->rs_buf + sizeof(rsx->rs_buf) | ||||
rs.s[rs.j] = si; | - rs->rs_have; | ||||
return (rs.s[(si + sj) & 0xff]); | memcpy(buf, keystream, m); | ||||
memset(keystream, 0, m); | |||||
buf += m; | |||||
n -= m; | |||||
rs->rs_have -= m; | |||||
} | } | ||||
if (rs->rs_have == 0) | |||||
static inline u_int32_t | _rs_rekey(NULL, 0); | ||||
arc4_getword(void) | |||||
{ | |||||
u_int32_t val; | |||||
val = arc4_getbyte() << 24; | |||||
val |= arc4_getbyte() << 16; | |||||
val |= arc4_getbyte() << 8; | |||||
val |= arc4_getbyte(); | |||||
return val; | |||||
} | } | ||||
void | |||||
arc4random_stir(void) | |||||
{ | |||||
_ARC4_LOCK(); | |||||
arc4_stir(); | |||||
_ARC4_UNLOCK(); | |||||
} | } | ||||
void | static inline void | ||||
arc4random_addrandom(u_char *dat, int datlen) | _rs_random_u32(uint32_t *val) | ||||
{ | { | ||||
_ARC4_LOCK(); | u_char *keystream; | ||||
if (!rs_initialized) | |||||
arc4_stir(); | _rs_stir_if_needed(sizeof(*val)); | ||||
arc4_addrandom(dat, datlen); | if (rs->rs_have < sizeof(*val)) | ||||
_ARC4_UNLOCK(); | _rs_rekey(NULL, 0); | ||||
keystream = rsx->rs_buf + sizeof(rsx->rs_buf) - rs->rs_have; | |||||
memcpy(val, keystream, sizeof(*val)); | |||||
memset(keystream, 0, sizeof(*val)); | |||||
rs->rs_have -= sizeof(*val); | |||||
} | } | ||||
u_int32_t | uint32_t | ||||
arc4random(void) | arc4random(void) | ||||
{ | { | ||||
u_int32_t val; | uint32_t val; | ||||
_ARC4_LOCK(); | _ARC4_LOCK(); | ||||
arc4_count -= 4; | _rs_random_u32(&val); | ||||
arc4_stir_if_needed(); | |||||
val = arc4_getword(); | |||||
_ARC4_UNLOCK(); | _ARC4_UNLOCK(); | ||||
return val; | return val; | ||||
} | } | ||||
void | void | ||||
arc4random_buf(void *_buf, size_t n) | arc4random_buf(void *buf, size_t n) | ||||
{ | { | ||||
u_char *buf = (u_char *)_buf; | |||||
_ARC4_LOCK(); | _ARC4_LOCK(); | ||||
arc4_stir_if_needed(); | _rs_random_buf(buf, n); | ||||
while (n--) { | |||||
if (--arc4_count <= 0) | |||||
arc4_stir(); | |||||
buf[n] = arc4_getbyte(); | |||||
} | |||||
_ARC4_UNLOCK(); | _ARC4_UNLOCK(); | ||||
} | } | ||||
/* | |||||
* Calculate a uniformly distributed random number less than upper_bound | |||||
* avoiding "modulo bias". | |||||
* | |||||
* Uniformity is achieved by generating new random numbers until the one | |||||
* returned is outside the range [0, 2**32 % upper_bound). This | |||||
* guarantees the selected random number will be inside | |||||
* [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) | |||||
* after reduction modulo upper_bound. | |||||
*/ | |||||
u_int32_t | |||||
arc4random_uniform(u_int32_t upper_bound) | |||||
{ | |||||
u_int32_t r, min; | |||||
if (upper_bound < 2) | |||||
return 0; | |||||
/* 2**32 % x == (2**32 - x) % x */ | |||||
min = -upper_bound % upper_bound; | |||||
/* | |||||
* This could theoretically loop forever but each retry has | |||||
* p > 0.5 (worst case, usually far better) of selecting a | |||||
* number inside the range we need, so it should rarely need | |||||
* to re-roll. | |||||
*/ | |||||
for (;;) { | |||||
r = arc4random(); | |||||
if (r >= min) | |||||
break; | |||||
} | |||||
return r % upper_bound; | |||||
} | |||||
#if 0 | |||||
/*-------- Test code for i386 --------*/ | |||||
#include <stdio.h> | |||||
#include <machine/pctr.h> | |||||
int | |||||
main(int argc, char **argv) | |||||
{ | |||||
const int iter = 1000000; | |||||
int i; | |||||
pctrval v; | |||||
v = rdtsc(); | |||||
for (i = 0; i < iter; i++) | |||||
arc4random(); | |||||
v = rdtsc() - v; | |||||
v /= iter; | |||||
printf("%qd cycles\n", v); | |||||
} | |||||
#endif |
MIN()?