Future of thread_rng

Status: proposal to allow hardware-dependent generators and replace HC128 with a faster variant of ChaCha (start reading here).

This topic comes up quite a bit from various angles; I think it's time to get some ideas down about the future of thread_rng (regarding the 0.6 release or later).

I see the following potential uses for thread_rng:

convenient random numbers in small games and simulations
use in randomised algorithms
as a source of secret data for various cryptographic applications

Also, I think it's worth mentioning where we do not expect thread_rng to be used:

anywhere reproducibility is required
complex simulations and games, due to above point, and also since thread_rng may not be the fastest option
where security is very important

And an important note on security: we should aim to provide a secure source of random data, but ultimately it is up to users to decide how much they trust our implementation and what their risks are. thread_rng does not have the simplest code to review and is currently young and subject to further change. Also we may or may not implement forward secrecy (backtracking resistance), and for ultimate security solutions using no local state may be preferred.

Our current implementation of thread_rng tries to satisfy the above with a fast, secure PRNG, but at the cost of high memory usage and initialisation time per thread. For applications with a low number of long-running threads this is reasonable, but for many worker threads may not be ideal.

There are two ways we can let users influence the implementation:

via feature flags
at the call site (pass parameters to thread_rng or call a different function)

Feature flags allow configuration on a per-application basis, e.g.

prefer low-memory-usage / fast initialisation over generation performance
disable entirely (i.e. panic on usage)
require forward secrecy
remove security requirements (??)

The last two options sound very risky to me — should we ask distributors and end-users to reason about the security of whole applications? It is quite possible that the people building applications — even developers — will not know about all uses of thread_rng requiring secure randomness.

This brings me to ask, is having only a single user-facing function ideal? What if instead:

strong_rng replaces thread_rng as a source of cryptographically secure randomness
weak_rng is added as a fast source of randomness; depending on feature flags this could just wrap strong_rng or could be independent

An advantage of the above is that feature-flags could allow replacing the current implementation (HC-128; 4176 bytes) with two smaller back ends (e.g. ChaCha + PCG; 136 + 16 bytes), while only compromising the speed of the secure generator.

Another advantage is that we could add forward-secrecy to strong_rng with less concern for performance implications.

But first, why bother when generators like Randen and RDRAND claim to satisfy all requirements anyway? This is a good question to which I only have vague answers: Randen is still new and unproven and may have portability issues; RDRAND is not fully trusted; and may not be the fastest option.

Second, what about users like HashMap where weaknesses are often not exploitable (depending on application design and usage) and in the worst case only allow DOS attacks (slow algorithms)? Another good question. One possible answer is that these use-cases should use weak_rng but by default this would be secure anyway; we provide feature flags to change that but discourage usage on servers. It might seem tempting to add a third function, but, frankly, this kind of thing is probably the main use case for weak_rng anyway.

Another, very different, option is that we keep thread_rng looking like it is but remove CryptoRng support and recommend it not be used for crypto keys. Then we can add a feature flag changing its implementation to an insecure generator with less concern. This may be a good option, but goes against our recent changes (switching to HC-128 and implementing CryptoRng).

BTW, lets not bikeshed thread_rng vs ThreadRng::new or other syntax here.

Using feature flags can affect dependencies, right? This might break assumptions of dependencies, so this seems dangerous. I would prefer to use different types instead and require the dependencies to be generic in the type of thread RNG.

Instead of providing several variants of ThreadRng, maybe it makes more sense to provide one conservative default and make it easy to construct custom ThreadRng (i.e. by making it generic in the RNG). Users who know the tradeoffs could pick the RNG best suited for their use case, maybe guided by a few recommendations in Rand.

I think HashMap should surely use a CSPRNG, otherwise it will likely be open to DOS attacks by an adversary who can observe random numbers (which would be a very plausible scenario for instance in a multiplayer game).

Yes, feature flags can affect dependencies, which is why I suggested what I did above.

Using a custom version of ThreadRng does not help reduce memory usage or per-thread initialisation time when dependencies are already using thread_rng.

