Crate evaluation for 2017-07-25: rand

[brson]

I was just reveiwing @briansmith’s rand definition in ring, and quite like it. This looks like a really good, minimal, and correct foundation. Though I think we want to give users more conveniences than that. The method that most casual end users want is more like the existing rand crate’s polymorphic random method.

I’d personally feel really good about paring rand way back to be more like ring’s rand with some conveniences. Leaving most of the other matters touched on by rand today to future work in other crates.

[brson]

ring is very minimal, it’s core definition being SecureRandom, that has one method.

The equivalent in rand is Rng, which also has a fill_bytes method, though that one does not return a Result type. Rng then has lots and lots of convenient methods on it. I wonder to what extent those convenient methods are enabling that nice polymorphic random function (I’d guess a lot).

[brson]

Another interesting comparison to draw between ring’s trait and rand’s is that ring’s SecureRandoms fundamental operation is fill_bytes while Rngs is next_u32, and it provides a default method for fill_bytes.

[brson]

Thanks for the review @jmst.

[brson]

Ok, just some more musings. One could imagine that a minimal rand crate is just the simple SecureRandom definition from ring, which gives you simple and correct access to random numbers, and then also a polymorphic random function that does the right thing for basic casual use cases.

Some of the consequences of this design might be

• If you want seedable, deterministic random numbers you would have to go elsewhere, maybe via a different implementation of the SecureRandom trait, in another crate.
• If you want seedable, deterministic random numbers in some other form than a byte buffer you would have to… maybe random is parameterized, or has another form that takes a SecureRandom.
• All the conveniences that today’s Rng trait provides, and that presumably feed into that nice random function could be hidden implementation details, or perhaps an extension trait.
• Performance of a naive implementation of the random function would be bad because it has to ask the OS for bytes in small chunks. This is a big part of the reason the thread local rng exists. So we would probably still need the thread local rng but it could be an implementation detail.

I also want to call attention to this point from @briansmith’s earlier review:

This mixing causes trouble for some applications. For example, Rng has next_f32 and next_f64 methods, which means that it cannot be fully implemented on any system that does not have floating point support and/or which wants to avoid linking in the floating point libraries.

The issue of working in float-free environments is real, and something worth thinking about. But of course the core library also suffers this problem, as it contains float definitions. I’m not sure if we have today a way to cfg based on cpu float capability, but it sure would be nice if the rng is not tied to that.

[brson]

Ok, just one more extreme idea. It seems viable to rename this crate to oldrand, change this crate to be nothing but the content of ring’s rand module (though maybe renaming SecureRandom to Random), and leaving all other conveniences to battle it out as experiments in other crates (though I do think we would immediately need that polymorphic random function somewhere). Then we would have a stronger foundation at the source of random number generation, and have room to breath about all the other features people might want.

[bhickey]

The RNG returned by thread_rng() should be guaranteed to be cryptographically secure, since that’s the safe default. An unsafe_thread_rng() could also be provided that is faster but cryptographically insecure. This mimics the Rust policy on hash table where the default is secure (note that misusing an insecure RNG is catastrophic, while misusing an insecure hash table merely leads to denial of service).

Maybe there should be a global_rng() / GlobalRng that would be the same as thread_rng() / ThreadRng except global and thus using an Arc<Mutex<<…>> instead of an Rc<RefCell<…>>. This could then be used to initialize the per-thread RNGs without requiring reading /dev/urandom. When the reseeding threshold is reached on a thread_rng, the global rng also needs to be reseeding before using it to reseed the thread rng, to preserve current behavior.

In principle I’m supportive of this, but I have some concerns around reproducibility. Ergonomic reproducible randomness is nice to have. Haskell’s Random Monad does a good job of this. Without global or thread state, we oblige users who want reproducible results to pass around additional nuisance parameters.

Today thread_rng() offers no reproducibility guarantees and with good reason: if we had seed_thread_rng(...), a callee could smash the caller’s seed. I have a prototype that tracks thread_rng state in a stack and offers rand state safety versus non-pathological callees.

What do you mean by this? AES can be used as a DRBG for sure, but you still need an entropy source.

The typical setup is to run AES CTR-DRBG. Seed AES from entropy and then encrypt a counter to generate your stream. While it’s true that AES-NI is pretty fast, the unaccelerated performance is lousy. ChaCha20 might be a good alternative. It isn’t much slower than AES-NI and was designed with low power devices in mind.

RNGs, especially cryptographically secure ones, should be designed, if possible, so that retrieving the seed doesn’t allow to determine past random numbers, but only future ones, and whether this is the case should be explicitly documented for the RNG

This sounds like an exciting area for research. I haven’t seen literature on the subject, but I’m more interested in PRNGs than CSRNGs. IIRC Blum-Blum-Shub should satisfy this property as long as the primes remain secret. A secure hash function might fit the bill, but I’d want to see actual cryptanalysis: n_t+1 = HMAC(n_t, k)

[jethrogb]

