Is CryptoRng useful?

[dhardy]

Perhaps this can stay open for a while as a discussion item. I'd especially like feedback from lib users who have looked at this trait.

This trait has requirements on the PRNG algorithm, but not the seeding method (as comes up in #537):

/// A marker trait used to indicate that an [`RngCore`] or [`BlockRngCore`]
/// implementation is supposed to be cryptographically secure.
/// 
/// *Cryptographically secure generators*, also known as *CSPRNGs*, should
/// satisfy an additional properties over other generators: given the first
/// *k* bits of an algorithm's output
/// sequence, it should not be possible using polynomial-time algorithms to
/// predict the next bit with probability significantly greater than 50%.
/// 
/// Some generators may satisfy an additional property, however this is not
/// required by this trait: if the CSPRNG's state is revealed, it should not be
/// computationally-feasible to reconstruct output prior to this. Some other
/// generators allow backwards-computation and are consided *reversible*.
/// 
/// Note that this trait is provided for guidance only and cannot guarantee
/// suitability for cryptographic applications. In general it should only be
/// implemented for well-reviewed code implementing well-regarded algorithms.
/// 
/// Note also that use of a `CryptoRng` does not protect against other
/// weaknesses such as seeding from a weak entropy source or leaking state.
/// 
/// [`RngCore`]: trait.RngCore.html
/// [`BlockRngCore`]: ../rand_core/block/trait.BlockRngCore.html
pub trait CryptoRng {}

The trait can guarantee absolutely nothing about the quality of the seed used on the PRNG. For example, it would be quite easy to write:

let key = [0u8; 32];
// TODO: randomise the key
let rng = ChaChaRng::from_seed(key);

and forget to actually add any entropy to the system.

Or, in some ways worse (because it is harder to spot), the key could be written using a non-crypto RNG (stretching an insecure key).

There is no easy way to guard against insecure seeding (and even if there were, there are other ways to go wrong in cryptography). Even if we added a function like this it wouldn't really help:

pub trait CryptoRng {
    /// Implementations must estimate the number of bits of entropy in their seed
    fn estimate_entropy(&self) -> u32;
}

It would be simple enough to detect seeds with too many 0s or 1s, but still extra complexity to implement. Detecting that the seed was set by a weak PRNG however would be much much harder (computationally very expensive and very complex) — this is not viable.

Summary: security is a property of the complete implementation, not just the type.

So my conclusion: CryptoRng appears to be making a promise it cannot guarantee when implemented on PRNG algorithms.

Options:

1. Keep the status quo; rely on documentation
2. Remove implementation of CryptoRng from PRNG algorithms and keep only on OsRng, JitterRng, EntropyRng and ThreadRng (which all manage their own seeding or directly get entropy from external sources)
3. Remove the CryptoRng trait altogether

[dhardy]

Since the rationale of CryptoRng is type-level documentation, the second option seems a good choice to me. It would improve the guarantee provided by something like this:

fn do_something_secret<CR: Rng + CryptoRng>(rng: &mut CR) { ... }

And it would still allow user-defined types to implement the traits, though of course we recommend only implementing on types which manage seeding internally. For example:

pub struct SecureRng(Hc128Rng);

impl SecureRng {
    pub fn new() -> Self {
        SecureRng(Hc128Rng::from_entropy())
    }
}

impl RngCore for SecureRng { /* derive core functions */ }

// Do NOT implement SeedableRng for SecureRng!
impl CryptoRng for SecureRng {}

[vks]

I agree that SeedableRng can be problematic for CSPRNG. If we want to be conservative, we could remove SeedableRng from StdRng (Option 4), although this would not allow some use cases:

1. Seeding with a key.
2. Using StdRng for its statistical quality only.

Changing the definition of CryptoRng to not apply to seedable RNGs would help, but even then I'm not sure it would be a helpful trait. If I wanted to make sure my randomness source is secure, I would probably just pick an implementation and not make the code generic. This is what all the Rust crypto libraries are doing, they essentially use their own implementation of OsRng.

In summary, I think generic code involving CryptoRng is probably a bad idea, so we might as well remove the trait.

[burdges]

We could do runtime checking by providing a function like

trait CryptoRng { fn is_crypto(&self) -> bool; }

for which that OsRng simply returns true, but any CSPRNGs copy a flag from their seed:

impl SeedableRng for ChaChaRng {
    type Seed = <ChaChaCore as SeedableRng>::Seed;

    fn from_seed(seed: Self::Seed) -> Self {
        ChaChaRng(BlockRng::<ChaChaCore>::from_seed(seed))
    }

    fn from_insecure_rng<R: RngCore>(rng: R) -> Result<Self, Error> {
        BlockRng::<ChaChaCore>::from_rng(rng).map(ChaChaRng)
    }

    fn from_rng<R: RngCore+CryptoRng>(rng: R) -> Result<Self, Error> {
        let mut n = Self::from_insecure_rng(rng);
        n.is_crypto_flag = rng.is_crypto_flag();
        n
    }
}

We should not even implement CryptoRng for completely non-cryptographic PRNGs, so numerical users might require seeding non-cryptographic PRNGs from non-cryptographic PRNGs. We could support this without special methods though:

pub fn seed_with_insecure_rng<R,T>(rng: R) -> T
where R: RngCore, T: RngCore+SeedableRng
{
    struct FakeCrypto(rng: R)
    impl CryptoRng for FakeCrypto { fn is_crypto(&self) -> bool { false } }
    impl RngCore for FakeCrypto { ... }
    T::from_rng( FakeCrypto(rng) )
}

[dhardy]

@burdges I already mentioned runtime checking in the first post. I don't like it, because e.g. from_seed could be called with something that's not random (but maybe still looking random).

[burdges]

Is this doable entirely at the type level once the const feature set improves? Ala

pub trait CryptoRng { const fn is_crypto() -> bool; }

We could give CSPRNGs a type level parameter like:

pub struct ChaChaRng<const IS_CRYPTO: bool>(BlockRng<ChaChaCore>);
impl<const IS: bool> CryptoRng for ChaChaRng<IS> { fn is_crypto() { IS }}

but I fear this will become annoying in practice.

There are interesting type level work around with wrapper types:

type CryptoRng { const fn is_crypto() -> bool; }
pub struct NonCrypto<R: RngCore+CryptoRng>()

impl SeedableRng for NonCrypto<ChaChaRng> {
    type Seed = <ChaChaCore as SeedableRng>::Seed;
    fn from_seed(seed: Self::Seed) -> Self {
        ChaChaRng(BlockRng::<ChaChaCore>::from_seed(seed))
    }
    fn from_rng<R: RngCore>(rng: R) -> Result<Self, Error> {
        BlockRng::<ChaChaCore>::from_rng(rng).map(ChaChaRng)
    }
}

impl SeedableRng for ChaChaRng {
    type Seed = !;  //. Or <ChaChaCore as SeedableRng>::Seed;
    fn from_seed(seed: Self::Seed) -> Self {
        panic!("Insecure seeding of cryptographically secure PRNG");
    }
    fn from_rng<R: RngCore>(rng: R) -> Result<Self, Error> {
        NonCrypto<ChaChaRng>::from_rng(rng)
    }
}

We could also split SeedableRng into an insecure trait SeedableRng and a secure trait FromRng:

pub trait SeedableRng : Sized {
    type Seed: Sized + Default + AsMut<[u8]>;
    fn from_seed(seed: Self::Seed) -> Self;
}
pub trait FromRng : SeedableRng {
    fn from_rng<R: RngCore>(mut rng: R) -> Result<Self, Error> {
        let mut seed = Self::Seed::default();
        rng.try_fill_bytes(seed.as_mut())?;
        Ok(Self::from_seed(seed))
    }
}

We'd simply explain that FromRng should be secure but code that used SeedableRng requires stricter auditing. meh..

[burdges]

I dislike all these answers myself actually. :) In fact I'll add several concerns that count against CryptoRng :

