1
$\begingroup$

I need a continuous (infinite) strong random generator, but I've only got limited entropy as seed. I know there's already a contradiction there, but I'm looking for a practical approach.

Suppose I have a piece of 1024 bit strong random entropy (a one time constant for this particular stream), and a cryptographically secure hash function, say Sha512 or Sha3-512.

Would this generate a proper stream of random data:

  • Next block of random bits = hash( unix or system time || entropy || last block of random bits )

Fundamentally I know there is no more real entropy in this than the initial 1024 bits. Plus maybe one bit or so per round from the unix or system time (maybe a few more if we take microseconds) but that's very predictable.

Yet considering the hash to be a CSPRNG, I'd say the output would be totally unpredictable, and good enough for all reasonable purposes? Or am I overlooking something?

As long as the initial seed remains hidden, would this 'leak' or impose any security risks when using this stream of randomness to extract encryption keys, for example? (which are supposed to be independent)

$\endgroup$
  • $\begingroup$ If you have a SHA-3 implementation, do you have the SHAKE functions too? Those do pretty much what you are after. $\endgroup$ – otus Dec 1 '15 at 12:27
  • 2
    $\begingroup$ Alternatively, just use one of the NIST 800-90 DRBGs. Using a vetted solution is always better than rolling your own. $\endgroup$ – poncho Dec 1 '15 at 18:04
  • $\begingroup$ Why don't you just use a stream cipher like AES-CTR or ChaCha20? $\endgroup$ – SEJPM Dec 1 '15 at 19:58
2
$\begingroup$

As noted in the comments, simply using your initial entropy to seed a deterministic random bitstream generator, such as those specified in NIST SP 800-90A Rev.1, or as a key to any secure stream cipher or a block cipher in OFB / CTR mode, should be enough to generate a bitstream practically indistinguishable from random.

Actually, 1024 bits of seed entropy is overkill for that. Even a 256-bit keyspace cannot be enumerated using known physics (yes, even quantum computing) and resources available to mankind, so the only way to break (i.e. distinguish from true randomness, without prior knowledge of the key) a DRBG with a 256-bit seed length is through cryptanalytic attacks that exploit some flaw in the generator — and adding more seed entropy generally doesn't help against attacks like that. This is fortunate, since most standard DRBGs / ciphers don't actually accept a seed / key longer than 256 bits, or, if they do, they'll internally hash it down to a shorter internal state.

That said, if your chosen DRBG does not directly accept long keys, and if you're not 100% sure that your 1024-bit seed really has 1024 bits of entropy, you may still want to hash it down to 256 bits (using a secure cryptographic hash function), instead of simply truncating it, before feeding it to the DRBG. Alternatively, you can simply use a hash-based DRBG (such as the Hash_DRBG or HMAC_DRBG constructions from SP 800-90A.1, or the SHAKE functions from SHA-3 / FIPS 202) that directly accepts an arbitrarily long seed, and automatically hashes it down to its internal state size.


In any case, without a better entropy source than system time, I would not bother with attempting to merge additional entropy into the PRNG state — or at least, not the way you're proposing to do it. Specifically, your proposed method has a couple of serious weaknesses:

  • If the initial entropy is ever leaked, an attacker can fairly easily predict future outputs just by observing a block of output and guessing when the next output will be generated. (The precise level of difficulty will depend on the precision of the clock input, and on the predictability of the usage patterns, but even in the best case it's unlikely to deter a serious attacker.)

  • In particular, by observing two output blocks separated by one unknown block, an attacker can both guess the middle block and verify their guess quite efficiently (most especially so if they can observe the two blocks within a short period of time).

  • Conversely, if the initial entropy is not leaked, mixing in the system time doesn't really provide any added value. It does, however, destroy the determinism of the generator, which might be considered a drawback.

  • Also, if the seed entropy is leaked, and an attacker can observe two or more previously generated successive outputs of the generator, they may be able to learn when those outputs were generated, which could be information one might not wish to reveal.

If you do wish to incorporate additional entropy from the system time (or other low-density entropy sources), I'd suggest using a proper entropy pool design such as Fortuna, which is designed to recover from state compromises by accumulating entropy into multiple internal pools that are only used to reseed to PRNG once they've accumulated enough entropy to resist brute force guessing.

$\endgroup$
1
$\begingroup$

A CSPRNG is able to recover from state compromises. Your proposed approach can't. Your design's internal state comprises the unix or system time, the 1024 bit entropy, and the previous block of random output. Once these values are compromised, an attacker can brute force the time value to guess the subsequent output blocks. If the attacker can request for random numbers from your generator, then that makes things even easier - he knows the time of his own requests and he has the previous output blocks that he requested.

The security of your design is also not robust. The whole point of CSPRNGs having entropy sources is to enable them to recover from state compromises. Put another way, if we're sure that a PRNG's internal state can never be compromised, then there no need to continually mix in new entropy into its internal state. Furthermore, we need as many entropy sources as we can get. This is because we want as much entropy as we can get (for reasons stated in the 1st paragraph), and also because we can never be sure the attacker won't compromise the sources themselves. In your case, you have only 1 entropy source - the unix or system time. That certainly isn't enough.

Another characteristic of your design that may be problematic (depends on application) is that you can't easily replicate your random sequence. A PRNG should be able to repeat the same output when given a particular seed. What you're doing here is reseeding before generating every output block. So the only way for you to replicate your output sequence would be to store all the time values. This would be fine for encryption keys, but if you want to repeat simulations with the same set of random parameters then you'll have some trouble.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.