Tor  0.4.4.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-2020, 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 
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 
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  **/
139 {
140  uint8_t seed[SEED_LEN];
141  crypto_strongest_rand(seed, sizeof(seed));
143  memwipe(seed, 0, sizeof(seed));
144  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  **/
157 crypto_fast_rng_new_from_seed(const uint8_t *seed)
158 {
159  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  crypto_fast_rng_t *result = tor_mmap_anonymous(sizeof(*result),
165  &inherit);
166  memcpy(result->buf.seed, seed, SEED_LEN);
167  /* Causes an immediate refill once the user asks for data. */
168  result->bytes_left = 0;
169  result->n_till_reseed = RESEED_AFTER;
170 #ifdef CHECK_PID
171  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  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  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 crypto_fast_rng_disable_reseed(crypto_fast_rng_t *rng)
199 {
200  rng->n_till_reseed = -1;
201 }
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 cipher_from_seed(const uint8_t *seed)
211 {
212  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
222 {
223  crypto_xof_t *xof = crypto_xof_new();
224  crypto_xof_add_bytes(xof, rng->buf.seed, SEED_LEN);
225  {
226  uint8_t seedbuf[SEED_LEN];
227  crypto_strongest_rand(seedbuf, SEED_LEN);
228  crypto_xof_add_bytes(xof, seedbuf, SEED_LEN);
229  memwipe(seedbuf, 0, SEED_LEN);
230  }
231  crypto_xof_squeeze_bytes(xof, rng->buf.seed, SEED_LEN);
232  crypto_xof_free(xof);
233 }
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
244 {
245  rng->n_till_reseed--;
246  if (rng->n_till_reseed == 0) {
247  /* It's time to reseed the RNG. */
249  rng->n_till_reseed = RESEED_AFTER;
250  } 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  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  crypto_cipher_t *c = cipher_from_seed(rng->buf.seed);
262  memset(&rng->buf, 0, sizeof(rng->buf));
263  crypto_cipher_crypt_inplace(c, (char*)&rng->buf, sizeof(rng->buf));
264  crypto_cipher_free(c);
265 
266  rng->bytes_left = sizeof(rng->buf.bytes);
267 }
268 
269 /**
270  * Release all storage held by <b>rng</b>.
271  **/
272 void
274 {
275  if (!rng)
276  return;
277  memwipe(rng, 0, sizeof(*rng));
278  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
287  const size_t n)
288 {
289 #ifdef CHECK_PID
290  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  tor_assert(rng->owner == getpid());
307  }
308 #endif /* defined(CHECK_PID) */
309 
310  size_t bytes_to_yield = n;
311 
312  while (bytes_to_yield) {
313  if (rng->bytes_left == 0)
315 
316  const size_t to_copy = MIN(rng->bytes_left, bytes_to_yield);
317 
318  tor_assert(sizeof(rng->buf.bytes) >= rng->bytes_left);
319  uint8_t *copy_from = rng->buf.bytes +
320  (sizeof(rng->buf.bytes) - rng->bytes_left);
321  memcpy(out, copy_from, to_copy);
322  memset(copy_from, 0, to_copy);
323 
324  out += to_copy;
325  bytes_to_yield -= to_copy;
326  rng->bytes_left -= to_copy;
327  }
328 }
329 
330 /**
331  * Extract <b>n</b> bytes from <b>rng</b> into the buffer at <b>out</b>.
332  **/
333 void
334 crypto_fast_rng_getbytes(crypto_fast_rng_t *rng, uint8_t *out, size_t n)
335 {
336  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  uint8_t seed[SEED_LEN];
342  crypto_fast_rng_getbytes_impl(rng, seed, SEED_LEN);
343  crypto_cipher_t *c = cipher_from_seed(seed);
344  memset(out, 0, n);
345  crypto_cipher_crypt_inplace(c, (char*)out, n);
346  crypto_cipher_free(c);
347  memwipe(seed, 0, sizeof(seed));
348  return;
349  }
350 
351  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 crypto_fast_rng_get_bytes_used_per_stream(void)
359 {
360  return BUFLEN;
361 }
362 #endif /* defined(TOR_UNIT_TESTS) */
363 
364 /**
365  * Thread-local instance for our fast RNG.
366  **/
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  **/
378 {
380 
381  if (PREDICT_UNLIKELY(rng == NULL)) {
382  rng = crypto_fast_rng_new();
384  }
385 
386  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
395 {
397  if (!rng)
398  return;
399  crypto_fast_rng_free(rng);
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  **/
409 crypto_replace_thread_fast_rng(crypto_fast_rng_t *rng)
410 {
413  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
424 {
426 }
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
435 {
438 }
#define crypto_xof_free(xof)
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:257
#define tor_assert(expr)
Definition: util_bug.h:102
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:55
#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
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:203
Headers for crypto_digest.c.
Compile-time assertions: CTASSERT(expression).
static void crypto_fast_rng_add_entopy(crypto_fast_rng_t *rng)
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)