3 ms·

Interesting. Would the re-keying process require a source of fresh entropy, if it's to be non-deterministic?

tptacek 11y ago
No. Modern CSPRNGs based on DRBGs are relying on fundamental crypto building blocks like block ciphers and hashes. A single bit difference between the previous state and the new state after the addition of any entropy whatsoever completely scrambles the RNG state. Obviously, you're getting many more bits than one out of your regular updates from the entropy collection subsystem.
- kevhito 11y ago
  Well, maybe? If the purpose re-keying is to recover from a transient compromise, then a single bit isn't really sufficient, is it? If the attacker has completely recovered the old seed, they can recover the entire rng stream up to the point where the reseeding happens. The attacker would notice the new output doesn't match, and at that point can't the attacker simply (brute force) try mixing in a 0 or 1 bit to see which one matches the new output of the rng? Even a few bits wouldn't protect against a brute force simulation of the reseeding. It seems like re-seeding a few bits at a time is in fact worse than storing up, say, 128 bits of new entropy then reseeding all 128 bits at the same time. With small incremental reseeding, the attacker can brute force each small reseeding if they can observe the rng outputs. Or is there something I'm not seeing about how reseeding works?
  - tptacek 11y ago
    I knew someone was going to say this. In fact, the last sentence of my comment was added in an edit after this rebuttal occurred to me. Yeah. Dunno. Definitely don't slowly permute your CSPRNG state one bit at a time.
  - tomsmeding 11y ago
    That's one of the things that's mentioned in the paper: don't seed one bit at the time. Moral of this discussion (not of the paper) is that you should regularly reseed, but only when you can completely replace the seed with entropy, and don't worry about making users wait for randomness because it makes you look interesting.

No. Modern CSPRNGs based on DRBGs are relying on fundamental crypto building blocks like block ciphers and hashes. A single bit difference between the previous state and the new state after the addition of any entropy whatsoever completely scrambles the RNG state. Obviously, you're getting many more bits than one out of your regular updates from the entropy collection subsystem.

kevhito 11y ago
Well, maybe? If the purpose re-keying is to recover from a transient compromise, then a single bit isn't really sufficient, is it? If the attacker has completely recovered the old seed, they can recover the entire rng stream up to the point where the reseeding happens. The attacker would notice the new output doesn't match, and at that point can't the attacker simply (brute force) try mixing in a 0 or 1 bit to see which one matches the new output of the rng? Even a few bits wouldn't protect against a brute force simulation of the reseeding. It seems like re-seeding a few bits at a time is in fact worse than storing up, say, 128 bits of new entropy then reseeding all 128 bits at the same time. With small incremental reseeding, the attacker can brute force each small reseeding if they can observe the rng outputs. Or is there something I'm not seeing about how reseeding works?
- tptacek 11y ago
  I knew someone was going to say this. In fact, the last sentence of my comment was added in an edit after this rebuttal occurred to me. Yeah. Dunno. Definitely don't slowly permute your CSPRNG state one bit at a time.
- tomsmeding 11y ago
  That's one of the things that's mentioned in the paper: don't seed one bit at the time. Moral of this discussion (not of the paper) is that you should regularly reseed, but only when you can completely replace the seed with entropy, and don't worry about making users wait for randomness because it makes you look interesting.