Constructing an PRNG from fresh entropy

[dhardy]

For discussion of this section of the RFC.

It has been suggested that it should be possible to override the implementation of NewSeeded (see also using an fn instead).

A second point relevant to the NewSeeded trait is allowing seeding via a back-up entropy source, first suggested at the end of this comment, with another note at the end of this comment.

Possibly we should have something like the following; this still doesn't address the question of allowing other implementations (regarding which I still don't understand the need for one):

pub trait NewSeeded: Sized {
    fn try_new() -> Result<Self, Error>;
    fn new_with_fallback() -> Self;
}

[pitdicker]

One thing I was thinking about a few days ago was that it is often good enough to seed a new rng with ThreadRng. Not sure yet if there is a real advantage.

It would be faster for sure. Its goal is to be about as secure as OsRng by using a cryptographical RNG and frequent reseeding from OsRng.

Would it be a good fall-back if the OsRng is not available? I don't think so. What is ThreadRng going to be initialized and reseeded with if OsRng is unavailable? In that scenario it would be unavailable to.

[dhardy]

If your goal is secure crypto seeding, think about entropy. If thread_rng is seeded from the system clock then used to seed a crypto-RNG, then there is only as much entropy as gained from the system clock — which is very likely not enough (you previously mentioned 20 bits, which allows brute force attacks quite easily).

If thread_rng is well-seeded from the OS and an attacker cannot directly see the output from thread_rng, then quite possibly the system is secure against attack — but that's a lot of ifs.

I don't actually see the point though — I mean most users won't need to seed a lot of PRNGs. I suppose a server creating a lot of encrypted communications might, but then that application should probably use its own master-CSPRNG and not piggy-back thread_rng (which, per the current design, merely has no known attack, rather than be considered secure).

[nagisa]

Continuing this. You said

To be honest, I don't see why anyone would need to write an alternative implementation for NewSeeded though.

I don’t really see either, why would anybody really want to write one. My problem with the trait is it giving a false sense of genericism, which doesn’t really exist here.

e.g. if somebody is exposing API that might initialise its own RNG, they might end up writing something along the lines of

fn banana<T: NewSeeded>() -> Result<Peach> {
    let mut new_rng = T::try_new()?;
    ...
}

hoping that they’re giving users the options to do something else, but that’s not really the case.

Now, the trivial solution to this problem is to promise to make the blanket implementation specialisable (i.e. default fn), and I would like to see such promise stated in the RFC.

[dhardy]

The Sample trait isn't meant to allow custom implementations either. So what?

Ok, I'll think some more about this. But if a user wanted, say, to use a different entropy source to initialise XyRng when calling try_new, IMO that's the wrong approach, and instead he/she should add a new function or trait to initialise from this different entropy source. This keeps the topics separate: gathering entropy, using a fallback if necessary, and constructing the RNG.

In other words, users are explicitly not supposed to override the behaviour of NewSeeded. Sorry if using a trait is confusing in that regard. Maybe there's another good design, I don't know.

[dhardy]

I opened #18 regarding seeding traits; lets keep this issue about where the entropy comes from and NewSeeded.

[dhardy]

Well, an alternative would be simple functions. Personally I don't like it as much because the calling syntax isn't so simple and NewSeeded served to group two similar items.

fn try_new_seeded<R: SeedFromRng>() -> Result<Self, Error> {
    let mut r = OsRng::new()?;
    R::from_rng(&mut r)
}
fn new_seeded_with_fallback<R: SeedFromRng>() -> Self {
    match try_new_seeded() {
        Some(result) => result,
        Err(_) => { /* TODO */ },
    }
}

[dhardy]

Note: IMO these functions shouldn't be member functions of OsRng because that is only one of multiple possible entropy sources. Presumably we'll have a fallback something like this.

[newpavlov]

I think the main source of confusion is the trait name, maybe it's worth to rename it to NewOsSeeded or to SeedFromOs? (plus second name will be aligned with the SeedFromRng trait)

[dhardy]

In principle I agree with @newpavlov but I'm not so keen on the suggested names, partly because we have multiple sources of entropy. I guess SeedFromOs is okay, but it's less clear that it provides a try_new function; having New in the name is a hint to this, right? How about NewSeededOs?

By the way, I made a PR implementing this, feel free to review.

[dhardy]

How about renaming NewSeeded to:

pub trait AutoSeeded: Sized {
    fn new() -> Result<Self, Error>;
}

The real question is what to do if OsRng is unavailable; this is why new returns a Result.