Tests or benchmarks in cryptographic crates might employ non-cryptographic PRNGs, like Xorshift, maybe so that benchmarks more accurately represent the crate's actual work, or maybe because the standard is written that way.

It's common curve libraries, etc. have functions to build an element with an Rng but frequently you actually want to construct this element with PRF output, so you do MyCurveScalar::generate( ChaChaRng::from_seed(my_prf_output) ), which such tricks cannot recognize as secure.

There are various cryptographic properties one might consider here, including the security level.

[dhardy]

I see @quininer has used CryptoRng in several places, e.g. oake, sarkara, keyber and @tendermint has in yubihsm.

All these examples are part of a generic API: allowing some kind of secret to be seeded from a user-provided secure RNG.

For these usages I think it makes sense to keep CryptoRng, but as mentioned above, recommending CryptoRngs do not implement SeedableRng makes sense. This doesn't provide a uniform way of constructing such RNGs however, so how about we add a method to CryptoRng?

pub trait CryptoRng {
    // like SeedableRng's version, but also require CryptoRng
    fn from_rng<R: RngCore + CryptoRng>(mut rng: R) -> Result<Self, Error>;
}

We could then implement FromEntropy for CryptoRngs as well as SeedableRngs.

In practice: this means that CSPRNGs would have two "guises": the seedable variant (impls RngCore and SeedableRng) and the secured variant (wraps the other; derives RngCore and impls CryptoRng via SeedableRng). Limitation: this doesn't really work for reproducible and secure CSPRNGs.

