I'm looking for an RNG that in the case that an attacker would get all or part (most likely part) of the pseudorandom data, there will be no way for them to deduce the original seed more efficiently than brute force.

Which RNG's would comply with my requirements?

  • 2
    Might be worth looking into "Cryptographically secure pseudorandom number generators". – AleksanderRas Aug 6 at 12:29
  • I did that but none of them explicitly state they fill said requirement – Tom Aug 6 at 12:31
  • 4
    Note that this requirement can be equivalently reformulated as "given any subset of RNG output it should be impossible to predict any non-given output better than guessing". – SEJPM Aug 6 at 13:07
up vote 2 down vote accepted

Random number generation is the generation of a sequence of numbers or symbols that cannot be reasonably predicted better than by a random chance... Source: Wikipedia

It follows that "an attacker [with] all or part" of the sequence cannot "predict any non-given [part of the sequence] better than guessing," as hinted in a comment, so guessing is the best an adversary can do.


The original question mentions pseudorandom data and an original seed, without relation to RNGs, so perhaps the question is missing something and I'm answering the wrong question.

An alternative cryptographic primitive based RNG can be implemented as:-

rng

This one has the advantage that it can run very quickly on any CPU that has native AES instructions, although it's not slow without them. Simply increment the counter every 128 bit output cycle. The key effectively forms the seed value you're referring to as you would initialise the counter at 0, although we still call it the key rather than seed in this construct.

For any secure (pseudo) random number generator the previous or next values do not depend on the output of the random number generator. The output of the random number generator depends on the state within a random number generator. The state depends of course on the given seed value(s) but may also depend on other values such as a counter.

Of course, if the seed values get known then all the output of the random number generator is compromised. This would completely destroy the security of the random number generator. In other words, if a random number generator somehow allows an attacker to retrieve the seed values then it is not considered secure, similar to a cipher leaking the key value.

So in the end you can choose any random number generator. It would be advisable to choose a PRNG from well known standards such as "NIST Special Publication 800-90A Revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators". Preferably you'd use an implementation that is FIPS or AIS 31 certified, if that is available to you.

Many DRBG implementations will use seeding from the operating system. DRBG's may also re-seed at specific (timed or output related) intervals. If you want to generate a deterministic stream of random bits you may be better off using a key stream generated for a stream cipher (Paul Uszak's answer gives one, Future Security's answer shows another) or, more recently, one generated using a XOF.


Notes:

  • Using the default implementation provided by a specific runtime, seeded by the operating system is often more secure than a theoretically secure one created by yourself; you may want to check what is available in your target runtimes.
  • You should keep the seed value(s) at least as secure as the highest security required for the output at any time. Using a secure random number generator makes little sense if the seed is leaked by other means.
  • My mouse is out of juice, I'll add the links later. – Maarten Bodewes Aug 7 at 1:07
  • Err, mice like cheese not juice. Is your's on a health drive? – Paul Uszak Aug 7 at 9:22

If you want random bytes and you want to minimize the amount of cryptography implementation you need to write or change then using a hash function with a secret key is the easiest way.

If you want a full API with all the features provided by ordinary insecure RNGs then you will need to modify that high level code, extend an RNG class, or implement your own.

You can generate random bytes using hash(key || counter++) where hash is a cryptographic hash (SHA-512, etc.), || means concatenation of byte strings, and counter is has enough bits to prevent repeat output. hmac(key, counter++) also works.

If you want back tracking resistance (state getting leaked doesn't let someone calculate past output) then use something like

output = hash(input); input = hash(input || counter++);

and initialize input to be a random value.

If you have a "fast key erasure" implementation available then I instead recommend that.

It is also possible to create PRNGs based on other cryptographic algorithms but primitives other than hashes require a bit more knowledge to use correctly.

Start with a seed, S. The first block of data is SHA-3(S). Each block from then on out is SHA-3 of the S xored with the previous block.

  • Why the xor? Why not just rehash the output over and over? – Paul Uszak Aug 7 at 23:14
  • Because then you could determine the next block without the seed. You would simply hash the current block and get the next one. – Shalop Aug 16 at 0:51

Your Answer

 
discard

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.