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