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 "../../internal.h"
31 #include "../delocate.h"
32
33
34 /* It's assumed that the operating system always has an unfailing source of
35 * entropy which is accessed via |CRYPTO_sysrand|. (If the operating system
36 * entropy source fails, it's up to |CRYPTO_sysrand| to abort the process—we
37 * don't try to handle it.)
38 *
39 * In addition, the hardware may provide a low-latency RNG. Intel's rdrand
40 * instruction is the canonical example of this. When a hardware RNG is
41 * available we don't need to worry about an RNG failure arising from fork()ing
42 * the process or moving a VM, so we can keep thread-local RNG state and use it
43 * as an additional-data input to CTR-DRBG.
44 *
45 * (We assume that the OS entropy is safe from fork()ing and VM duplication.
46 * This might be a bit of a leap of faith, esp on Windows, but there's nothing
47 * that we can do about it.) */
48
49 /* kReseedInterval is the number of generate calls made to CTR-DRBG before
50 * reseeding. */
51 static const unsigned kReseedInterval = 4096;
52
53 /* CRNGT_BLOCK_SIZE is the number of bytes in a “block” for the purposes of the
54 * continuous random number generator test in FIPS 140-2, section 4.9.2. */
55 #define CRNGT_BLOCK_SIZE 16
56
57 /* rand_thread_state contains the per-thread state for the RNG. */
58 struct rand_thread_state {
59 CTR_DRBG_STATE drbg;
60 /* calls is the number of generate calls made on |drbg| since it was last
61 * (re)seeded. This is bound by |kReseedInterval|. */
62 unsigned calls;
63 /* last_block_valid is non-zero iff |last_block| contains data from
64 * |CRYPTO_sysrand|. */
65 int last_block_valid;
66
67 #if defined(BORINGSSL_FIPS)
68 /* last_block contains the previous block from |CRYPTO_sysrand|. */
69 uint8_t last_block[CRNGT_BLOCK_SIZE];
70 /* next and prev form a NULL-terminated, double-linked list of all states in
71 * a process. */
72 struct rand_thread_state *next, *prev;
73 #endif
74 };
75
76 #if defined(BORINGSSL_FIPS)
77 /* thread_states_list is the head of a linked-list of all |rand_thread_state|
78 * objects in the process, one per thread. This is needed because FIPS requires
79 * that they be zeroed on process exit, but thread-local destructors aren't
80 * called when the whole process is exiting. */
81 DEFINE_BSS_GET(struct rand_thread_state *, thread_states_list);
82 DEFINE_STATIC_MUTEX(thread_states_list_lock);
83
84 static void rand_thread_state_clear_all(void) __attribute__((destructor));
rand_thread_state_clear_all(void)85 static void rand_thread_state_clear_all(void) {
86 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
87 for (struct rand_thread_state *cur = *thread_states_list_bss_get();
88 cur != NULL; cur = cur->next) {
89 CTR_DRBG_clear(&cur->drbg);
90 }
91 /* |thread_states_list_lock is deliberately left locked so that any threads
92 * that are still running will hang if they try to call |RAND_bytes|. */
93 }
94 #endif
95
96 /* rand_thread_state_free frees a |rand_thread_state|. This is called when a
97 * thread exits. */
rand_thread_state_free(void * state_in)98 static void rand_thread_state_free(void *state_in) {
99 struct rand_thread_state *state = state_in;
100
101 if (state_in == NULL) {
102 return;
103 }
104
105 #if defined(BORINGSSL_FIPS)
106 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
107
108 if (state->prev != NULL) {
109 state->prev->next = state->next;
110 } else {
111 *thread_states_list_bss_get() = state->next;
112 }
113
114 if (state->next != NULL) {
115 state->next->prev = state->prev;
116 }
117
118 CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get());
119
120 CTR_DRBG_clear(&state->drbg);
121 #endif
122
123 OPENSSL_free(state);
124 }
125
126 #if defined(OPENSSL_X86_64) && !defined(OPENSSL_NO_ASM) && \
127 !defined(BORINGSSL_UNSAFE_DETERMINISTIC_MODE)
128
129 /* These functions are defined in asm/rdrand-x86_64.pl */
130 extern int CRYPTO_rdrand(uint8_t out[8]);
131 extern int CRYPTO_rdrand_multiple8_buf(uint8_t *buf, size_t len);
132
have_rdrand(void)133 static int have_rdrand(void) {
134 return (OPENSSL_ia32cap_get()[1] & (1u << 30)) != 0;
135 }
136
hwrand(uint8_t * buf,const size_t len)137 static int hwrand(uint8_t *buf, const size_t len) {
138 if (!have_rdrand()) {
139 return 0;
140 }
141
142 const size_t len_multiple8 = len & ~7;
143 if (!CRYPTO_rdrand_multiple8_buf(buf, len_multiple8)) {
144 return 0;
145 }
146 const size_t remainder = len - len_multiple8;
147
148 if (remainder != 0) {
149 assert(remainder < 8);
150
151 uint8_t rand_buf[8];
152 if (!CRYPTO_rdrand(rand_buf)) {
153 return 0;
154 }
155 OPENSSL_memcpy(buf + len_multiple8, rand_buf, remainder);
156 }
157
158 #if defined(BORINGSSL_FIPS_BREAK_CRNG)
159 // This breaks the "continuous random number generator test" defined in FIPS
160 // 140-2, section 4.9.2, and implemented in rand_get_seed().
161 OPENSSL_memset(buf, 0, len);
162 #endif
163
164 return 1;
165 }
166
167 #else
168
hwrand(uint8_t * buf,size_t len)169 static int hwrand(uint8_t *buf, size_t len) {
170 return 0;
171 }
172
173 #endif
174
175 #if defined(BORINGSSL_FIPS)
176
rand_get_seed(struct rand_thread_state * state,uint8_t seed[CTR_DRBG_ENTROPY_LEN])177 static void rand_get_seed(struct rand_thread_state *state,
178 uint8_t seed[CTR_DRBG_ENTROPY_LEN]) {
179 if (!state->last_block_valid) {
180 if (!hwrand(state->last_block, sizeof(state->last_block))) {
181 CRYPTO_sysrand(state->last_block, sizeof(state->last_block));
182 }
183 state->last_block_valid = 1;
184 }
185
186 /* We overread from /dev/urandom or RDRAND by a factor of 10 and XOR to
187 * whiten. */
188 #define FIPS_OVERREAD 10
189 uint8_t entropy[CTR_DRBG_ENTROPY_LEN * FIPS_OVERREAD];
190
191 if (!hwrand(entropy, sizeof(entropy))) {
192 CRYPTO_sysrand(entropy, sizeof(entropy));
193 }
194
195 /* See FIPS 140-2, section 4.9.2. This is the “continuous random number
196 * generator test” which causes the program to randomly abort. Hopefully the
197 * rate of failure is small enough not to be a problem in practice. */
198 if (CRYPTO_memcmp(state->last_block, entropy, CRNGT_BLOCK_SIZE) == 0) {
199 printf("CRNGT failed.\n");
200 BORINGSSL_FIPS_abort();
201 }
202
203 for (size_t i = CRNGT_BLOCK_SIZE; i < sizeof(entropy);
204 i += CRNGT_BLOCK_SIZE) {
205 if (CRYPTO_memcmp(entropy + i - CRNGT_BLOCK_SIZE, entropy + i,
206 CRNGT_BLOCK_SIZE) == 0) {
207 printf("CRNGT failed.\n");
208 BORINGSSL_FIPS_abort();
209 }
210 }
211 OPENSSL_memcpy(state->last_block,
212 entropy + sizeof(entropy) - CRNGT_BLOCK_SIZE,
213 CRNGT_BLOCK_SIZE);
214
215 OPENSSL_memcpy(seed, entropy, CTR_DRBG_ENTROPY_LEN);
216
217 for (size_t i = 1; i < FIPS_OVERREAD; i++) {
218 for (size_t j = 0; j < CTR_DRBG_ENTROPY_LEN; j++) {
219 seed[j] ^= entropy[CTR_DRBG_ENTROPY_LEN * i + j];
220 }
221 }
222 }
223
224 #else
225
rand_get_seed(struct rand_thread_state * state,uint8_t seed[CTR_DRBG_ENTROPY_LEN])226 static void rand_get_seed(struct rand_thread_state *state,
227 uint8_t seed[CTR_DRBG_ENTROPY_LEN]) {
228 /* If not in FIPS mode, we don't overread from the system entropy source and
229 * we don't depend only on the hardware RDRAND. */
230 CRYPTO_sysrand(seed, CTR_DRBG_ENTROPY_LEN);
231 }
232
233 #endif
234
RAND_bytes_with_additional_data(uint8_t * out,size_t out_len,const uint8_t user_additional_data[32])235 void RAND_bytes_with_additional_data(uint8_t *out, size_t out_len,
236 const uint8_t user_additional_data[32]) {
237 if (out_len == 0) {
238 return;
239 }
240
241 /* Additional data is mixed into every CTR-DRBG call to protect, as best we
242 * can, against forks & VM clones. We do not over-read this information and
243 * don't reseed with it so, from the point of view of FIPS, this doesn't
244 * provide “prediction resistance”. But, in practice, it does. */
245 uint8_t additional_data[32];
246 if (!hwrand(additional_data, sizeof(additional_data))) {
247 /* Without a hardware RNG to save us from address-space duplication, the OS
248 * entropy is used. This can be expensive (one read per |RAND_bytes| call)
249 * and so can be disabled by applications that we have ensured don't fork
250 * and aren't at risk of VM cloning. */
251 if (!rand_fork_unsafe_buffering_enabled()) {
252 CRYPTO_sysrand(additional_data, sizeof(additional_data));
253 } else {
254 OPENSSL_memset(additional_data, 0, sizeof(additional_data));
255 }
256 }
257
258 for (size_t i = 0; i < sizeof(additional_data); i++) {
259 additional_data[i] ^= user_additional_data[i];
260 }
261
262 struct rand_thread_state stack_state;
263 struct rand_thread_state *state =
264 CRYPTO_get_thread_local(OPENSSL_THREAD_LOCAL_RAND);
265
266 if (state == NULL) {
267 state = OPENSSL_malloc(sizeof(struct rand_thread_state));
268 if (state == NULL ||
269 !CRYPTO_set_thread_local(OPENSSL_THREAD_LOCAL_RAND, state,
270 rand_thread_state_free)) {
271 /* If the system is out of memory, use an ephemeral state on the
272 * stack. */
273 state = &stack_state;
274 }
275
276 state->last_block_valid = 0;
277 uint8_t seed[CTR_DRBG_ENTROPY_LEN];
278 rand_get_seed(state, seed);
279 if (!CTR_DRBG_init(&state->drbg, seed, NULL, 0)) {
280 abort();
281 }
282 state->calls = 0;
283
284 #if defined(BORINGSSL_FIPS)
285 if (state != &stack_state) {
286 CRYPTO_STATIC_MUTEX_lock_write(thread_states_list_lock_bss_get());
287 struct rand_thread_state **states_list = thread_states_list_bss_get();
288 state->next = *states_list;
289 if (state->next != NULL) {
290 state->next->prev = state;
291 }
292 state->prev = NULL;
293 *states_list = state;
294 CRYPTO_STATIC_MUTEX_unlock_write(thread_states_list_lock_bss_get());
295 }
296 #endif
297 }
298
299 if (state->calls >= kReseedInterval) {
300 uint8_t seed[CTR_DRBG_ENTROPY_LEN];
301 rand_get_seed(state, seed);
302 #if defined(BORINGSSL_FIPS)
303 /* Take a read lock around accesses to |state->drbg|. This is needed to
304 * avoid returning bad entropy if we race with
305 * |rand_thread_state_clear_all|.
306 *
307 * This lock must be taken after any calls to |CRYPTO_sysrand| to avoid a
308 * bug on ppc64le. glibc may implement pthread locks by wrapping user code
309 * in a hardware transaction, but, on some older versions of glibc and the
310 * kernel, syscalls made with |syscall| did not abort the transaction. */
311 CRYPTO_STATIC_MUTEX_lock_read(thread_states_list_lock_bss_get());
312 #endif
313 if (!CTR_DRBG_reseed(&state->drbg, seed, NULL, 0)) {
314 abort();
315 }
316 state->calls = 0;
317 } else {
318 #if defined(BORINGSSL_FIPS)
319 CRYPTO_STATIC_MUTEX_lock_read(thread_states_list_lock_bss_get());
320 #endif
321 }
322
323 int first_call = 1;
324 while (out_len > 0) {
325 size_t todo = out_len;
326 if (todo > CTR_DRBG_MAX_GENERATE_LENGTH) {
327 todo = CTR_DRBG_MAX_GENERATE_LENGTH;
328 }
329
330 if (!CTR_DRBG_generate(&state->drbg, out, todo, additional_data,
331 first_call ? sizeof(additional_data) : 0)) {
332 abort();
333 }
334
335 out += todo;
336 out_len -= todo;
337 state->calls++;
338 first_call = 0;
339 }
340
341 if (state == &stack_state) {
342 CTR_DRBG_clear(&state->drbg);
343 }
344
345 #if defined(BORINGSSL_FIPS)
346 CRYPTO_STATIC_MUTEX_unlock_read(thread_states_list_lock_bss_get());
347 #endif
348
349 return;
350 }
351
RAND_bytes(uint8_t * out,size_t out_len)352 int RAND_bytes(uint8_t *out, size_t out_len) {
353 static const uint8_t kZeroAdditionalData[32] = {0};
354 RAND_bytes_with_additional_data(out, out_len, kZeroAdditionalData);
355 return 1;
356 }
357
RAND_pseudo_bytes(uint8_t * buf,size_t len)358 int RAND_pseudo_bytes(uint8_t *buf, size_t len) {
359 return RAND_bytes(buf, len);
360 }
361