[HN Gopher] Designing a New PRNG
___________________________________________________________________
Designing a New PRNG
Author : todsacerdoti
Score : 36 points
Date : 2021-12-19 01:21 UTC (1 days ago)
(HTM) web link (tom-kaitchuck.medium.com)
(TXT) w3m dump (tom-kaitchuck.medium.com)
| spekcular wrote:
| Dumb question: Why not just use AES? Most platforms have hardware
| acceleration so it should be pretty fast. Then there's no
| worrying about output quality.
|
| (Is there an application for which AES is not fast enough? Has it
| been benchmarked for speed against the various PRNG options?)
| tptacek wrote:
| This 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.
| jcranmer wrote:
| 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
| <technical reasons>, where a) both of them are correct, and b)
| the <technical reasons> 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.
| [deleted]
| masklinn wrote:
| 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.
| sobriquet9 wrote:
| 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.
| zokier wrote:
| 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-...
| omoikane wrote:
| I wish that issue would also link to the rebuttal:
| https://www.pcg-random.org/posts/on-vignas-pcg-critique.html
| loeg wrote:
| I agree that the motivation is pretty confused. One of the
| straightforward goals is to be faster than PCG-64 or
| xoshiro256++ -- that seems reasonable.
| matthewdgreen wrote:
| Seriously. Cut this shit out. Design a cryptographic RNG or
| decide precisely how you intend to justify a non-cryptographic
| RNG that had cryptographic security properties (but like, not all
| of them.)
| failrate wrote:
| I've used noise functions as good noncryptographic PRNG. E.g.
| Squirrel3 hash Fast and cheap with no apparent periods.
| nullc wrote:
| 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.
| ilhamsgenius wrote:
| ilhamsgenius wrote:
___________________________________________________________________
(page generated 2021-12-20 23:00 UTC)