ReseedingRng: combine fresh and old state?

[dhardy]

My comment, from #298:

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.

Pseudocode:

let key1 = self.gen();
let key2 = EntropyRng::new()?.gen();
let key = key1 ^ key2;
*self = Self::from_seed(key);

Using XOR to combine two keys has the disadvantage that if an attacker knows one input and the output then he can learn the other key, but that shouldn't matter here: one key comes from the OS (should be secure) and the other from the old generator — we assume cryptographic, hence knowledge of output should not allow calculation of state.

Theoretical advantage: if the external entropy source becomes compromised, the reseeded RNG may still remain secure. (Whether this advantage is significant or worthless I don't know.)

Performance impact: should be low I think since reseeding only happens rarely.

[burdges]

I'm fine with roughly this scheme but.. I'm wondering if key should be derived by "hashing" key1 and key2, although presumably if both provide CSPRNGs then XOR works.

Also, there would be no benefit from many cartographic hash function requirements, like collision resistance, so if one want hashing then we're talking more SipHash, but SipHash itself has too little output, so maybe some simple construction inspired by hash functions, like SipHash.

[dhardy]

Is there any benefit to hash functions? I suppose there's avalanche: make each output bit affected by every (or at least multiple) input bits. Assuming both input keys are the output of cryptographic PRNGs / have low bias, I don't see any real benefits from hashing.

[burdges]

I've no particular argument for hashing either. I've no variable-width ARX construction examples even. And endianness issues with the &[u8]. So XOR then. :)

[pitdicker]

This seems all very theoretical to me. Whether you need to use ReseedingRng is already questionable, and whether you should be afraid of a compromised OsRng is also questionable. Does that make combining the output of the old RNG with the output of OsRng preparing for a scenario that is questionable²?

I see no harm in it, but feel like we are over-thinking.

[pitdicker]

How shall we proceed with this issue?

It seems overly cautious to me, but not without merit. Maybe we should just do it?

One small disadvantage is that it would have to use from_seed instead of from_rng. And what should happen if ReseedingRng::try_fill fails? I suppose it is ok to just self-reseed, and schedule a delay just like we do now.

[dhardy]

I don't know; it's not high priority however. I guess the overhead should be small even if this computation is complex.

Perhaps we should forget it; I mean the only real advantage of this scheme is extra protection in case someone is able to manipulate the OS RNG, but if they can do that you probably have bigger problems anyway.

[dhardy]

@tarcieri can I get your opinion on this? Realistically the only reason I can see it being useful is if a bug reduces the entropy source's quality (e.g. AMD's RDRAND failure on resume-from-standby). Note that we already catch failures here and do catch this particular bug; this change would only help with bugs we haven't caught.

Of course if the source is compromised it seems pointless to assume anything else.

[tarcieri]

Reseeding, done correctly, is at least as secure as the most secure of the inputs. That said I'd need to see code to know if the desired solution is secure.

[dhardy]

Is the pseudo-code in the first post clear enough? If not, I can make a PR.

To go ahead, this needs to:

1. Not introduce any new weakness — I believe combining two full-size keys via XOR is sufficient to achieve this.
2. Have at least some perceived usefulness — yesterday I almost closed this before considering the "bugs" angle.

[dhardy]

This doesn't appear to be necessary.