DOS attacks

This is why I would not recommend using such a feature flag on servers. Interesting idea trying to use such an attack in multiplayer games, but there is no benefit for synchronous-step models (common in RTS) or attacking the server in server-centric models (common for FPS), and even if it were achievable vs other players the consequences are not high.

Going back to my proposal, I prefer fast_rng over weak_rng:

strong_rng for anything crypto
fast_rng for stuff like HashMap which by default is still a CSPRNG, but can be changed using a feature flag

Using a custom version of ThreadRng does not help reduce memory usage or per-thread initialisation time when dependencies are already using thread_rng.

I tried to argue that dependencies should make it possible for the user to choose the RNG, which wouldn't have this problem. If the thread RNG is not exposed via the API, it is an implementation detail and I think it should not be affected by feature flags, because it can have unintended consequences.

@pitdicker

Related to this, there are security trade-offs to decide:

Should we include fork protection, and if so should we check for fork on each value retrieved, or only when refreshing the buffer? According to @pitdicker this is 10-20% overhead vs 1-2% overhead.
Should we have forward secrecy, and if so should we immediately clear the buffer (high overhead) or should forward secrecy only protect past output after the next buffer refresh (moderate to low overhead, depending on RNG)?
Should we zero memory on drop? Obviously this is not guaranteed to happen and provides much less protection than forward secrecy.
Should we combine output with a fast external RNG (RDRAND) where available? I don't know how much overhead this would have, but it would greatly reduce the need to apply fork-protection and forward secrecy for each value output.

Given independent strong_rng and fast_rng these protections can be applied only where necessary, although if the two use the same back-end that is not the case.

@vks

@vks I don't get what you mean; you're saying use rand = { version = "0.5", features = ... }? That is feature flags. Or you're saying don't include a thread_rng function / state but only a macro or something allowing one to set up one's own version easily? But then each dependency would add its own thread-local generator, increasing memory usage even further. All dependencies have to use the same back-end(s) to avoid high memory usage (where several libs use Rand within an app).

I agree that having a fast_rng() and a secure_rng() (or strong_rng) seems like a good way to go.

Based on that I'd be tempted to provide very few security guarantees for fast_rng(). It's generally hard to get security from features that aren't designed for security, and I think it's great if we can optimize fast_rng() for performance rather than security.

I don't know enough about CSPRNG to have opinions about what guarantees that secure_rng() should provide.

On the topic of feature flags: Having feature flags which changes what guarantees fast_rng() and secure_rng() provides sounds very risky to me. That could result in someone wanting to relax security for library/feature X accidentally breaking security also for feature Y.

A better approach would be to encourage libraries which use rand to include feature flags which makes them use different Rng implementations to provides different performance/security trade-offs.

@sicking

While I partly agree with you @sicking it is important to consider uses like in HashMap which need unpredictable generators in some cases, but also fast ones. I think this is the original motivation for thread_rng.

I only see two solutions for this:

a fast & unpredictable generator like the current thread_rng
or a fast generator with opt-in or opt-out security via feature flags

A few comments on the first post, but I haven't though everything through yet...

Our current implementation of thread_rng tries to satisfy the above with a fast, secure PRNG, but at the cost of high memory usage and initialisation time per thread. For applications with a low number of long-running threads this is reasonable, but for many worker threads may not be ideal.

I am really not that concerned with the memory usage. While 4kb is a lot, it is also really not that much for any system that the standard library is available on.

The init time is something to worry about a bit more. On my PC it takes 5265 ns to initialize ThreadRng, of which only 400 ns are spend by OsRng. That is about 200.000 initializations per second, which I agree seems quite reasonable for long-running threads.

For the situation with many worker threads, isn't it better to use the scheme I ended up with of splitting an RNG using a wrapper such as SplittableRng (#399 (comment))? Also one lesson to take away from that thread was, that the overhead of TLS really becomes a big part of the performance of a fast PRNG such as Xorshift.

Performance with thread_rng, with caching:

test thread_rng_u32        ... bench:       2,887 ns/iter (+/- 28) = 1385 MB/s
test thread_rng_u64        ... bench:       4,320 ns/iter (+/- 26) = 1851 MB/s

Performance with thread_rng, without caching ThreadRng:

test thread_rng_u32        ... bench:       7,916 ns/iter (+/- 34) = 505 MB/s
test thread_rng_u64        ... bench:       8,593 ns/iter (+/- 58) = 930 MB/s

Performance with ReseedingRng<Hc128Core, ...> replaced by XorShiftRng:

test thread_rng_u32        ... bench:       6,323 ns/iter (+/- 13) = 632 MB/s
test thread_rng_u64        ... bench:       6,698 ns/iter (+/- 62) = 1194 MB/s
test gen_u32_xorshift      ... bench:         952 ns/iter (+/- 9) = 4201 MB/s
test gen_u64_xorshift      ... bench:       1,991 ns/iter (+/- 15) = 4018 MB/s

Retrieving the RNG from TLS greatly dominates the cost here.

The last two options sound very risky to me — should we ask distributors and end-users to reason about the security of whole applications? It is quite possible that the people building applications — even developers — will not know about all uses of thread_rng requiring secure randomness.

Yes, that is a big argument. It is the call site that determince whether ThreadRng is good enough to use. A scheme where the application is able to weaken the guarantees seems unacceptable to me.

On the other hand, we already reserve the right to change the algorithm of StdRng to another secure one. So making it partly configurable should not be a problem.

This brings me to ask, is having only a single user-facing function ideal? What if instead:

strong_rng replaces thread_rng as a source of cryptographically secure randomness

weak_rng is added as a fast source of randomness; depending on feature flags this could just wrap strong_rng or could be independent

Renaming thread_rng will be a very big breaking change, better to keep the name as it is in my opinion (or split that out into another discussion someday). And I still really dislike the name weak_rng. But I understand this is not about names, but about offering two kinds of functionality.

Still, having a thread-local variant using a fast RNG does not offer much advantage in the common case unless the RNG is cached.

But first, why bother when generators like Randen and RDRAND claim to satisfy all requirements anyway? This is a good question to which I only have vague answers: Randen is still new and unproven and may have portability issues; RDRAND is not fully trusted; and may not be the fastest option.

The performance of RDRAND, for comparison (1 value per iteration, instead of 1000 in the previous benchmarks):

test bench_u32 ... bench:          27 ns/iter (+/- 0) = 148 MB/s
test bench_u64 ... bench:          27 ns/iter (+/- 0) = 296 MB/s

RDRAND is 5-10× slower that the current ThreadRng.

Another, very different, option is that we keep thread_rng looking like it is but remove CryptoRng support and recommend it not be used for crypto keys.

Would you really recommend thread_rng for generating keys? At least for now we should be very careful before recommending that.

But what is the CryptoRng trait for, if not to say the generator is acceptable for cryptography?

As I said in the first post, ultimately such usage is about trust and risk, but the CryptoRng trait signals an intention to be secure. I agree, we should definitely not make a generator marked by this configurable to be insecure, but is it worth going the other way? Possibly not; just leaving thread_rng as-is is another option.

I feel like there are two very common use cases which I think would be great to have very easy-to-access APIs for:

A strong cryptographic rng. Useful for generating authentication tokens, temporary passwords, etc. I.e. must not be guessable in any form. As previously stated, I don't know enough about CSPRNG to provide more detailed requirements here.
A fast rng. Primary feature is that this generates values fast. But using this API should also generate a stream of values which is very unlikely to match the stream from any other run. I.e. should have a decent sized seed and be seeded from a source which is unlikely to generate duplicate values. However if it's hard-but-possible to guess future values based on a large enough set of old values, this is not a big deal. Useful for single-person games and simulations.

I was thinking 1 was secure_rng() and 2 was fast_rng(), but maybe that was wrong. In particular it might be better to encourage another API for 2 since something like fast_rng() requires a TLS access.

