backtracking resistant RNG

[MatMaul]

Background

It is sometimes necessary to use a backtracking resistant RNG for cryptographic or compliance reasons.
It seems this crate doesn't yet provide such thing.

Feature request

Creating one seems really easy since I believe we just need to take the output every X bytes and reseed the generator with it.
I am happy to provide a PR for that, I did a quick prototype for it directly in chacha20 crate.

I am opening this issue to request if you would take such a thing, and where do you think we should do that: here in rand crate, directly in chacha20 crate, elsewhere?

Do we want a specific Rng type for that?
Or should we make this the default since the computing cost is almost null?

Would we want to just take the output every X bytes and reseed the generator or would it be sensible to change the default alg to match current go impl that has a specification and a test vector, ChaCha8Rand? Actually an implementation already exists.

[dhardy]

It seems this crate doesn't yet provide such thing.

take the output every X bytes and reseed the generator with it

In a way we do: ThreadRng automatically reseeds periodically, though not frequently. #1750 proposes re-exposing the internal mechanism directly (something I'm still undecided on).

Note that there is a trade-off here; frequent reseeding has a performance cost, while infrequent reseeding limits the effectiveness of the backtracking resistance. Does your cryptographic regulation ("compliance") have anything to say in this regard?

If frequent reseeding is required I suggest you omit the local CSPRNG entirely and just use OsRng; on some platforms (Linux at least) this is fairly fast anyway.

Anything else, I don't think should be within the scope of rand.

[MatMaul]

Note that there is a trade-off here; frequent reseeding has a performance cost, while infrequent reseeding limits the effectiveness of the backtracking resistance.

I agree it's quite costly if we do a full rekeying that involves getting a seed from the system RNG, but rekeying with a seed coming from the previous output seems really low in term of perf impact.

Does your cryptographic regulation ("compliance") have anything to say in this regard?

The regulation doesn't talk about rekeying itself but asks (translated):

compromission of the internal state and/or the random sources should not allow the attaquer to gain any new information about previous output.

If frequent reseeding is required I suggest you omit the local CSPRNG entirely and just use OsRng; on some platforms (Linux at least) this is fairly fast anyway.

Yes that looks sensible indeed.

Anything else, I don't think should be within the scope of rand.

Thanks for the fast answer 🙏 I know where to go now!

[dhardy]

Reading that requirement literally, reseeding would be required after every output. This would have a non-trivial performance cost and may not be faster than using OsRng directly (testing required; platform dependent).

One can place the same requirement on the OS's random source; further analysis here is platform-dependent. Usage of a (reseeding) CSPRNG in process-local memory does not protect against compromise of the OS random source if that is not backtracking resistant.

[MatMaul]

I agree the requirements are quite broad and not precise enough here. It seems like Linux OS RNG has been deemed compliant ™️ so I think we are just going to use that.

[tarcieri]

Note that there is a trade-off here; frequent reseeding has a performance cost, while infrequent reseeding limits the effectiveness of the backtracking resistance.

There are constructions specifically designed for fast reseeding: https://blog.cr.yp.to/20170723-random.html