Thanks to @pitdicker's great work (#28) implementing jitterentropy we have a high quality alternative to OsRng. It's not perfect (it's slow, and it can fail on platforms with poor timers), but it appears to be high quality (passed 1 GiB in my PractRand test).

Do we need another fallback in case both OsRng and JitterRng fail? See this post.

@pitdicker already suggested that new should automatically use JitterRng as a fallback, and need not bother returning a Result (since failure of both entropy sources is very unlikely we would just panic in this case). This is presumably assuming the trait is available with std only since JitterRng also requires std (for a timer; actually the JitterRng code can still be used if another timer is provided but I don't think we can support that in AutoSeeded).

Regarding no_std, the AutoSeeded trait itself is no_std compatible but I don't see how its implementations could be. Since Rust requires trait implementations to be in the same module as either the trait or the object, keeping this trait would not be useful (except with no_std specific RNGs). On the other hand if AutoSeeded is #[cfg(feature="std")] then no_std code can come up with its own version no problem, although other code using rand::AutoSeeded would be incompatible. Maybe this isn't a problem we need to solve anyway though?

---

Questions:

• Any objections to the new name, AutoSeeded?
• Is there any good reason fn new should not use JitterRng?
• Is OsRng + JitterRng sufficient (i.e. are there any important std platforms likely to fail both)?
• Should fn new return Result<Self, _> or just Self?

[burdges]

Apologies for being out of the loop, but I never understood why AutoSeeded::new() could not simply be a default method for SeedableRng or whatever that's called now?

Is it merely so that OsRng could go into another crate separate from SeedableRng? If so, that sounds more like a reason not to separate the crates, and use features instead.

[dhardy]

Yes, it's so the crates can be separated.

Personally I think it's a good split: rand-core just contains low-level API stuff (well, also the impls module, but that's self-contained at least), and rand contains all the accessories needed to use that.

There's another reason I'm against using a default method: that would imply that implementations may want to override the default. But IMO having this method should be an automatic consequence of implementing SeedFromRng (and importing the trait), and users should be able to assume it acts the same way on all PRNGs.

Basically I consider AutoSeeded::new to be a library function, but with better syntax. Maybe that's an abuse of the language, but it seems appropriate enough to me.

[burdges]

I do not understand the reasoning for split there, but maybe that's a derail here.

If you prevent overriding anyways, then one can import a freestanding function like

pub fn auto_seed_rng<R: SeedableRng>() -> R

with only use rand::auto_seed_rng as opposed to remembering another name.

Also, there is a tendency for new to be inherent, and maybe some Rngs would still provide an inherent new, so importing or not this trait makes naming slightly confusing.

[dhardy]

Yes, there is a tendancy for types to define their own new function... but for PRNGs there are only two options:

• Use a default state (same every time): we already have new_unseeded, and IMO these methods should not exist
• Pass some type of seed to new — but since this is what SeedableRng is all about, the only other use would be compliant to some other standard, e.g. ChaCha::new_ietf — in which case the name should reflect the standard and not simply be new

In other words, the only sensible new any SeedableRng implementation should have is the one provided by AutoSeeded or a similar trait. Given that, I really don't see why you are against this trait. (The only identifier to remember is AutoSeeded, because new is, well, exactly the function you expect to use to create a new instance, right?)

[burdges]

I think Andrew Tanenbaum quote "The nice thing about standards is that there are so many of them to choose from" agrees with your suggestion of new_standard ;) but presumably many actually do initialize in one unique way.

I'd agree with dropping new_unseeded too: If you're going to seed it immediately, then you can always create the Rng like

let mut rng = if .. {
    MyRng::newlike1(..)
} else if .. {
    MyRng::newlike2(..)
} else { unreachable!() }

or maybe

let mut rng: MyRng;
loop {
    ...
    if .. {
        rng = MyRng::newlike(..)
        break;
    }
}

If you do not know if you'll ever seed it, then you need an Option<MyRng> anyways, or some lazy scheme like thunk-rs or some specialized LazyRng scheme that avoids interior mutability and heap allocation.

pub struct LazyRng<R,F>(LazyRngInner) where R: Rng, F: FnOnce() -> R;
enum LazyRngInner<R,F> {
    New(f),
    Run(r),
    Empty,
}

impl<R,F> Deref for LazyRngInner<R,F> where R: Rng, F: FnOnce() -> R {
    type Target = R;
    fn deref(&self) -> &R { panic!(); }  // Not pannicing here would require interior mutability
}
impl<R,F> DerefMut for LazyRngInner<R,F> where R: Rng, F: FnOnce() -> R {
    fn deref_mut(&mut self) -> &mut R { self.force() }
}

impl<R,F> LazyRng<R,F> where R: Rng, F: FnOnce() -> R {
    pub fn new(f: F) -> LazyRng<R,F> {
        LazyRng(LazyRngInner::New(f))
    }

    fn force(&mut self) -> &mut R {
        use LazyRngInner::*;
        let init = if let New(_) = self.0 { true } else { false };
        if init {
            let inner = ::std::mem::replace(&mut self.0, Empty).0;
            self.0 = Run(if let New(f) = inner { f() } else { unreachable!() })
        }
        match self.0 {
            New(f) => unreachable!(),
            Empty => unreachable!(),
            Run(r) => &mut r,
        }
    }

    pub fn into_inner(self) -> R {
        use LazyRngInner::*;
        self.force();
        match self.0 {
            New(f) => unreachable!(),
            Empty => unreachable!(),
            Run(r) => r,
        }
    }
}

In fact, I think LazyRng should impl Rng, and maybe even SeedableRng, directly because my DerefMut without Deref trick breaks &self methods, which individual Rngs may posses. Incidentally, this might make LazyRng a counterexample to AutoSeeded::new() being the only sensible new for any SeedableRng. I donno if this matters ;)

[dhardy]

Your LazyRng is quite esoteric — initialisation is usually fast enough that it's not worth doing lazy-initialisation on the off-chance you never need it, and usually it's preferable to handle possible errors early.

Yes, there are some other possible constructors one might want to name new, so we could rename the other constructor to new_auto or something — but I'm strongly against this because it's optimising for the esoteric case and burdening users with a harder name to remember.

[dhardy]

#54 is merged. I'm going to mark this "solved".

[dhardy]

Implemented