FYI You misquoted me

[scottmcm]

A secure hash function might fit the bill, but I’d want to see actual cryptanalysis

The folks behind Keccak (selected as SHA-3) talk about PRG use of the sponge construction in section 4.2 of http://sponge.noekeon.org/CSF-0.1.pdf

[bhickey]

Oops, fixed, I think. Sorry bout that. I was merging comments and made a copy-paste error.

[nagisa]

I’d love if the default trait method was something like filling a buffer and then any conveniences implemented in terms of that.

You probably want to allow users to specialise the from_u32 etc somehow, just so it would be possible to avoid putting the u32s into a buffer and extracting them back out when the RNG internally generates u32s. Filling a buffer should still be a required function, though.

For example RDRAND instruction can natively generate u16, u32 and u64 bit chunks.

Also I’m not sure I’ve seen noted in the thread yet is the huonw’s ages old attempt at redesigning rand https://github.com/huonw/rand/tree/next/src. I’m sure we can draw ideas about distributions and ranges of numbers from the crate.

[nagisa]

How about an AES-based RNG? Many CPUs have hardware AES acceleration, so it might be faster than anything else on those, while obviously being cryptographically secure (with proper constant time implementation).

As with RDRAND, I feel like it is a good idea to have it is as a separate crate. in fact I believe that we should strive to have the bare minimum (interface + thread_rng) in the rand crate and the other generators (weak, hardware accelerated, mixing, all sorts of PRNGs) in external crates. Possibly also split out the distributions (if we’re not putting them into the core rand interface as per huon’s proposal).

[troplin]

I don’t know if this has been discussed before, but both SecureRandom and Rng look a lot like std::io::Read.

IMO the basic primitive of a random number generator should be just a marker trait that inherits from Read.

[sfackler]

I’d be a bit hesitant to do that - the semantics we want are those of read_exact, not read, and accidentally short-reading your random data is very bad! In addition, none of the extra functionality (read_to_end, read_to_string, lines, etc) makes any sense in the context of an RNG. Matching Rng up to Read because a method has a similar signature seems like a false equivalence.

[troplin]

But Read is just a stream of bytes that can be read. Nothing in Read says, that the stream must be finite or that it must be text, and in fact in many cases it is not. All the counter points that you list here apply to any kind of byte stream, not just random data. Any stream of bytes should implement Read and if that does not fit here, then Read is a bad abstraction.

I do agree, that text based methods like read_to_string and lines don’t make sense. But they don’t make sense for most other byte streams either. IMO they don’t belong in Read at all.

[ExpHP]

By that same logic one could argue that it should be a subtrait of Iterator<Item=u8>; but one can’t expect every Rng to implement both with matching output.

I believe it is more reasonable that if somebody really wants to use an arbitrary Rng as a Read, there could be a wrapper adapter type.

[troplin]

Well yes, I think iterators and streams are very much related and it would be great if they were unified. But that’s not how it is and Read is very similar to what is proposed here, while Iterator<Item=u8> is not.

Personally, I wouldn’t even care about a separate trait at all and an RNG can implement Read or Iterator<Item=u8> or both.

[dhardy]

Okay, there are two quite different uses for RNGs:

1. (scientific) simulations and games
2. cryptography

For the former, quality of randomness (evenness of distribution and independence of samples) can be important. Performance is sometimes important. Having several well-known, seedable generators is useful (e.g. once I reproduced results from a MATLAB stochastic model using MT19937 in C++, thus proving the new implementation matched the old).

For the latter, I suspect many of you know more than me, but as I understand it, there are essentially two uses: (1) get a very high quality random number, likely using OS support, and (2) get a pretty good random number more quickly using a cryptographically-proven RNG.

There’s another dimension to generators: interaction with threads. If you want a crypto-RN in a multi-threaded app, the thread_rng approach works fine (as I understand it). If you want a deterministic simulation using an RNG, well, it’s hard to use any randomness in threads at all, but it may be possible by creating a “sub-RNG” at specific points seeded from a master-RNG (using a different algorithm to ensure indepedence of samples from the master RNG), and passing the sub-RNG to a worker thread.

[dhardy]

With the above in mind, rand could potentially be split into three crates, although I’m not sure it’s a good idea:

1. a crate containing a pseudo-random-number-generator (RNG) trait, and several implementations (crypto-grade, simulation-grade and otherwise)
2. a crate providing something like thread_rng which is crypto-grade, using OS-provided numbers and possibly a good RNG-based generator, all as a convenient source of “reasonbly secure” random numbers; this might depend on the first crate
3. a crate providing a set of distributions and support for generating numbers given an RNG implementing the trait in the first crate

Crypto apps might just use the second crate. Scientific simulators might use the first and third, doing their own initialisations. Games and such might use the second for convenience or do the same as simulators if they need more control or performance.

[notriddle]

As a specific case, games with procedural generation are only going to want the first one (seeded PRNG) so that the save file can just store the seed without storing the whole level.