• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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