5 ms·

> nobody had figured out any downsides to PCG's yet BTW, people have broken PCG already: https://hal.science/hal-02700791/file/main.pdf https://hal.science/hal

> nobody had figured out any downsides to PCG's yet BTW, people have broken PCG already: https://hal.science/hal-02700791/file/main.pdf https://hal.science/hal-02700791/file/main.pdf It takes up to 20000 CPU hours to break the seed from 512 output bits with an unknown state, increment and multiplier. (the multiplier is usually fixed constant)

WalterGillman 1y ago
I wonder how much it would take to break mine. https://github.com/waltergillman/xorshift_sbox https://github.com/waltergillman/xorshift_sbox I have not been blessed by an education so I can't be eloquent and write proofs and papers and stuff but it passes PractRand for 4GB with only 32 bits of state. Not very fast on modern computers, I will concede.
tptacek 1y ago
What does it mean to "break" PCG? It's not a secure random number generator.
- whyever 1y ago
  I agree, but https://www.pcg-random.org/ https://www.pcg-random.org/ still advertizes PCG as "challenging" to predict, and critizises other RNGs as predictable and insecure.
  - tptacek 1y ago
    Right, that's a problem, because nobody that cares about this should be using PCG.
  - avadodin 1y ago
    > Predictable — after 624 outputs, we can completely predict its output. > we recovers[sic] all the secret information using 512 consecutive output bytes oof
- camel-cdr 1y ago
  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.
  - charlieyu1 1y ago
    Any recoverability sounds very bad. Why shouldn’t I just use eg sha512 on the previous hash and drop half the bits?
    - tptacek 1y ago
      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.
    - throwaway150 1y ago
      > 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.
  - mahemm 1y ago
    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.
    - tptacek 1y ago
      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?

WalterGillman 1y ago

I wonder how much it would take to break mine. https://github.com/waltergillman/xorshift_sbox https://github.com/waltergillman/xorshift_sbox I have not been blessed by an education so I can't be eloquent and write proofs and papers and stuff but it passes PractRand for 4GB with only 32 bits of state. Not very fast on modern computers, I will concede.

tptacek 1y ago

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

whyever 1y ago
I agree, but https://www.pcg-random.org/ https://www.pcg-random.org/ still advertizes PCG as "challenging" to predict, and critizises other RNGs as predictable and insecure.
- tptacek 1y ago
  Right, that's a problem, because nobody that cares about this should be using PCG.
- avadodin 1y ago
  > Predictable — after 624 outputs, we can completely predict its output. > we recovers[sic] all the secret information using 512 consecutive output bytes oof
camel-cdr 1y ago
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.
- charlieyu1 1y ago
  Any recoverability sounds very bad. Why shouldn’t I just use eg sha512 on the previous hash and drop half the bits?
  - tptacek 1y ago
    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.
  - throwaway150 1y ago
    > 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.
- mahemm 1y ago
  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.
  - tptacek 1y ago
    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?