1 | /* Copyright (c) 2014, Google Inc. |
2 | * |
3 | * Permission to use, copy, modify, and/or distribute this software for any |
4 | * purpose with or without fee is hereby granted, provided that the above |
5 | * copyright notice and this permission notice appear in all copies. |
6 | * |
7 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
8 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
9 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
10 | * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
11 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
12 | * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
13 | * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ |
14 | |
15 | #include <openssl/rand.h> |
16 | |
17 | #include <assert.h> |
18 | #include <limits.h> |
19 | #include <string.h> |
20 | |
21 | #if defined(BORINGSSL_FIPS) |
22 | #include <unistd.h> |
23 | #endif |
24 | |
25 | #include <openssl/chacha.h> |
26 | #include <openssl/ctrdrbg.h> |
27 | #include <openssl/mem.h> |
28 | |
29 | #include "internal.h" |
30 | #include "fork_detect.h" |
31 | #include "../../internal.h" |
32 | #include "../delocate.h" |
33 | |
34 | |
35 | // It's assumed that the operating system always has an unfailing source of |
36 | // entropy which is accessed via |CRYPTO_sysrand[_for_seed]|. (If the operating |
37 | // system entropy source fails, it's up to |CRYPTO_sysrand| to abort the |
38 | // process—we don't try to handle it.) |
39 | // |
40 | // In addition, the hardware may provide a low-latency RNG. Intel's rdrand |
41 | // instruction is the canonical example of this. When a hardware RNG is |
42 | // available we don't need to worry about an RNG failure arising from fork()ing |
43 | // the process or moving a VM, so we can keep thread-local RNG state and use it |
44 | // as an additional-data input to CTR-DRBG. |
45 | // |
46 | // (We assume that the OS entropy is safe from fork()ing and VM duplication. |
47 | // This might be a bit of a leap of faith, esp on Windows, but there's nothing |
48 | // that we can do about it.) |
49 | |
50 | // kReseedInterval is the number of generate calls made to CTR-DRBG before |
51 | // reseeding. |
52 | static const unsigned kReseedInterval = 4096; |
53 | |
54 | // CRNGT_BLOCK_SIZE is the number of bytes in a “block” for the purposes of the |
55 | // continuous random number generator test in FIPS 140-2, section 4.9.2. |
56 | #define CRNGT_BLOCK_SIZE 16 |
57 | |
58 | // rand_thread_state contains the per-thread state for the RNG. |
59 | struct rand_thread_state { |
60 | CTR_DRBG_STATE drbg; |
61 | uint64_t fork_generation; |
62 | // calls is the number of generate calls made on |drbg| since it was last |
63 | // (re)seeded. This is bound by |kReseedInterval|. |
64 | unsigned calls; |
65 | // last_block_valid is non-zero iff |last_block| contains data from |
66 | // |get_seed_entropy|. |
67 | int last_block_valid; |
68 | |
69 | #if defined(BORINGSSL_FIPS) |
70 | // last_block contains the previous block from |get_seed_entropy|. |
71 | uint8_t last_block[CRNGT_BLOCK_SIZE]; |
72 | // next and prev form a NULL-terminated, double-linked list of all states in |
73 | // a process. |
74 | struct rand_thread_state *next, *prev; |
75 | #endif |
76 | }; |
77 | |
78 | #if defined(BORINGSSL_FIPS) |
79 | // thread_states_list is the head of a linked-list of all |rand_thread_state| |
80 | // objects in the process, one per thread. This is needed because FIPS requires |
81 | // that they be zeroed on process exit, but thread-local destructors aren't |
82 | // called when the whole process is exiting. |
83 | DEFINE_BSS_GET(struct rand_thread_state *, thread_states_list); |
84 | DEFINE_STATIC_MUTEX(thread_states_list_lock); |
85 | DEFINE_STATIC_MUTEX(state_clear_all_lock); |
86 | |
87 | static void rand_thread_state_clear_all(void) __attribute__((destructor)); |
88 | static void rand_thread_state_clear_all(void) { |
89 | CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get()); |
90 | CRYPTO_STATIC_MUTEX_lock_write(state_clear_all_lock_bss_get()); |
91 | for (struct rand_thread_state *cur = *thread_states_list_bss_get(); |
92 | cur != NULL; cur = cur->next) { |
93 | CTR_DRBG_clear(&cur->drbg); |
94 | } |
95 | // The locks are deliberately left locked so that any threads that are still |
96 | // running will hang if they try to call |RAND_bytes|. |
97 | } |
98 | #endif |
99 | |
100 | // rand_thread_state_free frees a |rand_thread_state|. This is called when a |
101 | // thread exits. |
102 | static void rand_thread_state_free(void *state_in) { |
103 | struct rand_thread_state *state = state_in; |
104 | |
105 | if (state_in == NULL) { |
106 | return; |
107 | } |
108 | |
109 | #if defined(BORINGSSL_FIPS) |
110 | CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get()); |
111 | |
112 | if (state->prev != NULL) { |
113 | state->prev->next = state->next; |
114 | } else { |
115 | *thread_states_list_bss_get() = state->next; |
116 | } |
117 | |
118 | if (state->next != NULL) { |
119 | state->next->prev = state->prev; |
120 | } |
121 | |
122 | CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get()); |
123 | |
124 | CTR_DRBG_clear(&state->drbg); |
125 | #endif |
126 | |
127 | OPENSSL_free(ptr: state); |
128 | } |
129 | |
130 | #if defined(OPENSSL_X86_64) && !defined(OPENSSL_NO_ASM) && \ |
131 | !defined(BORINGSSL_UNSAFE_DETERMINISTIC_MODE) |
132 | // rdrand should only be called if either |have_rdrand| or |have_fast_rdrand| |
133 | // returned true. |
134 | static int rdrand(uint8_t *buf, const size_t len) { |
135 | const size_t len_multiple8 = len & ~7; |
136 | if (!CRYPTO_rdrand_multiple8_buf(buf, len: len_multiple8)) { |
137 | return 0; |
138 | } |
139 | const size_t remainder = len - len_multiple8; |
140 | |
141 | if (remainder != 0) { |
142 | assert(remainder < 8); |
143 | |
144 | uint8_t rand_buf[8]; |
145 | if (!CRYPTO_rdrand(out: rand_buf)) { |
146 | return 0; |
147 | } |
148 | OPENSSL_memcpy(dst: buf + len_multiple8, src: rand_buf, n: remainder); |
149 | } |
150 | |
151 | return 1; |
152 | } |
153 | |
154 | #else |
155 | |
156 | static int rdrand(uint8_t *buf, size_t len) { |
157 | return 0; |
158 | } |
159 | |
160 | #endif |
161 | |
162 | #if defined(BORINGSSL_FIPS) |
163 | |
164 | void CRYPTO_get_seed_entropy(uint8_t *out_entropy, size_t out_entropy_len, |
165 | int *out_want_additional_input) { |
166 | *out_want_additional_input = 0; |
167 | if (have_rdrand() && rdrand(out_entropy, out_entropy_len)) { |
168 | *out_want_additional_input = 1; |
169 | } else { |
170 | CRYPTO_sysrand_for_seed(out_entropy, out_entropy_len); |
171 | } |
172 | } |
173 | |
174 | // In passive entropy mode, entropy is supplied from outside of the module via |
175 | // |RAND_load_entropy| and is stored in global instance of the following |
176 | // structure. |
177 | |
178 | struct entropy_buffer { |
179 | // bytes contains entropy suitable for seeding a DRBG. |
180 | uint8_t |
181 | bytes[CRNGT_BLOCK_SIZE + CTR_DRBG_ENTROPY_LEN * BORINGSSL_FIPS_OVERREAD]; |
182 | // bytes_valid indicates the number of bytes of |bytes| that contain valid |
183 | // data. |
184 | size_t bytes_valid; |
185 | // want_additional_input is true if any of the contents of |bytes| were |
186 | // obtained via a method other than from the kernel. In these cases entropy |
187 | // from the kernel is also provided via an additional input to the DRBG. |
188 | int want_additional_input; |
189 | }; |
190 | |
191 | DEFINE_BSS_GET(struct entropy_buffer, entropy_buffer); |
192 | DEFINE_STATIC_MUTEX(entropy_buffer_lock); |
193 | |
194 | void RAND_load_entropy(const uint8_t *entropy, size_t entropy_len, |
195 | int want_additional_input) { |
196 | struct entropy_buffer *const buffer = entropy_buffer_bss_get(); |
197 | |
198 | CRYPTO_STATIC_MUTEX_lock_write(entropy_buffer_lock_bss_get()); |
199 | const size_t space = sizeof(buffer->bytes) - buffer->bytes_valid; |
200 | if (entropy_len > space) { |
201 | entropy_len = space; |
202 | } |
203 | |
204 | OPENSSL_memcpy(&buffer->bytes[buffer->bytes_valid], entropy, entropy_len); |
205 | buffer->bytes_valid += entropy_len; |
206 | buffer->want_additional_input |= |
207 | want_additional_input && (entropy_len != 0); |
208 | CRYPTO_STATIC_MUTEX_unlock_write(entropy_buffer_lock_bss_get()); |
209 | } |
210 | |
211 | // get_seed_entropy fills |out_entropy_len| bytes of |out_entropy| from the |
212 | // global |entropy_buffer|. |
213 | static void get_seed_entropy(uint8_t *out_entropy, size_t out_entropy_len, |
214 | int *out_want_additional_input) { |
215 | struct entropy_buffer *const buffer = entropy_buffer_bss_get(); |
216 | if (out_entropy_len > sizeof(buffer->bytes)) { |
217 | abort(); |
218 | } |
219 | |
220 | CRYPTO_STATIC_MUTEX_lock_write(entropy_buffer_lock_bss_get()); |
221 | while (buffer->bytes_valid < out_entropy_len) { |
222 | CRYPTO_STATIC_MUTEX_unlock_write(entropy_buffer_lock_bss_get()); |
223 | RAND_need_entropy(out_entropy_len - buffer->bytes_valid); |
224 | CRYPTO_STATIC_MUTEX_lock_write(entropy_buffer_lock_bss_get()); |
225 | } |
226 | |
227 | *out_want_additional_input = buffer->want_additional_input; |
228 | OPENSSL_memcpy(out_entropy, buffer->bytes, out_entropy_len); |
229 | OPENSSL_memmove(buffer->bytes, &buffer->bytes[out_entropy_len], |
230 | buffer->bytes_valid - out_entropy_len); |
231 | buffer->bytes_valid -= out_entropy_len; |
232 | if (buffer->bytes_valid == 0) { |
233 | buffer->want_additional_input = 0; |
234 | } |
235 | |
236 | CRYPTO_STATIC_MUTEX_unlock_write(entropy_buffer_lock_bss_get()); |
237 | } |
238 | |
239 | // rand_get_seed fills |seed| with entropy. In some cases, it will additionally |
240 | // fill |additional_input| with entropy to supplement |seed|. It sets |
241 | // |*out_additional_input_len| to the number of extra bytes. |
242 | static void rand_get_seed(struct rand_thread_state *state, |
243 | uint8_t seed[CTR_DRBG_ENTROPY_LEN], |
244 | uint8_t additional_input[CTR_DRBG_ENTROPY_LEN], |
245 | size_t *out_additional_input_len) { |
246 | uint8_t entropy_bytes[sizeof(state->last_block) + |
247 | CTR_DRBG_ENTROPY_LEN * BORINGSSL_FIPS_OVERREAD]; |
248 | uint8_t *entropy = entropy_bytes; |
249 | size_t entropy_len = sizeof(entropy_bytes); |
250 | |
251 | if (state->last_block_valid) { |
252 | // No need to fill |state->last_block| with entropy from the read. |
253 | entropy += sizeof(state->last_block); |
254 | entropy_len -= sizeof(state->last_block); |
255 | } |
256 | |
257 | int want_additional_input; |
258 | get_seed_entropy(entropy, entropy_len, &want_additional_input); |
259 | |
260 | if (!state->last_block_valid) { |
261 | OPENSSL_memcpy(state->last_block, entropy, sizeof(state->last_block)); |
262 | entropy += sizeof(state->last_block); |
263 | entropy_len -= sizeof(state->last_block); |
264 | } |
265 | |
266 | // See FIPS 140-2, section 4.9.2. This is the “continuous random number |
267 | // generator test” which causes the program to randomly abort. Hopefully the |
268 | // rate of failure is small enough not to be a problem in practice. |
269 | if (CRYPTO_memcmp(state->last_block, entropy, sizeof(state->last_block)) == |
270 | 0) { |
271 | fprintf(stderr, "CRNGT failed.\n" ); |
272 | BORINGSSL_FIPS_abort(); |
273 | } |
274 | |
275 | assert(entropy_len % CRNGT_BLOCK_SIZE == 0); |
276 | for (size_t i = CRNGT_BLOCK_SIZE; i < entropy_len; i += CRNGT_BLOCK_SIZE) { |
277 | if (CRYPTO_memcmp(entropy + i - CRNGT_BLOCK_SIZE, entropy + i, |
278 | CRNGT_BLOCK_SIZE) == 0) { |
279 | fprintf(stderr, "CRNGT failed.\n" ); |
280 | BORINGSSL_FIPS_abort(); |
281 | } |
282 | } |
283 | OPENSSL_memcpy(state->last_block, entropy + entropy_len - CRNGT_BLOCK_SIZE, |
284 | CRNGT_BLOCK_SIZE); |
285 | |
286 | assert(entropy_len == BORINGSSL_FIPS_OVERREAD * CTR_DRBG_ENTROPY_LEN); |
287 | OPENSSL_memcpy(seed, entropy, CTR_DRBG_ENTROPY_LEN); |
288 | |
289 | for (size_t i = 1; i < BORINGSSL_FIPS_OVERREAD; i++) { |
290 | for (size_t j = 0; j < CTR_DRBG_ENTROPY_LEN; j++) { |
291 | seed[j] ^= entropy[CTR_DRBG_ENTROPY_LEN * i + j]; |
292 | } |
293 | } |
294 | |
295 | // If we used something other than system entropy then also |
296 | // opportunistically read from the system. This avoids solely relying on the |
297 | // hardware once the entropy pool has been initialized. |
298 | *out_additional_input_len = 0; |
299 | if (want_additional_input && |
300 | CRYPTO_sysrand_if_available(additional_input, CTR_DRBG_ENTROPY_LEN)) { |
301 | *out_additional_input_len = CTR_DRBG_ENTROPY_LEN; |
302 | } |
303 | } |
304 | |
305 | #else |
306 | |
307 | // rand_get_seed fills |seed| with entropy. In some cases, it will additionally |
308 | // fill |additional_input| with entropy to supplement |seed|. It sets |
309 | // |*out_additional_input_len| to the number of extra bytes. |
310 | static void rand_get_seed(struct rand_thread_state *state, |
311 | uint8_t seed[CTR_DRBG_ENTROPY_LEN], |
312 | uint8_t additional_input[CTR_DRBG_ENTROPY_LEN], |
313 | size_t *out_additional_input_len) { |
314 | // If not in FIPS mode, we don't overread from the system entropy source and |
315 | // we don't depend only on the hardware RDRAND. |
316 | CRYPTO_sysrand_for_seed(buf: seed, CTR_DRBG_ENTROPY_LEN); |
317 | *out_additional_input_len = 0; |
318 | } |
319 | |
320 | #endif |
321 | |
322 | void RAND_bytes_with_additional_data(uint8_t *out, size_t out_len, |
323 | const uint8_t user_additional_data[32]) { |
324 | if (out_len == 0) { |
325 | return; |
326 | } |
327 | |
328 | const uint64_t fork_generation = CRYPTO_get_fork_generation(); |
329 | |
330 | // Additional data is mixed into every CTR-DRBG call to protect, as best we |
331 | // can, against forks & VM clones. We do not over-read this information and |
332 | // don't reseed with it so, from the point of view of FIPS, this doesn't |
333 | // provide “prediction resistance”. But, in practice, it does. |
334 | uint8_t additional_data[32]; |
335 | // Intel chips have fast RDRAND instructions while, in other cases, RDRAND can |
336 | // be _slower_ than a system call. |
337 | if (!have_fast_rdrand() || |
338 | !rdrand(buf: additional_data, len: sizeof(additional_data))) { |
339 | // Without a hardware RNG to save us from address-space duplication, the OS |
340 | // entropy is used. This can be expensive (one read per |RAND_bytes| call) |
341 | // and so is disabled when we have fork detection, or if the application has |
342 | // promised not to fork. |
343 | if (fork_generation != 0 || rand_fork_unsafe_buffering_enabled()) { |
344 | OPENSSL_memset(dst: additional_data, c: 0, n: sizeof(additional_data)); |
345 | } else if (!have_rdrand()) { |
346 | // No alternative so block for OS entropy. |
347 | CRYPTO_sysrand(buf: additional_data, len: sizeof(additional_data)); |
348 | } else if (!CRYPTO_sysrand_if_available(buf: additional_data, |
349 | len: sizeof(additional_data)) && |
350 | !rdrand(buf: additional_data, len: sizeof(additional_data))) { |
351 | // RDRAND failed: block for OS entropy. |
352 | CRYPTO_sysrand(buf: additional_data, len: sizeof(additional_data)); |
353 | } |
354 | } |
355 | |
356 | for (size_t i = 0; i < sizeof(additional_data); i++) { |
357 | additional_data[i] ^= user_additional_data[i]; |
358 | } |
359 | |
360 | struct rand_thread_state stack_state; |
361 | struct rand_thread_state *state = |
362 | CRYPTO_get_thread_local(value: OPENSSL_THREAD_LOCAL_RAND); |
363 | |
364 | if (state == NULL) { |
365 | state = OPENSSL_malloc(size: sizeof(struct rand_thread_state)); |
366 | if (state == NULL || |
367 | !CRYPTO_set_thread_local(index: OPENSSL_THREAD_LOCAL_RAND, value: state, |
368 | destructor: rand_thread_state_free)) { |
369 | // If the system is out of memory, use an ephemeral state on the |
370 | // stack. |
371 | state = &stack_state; |
372 | } |
373 | |
374 | state->last_block_valid = 0; |
375 | uint8_t seed[CTR_DRBG_ENTROPY_LEN]; |
376 | uint8_t personalization[CTR_DRBG_ENTROPY_LEN] = {0}; |
377 | size_t personalization_len = 0; |
378 | rand_get_seed(state, seed, additional_input: personalization, out_additional_input_len: &personalization_len); |
379 | |
380 | if (!CTR_DRBG_init(drbg: &state->drbg, entropy: seed, personalization, |
381 | personalization_len)) { |
382 | abort(); |
383 | } |
384 | state->calls = 0; |
385 | state->fork_generation = fork_generation; |
386 | |
387 | #if defined(BORINGSSL_FIPS) |
388 | if (state != &stack_state) { |
389 | CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get()); |
390 | struct rand_thread_state **states_list = thread_states_list_bss_get(); |
391 | state->next = *states_list; |
392 | if (state->next != NULL) { |
393 | state->next->prev = state; |
394 | } |
395 | state->prev = NULL; |
396 | *states_list = state; |
397 | CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get()); |
398 | } |
399 | #endif |
400 | } |
401 | |
402 | if (state->calls >= kReseedInterval || |
403 | state->fork_generation != fork_generation) { |
404 | uint8_t seed[CTR_DRBG_ENTROPY_LEN]; |
405 | uint8_t reseed_additional_data[CTR_DRBG_ENTROPY_LEN] = {0}; |
406 | size_t reseed_additional_data_len = 0; |
407 | rand_get_seed(state, seed, additional_input: reseed_additional_data, |
408 | out_additional_input_len: &reseed_additional_data_len); |
409 | #if defined(BORINGSSL_FIPS) |
410 | // Take a read lock around accesses to |state->drbg|. This is needed to |
411 | // avoid returning bad entropy if we race with |
412 | // |rand_thread_state_clear_all|. |
413 | CRYPTO_STATIC_MUTEX_lock_read(state_clear_all_lock_bss_get()); |
414 | #endif |
415 | if (!CTR_DRBG_reseed(drbg: &state->drbg, entropy: seed, additional_data: reseed_additional_data, |
416 | additional_data_len: reseed_additional_data_len)) { |
417 | abort(); |
418 | } |
419 | state->calls = 0; |
420 | state->fork_generation = fork_generation; |
421 | } else { |
422 | #if defined(BORINGSSL_FIPS) |
423 | CRYPTO_STATIC_MUTEX_lock_read(state_clear_all_lock_bss_get()); |
424 | #endif |
425 | } |
426 | |
427 | int first_call = 1; |
428 | while (out_len > 0) { |
429 | size_t todo = out_len; |
430 | if (todo > CTR_DRBG_MAX_GENERATE_LENGTH) { |
431 | todo = CTR_DRBG_MAX_GENERATE_LENGTH; |
432 | } |
433 | |
434 | if (!CTR_DRBG_generate(drbg: &state->drbg, out, out_len: todo, additional_data, |
435 | additional_data_len: first_call ? sizeof(additional_data) : 0)) { |
436 | abort(); |
437 | } |
438 | |
439 | out += todo; |
440 | out_len -= todo; |
441 | // Though we only check before entering the loop, this cannot add enough to |
442 | // overflow a |size_t|. |
443 | state->calls++; |
444 | first_call = 0; |
445 | } |
446 | |
447 | if (state == &stack_state) { |
448 | CTR_DRBG_clear(drbg: &state->drbg); |
449 | } |
450 | |
451 | #if defined(BORINGSSL_FIPS) |
452 | CRYPTO_STATIC_MUTEX_unlock_read(state_clear_all_lock_bss_get()); |
453 | #endif |
454 | } |
455 | |
456 | int RAND_bytes(uint8_t *out, size_t out_len) { |
457 | static const uint8_t kZeroAdditionalData[32] = {0}; |
458 | RAND_bytes_with_additional_data(out, out_len, user_additional_data: kZeroAdditionalData); |
459 | return 1; |
460 | } |
461 | |
462 | int RAND_pseudo_bytes(uint8_t *buf, size_t len) { |
463 | return RAND_bytes(out: buf, out_len: len); |
464 | } |
465 | |
466 | void RAND_get_system_entropy_for_custom_prng(uint8_t *buf, size_t len) { |
467 | if (len > 256) { |
468 | abort(); |
469 | } |
470 | CRYPTO_sysrand_for_seed(buf, len); |
471 | } |
472 | |