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