Designing a New PRNG
tom-kaitchuck.medium.com
Designing a New PRNG
1–10 of 52 posts
Re: Designing a New PRNG
#2This is all pretty confusing to me, because it's discussing a non-cryptographic RNG but talking about invertibility and "having been cracked" as a motivation for replacing that RNG. If you need a secure RNG, you use a CSPRNG. For all other cases: why is "having been cracked" motivating?
This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of security applications? I don't know what those applications are, but somehow PCG targets them? If you care about this stuff, you should simply be using getrandom(2).
For what it's worth: I get why you'd want a high-quality generator of insecure random data (for simulations and stuff), and that there's an interesting discussion to have about what generator does the best job at handling that workload. I'm just saying it seems to have nothing to do with invertibility and crackability.
Re: Designing a New PRNG
#3No post body was provided.
Re: Designing a New PRNG
#4No post body was provided.
Re: Designing a New PRNG
#5This is all pretty confusing to me, because it's discussing a non-cryptographic RNG but talking about invertibility and "having been cracked" as a motivation for replacing that RNG. If you need a secure RNG, you use a CSPRNG. For all other cases: why is "having been cracked" motivating? This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of securi…
From what I understand of the matter, the crux of it is that there are two modern PRNG families whose creators are running around telling you to use their PRNG over the other's because , where a) both of them are correct, and b) the don't elucidate the tradeoffs being made to people whose prior understanding amounts to "I just want a source of random numbers!" This is contrast to something like a linear congruential generator, where the failure mode of the random data is pretty easy to explain.
Re: Designing a New PRNG
#6This is all pretty confusing to me, because it's discussing a non-cryptographic RNG but talking about invertibility and "having been cracked" as a motivation for replacing that RNG. If you need a secure RNG, you use a CSPRNG. For all other cases: why is "having been cracked" motivating? This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of securi…
I think the allure here is the same as with ciphers. Everyone can create a cipher they cannot break, but cryptographers can break easily.
Likewise, it's easy to invent another PRNG, but not so easy to figure out that, say, its output always falls on one of seventeen parallel planes when treated as consecutive (x, y, z) coordinates.
If you want random numbers that are fast and almost-cryptographically-strong, you can take some ARX block cipher and reduce number of rounds as you see fit. But it's not nearly as much fun.
Re: Designing a New PRNG
#7This is all pretty confusing to me, because it's discussing a non-cryptographic RNG but talking about invertibility and "having been cracked" as a motivation for replacing that RNG. If you need a secure RNG, you use a CSPRNG. For all other cases: why is "having been cracked" motivating? This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of securi…
From what I understand of the matter, the crux of it is that there are two modern PRNG families whose creators are running around telling you to use their PRNG over the other's because , where a) both of them are correct, and b) the don't elucidate the tradeoffs being made to people whose prior understanding amounts to "I just want a source of random numbers!" This is contrast to something like a linear congruential…
I think you misread tptacek's line of questioning. It's not about the quality / superiority of what over what, but the initial motivation for rand switching away from PCG:
> This was done after some concerns were raised by the author of xoshiro, who posted a blog entry on PCG and also raised an issue on the possibility of PCG being invertible.
PCG and the XOR family are both non-cryptographic RNGs, how is predictability or invertibility relevant then? If those are concerns, surely a CSPRNG should be used?
The "quality" of randomness is very much a concern in non-secure contexts e.g. patterns in an RNG can bias your simulation, but it doesn't seem like it'd matter if somebody can recover even your simulation seed.
Re: Designing a New PRNG
#8I've used noise functions as good noncryptographic PRNG. E.g. Squirrel3 hash
Fast and cheap with no apparent periods.
Re: Designing a New PRNG
#9This is all pretty confusing to me, because it's discussing a non-cryptographic RNG but talking about invertibility and "having been cracked" as a motivation for replacing that RNG. If you need a secure RNG, you use a CSPRNG. For all other cases: why is "having been cracked" motivating? This was always my complaint with PCG, that it talked about "difficulty to predict" and its suitability for... some kinds? of securi…
Seems that vigna (author of the xoshiro family of rngs) mostly agrees with you
> Personally, I don't believe in the "middle ground" of "difficult-to-predict-but-not-crypto": usually it just means it is so easy to break that nobody
https://github.com/rust-random/rand/issues/905#issuecomment-...
Re: Designing a New PRNG
#10I've used noise functions as good noncryptographic PRNG. E.g. Squirrel3 hash Fast and cheap with no apparent periods.
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.