[burdges]

Isn't that going to break OsRng: CryptoRng? You could add a method to FromEntropy ala

/// ...
/// This trait assures cryptographic security when used together with most rand crate methods, including `FromEntropy`, but not when used with `SeedableRng` or methods from outside `rand`, including inherent methods.
/// ...
pub trait CryptoRng { }

pub trait FromEntropy: SeedableRng {
    fn from_entropy() -> Self;
    fn from_crypto_rng<R: RngCore + CryptoRng>(mut rng: R) -> Result<Self, Error>;
}

But..

I disagree strongly with not implementing SeedableRng for CSPRNGs because PRFs are ubiquitous, as I said above. In fact, I'll argue that all CSPRNGs use cases require from_seed, except for those already handled entirely inside rand, ala ThreadRng or EntropyRng or whatever, which makes the FromEntropy solution useless. In fact, even the English phrase CSPRNG refers to algorithmic assumptions/properties, not input to the algorithm, so that's all one could mean by CryptoRng.

There are ways to consider the CSPRNG inputs when doing formal verification, but this requires languages with much stronger dependent types, like F*, and even languages that understand game-hopping proofs, like CryptoVerif/ProtoVerif. There is a tentative project to compile Rust to F* for these purposes, btw.

Also, we should not imho go with runtime checking but my initial runtime musings actually did handle from_seed correctly. You could even require justification strings everywhere:

trait CryptoRng {
    fn assert_crypto(&self, &'static str);
    fn is_crypto(&self) -> Result<&'static str,&'static str>;
    fn claim_crypto(&mut self, &'static str);
}

But CryptoRng itself still means "the algorithm is a CSPRNG".

[dhardy]

Good argument @burdges. Then I guess we should do nothing here.

I brought this up because in #537 @vks keeps saying that CryptoRngs should not implement seed_from_u64 (because that's not appropriate for cryptography), but I don't see why the algorithms shouldn't still implement it for non-crypto uses.

[vks]

I don't see why the algorithms shouldn't still implement it for non-crypto uses.

It's a tradeoff. On the one hand, seed_from_u64 is never the correct way to initialize a CSPRNG that is actually required to be cryptographically secure, on the other hand, not having it makes them more annoying to initialize for non-crypto purposes.

[burdges]

If seed_from_u64 becomes a SeedableRng method, then you could either ask that it panic all CryptoRngs, or else provide a wrapper type that it panics. I think either sounds fine since if you were using ChaChaRng as just a better numerical PRNG then you'd also likely be okay calling from_seed, no?

[dhardy]

No, because either the type CryptoRng protects against bad seeding or it does not, and as we have discussed here protecting against bad seeding does not appear to be viable.

I don't see some halfway-house solution (deliberately breaking seed_from_u64 on crypto PRNGs) as useful.

[vks]

What's the decision here? Keep the status quo?

[dhardy]

Yes. @burdges is right that we can't really just make SeedableRng incompatible with CryptoRng and I don't see another good option.

Runtime checking would be a partial fix, but then really we'd want to modify from_seed:

fn from_seed(seed: Self::Seed, is_crypto: bool) -> Self;

(or wrap the boolean with a struct / enum, but same effect)

The status quo is poor but foo<R: Rng + CryptoRng>(rng: &mut R) is basically documentation.

[burdges]

Yes, I think a bool or Option<&'static str> argument works fine, if you want (debug) runtime checking. I'd like runtime checking more if I didn't know about plans to compile Rust to F* for much stronger validation ;)