Hacker News Reader

Comment by tptacek | Hacker News Reader

What does it mean to "break" PCG? It's not a secure random number generator.

Seed recovery. It's not meant to be cryptographically secure, but previously nobody had reversed it.

Showing that reversal takes that many CPU hours shows how good the PRNG quality is.

To me this is completely unrelated to the quality of the PRNG, because security is explicitly a non-goal of the design. A general-purpose non-cryptographically secure PRNG is evaluated primarily on speed and uniformity of output. Any other qualities can certainly be interesting, but they're orthogonal to (how I would evaluate) quality.

Right: put differently, why would you bother to select among the insecure RNGs an RNG whose "seed" was "harder" to recover? What beneficial property would that provide your system?

CSPRNGs have all of the desirable properties for the output.

All else being equal, I don't think it is possible for a trivially reversible generator to have better statistical properties than a generator whose output behaves more like a CSPRNG.

It can definitely be good enough and or faster, though.

Right, I think defaulting to a CSPRNG is a pretty sane decision, and you'd know if you had need of a non-CSPRNG RNG. But what does that say about the choice between PCG and xorshiro?

Defaulting to a CSPRNG pre-seeded with system randomness is not a bad choice per se(especially given many users don't know they need one) but current ones are much slower than the RNGs we are discussing.

If you're going to provide a non-CS one for general simulation purposes, you probably want the one that is the closest to indistinguishable from random data as you can without compromising performance, though.

Some people will have more than enough with a traditional LCG(MC isn't even using RNGs anymore) but others may be using more of the output in semantically relevant ways where it won't work.

If Xoshiro's state can be trivially recovered from a short span of the output, there is a local bias right there that PractRand lets through but that your application could accidentally uncover.

The choice is: Are the performance gains enough to justify that risk?

Why does it matter if the state can be trivially recovered? What does that have to do with the applications in which these generators are actually used? If the word "risk" applies to your situation, you can't use either xorshiro or PCG.

This is too deep to reply but if a bit is dependent on the value of a bit a couple bytes back then it is not acting randomly.

It's not about security.

I hope you can agree that if every time there is a treasure chest to the left of a door, a pink rabbit spawns on the top left of the room, that's not acting very random-like.

I'm not taking a position on the perceived added value of PCG over Xoshiro.

The property you're talking about (next bit unpredictability) is important for a CSPRNG, but it doesn't matter at all for a PRNG. A PRNG just needs to be fast and have a uniform output. LCGs, for instance, do not have next bit unpredictability and are a perfectly fine class of PRNG.

The paper that triggered this thread "breaking" PCG sees it as potentially in the same class of issues as using RANDU.

> our results […] do mean that [PCG']s output has detectable properties. Whether these properties may affect the result of Monte-Carlo numerical simulations is another matter entirely.

Again this is on PCG which required a breaking effort.

The short version of Xorshift as originally presented by Marsaglia outputting its whole state for example is bound to have behaviors like my room-generation example emerging fairly easily. Particularly, with low hamming-weight states.

I doubt Xoshiro's output is that bad but if presented as trivial to recover vs PCG, that to me indicates potential issues when using the output for simulation.

Any recoverability sounds very bad.

Why shouldn’t I just use eg sha512 on the previous hash and drop half the bits?

It's not bad because "preventing seed recovery" isn't the job of an insecure RNG. If you care about seed recovery, you must use a secure generator. There aren't degrees of security here; PCG is insecure, and (say) the LRNG or CTR-DRBG are not.

> Any recoverability sounds very bad.

PRNGs are not meant to be cryptographically secure. If you don't want recoverability by all means use SHA512 or a proper CSPRNG.

But saying PRNGs are bad because there is recoverability is like saying salt is bad because it isn't sweet. PRNGs are not meant for non-recoverability and salt isn't meant to be sweet.

I agree, but https://www.pcg-random.org/ still advertizes PCG as "challenging" to predict, and critizises other RNGs as predictable and insecure.

Right, that's a problem, because nobody that cares about this should be using PCG.

> Predictable — after 624 outputs, we can completely predict its output.

> we recovers[sic] all the secret information using 512 consecutive output bytes

oof

Reply on news.ycombinator.com