Reconsider ReseedingRng

[vks]

Cryptographers are arguing against using any kind of reseeding, because it can compromise security (djb). Now that we are using an accepted stream cipher, the old argument about ISAAC does not hold anymore. I think we should stop reseeding StdRng and remove ReseedingRng. This would simplify the code, improve performance and arguably improve security as well.

[dhardy]

Because of @pitdicker's work (#281) the performance overhead should be negligible, although there would be code simplifications.

I think the crux of the linked argument is that including randomness from a potentially compromised source can be dangerous, but we only use randomness from OsRng or JitterRng. If either of these are compromised then we can offer no security anyway, as I see it (unless we always used both or just JitterRng which should be very difficult to compromise, but this has significant performance implications).

As for whether reseeding is useful, I don't know.

[pitdicker]

We already don't reseed StdRng, and we make clear that reseeding is generally not necessary.

There have already been a lot of discussion around this, have you read that? I have also read that post by djb, and he mainly argues against the merit of adding entropy to an RNG. What if an attacker can control that entropy source? Still, it is a good point. But I think it applies more to the OS RNG that should consider to just stop adding entropy, so there is no risk during a (pretty hypothetical) attack an entropy sources later.

In our case the entropy source is the OS RNG. Should we ever program defensively because it might have been breached? And if so, how do you know the initial seed of the RNG is ok, but later reseeds are not?

Still in our case there is the argument of security in depth. Reseeding protects against for example faulty implementations, and also user space is less protected than the kernel. Also ReseedingRng is the ideal place to add things like fork protection without overhead. And once #281 lands the performance overhead is basically zero.

Removing ReseedingRng would simplify code a little as you say. It would not improve performance, and be a small step back in terms of features and security.

[vks]

@dhardy

unless we always used both or just JitterRng which should be very difficult to compromise, but this has significant performance implications

That is not quite correct. Using both does not solve the problem, because compromising one of several entropy sources is enough, as discussed in the blog post I linked.

@pitdicker

We already don't reseed StdRng, and we make clear that reseeding is generally not necessary.

My bad, we are only reseeding thread_rng().

But I think it applies more to the OS RNG that should consider to just stop adding entropy, so there is no risk during a (pretty hypothetical) attack an entropy sources later.

Why? I don't see any difference for our use case.

In our case the entropy source is the OS RNG. Should we ever program defensively because it might have been breached? And if so, how do you know the initial seed of the RNG is ok, but later reseeds are not?

Should we ever program defensively because the the crypto algorithm might have been breached? How do you know reseeding fixes the breach?

It is possible that an entropy source becomes compromised later. "This source was not compromised" is a weaker assumption than "this source never was and never will be compromised". This is similar to the "trust on first use" approach often used with SSH.

Also ReseedingRng is the ideal place to add things like fork protection without overhead. And once #281 lands the performance overhead is basically zero.

Is it? Currently this would mean that only thread_rng() gets fork protection.

It would not improve performance, and be a small step back in terms of features and security.

Whether or not ReseedingRng improves security boils down to the question whether you think it is more likely that the crypto algorithm becomes compromised (assuming it can be fixed at all by reseeding) or that an entropy source becomes compromised after the initial seed. The latter is deemed more likely by djb and I'm inclined to agree with him.

[vks]

There have already been a lot of discussion around this, have you read that?

Where? I'm only aware of #230.

[dhardy]

Using both does not solve the problem, because compromising one of several entropy sources is enough, as discussed in the blog post I linked.

The attack mentions relies on the source of z being malicious and able to calculate H(x,y,z), which implies it must know x and y. In this case (and probably most cases) neither source of entropy can predict the results of the other sources. This means the source of z cannot determine H(x,y,z) until after producing z (if at all), hence it cannot influence the output.

Is it? Currently this would mean that only thread_rng() gets fork protection.

We certainly can't protect all CryptoRngs from forks because sometimes they are required to produce deterministic output from a specified seed, hence this would need to be in a wrapper, and ReseedingRng becomes a logical choice for that.

I do wonder if we should make ReseedingRng combine state from both its previous output and fresh entropy (e.g. produce two seeds and XOR them). And no, DJB's attack doesn't make this weaker than the status quo, because (a) if an attacker can compromise the entropy source after initial seeding, with the current approach he would be able to fully control the reseeded RNG where with combination he would need to know the original seed to do the same, and (b) if an entropy source were compromised during initial seeding then fixed, then the attacker would not know the fresh entropy used later so the reseeding key would be unpredictable.

