3
$\begingroup$

Is the PCG family of PRNG algorithms cryptographically secure, and if not, what about them makes them inadequate for that?

I have a good enough understanding of the general problem space that if you mention something like "backtracking resistance" and give a sentence summary of what it means, I can connect the dots enough to understand why it matters for security.

I have a (likely incomplete) understanding of what it takes to make a cryptographically secure PRNG - for example I know that resistance to predictability or backtracking matters, ideally resistance that stays strong even as the attacker learns more outputs of the PRNG or learns bits of the PRNG's internal state.

But I lack the deep experience and knowledge needed to actually evaluate PRNGs myself to figure out if they meet any of these properties, or to be confident that I haven't missed something.

I do know that PCG was not designed to be suitable for cryptography - it seems to have been optimized for good statistical properties and efficiency of producing outputs.

I have also found people saying that PCG is not cryptographically secure.

But what I have not found is any actual analysis of PCG - any write-up explaining what properties it fails to fulfill, and so on.

Improve this question
$\endgroup$
  • $\begingroup$ It would appear PCG uses roughly 20 basic instructions (like add, rotate, xor, shift) for each iteration. It would appear that this is likely not enough for cryptographic security. $\endgroup$ – SEJPM♦ Jan 19 '20 at 12:41
  • 3
    $\begingroup$ "I do know that PCG was not designed to be suitable for cryptography - it seems to have been optimized for good statistical properties and efficiency of producing outputs." In practical terms, if it wasn't designed to be secure, then it isn't. No need to look further than that. The onus to prove that things are secure is on the person that claims it to be secure, not on you (something commonly forgotten by inspiring cryptographers). $\endgroup$ – Maarten Bodewes♦ Jan 19 '20 at 14:01
  • $\begingroup$ This site with strong criticisms of the PCG generators claims to demonstrate it's predictable, and includes two programs that it says reconstruct the state of a PCG generators from their outputs, one for a 64-bit generator and one for 128 bits. I haven't verified them myself but if you're interested you should definitely have a look. $\endgroup$ – Luis Casillas Jan 20 '20 at 22:17
  • $\begingroup$ @LuisCasillas Thank you - I've heard of Vigna's criticisms. The author of the PCG generators has published a counter to Vigna's criticisms in particular, claiming something along the lines that Vigna slightly modified the implementation of the PCG algorithm he claimed to be broken. But currently I lack the technical proficiency to efficiency assess or verify their respective arguments on that particular detail, or if that generator is exactly the same one that Maarten mentioned as being the only one purporting to be vaguely maybe secure-ish. $\endgroup$ – mtraceur Jan 20 '20 at 22:24
  • 1
    $\begingroup$ It's a lot like homemade encryption algorithms. "Bet you can't break it!" isn't a real argument in favor of declaring an algorithm to be secure. You can't expect others to point out non-trivial flaws unless you make a good case for why the algorithm should be secure. Maybe a homemade cipher actually is a little tough to break, but that doesn't mean it's safe to rely on that initial difficulty as a permanent deterrent. The same is true for RNGs. It's not hard to make one which requires non-trivial effort to break. It's a lot harder to make good RNGs which can confidently be said to be safe. $\endgroup$ – Future Security Jan 21 '20 at 17:19
4
$\begingroup$

I've looked a bit more into it and there is one PCG type with a 128 bit state, where the output is marginally decoupled from the internal state.

PCG is a suite of algorithms to generate pseudo-random numbers that have been created on top of existing lightweight random number generators so that they:

  1. stay lightweight;
  2. pass the various statistical randomness tests;
  3. are possibly less predictable.

Now only the 3rd part is of interest with regards to cryptography. However, all but one of the algorithms seem to have a state of 64 bit or less (if I discount the one that has been deemed insecure by the author). That makes them directly unsuitable for cryptographic random number generation.

That leaves us with PCG-XSL-RR, the only one that makes any claim to be secure. This seems to have been accomplished by adding a XorShift on the state and a few very simple operations to derive the output of the state:

output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122)

Although there are certainly very simple stream ciphers, it seems to me that we need analysis to see if many outputs cannot be used to derive the state bits. As long as that analysis is not performed, just stating that it might be secure, and that the prediction difficulty is "challenging" doesn't make a cryptographically secure algorithm.

Personally calling it "secure" is therefore unwarranted. Listing the prediction difficulty as "challenging" means using weasel words to indicate that no sufficient analysis is performed and that the security of the algorithm is unknown. If the state can be retrieved then the algorithm would be fully predictable after all. Without knowing the details of how much output is required for such an unknown attack, how can we have any trust in that statement?

Now that was putting it very black and white, and even accuses the author of incorrect statements. However, we have to consider all the statements made by the author of the algorithm to at least partially exonerate her:

I know that if I were trying to predict a random number generator, I'd want something easier than the PCG family. But if I wanted actual crypographic security for secure communication, I'd probably want to use something that has been around longer and seen more scrutiny.

Hopefully as time passes, the PCG generation scheme will receive scrutiny from people with far more expertise in crypographic security than me, and we will have a clearer picture about how easily it can be predicted. With that in mind, I hope to offer some crypographic secuity challenges in the future to encourage people to try to break it.

So please consider it insecure until analysis has shown otherwise, and maybe use a generator where the words "cryptographic" and "security" are spelled correctly, preferably with the word "analysis" attached to it...

Improve this answer
$\endgroup$
  • $\begingroup$ Do you know by chance whether the output is the "state" for the next output? $\endgroup$ – SEJPM♦ Jan 20 '20 at 14:37
  • $\begingroup$ According to the docs, for the 128 bit state version, the state is always "folded onto itself" before being output by the XOR in there (^). uint64_t(state ^ (state >> 64)) is just that. Of course, that this hides all possible information about the state seems ludicrous to me. That the XOR then can have 2^64 uncertainty is true if you put all the bits together, but I would rather try and analyze it bit for bit and write out the formulas for a start. $\endgroup$ – Maarten Bodewes♦ Jan 20 '20 at 15:12
  • $\begingroup$ After upvoting this (I think I was the first upvote) I went off to write another question, because your remark showed me the possibility of leaking too much state. Anyway, thank you, this really helped me mentally grasp onto some precise and concrete things I was missing about what an CSPRNG needs. Per stack best practices I'm still waiting a bit before accepting, but this does address my question enough to get a check mark if it remains the only or best answer. $\endgroup$ – mtraceur Jan 21 '20 at 0:10
  • $\begingroup$ Yeah, I read the other question but I saw that fgrieu already answered it :) $\endgroup$ – Maarten Bodewes♦ Jan 21 '20 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.