Seeding PRNGs (traits and bit size)

[dhardy]

Update again:

pub trait SeedRestriction: private::Sealed + Default + AsMut<[u8]> {}

pub trait SeedableRng: Sized {
    type Seed: SeedRestriction;

    fn from_seed(seed: Self::Seed) -> Self;

    fn from_rng<R: Rng>(mut rng: R) -> Result<Self, Error> {
        let mut seed = Self::Seed::default();
        let size = mem::size_of::<Self::Seed>() as usize;
        unsafe {
            let ptr = seed.as_mut().as_mut_ptr() as *mut u8;
            let slice = slice::from_raw_parts_mut(ptr, size);
            rng.try_fill_bytes(slice)?;
        }
        Ok(Self::from_seed(seed))
    }
}

---

So far we have proposed the following:

• seeding via a u64 (convenient non-crypto usage)
• seeding via the full state size (512-bits for ChaCha, 8192 for Isaac, 16384 for Isaac64)
• seeding from another RNG

If we're seeding from another RNG, there's probably no reason not to fill the entire state space from this source; we are very likely seeding from a CSPRNG which can easily provide as many bytes as we need for little more cost than just copying a smaller set of bytes multiple times.

On the other hand if we are providing a seed, we might want to use the maximum key size possible. On the other hand, we may well only want to provide a sub-set, such as a 128-bit or 256-bit key (AES uses these key sizes). So should we add functions to seed from 128-bit and 256-bit keys instead of forcing users to copy their key into a larger zero-initialised array?

Actually, the current implementations allow seeding from u32 or u64 slices of undefined length. Keeping this functionality seems sensible.

But why not support seeding from byte slices instead? The only difference is that enforced alignment may allow more efficient copying from a slice of u32 or u64. Considering the user may already have a key in a byte-slice, this enforcement probably does more harm than good (forcing an extra copy or unsafe pointer-coercion).

This leaves me wondering if the current SeedableRng proposal is such a good idea; perhaps instead we should have the following:

pub trait SeedableRng: Rng {
    // when associated constants are allowed:
    const MAX_SEED_BYTES: usize;
    // alternative:
    fn max_seed_bytes() -> usize;
    
    // supports any number of bytes up to max_seed_bytes()
    fn seed_from_slice(&mut self, &[u8]);
    
    // not technically required, but convenient:
    fn seed_from_u64(&mut self, seed: u64);
}

(SeedFromRng may stay a separate trait providing the other type of seeding.)

[burdges]

I'd say drop the u64 honestly because afaik the only use cases is pulling out less randomness from another PRNG to seed a lot of PRNGs and that sounds useless even if you care about convenience and speed.

I donno if seeding by the whole internal state always makes much sense either. Yes, you could set the internal state for some permutation like ChaCha or Keccak to produce random numbers, but the normal usage of ChaCha allocates 128 bits to fixed constants, at least a u32 for a counter, and the remainder to the nonce.

I dislike using slice methods since they make user pepper their code with asserts to emulate type checking. It's also bad to encourage unsafe code by not returning the actual type. Afaik, there is never any reason for this trait to be object safe since you only make new Rngs with it, not using existing ones, so why not something intuitive like :

pub trait SeedableRng: Rng {
    type Seed: Rand;
    fn from_seed(seed: Seed) -> Self;
    fn from_rng(rng: &mut Rng) -> Self { Self::from_seed(rng.gen()) }
}

There are uses for object safety in some sort of ReseedableRng trait, so one might imagine something more like :

pub trait ReseedableRng: Rng {
    fn add_entropy_u128(&mut self, entropy: u128); 
    fn reseed_from_rng(&mut self, rng: &mut Rng);
}

[dhardy]

No, the use-case of seeding from u64 was simulations and the like which just want a convenient way of seeding any PRNG from a number and swapping the PRNG. But so long as we standardise seed types somehow, we don't need seed_from_u64 for that (e.g. the byte slice version would also work).

I don't see much use in using ReseedableRng over just replacing with a new instance (like ReseedWithDefault does now) — ?

I'm not sure I see any point in setting the entire internal state either. But using a fixed bit-size like add_entropy_u128 isn't a good choice either, and only allowing a single key size also doesn't feel right.

You missed my point about being able to seed from whatever key size the user has directly (without e.g. copying into SeedableRng::Seed), but maybe that's less important. Using a byte slice is however more flexible for users and not really hard for PRNGs to implement.