Maybe what I'm asking for for 2 is more dhardy#60 plus an empty ::new() function which seeds the returned object from something like secure_rng() or thread_rng()?

And to be clear, I think there are many uses of rng which does not fall into either of these categories. For these I think having APIs which are explicit about which RNG algorithm is used and what the source of seed is the way to go. That way developers can choose whatever algorithm provides the tradeoffs that match their requirements.

I don't know if HashSet falls into category 2 or not. Based on the fact that it currently uses a simple counter (though starting at a more strongly generated random number) makes me think that 2 is probably fine. But I haven't done enough research to be sure.

However the point is that if 2 is not fine for HashSet then it can use the solution from the last paragraph in the previous comment.

Though in reality I suspect that specifically HashSet won't use anything we're doing here since it's part of std.

Category 2 (simply fast) is actually pretty easy. Our current thread_rng is very fast (as long as the handle is cached), though sometimes SmallRng will be faster (we say specifically in the docs that benchmarking is important since performance is context dependent).

But when it comes to seeding a hash algorithm for HashMap and HashSet, the std currently uses an internal copy of the old thread_rng using the ISAAC generator, which is fast and possibly (hopefully) secure. This is because if the seed is known, an attacker can cause denial-of-service by causing a server to store many items in a single hash-bucket (which thus get stored in a simple list). This could instead be solved with better algorithms (e.g. a tree-based map), but these are ~~usually~~ sometimes slower (actually, I think hash-maps get over-used relative to their performance).

@sicking

@sicking

A fast rng. Primary feature is that this generates values fast.

I don't think this is well-defined. You can usually make RNGs faster by increasing the size of the state, because it allows for more instruction parallelism. Also, in which regard should it be fast? Initialization? Generating u64? Filling byte buffers?

That's a bit surprising to hear, considering chacha8 and chacha12 are consistently faster than hc128 across multiple architectures on SUPERCOP (with chacha20 often beating it out as well)

I have wondered about those benchmarks before. Some of those benchmarks of HC-128 are even off by two orders of magnitude! Maybe it is also counting initialization time, combined with a terrible implementation? And using an implementation of ChaCha that is much faster than anything there is in Rust at the moment?

I also tried the chacha crate, and it seems to be faster than our implementation, but still 3 times slower than HC-128.

There isn't a particularly good implementation of ChaCha in Rust right now that I know of (which is why I plan on writing one soon).

I wrote an explicitly vectorized ChaCha4 implementation for my simd_prngs repo but it's still very slow.

I guess I missed the previous discussion of Randen, but it looks like a very nice option for platforms where hardware AES is available:

https://github.com/google/randen
https://github.com/jedisct1/randen-rng (C reimplementation w\ SIMD/NEON ASM intrinsics)

Yes [you did]: #462

Edit to clarify: Randen looks like a good RNG, but I'd want to see third-party cryptographic review before promoting it here.

@dhardy

@dhardy I think this can be closed, now that we use a SIMD-optimized implementation of ChaCha?

I guess. We still haven't examined Randen or forward secrecy, but these are separate topics.

Navigation Menu

Repository navigation

Future of `thread_rng` #463

15 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Future of thread_rng #463

Description

Activity

vks commented on May 17, 2018

dhardy commented on May 17, 2018

vks commented on May 18, 2018

dhardy commented on May 18, 2018

dhardy commented on May 18, 2018

sicking commented on May 20, 2018

dhardy commented on May 20, 2018

pitdicker commented on May 20, 2018

dhardy commented on May 21, 2018

sicking commented on May 22, 2018

sicking commented on May 22, 2018

dhardy commented on May 22, 2018

vks commented on May 22, 2018

15 remaining items

pitdicker commented on Jul 12, 2018

vks commented on Jul 12, 2018

tarcieri commented on Jul 12, 2018

TheIronBorn commented on Jul 12, 2018

tarcieri commented on Jul 29, 2018

dhardy commented on Jul 30, 2018

vks commented on Jun 5, 2019

dhardy commented on Jun 5, 2019

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Future of `thread_rng` #463