| 1 |
/* ---------------------------------------------------------------------------- |
| 2 |
Copyright (c) 2019-2021, Microsoft Research, Daan Leijen |
| 3 |
This is free software; you can redistribute it and/or modify it under the |
| 4 |
terms of the MIT license. A copy of the license can be found in the file |
| 5 |
"LICENSE" at the root of this distribution. |
| 6 |
-----------------------------------------------------------------------------*/ |
| 7 |
#include "mimalloc.h" |
| 8 |
#include "mimalloc/internal.h" |
| 9 |
#include "mimalloc/prim.h" // _mi_prim_random_buf |
| 10 |
#include <string.h> // memset |
| 11 |
|
| 12 |
/* ---------------------------------------------------------------------------- |
| 13 |
We use our own PRNG to keep predictable performance of random number generation |
| 14 |
and to avoid implementations that use a lock. We only use the OS provided |
| 15 |
random source to initialize the initial seeds. Since we do not need ultimate |
| 16 |
performance but we do rely on the security (for secret cookies in secure mode) |
| 17 |
we use a cryptographically secure generator (chacha20). |
| 18 |
-----------------------------------------------------------------------------*/ |
| 19 |
|
| 20 |
#define MI_CHACHA_ROUNDS (20) // perhaps use 12 for better performance? |
| 21 |
|
| 22 |
|
| 23 |
/* ---------------------------------------------------------------------------- |
| 24 |
Chacha20 implementation as the original algorithm with a 64-bit nonce |
| 25 |
and counter: https://en.wikipedia.org/wiki/Salsa20 |
| 26 |
The input matrix has sixteen 32-bit values: |
| 27 |
Position 0 to 3: constant key |
| 28 |
Position 4 to 11: the key |
| 29 |
Position 12 to 13: the counter. |
| 30 |
Position 14 to 15: the nonce. |
| 31 |
|
| 32 |
The implementation uses regular C code which compiles very well on modern compilers. |
| 33 |
(gcc x64 has no register spills, and clang 6+ uses SSE instructions) |
| 34 |
-----------------------------------------------------------------------------*/ |
| 35 |
|
| 36 |
static inline uint32_t rotl(uint32_t x, uint32_t shift) { |
| 37 |
return (x << shift) | (x >> (32 - shift)); |
| 38 |
} |
| 39 |
|
| 40 |
static inline void qround(uint32_t x[16], size_t a, size_t b, size_t c, size_t d) { |
| 41 |
x[a] += x[b]; x[d] = rotl(x[d] ^ x[a], 16); |
| 42 |
x[c] += x[d]; x[b] = rotl(x[b] ^ x[c], 12); |
| 43 |
x[a] += x[b]; x[d] = rotl(x[d] ^ x[a], 8); |
| 44 |
x[c] += x[d]; x[b] = rotl(x[b] ^ x[c], 7); |
| 45 |
} |
| 46 |
|
| 47 |
static void chacha_block(mi_random_ctx_t* ctx) |
| 48 |
{ |
| 49 |
// scramble into `x` |
| 50 |
uint32_t x[16]; |
| 51 |
for (size_t i = 0; i < 16; i++) { |
| 52 |
x[i] = ctx->input[i]; |
| 53 |
} |
| 54 |
for (size_t i = 0; i < MI_CHACHA_ROUNDS; i += 2) { |
| 55 |
qround(x, 0, 4, 8, 12); |
| 56 |
qround(x, 1, 5, 9, 13); |
| 57 |
qround(x, 2, 6, 10, 14); |
| 58 |
qround(x, 3, 7, 11, 15); |
| 59 |
qround(x, 0, 5, 10, 15); |
| 60 |
qround(x, 1, 6, 11, 12); |
| 61 |
qround(x, 2, 7, 8, 13); |
| 62 |
qround(x, 3, 4, 9, 14); |
| 63 |
} |
| 64 |
|
| 65 |
// add scrambled data to the initial state |
| 66 |
for (size_t i = 0; i < 16; i++) { |
| 67 |
ctx->output[i] = x[i] + ctx->input[i]; |
| 68 |
} |
| 69 |
ctx->output_available = 16; |
| 70 |
|
| 71 |
// increment the counter for the next round |
| 72 |
ctx->input[12] += 1; |
| 73 |
if (ctx->input[12] == 0) { |
| 74 |
ctx->input[13] += 1; |
| 75 |
if (ctx->input[13] == 0) { // and keep increasing into the nonce |
| 76 |
ctx->input[14] += 1; |
| 77 |
} |
| 78 |
} |
| 79 |
} |
| 80 |
|
| 81 |
static uint32_t chacha_next32(mi_random_ctx_t* ctx) { |
| 82 |
if (ctx->output_available <= 0) { |
| 83 |
chacha_block(ctx); |
| 84 |
ctx->output_available = 16; // (assign again to suppress static analysis warning) |
| 85 |
} |
| 86 |
const uint32_t x = ctx->output[16 - ctx->output_available]; |
| 87 |
ctx->output[16 - ctx->output_available] = 0; // reset once the data is handed out |
| 88 |
ctx->output_available--; |
| 89 |
return x; |
| 90 |
} |
| 91 |
|
| 92 |
static inline uint32_t read32(const uint8_t* p, size_t idx32) { |
| 93 |
const size_t i = 4*idx32; |
| 94 |
return ((uint32_t)p[i+0] | (uint32_t)p[i+1] << 8 | (uint32_t)p[i+2] << 16 | (uint32_t)p[i+3] << 24); |
| 95 |
} |
| 96 |
|
| 97 |
static void chacha_init(mi_random_ctx_t* ctx, const uint8_t key[32], uint64_t nonce) |
| 98 |
{ |
| 99 |
// since we only use chacha for randomness (and not encryption) we |
| 100 |
// do not _need_ to read 32-bit values as little endian but we do anyways |
| 101 |
// just for being compatible :-) |
| 102 |
memset(ctx, 0, sizeof(*ctx)); |
| 103 |
for (size_t i = 0; i < 4; i++) { |
| 104 |
const uint8_t* sigma = (uint8_t*)"expand 32-byte k"; |
| 105 |
ctx->input[i] = read32(sigma,i); |
| 106 |
} |
| 107 |
for (size_t i = 0; i < 8; i++) { |
| 108 |
ctx->input[i + 4] = read32(key,i); |
| 109 |
} |
| 110 |
ctx->input[12] = 0; |
| 111 |
ctx->input[13] = 0; |
| 112 |
ctx->input[14] = (uint32_t)nonce; |
| 113 |
ctx->input[15] = (uint32_t)(nonce >> 32); |
| 114 |
} |
| 115 |
|
| 116 |
static void chacha_split(mi_random_ctx_t* ctx, uint64_t nonce, mi_random_ctx_t* ctx_new) { |
| 117 |
memset(ctx_new, 0, sizeof(*ctx_new)); |
| 118 |
_mi_memcpy(ctx_new->input, ctx->input, sizeof(ctx_new->input)); |
| 119 |
ctx_new->input[12] = 0; |
| 120 |
ctx_new->input[13] = 0; |
| 121 |
ctx_new->input[14] = (uint32_t)nonce; |
| 122 |
ctx_new->input[15] = (uint32_t)(nonce >> 32); |
| 123 |
mi_assert_internal(ctx->input[14] != ctx_new->input[14] || ctx->input[15] != ctx_new->input[15]); // do not reuse nonces! |
| 124 |
chacha_block(ctx_new); |
| 125 |
} |
| 126 |
|
| 127 |
|
| 128 |
/* ---------------------------------------------------------------------------- |
| 129 |
Random interface |
| 130 |
-----------------------------------------------------------------------------*/ |
| 131 |
|
| 132 |
#if MI_DEBUG>1 |
| 133 |
static bool mi_random_is_initialized(mi_random_ctx_t* ctx) { |
| 134 |
return (ctx != NULL && ctx->input[0] != 0); |
| 135 |
} |
| 136 |
#endif |
| 137 |
|
| 138 |
void _mi_random_split(mi_random_ctx_t* ctx, mi_random_ctx_t* ctx_new) { |
| 139 |
mi_assert_internal(mi_random_is_initialized(ctx)); |
| 140 |
mi_assert_internal(ctx != ctx_new); |
| 141 |
chacha_split(ctx, (uintptr_t)ctx_new /*nonce*/, ctx_new); |
| 142 |
} |
| 143 |
|
| 144 |
uintptr_t _mi_random_next(mi_random_ctx_t* ctx) { |
| 145 |
mi_assert_internal(mi_random_is_initialized(ctx)); |
| 146 |
#if MI_INTPTR_SIZE <= 4 |
| 147 |
return chacha_next32(ctx); |
| 148 |
#elif MI_INTPTR_SIZE == 8 |
| 149 |
return (((uintptr_t)chacha_next32(ctx) << 32) | chacha_next32(ctx)); |
| 150 |
#else |
| 151 |
# error "define mi_random_next for this platform" |
| 152 |
#endif |
| 153 |
} |
| 154 |
|
| 155 |
|
| 156 |
/* ---------------------------------------------------------------------------- |
| 157 |
To initialize a fresh random context. |
| 158 |
If we cannot get good randomness, we fall back to weak randomness based on a timer and ASLR. |
| 159 |
-----------------------------------------------------------------------------*/ |
| 160 |
|
| 161 |
uintptr_t _mi_os_random_weak(uintptr_t extra_seed) { |
| 162 |
uintptr_t x = (uintptr_t)&_mi_os_random_weak ^ extra_seed; // ASLR makes the address random |
| 163 |
x ^= _mi_prim_clock_now(); |
| 164 |
// and do a few randomization steps |
| 165 |
uintptr_t max = ((x ^ (x >> 17)) & 0x0F) + 1; |
| 166 |
for (uintptr_t i = 0; i < max; i++) { |
| 167 |
x = _mi_random_shuffle(x); |
| 168 |
} |
| 169 |
mi_assert_internal(x != 0); |
| 170 |
return x; |
| 171 |
} |
| 172 |
|
| 173 |
static void mi_random_init_ex(mi_random_ctx_t* ctx, bool use_weak) { |
| 174 |
uint8_t key[32] = {0}; |
| 175 |
if (use_weak || !_mi_prim_random_buf(key, sizeof(key))) { |
| 176 |
// if we fail to get random data from the OS, we fall back to a |
| 177 |
// weak random source based on the current time |
| 178 |
#if !defined(__wasi__) |
| 179 |
if (!use_weak) { _mi_warning_message("unable to use secure randomness\n"); } |
| 180 |
#endif |
| 181 |
uintptr_t x = _mi_os_random_weak(0); |
| 182 |
for (size_t i = 0; i < 8; i++) { // key is eight 32-bit words. |
| 183 |
x = _mi_random_shuffle(x); |
| 184 |
((uint32_t*)key)[i] = (uint32_t)x; |
| 185 |
} |
| 186 |
ctx->weak = true; |
| 187 |
} |
| 188 |
else { |
| 189 |
ctx->weak = false; |
| 190 |
} |
| 191 |
chacha_init(ctx, key, (uintptr_t)ctx /*nonce*/ ); |
| 192 |
} |
| 193 |
|
| 194 |
void _mi_random_init(mi_random_ctx_t* ctx) { |
| 195 |
mi_random_init_ex(ctx, false); |
| 196 |
} |
| 197 |
|
| 198 |
void _mi_random_init_weak(mi_random_ctx_t * ctx) { |
| 199 |
mi_random_init_ex(ctx, true); |
| 200 |
} |
| 201 |
|
| 202 |
void _mi_random_reinit_if_weak(mi_random_ctx_t * ctx) { |
| 203 |
if (ctx->weak) { |
| 204 |
_mi_random_init(ctx); |
| 205 |
} |
| 206 |
} |
| 207 |
|
| 208 |
/* -------------------------------------------------------- |
| 209 |
test vectors from <https://tools.ietf.org/html/rfc8439> |
| 210 |
----------------------------------------------------------- */ |
| 211 |
/* |
| 212 |
static bool array_equals(uint32_t* x, uint32_t* y, size_t n) { |
| 213 |
for (size_t i = 0; i < n; i++) { |
| 214 |
if (x[i] != y[i]) return false; |
| 215 |
} |
| 216 |
return true; |
| 217 |
} |
| 218 |
static void chacha_test(void) |
| 219 |
{ |
| 220 |
uint32_t x[4] = { 0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567 }; |
| 221 |
uint32_t x_out[4] = { 0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb }; |
| 222 |
qround(x, 0, 1, 2, 3); |
| 223 |
mi_assert_internal(array_equals(x, x_out, 4)); |
| 224 |
|
| 225 |
uint32_t y[16] = { |
| 226 |
0x879531e0, 0xc5ecf37d, 0x516461b1, 0xc9a62f8a, |
| 227 |
0x44c20ef3, 0x3390af7f, 0xd9fc690b, 0x2a5f714c, |
| 228 |
0x53372767, 0xb00a5631, 0x974c541a, 0x359e9963, |
| 229 |
0x5c971061, 0x3d631689, 0x2098d9d6, 0x91dbd320 }; |
| 230 |
uint32_t y_out[16] = { |
| 231 |
0x879531e0, 0xc5ecf37d, 0xbdb886dc, 0xc9a62f8a, |
| 232 |
0x44c20ef3, 0x3390af7f, 0xd9fc690b, 0xcfacafd2, |
| 233 |
0xe46bea80, 0xb00a5631, 0x974c541a, 0x359e9963, |
| 234 |
0x5c971061, 0xccc07c79, 0x2098d9d6, 0x91dbd320 }; |
| 235 |
qround(y, 2, 7, 8, 13); |
| 236 |
mi_assert_internal(array_equals(y, y_out, 16)); |
| 237 |
|
| 238 |
mi_random_ctx_t r = { |
| 239 |
{ 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574, |
| 240 |
0x03020100, 0x07060504, 0x0b0a0908, 0x0f0e0d0c, |
| 241 |
0x13121110, 0x17161514, 0x1b1a1918, 0x1f1e1d1c, |
| 242 |
0x00000001, 0x09000000, 0x4a000000, 0x00000000 }, |
| 243 |
{0}, |
| 244 |
0 |
| 245 |
}; |
| 246 |
uint32_t r_out[16] = { |
| 247 |
0xe4e7f110, 0x15593bd1, 0x1fdd0f50, 0xc47120a3, |
| 248 |
0xc7f4d1c7, 0x0368c033, 0x9aaa2204, 0x4e6cd4c3, |
| 249 |
0x466482d2, 0x09aa9f07, 0x05d7c214, 0xa2028bd9, |
| 250 |
0xd19c12b5, 0xb94e16de, 0xe883d0cb, 0x4e3c50a2 }; |
| 251 |
chacha_block(&r); |
| 252 |
mi_assert_internal(array_equals(r.output, r_out, 16)); |
| 253 |
} |
| 254 |
*/ |