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
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 // |CRYPTO_sysrand_for_seed|.
67 int last_block_valid;
68
69 #if defined(BORINGSSL_FIPS)
70 // last_block contains the previous block from |CRYPTO_sysrand_for_seed|.
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
86 static void rand_thread_state_clear_all(void) __attribute__((destructor));
rand_thread_state_clear_all(void)87 static void rand_thread_state_clear_all(void) {
88 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
89 for (struct rand_thread_state *cur = *thread_states_list_bss_get();
90 cur != NULL; cur = cur->next) {
91 CTR_DRBG_clear(&cur->drbg);
92 }
93 // |thread_states_list_lock is deliberately left locked so that any threads
94 // that are still running will hang if they try to call |RAND_bytes|.
95 }
96 #endif
97
98 // rand_thread_state_free frees a |rand_thread_state|. This is called when a
99 // thread exits.
rand_thread_state_free(void * state_in)100 static void rand_thread_state_free(void *state_in) {
101 struct rand_thread_state *state = state_in;
102
103 if (state_in == NULL) {
104 return;
105 }
106
107 #if defined(BORINGSSL_FIPS)
108 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
109
110 if (state->prev != NULL) {
111 state->prev->next = state->next;
112 } else {
113 *thread_states_list_bss_get() = state->next;
114 }
115
116 if (state->next != NULL) {
117 state->next->prev = state->prev;
118 }
119
120 CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get());
121
122 CTR_DRBG_clear(&state->drbg);
123 #endif
124
125 OPENSSL_free(state);
126 }
127
128 #if defined(OPENSSL_X86_64) && !defined(OPENSSL_NO_ASM) && \
129 !defined(BORINGSSL_UNSAFE_DETERMINISTIC_MODE)
130 // rdrand should only be called if either |have_rdrand| or |have_fast_rdrand|
131 // returned true.
rdrand(uint8_t * buf,const size_t len)132 static int rdrand(uint8_t *buf, const size_t len) {
133 const size_t len_multiple8 = len & ~7;
134 if (!CRYPTO_rdrand_multiple8_buf(buf, len_multiple8)) {
135 return 0;
136 }
137 const size_t remainder = len - len_multiple8;
138
139 if (remainder != 0) {
140 assert(remainder < 8);
141
142 uint8_t rand_buf[8];
143 if (!CRYPTO_rdrand(rand_buf)) {
144 return 0;
145 }
146 OPENSSL_memcpy(buf + len_multiple8, rand_buf, remainder);
147 }
148
149 #if defined(BORINGSSL_FIPS_BREAK_CRNG)
150 // This breaks the "continuous random number generator test" defined in FIPS
151 // 140-2, section 4.9.2, and implemented in rand_get_seed().
152 OPENSSL_memset(buf, 0, len);
153 #endif
154
155 return 1;
156 }
157
158 #else
159
rdrand(uint8_t * buf,size_t len)160 static int rdrand(uint8_t *buf, size_t len) {
161 return 0;
162 }
163
164 #endif
165
166 #if defined(BORINGSSL_FIPS)
167
rand_get_seed(struct rand_thread_state * state,uint8_t seed[CTR_DRBG_ENTROPY_LEN])168 static void rand_get_seed(struct rand_thread_state *state,
169 uint8_t seed[CTR_DRBG_ENTROPY_LEN]) {
170 if (!state->last_block_valid) {
171 if (!have_rdrand() ||
172 !rdrand(state->last_block, sizeof(state->last_block))) {
173 CRYPTO_sysrand_for_seed(state->last_block, sizeof(state->last_block));
174 }
175 state->last_block_valid = 1;
176 }
177
178 // We overread from /dev/urandom or RDRAND by a factor of 10 and XOR to
179 // whiten.
180 #define FIPS_OVERREAD 10
181 uint8_t entropy[CTR_DRBG_ENTROPY_LEN * FIPS_OVERREAD];
182
183 int used_rdrand = have_rdrand() && rdrand(entropy, sizeof(entropy));
184 if (!used_rdrand) {
185 CRYPTO_sysrand_for_seed(entropy, sizeof(entropy));
186 }
187
188 // See FIPS 140-2, section 4.9.2. This is the “continuous random number
189 // generator test” which causes the program to randomly abort. Hopefully the
190 // rate of failure is small enough not to be a problem in practice.
191 if (CRYPTO_memcmp(state->last_block, entropy, CRNGT_BLOCK_SIZE) == 0) {
192 fprintf(stderr, "CRNGT failed.\n");
193 BORINGSSL_FIPS_abort();
194 }
195
196 for (size_t i = CRNGT_BLOCK_SIZE; i < sizeof(entropy);
197 i += CRNGT_BLOCK_SIZE) {
198 if (CRYPTO_memcmp(entropy + i - CRNGT_BLOCK_SIZE, entropy + i,
199 CRNGT_BLOCK_SIZE) == 0) {
200 fprintf(stderr, "CRNGT failed.\n");
201 BORINGSSL_FIPS_abort();
202 }
203 }
204 OPENSSL_memcpy(state->last_block,
205 entropy + sizeof(entropy) - CRNGT_BLOCK_SIZE,
206 CRNGT_BLOCK_SIZE);
207
208 OPENSSL_memcpy(seed, entropy, CTR_DRBG_ENTROPY_LEN);
209
210 for (size_t i = 1; i < FIPS_OVERREAD; i++) {
211 for (size_t j = 0; j < CTR_DRBG_ENTROPY_LEN; j++) {
212 seed[j] ^= entropy[CTR_DRBG_ENTROPY_LEN * i + j];
213 }
214 }
215
216 #if defined(OPENSSL_URANDOM)
217 // If we used RDRAND, also opportunistically read from the system. This avoids
218 // solely relying on the hardware once the entropy pool has been initialized.
219 if (used_rdrand) {
220 CRYPTO_sysrand_if_available(entropy, CTR_DRBG_ENTROPY_LEN);
221 for (size_t i = 0; i < CTR_DRBG_ENTROPY_LEN; i++) {
222 seed[i] ^= entropy[i];
223 }
224 }
225 #endif
226 }
227
228 #else
229
rand_get_seed(struct rand_thread_state * state,uint8_t seed[CTR_DRBG_ENTROPY_LEN])230 static void rand_get_seed(struct rand_thread_state *state,
231 uint8_t seed[CTR_DRBG_ENTROPY_LEN]) {
232 // If not in FIPS mode, we don't overread from the system entropy source and
233 // we don't depend only on the hardware RDRAND.
234 CRYPTO_sysrand(seed, CTR_DRBG_ENTROPY_LEN);
235 }
236
237 #endif
238
RAND_bytes_with_additional_data(uint8_t * out,size_t out_len,const uint8_t user_additional_data[32])239 void RAND_bytes_with_additional_data(uint8_t *out, size_t out_len,
240 const uint8_t user_additional_data[32]) {
241 if (out_len == 0) {
242 return;
243 }
244
245 const uint64_t fork_generation = CRYPTO_get_fork_generation();
246
247 // Additional data is mixed into every CTR-DRBG call to protect, as best we
248 // can, against forks & VM clones. We do not over-read this information and
249 // don't reseed with it so, from the point of view of FIPS, this doesn't
250 // provide “prediction resistance”. But, in practice, it does.
251 uint8_t additional_data[32];
252 // Intel chips have fast RDRAND instructions while, in other cases, RDRAND can
253 // be _slower_ than a system call.
254 if (!have_fast_rdrand() ||
255 !rdrand(additional_data, sizeof(additional_data))) {
256 // Without a hardware RNG to save us from address-space duplication, the OS
257 // entropy is used. This can be expensive (one read per |RAND_bytes| call)
258 // and so is disabled when we have fork detection, or if the application has
259 // promised not to fork.
260 if (fork_generation != 0 || rand_fork_unsafe_buffering_enabled()) {
261 OPENSSL_memset(additional_data, 0, sizeof(additional_data));
262 } else if (!have_rdrand()) {
263 // No alternative so block for OS entropy.
264 CRYPTO_sysrand(additional_data, sizeof(additional_data));
265 } else if (!CRYPTO_sysrand_if_available(additional_data,
266 sizeof(additional_data)) &&
267 !rdrand(additional_data, sizeof(additional_data))) {
268 // RDRAND failed: block for OS entropy.
269 CRYPTO_sysrand(additional_data, sizeof(additional_data));
270 }
271 }
272
273 for (size_t i = 0; i < sizeof(additional_data); i++) {
274 additional_data[i] ^= user_additional_data[i];
275 }
276
277 struct rand_thread_state stack_state;
278 struct rand_thread_state *state =
279 CRYPTO_get_thread_local(OPENSSL_THREAD_LOCAL_RAND);
280
281 if (state == NULL) {
282 state = OPENSSL_malloc(sizeof(struct rand_thread_state));
283 if (state == NULL ||
284 !CRYPTO_set_thread_local(OPENSSL_THREAD_LOCAL_RAND, state,
285 rand_thread_state_free)) {
286 // If the system is out of memory, use an ephemeral state on the
287 // stack.
288 state = &stack_state;
289 }
290
291 state->last_block_valid = 0;
292 uint8_t seed[CTR_DRBG_ENTROPY_LEN];
293 rand_get_seed(state, seed);
294 if (!CTR_DRBG_init(&state->drbg, seed, NULL, 0)) {
295 abort();
296 }
297 state->calls = 0;
298 state->fork_generation = fork_generation;
299
300 #if defined(BORINGSSL_FIPS)
301 if (state != &stack_state) {
302 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
303 struct rand_thread_state **states_list = thread_states_list_bss_get();
304 state->next = *states_list;
305 if (state->next != NULL) {
306 state->next->prev = state;
307 }
308 state->prev = NULL;
309 *states_list = state;
310 CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get());
311 }
312 #endif
313 }
314
315 if (state->calls >= kReseedInterval ||
316 state->fork_generation != fork_generation) {
317 uint8_t seed[CTR_DRBG_ENTROPY_LEN];
318 rand_get_seed(state, seed);
319 #if defined(BORINGSSL_FIPS)
320 // Take a read lock around accesses to |state->drbg|. This is needed to
321 // avoid returning bad entropy if we race with
322 // |rand_thread_state_clear_all|.
323 //
324 // This lock must be taken after any calls to |CRYPTO_sysrand| to avoid a
325 // bug on ppc64le. glibc may implement pthread locks by wrapping user code
326 // in a hardware transaction, but, on some older versions of glibc and the
327 // kernel, syscalls made with |syscall| did not abort the transaction.
328 CRYPTO_STATIC_MUTEX_lock_read(thread_states_list_lock_bss_get());
329 #endif
330 if (!CTR_DRBG_reseed(&state->drbg, seed, NULL, 0)) {
331 abort();
332 }
333 state->calls = 0;
334 state->fork_generation = fork_generation;
335 } else {
336 #if defined(BORINGSSL_FIPS)
337 CRYPTO_STATIC_MUTEX_lock_read(thread_states_list_lock_bss_get());
338 #endif
339 }
340
341 int first_call = 1;
342 while (out_len > 0) {
343 size_t todo = out_len;
344 if (todo > CTR_DRBG_MAX_GENERATE_LENGTH) {
345 todo = CTR_DRBG_MAX_GENERATE_LENGTH;
346 }
347
348 if (!CTR_DRBG_generate(&state->drbg, out, todo, additional_data,
349 first_call ? sizeof(additional_data) : 0)) {
350 abort();
351 }
352
353 out += todo;
354 out_len -= todo;
355 // Though we only check before entering the loop, this cannot add enough to
356 // overflow a |size_t|.
357 state->calls++;
358 first_call = 0;
359 }
360
361 if (state == &stack_state) {
362 CTR_DRBG_clear(&state->drbg);
363 }
364
365 #if defined(BORINGSSL_FIPS)
366 CRYPTO_STATIC_MUTEX_unlock_read(thread_states_list_lock_bss_get());
367 #endif
368 }
369
RAND_bytes(uint8_t * out,size_t out_len)370 int RAND_bytes(uint8_t *out, size_t out_len) {
371 static const uint8_t kZeroAdditionalData[32] = {0};
372 RAND_bytes_with_additional_data(out, out_len, kZeroAdditionalData);
373 return 1;
374 }
375
RAND_pseudo_bytes(uint8_t * buf,size_t len)376 int RAND_pseudo_bytes(uint8_t *buf, size_t len) {
377 return RAND_bytes(buf, len);
378 }
379