Where?

A lot of discussion has been badly organised. You could spend several hours reading comments in the RFCs I wrote, but I'm not sure where exactly.

[pitdicker]

I am sorry, that was a little frustration from my side. Some things just have just come up several times since august last year, or at least that seems so to me. And if not in the last half year, then in the history of issues/PRs/RFC about rand to rust repro before...

Actually I made a PR to remove ReseedingRng once, dhardy#6. The commit that did so is gone from it now however, so no evidence 😄. It came up once in a while in the rfc discussions rust-lang/rfcs#2106 and rust-lang/rfcs#2152. And dhardy#59 was the latest plan to combine (some form of) fork protection with ReseedingRng. The comment from djb also came into the discussion before, even in a much older RFC rust-lang/rfcs#722. But somehow I can't find back some of the things I remember we discussed.

But I think it applies more to the OS RNG that should consider to just stop adding entropy, so there is no risk during a (pretty hypothetical) attack an entropy sources later.

Why? I don't see any difference for our use case.

The RNG in the Linux kernel (what this is mostly about) is of a type we don't yet have in Rand. It has an actual entropy pool that frequently gets integrated into the state of the RNG. And the algorithms that do so have been under frequent discussion (and where not the best if I remember). What we have is a CSPRNG of which the entire that gets completely re-initialized. I have even argued for such a complete re-initialization because of the comment by djb in your first post.

Should we ever program defensively because the the crypto algorithm might have been breached? How do you know reseeding fixes the breach?

Depends on how obscure the algorithm is you use 😄. For things like ChaCha I would say we are ok. What we may have to worry more about, are Rust re-implementations that can be of variable quality of algorithms. But this is not the primary argument for ReseedingRng.

I believe the common way a CSPRNGs might turn out to be 'broken' is if over the course of very many runs slowly details about the RNGs internal state get revealed. If you reseed (by recreating the RNG from scratch) during this window, you prevent the vulnerability.

@dhardy Again we wrote a reply at the same time 😄.

[vks]

Thanks a lot for the clarification!

[burdges]

In fact, I read DJB's comments primarily as a narrower critique on algorithms, like ECDSA, that use more randomness than more deterministic algorithms, like EdDSA, because CSPRNG designers cannot fully eliminate these problems.

In his example, DJB discusses a PRNG that holds x and y fixed with the adversary altering r before forcing a re-computation of H(x,y,r), but actually it frequently makes no difference if x and y are fix or exist at all. In fact, an attacker who can force reseeding, and observe, the output can always force a partially desirable output, no matter whatever else you do. There is no inherent advantage or disadvantage to doing your own entropy pool or not doing one, except.. You do want a solid entropy pool at some level, so.. If you do not believe in the kernel's pool then you should send Linus a pull request. ;)

In fact, an attacker who can force new threads can do this attack independently of any ThreadRng design. It's largely the iteration speed that determines the attack's effectiveness. I'd therefore expect that ThreadRng using ReseedingRng with a CSPRNG and a long reseeding interval is no more vulnerable than any given ThreadRng design alone.

All this becomes worse if the attacker can observe the x and y of course, because they can do this attack themselves "offline". You should thus be careful about using a ReseedingRng with fixed secret information and a PRNG not designed to hide its seed. In principle, ReseedingRng could use non-fixed secret information, like hashing some of its own output with the incoming entropy, but again if it uses a bad enough PRNG then this still sucks.

Interestingly, there might be a use case for the otherwise useless CryptoRng here, roughly restricting ReseedingRng<R,S>: CryptoRng to when R: CryptoRng and S: CryptoRng.

[dhardy]

What's the conclusion of this discussion — no actionable items? I suggested one thing but it's off-topic so I'll open another issue.

[burdges]

Also the impl<R: CryptoRng, Rsdr: CryptoRng> CryptoRng for ReseedingRng<R, Rsdr> {} idea.

[pitdicker]

So we added the CryptoRng bound (it was supposed to be there in the first place though), and #301 explores a follow up idea.

Then I think this issue can be closed?