Score:0

What would be the benefits of a fast PRNG that produces an 8-bit output and could pass 1 Peta Byte of the PractRand test?

cn flag

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?

fgrieu avatar
ng flag
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.
Tunnel_Vision avatar
cn flag
Thank you for your feedback! Which other statistical test should pass? For example: NBT (Next Bit Test) is enough?
poncho avatar
my flag
"Which other statistical test should pass?" - all of them, including tests designed with the design of your algorithm in mind...
SAI Peregrinus avatar
si flag
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.
Score:2
fr flag

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.

Paul Uszak avatar
cn flag
Speed is not relevant to real cryptography.
bk2204 avatar
fr flag
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."
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.