tor  0.4.2.0-alpha-dev
crypto_rand_fast.c
Go to the documentation of this file.
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-2019, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
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_RAND_FAST_PRIVATE
36 #define CRYPTO_PRIVATE
37 
42 #include "lib/intmath/cmp.h"
43 #include "lib/cc/ctassert.h"
44 #include "lib/malloc/map_anon.h"
45 #include "lib/thread/threads.h"
46 
47 #include "lib/log/util_bug.h"
48 
49 #ifdef HAVE_SYS_TYPES_H
50 #include <sys/types.h>
51 #endif
52 #ifdef HAVE_UNISTD_H
53 #include <unistd.h>
54 #endif
55 
56 #include <string.h>
57 
58 #ifdef NOINHERIT_CAN_FAIL
59 #define CHECK_PID
60 #endif
61 
62 #ifdef CHECK_PID
63 #define PID_FIELD_LEN sizeof(pid_t)
64 #else
65 #define PID_FIELD_LEN 0
66 #endif
67 
68 /* Alias for CRYPTO_FAST_RNG_SEED_LEN to make our code shorter.
69  */
70 #define SEED_LEN (CRYPTO_FAST_RNG_SEED_LEN)
71 
72 /* The amount of space that we mmap for a crypto_fast_rng_t.
73  */
74 #define MAPLEN 4096
75 
76 /* The number of random bytes that we can yield to the user after each
77  * time we fill a crypto_fast_rng_t's buffer.
78  */
79 #define BUFLEN (MAPLEN - 2*sizeof(uint16_t) - SEED_LEN - PID_FIELD_LEN)
80 
81 /* The number of buffer refills after which we should fetch more
82  * entropy from crypto_strongest_rand().
83  */
84 #define RESEED_AFTER 16
85 
86 /* The length of the stream cipher key we will use for the PRNG, in bytes.
87  */
88 #define KEY_LEN (CRYPTO_FAST_RNG_SEED_LEN - CIPHER_IV_LEN)
89 /* The length of the stream cipher key we will use for the PRNG, in bits.
90  */
91 #define KEY_BITS (KEY_LEN * 8)
92 
93 /* Make sure that we have a key length we can actually use with AES. */
94 CTASSERT(KEY_BITS == 128 || KEY_BITS == 192 || KEY_BITS == 256);
95 
104  int16_t n_till_reseed;
106  uint16_t bytes_left;
107 #ifdef CHECK_PID
108 
110  pid_t owner;
111 #endif
112  struct cbuf {
115  uint8_t seed[SEED_LEN];
121  uint8_t bytes[BUFLEN];
122  } buf;
123 };
124 
125 /* alignof(uint8_t) should be 1, so there shouldn't be any padding in cbuf.
126  */
127 CTASSERT(sizeof(struct cbuf) == BUFLEN+SEED_LEN);
128 /* We're trying to fit all of the RNG state into a nice mmapable chunk.
129  */
130 CTASSERT(sizeof(crypto_fast_rng_t) <= MAPLEN);
131 
140 {
141  uint8_t seed[SEED_LEN];
142  crypto_strongest_rand(seed, sizeof(seed));
144  memwipe(seed, 0, sizeof(seed));
145  return result;
146 }
147 
158 crypto_fast_rng_new_from_seed(const uint8_t *seed)
159 {
160  unsigned inherit = INHERIT_RES_KEEP;
161  /* We try to allocate this object as securely as we can, to avoid
162  * having it get dumped, swapped, or shared after fork.
163  */
164  crypto_fast_rng_t *result = tor_mmap_anonymous(sizeof(*result),
166  &inherit);
167  memcpy(result->buf.seed, seed, SEED_LEN);
168  /* Causes an immediate refill once the user asks for data. */
169  result->bytes_left = 0;
170  result->n_till_reseed = RESEED_AFTER;
171 #ifdef CHECK_PID
172  if (inherit == INHERIT_RES_KEEP) {
173  /* This value will neither be dropped nor zeroed after fork, so we need to
174  * check our pid to make sure we are not sharing it across a fork. This
175  * can be expensive if the pid value isn't cached, sadly.
176  */
177  result->owner = getpid();
178  }
179 #elif defined(_WIN32)
180  /* Windows can't fork(), so there's no need to noinherit. */
181 #else
182  /* We decided above that noinherit would always do _something_. Assert here
183  * that we were correct. */
184  tor_assertf(inherit != INHERIT_RES_KEEP,
185  "We failed to create a non-inheritable memory region, even "
186  "though we believed such a failure to be impossible! This is "
187  "probably a bug in Tor support for your platform; please report "
188  "it.");
189 #endif /* defined(CHECK_PID) || ... */
190  return result;
191 }
192 
193 #ifdef TOR_UNIT_TESTS
194 
198 void
199 crypto_fast_rng_disable_reseed(crypto_fast_rng_t *rng)
200 {
201  rng->n_till_reseed = -1;
202 }
203 #endif /* defined(TOR_UNIT_TESTS) */
204 
210 static inline crypto_cipher_t *
211 cipher_from_seed(const uint8_t *seed)
212 {
213  return crypto_cipher_new_with_iv_and_bits(seed, seed+KEY_LEN, KEY_BITS);
214 }
215 
221 static void
223 {
224  crypto_xof_t *xof = crypto_xof_new();
225  crypto_xof_add_bytes(xof, rng->buf.seed, SEED_LEN);
226  {
227  uint8_t seedbuf[SEED_LEN];
228  crypto_strongest_rand(seedbuf, SEED_LEN);
229  crypto_xof_add_bytes(xof, seedbuf, SEED_LEN);
230  memwipe(seedbuf, 0, SEED_LEN);
231  }
232  crypto_xof_squeeze_bytes(xof, rng->buf.seed, SEED_LEN);
233  crypto_xof_free(xof);
234 }
235 
243 static void
245 {
246  rng->n_till_reseed--;
247  if (rng->n_till_reseed == 0) {
248  /* It's time to reseed the RNG. */
250  rng->n_till_reseed = RESEED_AFTER;
251  } else if (rng->n_till_reseed < 0) {
252 #ifdef TOR_UNIT_TESTS
253  /* Reseeding is disabled for testing; never do it on this prng. */
254  rng->n_till_reseed = -1;
255 #else
256  /* If testing is disabled, this shouldn't be able to become negative. */
257  tor_assert_unreached();
258 #endif /* defined(TOR_UNIT_TESTS) */
259  }
260  /* Now fill rng->buf with output from our stream cipher, initialized from
261  * that seed value. */
262  crypto_cipher_t *c = cipher_from_seed(rng->buf.seed);
263  memset(&rng->buf, 0, sizeof(rng->buf));
264  crypto_cipher_crypt_inplace(c, (char*)&rng->buf, sizeof(rng->buf));
265  crypto_cipher_free(c);
266 
267  rng->bytes_left = sizeof(rng->buf.bytes);
268 }
269 
273 void
275 {
276  if (!rng)
277  return;
278  memwipe(rng, 0, sizeof(*rng));
279  tor_munmap_anonymous(rng, sizeof(*rng));
280 }
281 
286 static void
288  const size_t n)
289 {
290 #ifdef CHECK_PID
291  if (rng->owner) {
292  /* Note that we only need to do this check when we have owner set: that
293  * is, when our attempt to block inheriting failed, and the result was
294  * INHERIT_RES_KEEP.
295  *
296  * If the result was INHERIT_RES_DROP, then any attempt to access the rng
297  * memory after forking will crash.
298  *
299  * If the result was INHERIT_RES_ZERO, then forking will set the bytes_left
300  * and n_till_reseed fields to zero. This function will call
301  * crypto_fast_rng_refill(), which will in turn reseed the PRNG.
302  *
303  * So we only need to do this test in the case when mmap_anonymous()
304  * returned INHERIT_KEEP. We avoid doing it needlessly, since getpid() is
305  * often a system call, and that can be slow.
306  */
307  tor_assert(rng->owner == getpid());
308  }
309 #endif /* defined(CHECK_PID) */
310 
311  size_t bytes_to_yield = n;
312 
313  while (bytes_to_yield) {
314  if (rng->bytes_left == 0)
316 
317  const size_t to_copy = MIN(rng->bytes_left, bytes_to_yield);
318 
319  tor_assert(sizeof(rng->buf.bytes) >= rng->bytes_left);
320  uint8_t *copy_from = rng->buf.bytes +
321  (sizeof(rng->buf.bytes) - rng->bytes_left);
322  memcpy(out, copy_from, to_copy);
323  memset(copy_from, 0, to_copy);
324 
325  out += to_copy;
326  bytes_to_yield -= to_copy;
327  rng->bytes_left -= to_copy;
328  }
329 }
330 
334 void
335 crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n)
336 {
337  if (PREDICT_UNLIKELY(n > BUFLEN)) {
338  /* The user has asked for a lot of output; generate it from a stream
339  * cipher seeded by the PRNG rather than by pulling it out of the PRNG
340  * directly.
341  */
342  uint8_t seed[SEED_LEN];
343  crypto_fast_rng_getbytes_impl(rng, seed, SEED_LEN);
344  crypto_cipher_t *c = cipher_from_seed(seed);
345  memset(out, 0, n);
346  crypto_cipher_crypt_inplace(c, (char*)out, n);
347  crypto_cipher_free(c);
348  memwipe(seed, 0, sizeof(seed));
349  return;
350  }
351 
352  crypto_fast_rng_getbytes_impl(rng, out, n);
353 }
354 
355 #if defined(TOR_UNIT_TESTS)
356 
358 size_t
359 crypto_fast_rng_get_bytes_used_per_stream(void)
360 {
361  return BUFLEN;
362 }
363 #endif /* defined(TOR_UNIT_TESTS) */
364 
369 
379 {
381 
382  if (PREDICT_UNLIKELY(rng == NULL)) {
383  rng = crypto_fast_rng_new();
385  }
386 
387  return rng;
388 }
389 
394 void
396 {
398  if (!rng)
399  return;
400  crypto_fast_rng_free(rng);
402 }
403 
404 #ifdef TOR_UNIT_TESTS
405 
410 crypto_replace_thread_fast_rng(crypto_fast_rng_t *rng)
411 {
414  return old_rng;
415 }
416 #endif /* defined(TOR_UNIT_TESTS) */
417 
423 void
425 {
427 }
428 
434 void
436 {
439 }
void crypto_cipher_crypt_inplace(crypto_cipher_t *env, char *buf, size_t len)
Common functions for using (pseudo-)random number generators.
Headers for map_anon.c.
#define CTASSERT(x)
Definition: ctassert.h:44
void crypto_rand_fast_shutdown(void)
Headers for crypto_cipher.c.
Macro definitions for MIN, MAX, and CLAMP.
void crypto_rand_fast_init(void)
void crypto_xof_add_bytes(crypto_xof_t *xof, const uint8_t *data, size_t len)
static crypto_cipher_t * cipher_from_seed(const uint8_t *seed)
static tor_threadlocal_t thread_rng
void tor_munmap_anonymous(void *mapping, size_t sz)
Definition: map_anon.c:229
void crypto_xof_squeeze_bytes(crypto_xof_t *xof, uint8_t *out, size_t len)
crypto_fast_rng_t * crypto_fast_rng_new_from_seed(const uint8_t *seed)
crypto_fast_rng_t * get_thread_fast_rng(void)
void memwipe(void *mem, uint8_t byte, size_t sz)
Definition: crypto_util.c:57
#define ANONMAP_NOINHERIT
Definition: map_anon.h:32
crypto_fast_rng_t * crypto_fast_rng_new(void)
Header for threads.c.
void crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n)
int tor_threadlocal_init(tor_threadlocal_t *threadlocal)
Common functions for cryptographic routines.
static void crypto_fast_rng_refill(crypto_fast_rng_t *rng)
#define ANONMAP_PRIVATE
Definition: map_anon.h:23
tor_assert(buffer)
void crypto_fast_rng_free_(crypto_fast_rng_t *rng)
void tor_threadlocal_set(tor_threadlocal_t *threadlocal, void *value)
void * tor_mmap_anonymous(size_t sz, unsigned flags, inherit_res_t *inherit_result_out)
Definition: map_anon.c:175
Headers for crypto_digest.c.
Compile-time assertions: CTASSERT(expression).
static void crypto_fast_rng_add_entopy(crypto_fast_rng_t *rng)
uint8_t seed[SEED_LEN]
void crypto_strongest_rand(uint8_t *out, size_t out_len)
Definition: crypto_rand.c:340
crypto_cipher_t * crypto_cipher_new_with_iv_and_bits(const uint8_t *key, const uint8_t *iv, int bits)
Definition: crypto_cipher.c:29
void * tor_threadlocal_get(tor_threadlocal_t *threadlocal)
static void crypto_fast_rng_getbytes_impl(crypto_fast_rng_t *rng, uint8_t *out, const size_t n)
Macros to manage assertions, fatal and non-fatal.
crypto_xof_t * crypto_xof_new(void)
void tor_threadlocal_destroy(tor_threadlocal_t *threadlocal)
void destroy_thread_fast_rng(void)