4 ms·

I've used noise functions as good noncryptographic PRNG. E.g. Squirrel3 hash Fast and cheap with no apparent periods.

nullc 5y ago
Every RNG with a fixed size state has a period. If the period is not known, it's probably seed dependent and there may be some seeds with very small period. If 'very small' is small enough (such as 2 or 5) then those seeds will cause some ordinary uses to fail badly in obvious ways. If bad seeds are common enough (say 1 in 2^64) then you could actually see rare failures in production. (Cryptographic RNGs tend to avoid this risk just by having a pretty gigantic and well mixed state, so any bad seed-- if one exists-- would be extremely unlikely to be hit. They also usually have structures that are 'close' to permutations which makes it hard for them to have small periods.) For insecure small state RNGs the risk of small periods makes it useful to build RNGs based on structures that make it easy to know the period. Unfortunately, those same structures also tend to do things like make the RNG efficiently invertible. Invertibility itself shouldn't be a problem since these sorts of non-cryptographic RNGs should never be used where security is a factor, but the existence of invertibility has a bad smell even when you're just concerned that the pattern of the RNG may trigger pathological behavior in the underlying system (as the structure of LCGs often does). If it's not obvious to you why invertibility (or predictability in general) is a bad smell, think of it this way: Using the inversion I can create a randomness test that the RNG will fail (by recovering the state and checking it) and I can create an application that will fail using it. The application would be contrived, for sure, but it would exist. If we don't know how to predict the RNG then we also probably don't know how to create an application that will fail with it, even a contrived one (assuming the RNG otherwise has good statistical properties). Though this only goes so far, because with a small state every RNG is going to be invertible (up to seeds with equal output) by an exhaustive test.
- kittywav 5y ago
  Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).
  - nullc 5y ago
    Assuming its a permutation and you output the whole thing. However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant). In that case the 'state' has a long period, true, but the output doesn't. If instead you use a construction where the output is guaranteed to have a known (large) period, you can follow that up with whatever permutation you want, but to preserve the period all of the permutation must be output.
    - kittywav 5y ago
      > Assuming its a permutation and you output the whole thing. I'm assuming the state-mixing function is a permutation (i.e. the counter affects the whole state in a reversible way), but it is not required that the whole state is outputted. > However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant). The counter will always have the full period of 2^N (assuming N-bit counter), regardless of how it is initialized (i.e. regardless of seeding), as long as it is a simple "i = (i + 1) mod 2^N" counter. What this does is to effectively change the (presumably fixed) state permutation function: instead of using a fixed one, you're applying a repeating sequence of 2^N slightly different state permutation functions, which ensures that the period of the state should be at least as large as that (and probably much larger). Assuming the chosen state permutation function is reasonable (and does indeed mix the counter effectively), truncating the state to provide output should not lead to short cycles: if it does, then your permutation is probably not reasonable as primitive for a PRNG (i.e. you have worse problems in your generator than "small period"). For more information on the use of counters to ensure lower bounds on the periods of stream ciphers and PRNG, take a look at Rabbit [1] (or, in general, at the concept of "counter-assisted stream ciphers" [2]). [1] https://www.ecrypt.eu.org/stream/rabbitpf.html https://www.ecrypt.eu.org/stream/rabbitpf.html [2] https://arxiv.org/abs/cs/0112014v5 https://arxiv.org/abs/cs/0112014v5

Every RNG with a fixed size state has a period. If the period is not known, it's probably seed dependent and there may be some seeds with very small period. If 'very small' is small enough (such as 2 or 5) then those seeds will cause some ordinary uses to fail badly in obvious ways. If bad seeds are common enough (say 1 in 2^64) then you could actually see rare failures in production. (Cryptographic RNGs tend to avoid this risk just by having a pretty gigantic and well mixed state, so any bad seed-- if one exists-- would be extremely unlikely to be hit. They also usually have structures that are 'close' to permutations which makes it hard for them to have small periods.) For insecure small state RNGs the risk of small periods makes it useful to build RNGs based on structures that make it easy to know the period. Unfortunately, those same structures also tend to do things like make the RNG efficiently invertible. Invertibility itself shouldn't be a problem since these sorts of non-cryptographic RNGs should never be used where security is a factor, but the existence of invertibility has a bad smell even when you're just concerned that the pattern of the RNG may trigger pathological behavior in the underlying system (as the structure of LCGs often does). If it's not obvious to you why invertibility (or predictability in general) is a bad smell, think of it this way: Using the inversion I can create a randomness test that the RNG will fail (by recovering the state and checking it) and I can create an application that will fail using it. The application would be contrived, for sure, but it would exist. If we don't know how to predict the RNG then we also probably don't know how to create an application that will fail with it, even a contrived one (assuming the RNG otherwise has good statistical properties). Though this only goes so far, because with a small state every RNG is going to be invertible (up to seeds with equal output) by an exhaustive test.

kittywav 5y ago
Just a small comment: you can do things to ensure that the period of a PRNG is longer than a certain lower bound for any input seed. For example, if you make the state-mixing function depend on a 64-bit counter, you'll ensure that the period is at least 2^64 (assuming the state-mixing function is reversible).
- nullc 5y ago
  Assuming its a permutation and you output the whole thing. However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant). In that case the 'state' has a long period, true, but the output doesn't. If instead you use a construction where the output is guaranteed to have a known (large) period, you can follow that up with whatever permutation you want, but to preserve the period all of the permutation must be output.
  - kittywav 5y ago
    > Assuming its a permutation and you output the whole thing. I'm assuming the state-mixing function is a permutation (i.e. the counter affects the whole state in a reversible way), but it is not required that the whole state is outputted. > However, you wouldn't output the whole thing (or you instantly leak the state), and I think in that case you don't get an automatic useful guarantee about the period anymore: For some seeds you could have the whole 0..2^64-1 counter span just output a few repeating values (or even a constant). The counter will always have the full period of 2^N (assuming N-bit counter), regardless of how it is initialized (i.e. regardless of seeding), as long as it is a simple "i = (i + 1) mod 2^N" counter. What this does is to effectively change the (presumably fixed) state permutation function: instead of using a fixed one, you're applying a repeating sequence of 2^N slightly different state permutation functions, which ensures that the period of the state should be at least as large as that (and probably much larger). Assuming the chosen state permutation function is reasonable (and does indeed mix the counter effectively), truncating the state to provide output should not lead to short cycles: if it does, then your permutation is probably not reasonable as primitive for a PRNG (i.e. you have worse problems in your generator than "small period"). For more information on the use of counters to ensure lower bounds on the periods of stream ciphers and PRNG, take a look at Rabbit [1] (or, in general, at the concept of "counter-assisted stream ciphers" [2]). [1] https://www.ecrypt.eu.org/stream/rabbitpf.html https://www.ecrypt.eu.org/stream/rabbitpf.html [2] https://arxiv.org/abs/cs/0112014v5 https://arxiv.org/abs/cs/0112014v5