I don't see where asserts would need to be used. The API should allow usage with any number of bytes up to the maximum and just ignore extra bytes; the only things might be considered "wrong" are providing too many bytes (not really important) or not enough bytes (perhaps this makes it easier for users to provide insecure implementations, I don't know).

[dhardy]

Part of the issue with having an associated fixed-size type Seed as @burdges proposes is the question of what the seed-type should be for PRNGs with large internal state like Isaac (as @burdges says, there's little sense in requiring a key as big as the whole internal space, yet using anything else explicitly prevents users from setting all bits with fresh entropy, which seems a premature decision unless there is a strong proof that more bits of entropy does not make the algorithm more secure).

Although slices aren't ideal, is there a better solution (besides allowing a whole family of seeding functions/traits using different sizes)?

[burdges]

The seed sized should be determined by the PRNG, normally being 256 bits, but perhaps the type expresses alignment issues. In many usages like data structures, there should be a fatal error if the seed size does not match the seed provided, so this can either be done with type checking or with asserts.

[dhardy]

I disagree; users should be able to use a 128-bit seed with a generator like ChaCha if they wish, or a 256-bit seed, or even a 512-bit seed (if the generator can use it). Not to rule out other sizes (e.g. 192 or 384).

[burdges]

I think if a user who wants to use a 128 bit seed with ChaCha then they should explicitly pad the seed with zeros, or call some special method whose documentation indicates this behavior. It's harder to audit code when you need to think about lengths of all the slices.

I take it Isaac+ has no standard that defines a seeding procedure? I suppose either there is a security argument that some smaller seed plus zeros is fine even from the beginning, or else you seed with the smaller value and run if for one round before using the output. You could provide a from_slice_with_zeros inherent method just for Isaac, probably with panic if the slice exceeds 256 u32s or if the slice is shorter than whatever the minimum is. We could set SeedableRng::Seed to whatever makes SeedableRng::from_rng happy too, maybe running this one throw away round if that's common. I have not read the security papers on Isaac+ so I don't know the recommendations.

I'm not advocating for ReseedableRng per se, but there is no way to make SeedableRng object safe without asking folk to create unseeded Rngs first, and that creates security bugs.

[dhardy]

Point noted about not wanting to check slice lengths, but this is normal practice with large buffers. Anything else makes it hard to avoid extra copy operations, though maybe we shouldn't worry too much about that here.

Uh, probably @burdges you didn't see that we abandoned ISAAC+ (see also here).

No, I'm not aware of a standard seeding routing for ISAAC. The author recommends seeding with the output of a secure cipher (see bottom of page). We could make a seeding routine for some selected key size (maybe to 256 bits), I suppose, and either pad with zero (current code does this) or use another PRNG (e.g. ChaCha) to expand the given 256-bits to the full state size. @pitdicker has just been looking at this.

If we go that route, we either have to prevent direct provision of the full state size or add another function. And then we need to choose which seeding functions we have, e.g. from 64 and 256 bits, maybe also 128 and 512?

[burdges]

If you have a long enough slice, then the arrayref crate gives you fixed length arrays without copies, which gives you the correct panic behavior and puts the panic closer to the user's call site than if the panic happens in a library called by a library called by your library.

I'd forgotten about ISAAC+. It sounds like ISAAC users need access to the full state, since the author does not express confidence in his seeding routine, but not necessarily through SeedableRng.

I think you want impl FromIterator<u32> for Isaac for this, so that Isaac::from_iter(my_seed_slice) works where my_seed_slice: &[u32], but also Isaac::from_iter(rng.gen_iter()) seeds by setting the whole state. We can obtain other seeding behaviors like

Isaac::from_iter(my_seed_slice.iter().chain(seed_pad))
Isaac::from_iter(my_seed_slice.iter().cycle().zip(seed_pad).map(|(x,y)| x^y))

where seed_pad is a static nonzero padding slice. In theory, all these calls avoid copies thanks to the effort spent optimizing rust for Iterators. I'm not bothered by an iterator consuming a short seed without panicing for several reasons, although maybe if you do the same for ChaChaRng.

[dhardy]

Interesting point. impl FromIterator<T> could replace SeedFromRng entirely, except of course that T would vary (usually between u32 and u64 but maybe not exclusively). This hiding of the underlying type is the core difference between Rng and Iterator.

Of course, it would be possible to set the state of a PRNG like ISAAC using SeedFromRng, but constructing a mock Rng implementation to do that isn't so simple (also the code doing it would be more obscure).

Implementing SeedFromRng, SeedableRng with a fixed key size (e.g. 256-bit), seed_from_u64, and FromIterator<T> for some T does meet all requirements I guess. Hmm, now PRNGs need to implement 4 seeding functions?

Of course, we could throw out seed_from_u64, but since both SeedableRng::Seed and T in FromIterator<T> are implementation-defined, seed_from_u64 is the only uniform deterministic seeding method all PRNGs support (ignoring contrived seeding via SeedFromRng).

I suppose we could fix that T and require all PRNGs to support FromIterator<u32>, but this forces 64-bit generators to deal with alignment and type-coercion issues.

[newpavlov]

Can't we use something like this?

pub trait SeedableRng: Rng {
    const SeedSize: usize;

    fn from_seed<S: ToSeed<Self::SeedSize>>(seed: S) -> Self;

    fn from_rng(rng: &mut Rng) -> Self {
        let mut buf = [0u8; Self::SeedSize];
        self.fill(&mut buf);
        Self::from_seed(buf)
    }
}

pub trait ToSeed<const SeedSize: usize> {
    fn to_seed(&self) -> [u8; SeedSize];
}

And implement ToSeed for numeric types, arrays and slices of those numeric types? If input is larger than needed then we truncate it, if smaller we pad it with zeros. We also could add to output of to_seed number of input bytes, so from_seed could e.g. panic if needed. Yes, here we'll do unnecessary copies, but: a) compiler will be able to optimize some of those, b) I don't think we should worry about it that much, as copy cost should be negligible for most applications. Drawback is that we force RNG implementations to work with seeds in the form of fixed-sized byte arrays, not sure if it's a big issue or not.

[dhardy]

I don't see much point in that @newpavlov. I didn't really get @burdges requirements with asserting length, but the only difference between this and passing a slice directly is that it is possible to make some assertions about length in to_seed (though we may not want that).

The problem with this is that it assumes each RNG has an ideal length of seed which is the maximum possible length, and always pads smaller seeds with zero. This may not be the case; e.g. small seeds may be repeated and/or modified with some magic number, and there may not be an ideal seed size, as in ISAAC could use a whole 8192 seeding bits but 256 would often be more reasonable.

[newpavlov]

The point is that from_seed will be able to consume almost everything what (reasonable) users would like to feed it (e.g. from_seed(0x123456u64), from_seed([1u8, 2, 3]), from_seed(&buf[..100]), etc.) without any need for additional methods. Instead of converting seed into array of given size we could convert it into slice of bytes, so from_seed implementation could be smarter. But we'll still need something like const OptimalSeedSize: usize; for from_rng.

Click to expand

pub trait SeedableRng: Rng {
    const OptimalSeedSize: usize;

    fn from_seed<S: ToSlice>(seed: S) -> Self;

    fn from_rng(rng: &mut Rng) -> Self {
        let mut buf = [0u8; Self::OptimalSeedSize];
        self.fill(&mut buf);
        Self::from_seed(&buf)
    }
}

pub trait ToSlice {
    fn to_seed(&self) -> &[u8];
}

UPD: But drawback of this approach will be usage of native endian...

[burdges]

Is there no iterator adapter in the itertools crate or whatever that agglomerates or splits numeric types according to a specific endianness? It'd be easy enough to write, but does need endianness.

I think FromIterator<T> makes lots of sense if a common way to seed to set the whole internal state, like Isaac. It's less clear for ChaCha where standard versions all fix the first 128 bits and the counter comes in between the key and the nonce.

A priori, I'd think lengths should be avoided @newpavlov favoring actual types [T; N] instead. Firstly, rust still handles associated types much better than associated constants. Second, someone can have seeds with unusual properties that way, like additional configuration, a custom Rand, or GenericArray. Yes I'm happy GenericArray will disappear with const-dependent types arrival, but the example stands.

Afaik, we expect tricks like impl<const N: usize, T> Foo for T where T: Bar<Item=[u8; N]> to work eventually, so associated types should be strictly more powerful than associated constants. It'd change if associated constants ever got special treatment in vtables to make them object safe, but that'll be years away if ever. We cannot get object safety here anyways since we need -> Self methods.