Line data Source code
1 : /* Copyright (c) 2001, Matej Pfajfar.
2 : * Copyright (c) 2001-2004, Roger Dingledine.
3 : * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 : * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 : /* See LICENSE for licensing information */
6 :
7 : /**
8 : * \file crypto_rand_fast.c
9 : *
10 : * \brief A fast strong PRNG for use when our underlying cryptographic
11 : * library's PRNG isn't fast enough.
12 : **/
13 :
14 : /* This library is currently implemented to use the same implementation
15 : * technique as libottery, using AES-CTR-256 as our underlying stream cipher.
16 : * It's backtracking-resistant immediately, and prediction-resistant after
17 : * a while.
18 : *
19 : * Here's how it works:
20 : *
21 : * We generate pseudorandom bytes using AES-CTR-256. We generate BUFLEN bytes
22 : * at a time. When we do this, we keep the first SEED_LEN bytes as the key
23 : * and the IV for our next invocation of AES_CTR, and yield the remaining
24 : * BUFLEN - SEED_LEN bytes to the user as they invoke the PRNG. As we yield
25 : * bytes to the user, we clear them from the buffer.
26 : *
27 : * After we have refilled the buffer RESEED_AFTER times, we mix in an
28 : * additional SEED_LEN bytes from our strong PRNG into the seed.
29 : *
30 : * If the user ever asks for a huge number of bytes at once, we pull SEED_LEN
31 : * bytes from the PRNG and use them with our stream cipher to fill the user's
32 : * request.
33 : */
34 :
35 : #define CRYPTO_PRIVATE
36 :
37 : #include "lib/crypt_ops/crypto_rand.h"
38 : #include "lib/crypt_ops/crypto_cipher.h"
39 : #include "lib/crypt_ops/crypto_digest.h"
40 : #include "lib/crypt_ops/crypto_util.h"
41 : #include "lib/intmath/cmp.h"
42 : #include "lib/cc/ctassert.h"
43 : #include "lib/malloc/map_anon.h"
44 : #include "lib/thread/threads.h"
45 :
46 : #include "lib/log/util_bug.h"
47 :
48 : #ifdef HAVE_SYS_TYPES_H
49 : #include <sys/types.h>
50 : #endif
51 : #ifdef HAVE_UNISTD_H
52 : #include <unistd.h>
53 : #endif
54 :
55 : #include <string.h>
56 :
57 : #ifdef NOINHERIT_CAN_FAIL
58 : #define CHECK_PID
59 : #endif
60 :
61 : #ifdef CHECK_PID
62 : #define PID_FIELD_LEN sizeof(pid_t)
63 : #else
64 : #define PID_FIELD_LEN 0
65 : #endif
66 :
67 : /* Alias for CRYPTO_FAST_RNG_SEED_LEN to make our code shorter.
68 : */
69 : #define SEED_LEN (CRYPTO_FAST_RNG_SEED_LEN)
70 :
71 : /* The amount of space that we mmap for a crypto_fast_rng_t.
72 : */
73 : #define MAPLEN 4096
74 :
75 : /* The number of random bytes that we can yield to the user after each
76 : * time we fill a crypto_fast_rng_t's buffer.
77 : */
78 : #define BUFLEN (MAPLEN - 2*sizeof(uint16_t) - SEED_LEN - PID_FIELD_LEN)
79 :
80 : /* The number of buffer refills after which we should fetch more
81 : * entropy from crypto_strongest_rand().
82 : */
83 : #define RESEED_AFTER 16
84 :
85 : /* The length of the stream cipher key we will use for the PRNG, in bytes.
86 : */
87 : #define KEY_LEN (CRYPTO_FAST_RNG_SEED_LEN - CIPHER_IV_LEN)
88 : /* The length of the stream cipher key we will use for the PRNG, in bits.
89 : */
90 : #define KEY_BITS (KEY_LEN * 8)
91 :
92 : /* Make sure that we have a key length we can actually use with AES. */
93 : CTASSERT(KEY_BITS == 128 || KEY_BITS == 192 || KEY_BITS == 256);
94 :
95 : struct crypto_fast_rng_t {
96 : /** How many more fills does this buffer have before we should mix
97 : * in the output of crypto_strongest_rand()?
98 : *
99 : * This value may be negative if unit tests are enabled. If so, it
100 : * indicates that we should never mix in extra data from
101 : * crypto_strongest_rand().
102 : */
103 : int16_t n_till_reseed;
104 : /** How many bytes are remaining in cbuf_t.bytes? */
105 : uint16_t bytes_left;
106 : #ifdef CHECK_PID
107 : /** Which process owns this fast_rng? If this value is zero, we do not
108 : * need to test the owner. */
109 : pid_t owner;
110 : #endif
111 : struct cbuf_t {
112 : /** The seed (key and IV) that we will use the next time that we refill
113 : * cbuf_t. */
114 : uint8_t seed[SEED_LEN];
115 : /**
116 : * Bytes that we are yielding to the user. The next byte to be
117 : * yielded is at bytes[BUFLEN-bytes_left]; all other bytes in this
118 : * array are set to zero.
119 : */
120 : uint8_t bytes[BUFLEN];
121 : } buf;
122 : };
123 :
124 : /* alignof(uint8_t) should be 1, so there shouldn't be any padding in cbuf_t.
125 : */
126 : CTASSERT(sizeof(struct cbuf_t) == BUFLEN+SEED_LEN);
127 : /* We're trying to fit all of the RNG state into a nice mmapable chunk.
128 : */
129 : CTASSERT(sizeof(crypto_fast_rng_t) <= MAPLEN);
130 :
131 : /**
132 : * Initialize and return a new fast PRNG, using a strong random seed.
133 : *
134 : * Note that this object is NOT thread-safe. If you need a thread-safe
135 : * prng, use crypto_rand(), or wrap this in a mutex.
136 : **/
137 : crypto_fast_rng_t *
138 149 : crypto_fast_rng_new(void)
139 : {
140 149 : uint8_t seed[SEED_LEN];
141 149 : crypto_strongest_rand(seed, sizeof(seed));
142 149 : crypto_fast_rng_t *result = crypto_fast_rng_new_from_seed(seed);
143 149 : memwipe(seed, 0, sizeof(seed));
144 149 : return result;
145 : }
146 :
147 : /**
148 : * Initialize and return a new fast PRNG, using a seed value specified
149 : * in <b>seed</b>. This value must be CRYPTO_FAST_RNG_SEED_LEN bytes
150 : * long.
151 : *
152 : * Note that this object is NOT thread-safe. If you need a thread-safe
153 : * prng, you should probably look at get_thread_fast_rng(). Alternatively,
154 : * use crypto_rand(), wrap this in a mutex.
155 : **/
156 : crypto_fast_rng_t *
157 170 : crypto_fast_rng_new_from_seed(const uint8_t *seed)
158 : {
159 170 : unsigned inherit = INHERIT_RES_KEEP;
160 : /* We try to allocate this object as securely as we can, to avoid
161 : * having it get dumped, swapped, or shared after fork.
162 : */
163 170 : crypto_fast_rng_t *result = tor_mmap_anonymous(sizeof(*result),
164 : ANONMAP_PRIVATE | ANONMAP_NOINHERIT,
165 : &inherit);
166 170 : memcpy(result->buf.seed, seed, SEED_LEN);
167 : /* Causes an immediate refill once the user asks for data. */
168 170 : result->bytes_left = 0;
169 170 : result->n_till_reseed = RESEED_AFTER;
170 : #ifdef CHECK_PID
171 170 : if (inherit == INHERIT_RES_KEEP) {
172 : /* This value will neither be dropped nor zeroed after fork, so we need to
173 : * check our pid to make sure we are not sharing it across a fork. This
174 : * can be expensive if the pid value isn't cached, sadly.
175 : */
176 0 : result->owner = getpid();
177 : }
178 : #elif defined(_WIN32)
179 : /* Windows can't fork(), so there's no need to noinherit. */
180 : #else
181 : /* We decided above that noinherit would always do _something_. Assert here
182 : * that we were correct. */
183 : tor_assertf(inherit != INHERIT_RES_KEEP,
184 : "We failed to create a non-inheritable memory region, even "
185 : "though we believed such a failure to be impossible! This is "
186 : "probably a bug in Tor support for your platform; please report "
187 : "it.");
188 : #endif /* defined(CHECK_PID) || ... */
189 170 : return result;
190 : }
191 :
192 : #ifdef TOR_UNIT_TESTS
193 : /**
194 : * Unit tests only: prevent a crypto_fast_rng_t from ever mixing in more
195 : * entropy.
196 : */
197 : void
198 20 : crypto_fast_rng_disable_reseed(crypto_fast_rng_t *rng)
199 : {
200 20 : rng->n_till_reseed = -1;
201 20 : }
202 : #endif /* defined(TOR_UNIT_TESTS) */
203 :
204 : /**
205 : * Helper: create a crypto_cipher_t object from SEED_LEN bytes of
206 : * input. The first KEY_LEN bytes are used as the stream cipher's key,
207 : * and the remaining CIPHER_IV_LEN bytes are used as its IV.
208 : **/
209 : static inline crypto_cipher_t *
210 12717 : cipher_from_seed(const uint8_t *seed)
211 : {
212 12717 : return crypto_cipher_new_with_iv_and_bits(seed, seed+KEY_LEN, KEY_BITS);
213 : }
214 :
215 : /**
216 : * Helper: mix additional entropy into <b>rng</b> by using our XOF to mix the
217 : * old value for the seed with some additional bytes from
218 : * crypto_strongest_rand().
219 : **/
220 : static void
221 0 : crypto_fast_rng_add_entopy(crypto_fast_rng_t *rng)
222 : {
223 0 : crypto_xof_t *xof = crypto_xof_new();
224 0 : crypto_xof_add_bytes(xof, rng->buf.seed, SEED_LEN);
225 : {
226 0 : uint8_t seedbuf[SEED_LEN];
227 0 : crypto_strongest_rand(seedbuf, SEED_LEN);
228 0 : crypto_xof_add_bytes(xof, seedbuf, SEED_LEN);
229 0 : memwipe(seedbuf, 0, SEED_LEN);
230 : }
231 0 : crypto_xof_squeeze_bytes(xof, rng->buf.seed, SEED_LEN);
232 0 : crypto_xof_free(xof);
233 0 : }
234 :
235 : /**
236 : * Helper: refill the seed bytes and output buffer of <b>rng</b>, using
237 : * the input seed bytes as input (key and IV) for the stream cipher.
238 : *
239 : * If the n_till_reseed counter has reached zero, mix more random bytes into
240 : * the seed before refilling the buffer.
241 : **/
242 : static void
243 12716 : crypto_fast_rng_refill(crypto_fast_rng_t *rng)
244 : {
245 12716 : rng->n_till_reseed--;
246 12716 : if (rng->n_till_reseed == 0) {
247 : /* It's time to reseed the RNG. */
248 0 : crypto_fast_rng_add_entopy(rng);
249 0 : rng->n_till_reseed = RESEED_AFTER;
250 12716 : } else if (rng->n_till_reseed < 0) {
251 : #ifdef TOR_UNIT_TESTS
252 : /* Reseeding is disabled for testing; never do it on this prng. */
253 12511 : rng->n_till_reseed = -1;
254 : #else
255 : /* If testing is disabled, this shouldn't be able to become negative. */
256 : tor_assert_unreached();
257 : #endif /* defined(TOR_UNIT_TESTS) */
258 : }
259 : /* Now fill rng->buf with output from our stream cipher, initialized from
260 : * that seed value. */
261 12716 : crypto_cipher_t *c = cipher_from_seed(rng->buf.seed);
262 12716 : memset(&rng->buf, 0, sizeof(rng->buf));
263 12716 : crypto_cipher_crypt_inplace(c, (char*)&rng->buf, sizeof(rng->buf));
264 12716 : crypto_cipher_free(c);
265 :
266 12716 : rng->bytes_left = sizeof(rng->buf.bytes);
267 12716 : }
268 :
269 : /**
270 : * Release all storage held by <b>rng</b>.
271 : **/
272 : void
273 39 : crypto_fast_rng_free_(crypto_fast_rng_t *rng)
274 : {
275 39 : if (!rng)
276 : return;
277 27 : memwipe(rng, 0, sizeof(*rng));
278 27 : tor_munmap_anonymous(rng, sizeof(*rng));
279 : }
280 :
281 : /**
282 : * Helper: extract bytes from the PRNG, refilling it as necessary. Does not
283 : * optimize the case when the user has asked for a huge output.
284 : **/
285 : static void
286 12674481 : crypto_fast_rng_getbytes_impl(crypto_fast_rng_t *rng, uint8_t *out,
287 : const size_t n)
288 : {
289 : #ifdef CHECK_PID
290 12674481 : if (rng->owner) {
291 : /* Note that we only need to do this check when we have owner set: that
292 : * is, when our attempt to block inheriting failed, and the result was
293 : * INHERIT_RES_KEEP.
294 : *
295 : * If the result was INHERIT_RES_DROP, then any attempt to access the rng
296 : * memory after forking will crash.
297 : *
298 : * If the result was INHERIT_RES_ZERO, then forking will set the bytes_left
299 : * and n_till_reseed fields to zero. This function will call
300 : * crypto_fast_rng_refill(), which will in turn reseed the PRNG.
301 : *
302 : * So we only need to do this test in the case when mmap_anonymous()
303 : * returned INHERIT_KEEP. We avoid doing it needlessly, since getpid() is
304 : * often a system call, and that can be slow.
305 : */
306 0 : tor_assert(rng->owner == getpid());
307 : }
308 : #endif /* defined(CHECK_PID) */
309 :
310 : size_t bytes_to_yield = n;
311 :
312 25348980 : while (bytes_to_yield) {
313 12674499 : if (rng->bytes_left == 0)
314 12716 : crypto_fast_rng_refill(rng);
315 :
316 12674499 : const size_t to_copy = MIN(rng->bytes_left, bytes_to_yield);
317 :
318 12674499 : tor_assert(sizeof(rng->buf.bytes) >= rng->bytes_left);
319 12674499 : uint8_t *copy_from = rng->buf.bytes +
320 12674499 : (sizeof(rng->buf.bytes) - rng->bytes_left);
321 12674499 : memcpy(out, copy_from, to_copy);
322 12674499 : memset(copy_from, 0, to_copy);
323 :
324 12674499 : out += to_copy;
325 12674499 : bytes_to_yield -= to_copy;
326 12674499 : rng->bytes_left -= to_copy;
327 : }
328 12674481 : }
329 :
330 : /**
331 : * Extract <b>n</b> bytes from <b>rng</b> into the buffer at <b>out</b>.
332 : **/
333 : void
334 12674481 : crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n)
335 : {
336 12674481 : if (PREDICT_UNLIKELY(n > BUFLEN)) {
337 : /* The user has asked for a lot of output; generate it from a stream
338 : * cipher seeded by the PRNG rather than by pulling it out of the PRNG
339 : * directly.
340 : */
341 1 : uint8_t seed[SEED_LEN];
342 1 : crypto_fast_rng_getbytes_impl(rng, seed, SEED_LEN);
343 1 : crypto_cipher_t *c = cipher_from_seed(seed);
344 1 : memset(out, 0, n);
345 1 : crypto_cipher_crypt_inplace(c, (char*)out, n);
346 1 : crypto_cipher_free(c);
347 1 : memwipe(seed, 0, sizeof(seed));
348 1 : return;
349 : }
350 :
351 12674480 : crypto_fast_rng_getbytes_impl(rng, out, n);
352 : }
353 :
354 : #if defined(TOR_UNIT_TESTS)
355 : /** for white-box testing: return the number of bytes that are returned from
356 : * the user for each invocation of the stream cipher in this RNG. */
357 : size_t
358 1 : crypto_fast_rng_get_bytes_used_per_stream(void)
359 : {
360 1 : return BUFLEN;
361 : }
362 : #endif /* defined(TOR_UNIT_TESTS) */
363 :
364 : /**
365 : * Thread-local instance for our fast RNG.
366 : **/
367 : static tor_threadlocal_t thread_rng;
368 :
369 : /**
370 : * Return a per-thread fast RNG, initializing it if necessary.
371 : *
372 : * You do not need to free this yourself.
373 : *
374 : * It is NOT safe to share this value across threads.
375 : **/
376 : crypto_fast_rng_t *
377 12673836 : get_thread_fast_rng(void)
378 : {
379 12673836 : crypto_fast_rng_t *rng = tor_threadlocal_get(&thread_rng);
380 :
381 12673836 : if (PREDICT_UNLIKELY(rng == NULL)) {
382 148 : rng = crypto_fast_rng_new();
383 148 : tor_threadlocal_set(&thread_rng, rng);
384 : }
385 :
386 12673836 : return rng;
387 : }
388 :
389 : /**
390 : * Used when a thread is exiting: free the per-thread fast RNG if needed.
391 : * Invoked from the crypto subsystem's thread-cleanup code.
392 : **/
393 : void
394 1162 : destroy_thread_fast_rng(void)
395 : {
396 1162 : crypto_fast_rng_t *rng = tor_threadlocal_get(&thread_rng);
397 1162 : if (!rng)
398 1162 : return;
399 5 : crypto_fast_rng_free(rng);
400 5 : tor_threadlocal_set(&thread_rng, NULL);
401 : }
402 :
403 : #ifdef TOR_UNIT_TESTS
404 : /**
405 : * Replace the current thread's rng with <b>rng</b>. For use by the
406 : * unit tests only. Returns the previous thread rng.
407 : **/
408 : crypto_fast_rng_t *
409 52 : crypto_replace_thread_fast_rng(crypto_fast_rng_t *rng)
410 : {
411 52 : crypto_fast_rng_t *old_rng = tor_threadlocal_get(&thread_rng);
412 52 : tor_threadlocal_set(&thread_rng, rng);
413 52 : return old_rng;
414 : }
415 : #endif /* defined(TOR_UNIT_TESTS) */
416 :
417 : /**
418 : * Initialize the global thread-local key that will be used to keep track
419 : * of per-thread fast RNG instances. Called from the crypto subsystem's
420 : * initialization code.
421 : **/
422 : void
423 5561 : crypto_rand_fast_init(void)
424 : {
425 5561 : tor_threadlocal_init(&thread_rng);
426 5561 : }
427 :
428 : /**
429 : * Initialize the global thread-local key that will be used to keep track
430 : * of per-thread fast RNG instances. Called from the crypto subsystem's
431 : * shutdown code.
432 : **/
433 : void
434 235 : crypto_rand_fast_shutdown(void)
435 : {
436 235 : destroy_thread_fast_rng();
437 235 : tor_threadlocal_destroy(&thread_rng);
438 235 : }
|
