Simple seedable insecure random number generation, stable across Rust versions

[joshtriplett]

API design partially based on discussions with @BartMassey. Revised based on feedback, in particular from @Amanieu and @joboet.

Proposal

Problem statement

People regularly want to generate random numbers for a variety of use cases. Doing so currently requires using a crate from crates.io. rand is the 6th most downloaded crate on crates.io, and fastrand is quite popular as well. Many, many people over the years have expressed frustration that random number generation is not available in the standard library (despite the standard library using randomness internally for HashMap).

There are multiple reasons why we have not historically added this capability. Primarily, there are three capabilities people want, and those capabilities seem to present a "pick any two" constraint:

• Secure random number generation
• Seedable random number generation
• Stability between versions of Rust when seeded

These constraints arise from the possibility of a secure random number generator potentially requiring updates for security reasons. Changing the random number generator would result in different sequences for the same seed.

In addition to that primary constraint, there have also been design difficulties: there are numerous pieces of additional functionality people may want surrounding random number generation, which makes any proposal for it subject to massive scope creep and bikeshed painting. Most notably: users of random numbers may want to represent the state of the RNG explicitly as something they can pass around, or implicitly as global state for simplicity.

This ACP proposes a solution that aims to be as simple as possible, satisfy all the stated constraints on the problem, and allow for future expansion if desired. This ACP handles the "pick any two" constraint above by providing a seedable random source that is explicitly identified as insecure. This will allow us to keep the insecure seedable generator the same across Rust versions and targets.

This ACP builds on the accepted ACP 393, which added an RNG that is secure but does not guarantee identical output across Rust versions.

Motivating examples or use cases

• Generating randomness for games (e.g. rolling dice).
  • Allowing "replay" of such games by providing a seed
• Randomly shuffling a list
• Randomly sampling elements from a set
• Random test case generation / fuzz testing
  • Allowing reproduction of such test cases by providing a seed

Solution sketch

This builds upon the APIs added in ACP 393, and only specifies the new APIs.

This would live in the core::random module.

/// A seeded, insecure random number generator.
///
/// This source uses the ChaCha CSPRNG, but does not claim to be hardened for security; for secure
/// randomness use `DefaultRandomSource` or another `RandomSource`.
///
/// This source does not attempt to protect against `fork`, VM forks, or similar; if the process or
/// VM forks, this source will return the same series of outputs in both forks.
pub struct InsecureRandomSource { /* no public fields */ }

impl InsecureRandomSource {
    /// Create a seeded random source from the specified seed.
    ///
    /// Two instances of this source created from the same seed will produce the same series of
    /// outputs, even on different Rust versions or different targets.
    pub fn from_seed(seed: [u8; 32]) -> Self { /* ... */ }

    /// Get the original seed of this random source.
    pub fn get_seed(&self) -> [u8; 32] { /* ... */ }
}

impl RandomSource for InsecureRandomSource { /* ... */ }

// Note that the Debug impl does not expose the seed or internal state.
impl Debug for InsecureRandomSource { /* ... */ }

// A cloned copy of a random source will return the same series of outputs.
//
// The `InsecureRandomSource` does not implement `Copy`, so that producing two sources with the
// same outputs requires an explicit clone.
impl Clone for InsecureRandomSource { /* ... */ }

This ACP proposes using a simple implementation of a ChaCha-based RNG.

The seeded insecure random number generator, given the same seed, will provide the same sequence of random numbers, on all targets.

Alternatives

We could avoid providing seeded random number generation at all, and refer people who need seeded random number generation to external crates.

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[joshtriplett]

I've updated this proposal to build upon the now-accepted ACP 393, along with the changes proposed by @joboet.

[Amanieu]

I don't think "insecure" is the important part of these. In fact, it is downright misleading since ChaCha is a CSPRNG. The key property of this RNG is that it is seedable and once seeded is guaranteed to always return the same results. A better name would be SeedableRandomSource.

[joshtriplett]

@Amanieu

Given sufficient confidence in ChaCha as an algorithm, it's certainly possible for us to create an implementation that 1) implements all the necessary protections a secure implementation might want (e.g. protection against fork, protection against VM fork, memory locking, protection keys where available), 2) commits to fixing those if there's an issue with them, 3) commits to addressing future scenarios we haven't thought of yet, and 4) still provides the same outputs in future versions.

However, it's much much easier and more maintainable for the uses requiring secure randomness to call getrandom or equivalent (via DefaultRandomSource), and delegate secure randomness to the kernel and/or hardware. That means we don't have to take on that maintenance burden ourselves.

The point of this proposal is to have a "good enough" RNG that doesn't make some of those promises, and is easy to maintain, and provides seedability.

If people really want to name this ChaChaRandomSource we can. But I still think it's important to disclaim any potential claims about security that people might otherwise assume, and point people towards DefaultRandomSource for secure randomness. (I've expanded the doc comments in this proposal accordingly.)

[pitaj]

Is my understanding that this would fulfill the Math.random() use case?

[the8472]

I don't think "insecure" is the important part of these. In fact, it is downright misleading since ChaCha is a CSPRNG.

So was RC4 in the distant past. The issue is that no practical cryptographic algorithm rests on proofs that the problem is outside P, and how could they, since P!=NP has not been proven yet. And many symmetric algorithms do not rest on mathematical proofs at all.

So even if we assume today that they're secure for practical purposes, we cannot promise so for the future. This is why josh is correct about the "pick any two" aspect.

If we promise seedability and stability then we should be prepared for the possibility that it one day will be considered insecure. At which point we would not want to be in a situation where users rely on it for security purposes, which means actively discouraging its use for such purposes.

[CAD97]

Allowing "replay" of such games by providing a seed

I just want to note that a PRNG is likely a poor choice for this specific use case; noise based RNG (link: GDC talk) is what is actually appropriate. Specifically, PRNGs are limited to advancing their state forward. RNG derived from chaotic integer noise (essentially a hash function) on the other hand is random access, allowing replays to be jumped around without burning CPU time spinning the PRNG.

Of course other constraints might still prevent random seeks, and “keyframe” style solutions to those can be applied to the PRNG as well, but (since this is a notable use case for using deterministic RNG) this still bears mentioning.

[the8472]

Not all RNGs are trapdoors, e.g. the ChaCha keystream is seekable and can double as an RNG. Block ciphers in counter mode would do too. It's mostly dedicated cryptographic RNG constructions that are trapdoors to provide forward secrecy, which isn't relevant for insecure ones.

Though you'd still need an API for seeking.