0
$\begingroup$

Assuming that all other elements like the internal state of the algorithm are considered secured and very hard to discover from a cryptanalytic standpoint.

How significant would be for the algorithm to be able to pass the PractRand with the specifications mentioned?

$\endgroup$
4
  • 3
    $\begingroup$ It's trivial to make a PRNG that spits bytes, that could pass 1 Peta Byte of the PractRand test, and which full internal state is computationally impossible to discover, yet is insecure for cryptographic purposes. Draw your own conclusion about whatever exactly is asked. $\endgroup$
    – fgrieu
    Feb 28, 2022 at 20:07
  • $\begingroup$ Thank you for your feedback! Which other statistical test should pass? For example: NBT (Next Bit Test) is enough? $\endgroup$ Feb 28, 2022 at 20:51
  • 2
    $\begingroup$ "Which other statistical test should pass?" - all of them, including tests designed with the design of your algorithm in mind... $\endgroup$
    – poncho
    Feb 28, 2022 at 22:15
  • 2
    $\begingroup$ Statistical tests can't show that an RNG is secure, only that it's not obviously terrible. They are used to test implementations of well-analyzed designs, not to analyze security of a design. $\endgroup$ Mar 1, 2022 at 2:56

1 Answer 1

2
$\begingroup$

When we design a cryptographic PRNG, we want more than just statistical tests to pass. The gold-standard here is the next-bit test, which says that given all of the output up to a certain point, it is only negligibly easier than even to guess the next bit. This is not a statistical test, but a test which implies that the attacker has full knowledge of the algorithm and the ability to cryptanalyze it, and still cannot find a better solution than brute force.

To show an example of an insecure CSPRNG which could well pass any statistical test but won't pass the next-bit test, imagine a secret seed $ S $, a secure hash function $ H(x) $, and a PRNG that outputs $ H(S) || H(H(S)) || H(H(H(S))) || ... $. Because our hash function is secure, its output appears random, but it is in fact very easy to guess the next output given the existing output.

It is, of course, totally possible to make a CSPRNG that outputs single bytes at a time. RC4 is a stream cipher that has this design and has been used a CSPRNG in many systems, although it's no longer considered secure. We could well design other CSPRNGs that are secure and byte oriented. As a practical matter, though, it is usually more efficient to operate on larger chunks of data, which is why algorithms such as ChaCha20 or the NIST DRBGs tend to be used more frequently.

As to the benefits of a fast non-cryptographic PRNG, there is little reason to use them. ChaCha20 can output data at 3 GB/s on my system, and it is cryptographically secure. In the unlikely event this isn't fast enough, a smaller number of rounds could be used (e.g., ChaCha12) and the performance would be better while still being cryptographically secure. Random number generation with a suitable algorithm is almost never the bottleneck, so using a CSPRNG, which will always pass the next-bit test and is therefore of the highest possible quality, is sufficient in almost all cases.

$\endgroup$
2
  • $\begingroup$ Speed is not relevant to real cryptography. $\endgroup$
    – Paul Uszak
    Mar 3, 2022 at 22:21
  • 1
    $\begingroup$ Sure, but it matters in the real world, because people use speed as an excuse to use insecure systems. That's how we get people using MD5 still: it's fast and it's "good enough." $\endgroup$
    – bk2204
    Mar 4, 2022 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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