4 ms·

They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if y

They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if you always start them in the same state, they'll always produce the same sequence. So a PRNG needs "seeding". You need some value to put in at the start that is different every time. Using the time on the computer results in a different seed on each run, and so a different number sequence each time. If you need random numbers for cryptography (very good quality random numbers are important for lots of crypto processes) then you need to do more - they need to be completely unpredictable. If you just used the time, someone could seed a copy of the RNG with the same time, and predict the randomness sequence. So what we want is a seed that comes from actual randomness (also called "entropy"). That entropy has to come from somewhere - ideally some hardware source using some statistically random physical effect.

simonmales 2y ago
Well written, h/t.
magicalhippo 2y ago
> Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.
- markh1967 2y ago
  A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
- mturmon 2y ago
  Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.
UncleMeat 2y ago
The key thing with crypto is not the source of the seed, but the algorithm. Throwing true randomness into a random number generator that isn't mean to provide cryptographic hardness won't save you and a cryptographically secure pseudo random number generator is often just fine when seeded without true randomness.
- toast0 2y ago
  It's both. Cryptographic generators do have better properties on their outputs than noncryptographic hashes (usually at a cost in cpu time, although the cost is often small enough to ignore); but if the seed is guessable, the output sequence is guessable too. Using timestamp in seconds and process id for example would be easy enough to guess. There was some good work about a decade ago to provide more usable apis to get a quality seed from the OS (getentropy, getrandom), so using a self built seed is pretty suboptimal unless you have a case where you need to repeat the sequence later (recording the seed from the OS is also an option)
  - deleted 2y ago
    [deleted]
  - UncleMeat 2y ago
    It depends on what you mean by guessable. Guessing a few bits of the seed with confidence won't help you crack a csprng. Yes, people shouldn't be using a timestamp in seconds as a seed. But you also don't need to spring for hardware randomness in order to get strong protections.
    - kbolino 2y ago
      The problem with using the current time is that "guessing a few bits with confidence" is the same as guessing the whole thing because there's only a few bits that need to be guessed. You might think a time_t value has 55 and growing years worth of values to guess, but in reality, if I'm attacking you or something related to you, I have probably narrowed it down to days, hours, or even just minutes worth of values to guess. Higher-precision timers confer some additional entropy but even then it's usually not enough -- if I'm intercepting live traffic I have a very good idea of the current time, if I'm forging a signature from a certificate I know when it was issued, if I'm trying to decrypt emails or files I usually have attached metadata to narrow my guesses, etc. The CSPRNG has only made it practically impossible to predict future outputs from past outputs alone; however, if I can guess the seed, I can predict every output past, present, and future. CSPRNGs aren't magic and have to be used properly, and in any security-sensitive context, properly means with a truly random seed. The best CSPRNG in the world cannot create entropy out of thin air. It can, however, stretch a good source of entropy very far. There are cases when using a CSPRNG with a low-quality seed is appropriate, but the minimum acceptable entropy in the seed depends on the application, not on the RNG.

simonmales 2y ago

Well written, h/t.

magicalhippo 2y ago

> Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.

markh1967 2y ago
A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
mturmon 2y ago
Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.

UncleMeat 2y ago

The key thing with crypto is not the source of the seed, but the algorithm. Throwing true randomness into a random number generator that isn't mean to provide cryptographic hardness won't save you and a cryptographically secure pseudo random number generator is often just fine when seeded without true randomness.

toast0 2y ago
It's both. Cryptographic generators do have better properties on their outputs than noncryptographic hashes (usually at a cost in cpu time, although the cost is often small enough to ignore); but if the seed is guessable, the output sequence is guessable too. Using timestamp in seconds and process id for example would be easy enough to guess. There was some good work about a decade ago to provide more usable apis to get a quality seed from the OS (getentropy, getrandom), so using a self built seed is pretty suboptimal unless you have a case where you need to repeat the sequence later (recording the seed from the OS is also an option)
- deleted 2y ago
  [deleted]
- UncleMeat 2y ago
  It depends on what you mean by guessable. Guessing a few bits of the seed with confidence won't help you crack a csprng. Yes, people shouldn't be using a timestamp in seconds as a seed. But you also don't need to spring for hardware randomness in order to get strong protections.
  - kbolino 2y ago
    The problem with using the current time is that "guessing a few bits with confidence" is the same as guessing the whole thing because there's only a few bits that need to be guessed. You might think a time_t value has 55 and growing years worth of values to guess, but in reality, if I'm attacking you or something related to you, I have probably narrowed it down to days, hours, or even just minutes worth of values to guess. Higher-precision timers confer some additional entropy but even then it's usually not enough -- if I'm intercepting live traffic I have a very good idea of the current time, if I'm forging a signature from a certificate I know when it was issued, if I'm trying to decrypt emails or files I usually have attached metadata to narrow my guesses, etc. The CSPRNG has only made it practically impossible to predict future outputs from past outputs alone; however, if I can guess the seed, I can predict every output past, present, and future. CSPRNGs aren't magic and have to be used properly, and in any security-sensitive context, properly means with a truly random seed. The best CSPRNG in the world cannot create entropy out of thin air. It can, however, stretch a good source of entropy very far. There are cases when using a CSPRNG with a low-quality seed is appropriate, but the minimum acceptable entropy in the seed depends on the application, not on the RNG.