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
rotl(uint32_t x,uint32_t shift)36 static inline uint32_t rotl(uint32_t x, uint32_t shift) {
37 return (x << shift) | (x >> (32 - shift));
38 }
39
qround(uint32_t x[16],size_t a,size_t b,size_t c,size_t d)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
chacha_block(mi_random_ctx_t * ctx)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
chacha_next32(mi_random_ctx_t * ctx)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
read32(const uint8_t * p,size_t idx32)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
chacha_init(mi_random_ctx_t * ctx,const uint8_t key[32],uint64_t nonce)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
chacha_split(mi_random_ctx_t * ctx,uint64_t nonce,mi_random_ctx_t * ctx_new)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
mi_random_is_initialized(mi_random_ctx_t * ctx)133 static bool mi_random_is_initialized(mi_random_ctx_t* ctx) {
134 return (ctx != NULL && ctx->input[0] != 0);
135 }
136 #endif
137
_mi_random_split(mi_random_ctx_t * ctx,mi_random_ctx_t * ctx_new)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
_mi_random_next(mi_random_ctx_t * ctx)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
_mi_os_random_weak(uintptr_t extra_seed)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
mi_random_init_ex(mi_random_ctx_t * ctx,bool use_weak)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
_mi_random_init(mi_random_ctx_t * ctx)194 void _mi_random_init(mi_random_ctx_t* ctx) {
195 mi_random_init_ex(ctx, false);
196 }
197
_mi_random_init_weak(mi_random_ctx_t * ctx)198 void _mi_random_init_weak(mi_random_ctx_t * ctx) {
199 mi_random_init_ex(ctx, true);
200 }
201
_mi_random_reinit_if_weak(mi_random_ctx_t * ctx)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 */
255