5 ms·

> There are concepts like "k-dimensional equidistribution" etc. etc... where in some ways the requirements of a PRNG are far, far, higher than a cryptographical

> There are concepts like "k-dimensional equidistribution" etc. etc... where in some ways the requirements of a PRNG are far, far, higher than a cryptographically sound PRNG Huh? If you can chew through however many gigabytes of the supposed CSPRNG’s output, do some statistics, and with a non-negligible probability tell if the bytes in fact came from the CSPRNG in question or an actual iid random source, then you’ve got a distinguisher and the CSPRNG is broken.

jmalicki 8mo ago
It all comes down to actual specific statistical tests, and how hard they are to break in specific applications. No CSPRNG is absolutely perfect, no CSPRNG has ever absolutely passed every statistical test thrown at it. In MCMC, it stresses very different statistical tests than the typical CSPRNG tests. Every PRNG is absolutely broken if you want to be absolute about it. MCMC and crypto applications push on different aspects where statistical issues will cause application level failures. See e.g. this paper https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf (it's not the end all be all, but it's a good survey of why this stuff matters and why it's different)
- deleted 8mo ago
  [deleted]
- mananaysiempre 8mo ago
  > no CSPRNG has ever absolutely passed every statistical test thrown at it As far as I know (admittedly not a high standard), there is no published statistical test that you could run on, for example, a single AES-256-CTR bitstream set up with a random key and IV, running on a single computer, that would be able to tell you with a meaningful likelihood ratio that you were looking at a pseudorandom rather than truly random input before the computer in question broke down. (I’m assuming related-key attacks are out of scope if we’re talking about an RNG for simulation purposes.)
  - coppsilgold 8mo ago
    Cryptographic operations when done correctly result in full chaos within the discrete domain (the so-called avalanche effect). Any bias of any kind gives rise to a distinguisher and the primitive is regarded as broken. One way to imagine what symmetric cryptography does is a cellular automaton that is completely shuffled every iteration. In the case of Keccak/SHA3, that is almost exactly what happens too.
    - jmalicki 8mo ago
      There has never been a perfect CSPRNG.
      - coppsilgold 8mo ago
        > There has never been a perfect CSPRNG. What is a perfect CSPRNG?
      - adrian_b 8mo ago
        There have been a very large number of CSPRNGs for which there does not exist any known practical method to distinguish them from TRNGs. For all of them there are theoretical methods that can distinguish a sequence generated by them from a random sequence, but all such methods require an impossible amount of work. For instance, a known distinguisher for the Keccak function that is used inside SHA-3 requires an amount of work over 2^1500 (which was notable because it was an improvement over a naive method that would have required an amount of work of 2^1600). This is a so ridiculously large number in comparison with the size and age of the known Universe, that it is really certain that nobody will ever run such a test and find a positive result. There are a lot of other such CPRNGs for which the best known distinguishers require a work of over 2^100, or 2^200, or even 2^500, and for those it is also pretty certain that no practical tests will find statistical defects. There are a lot of CSPRNGs that could not be distinguished from TRNGs even by using hypothetical quantum computers. Even many of the pretty bad cryptographic PRNGs, which today are considered broken according to their original definitions, can be made impossible to distinguish from TRNGs by just increasing the number of iterations in their mixing functions. This is not done because later more efficient mixing functions have been designed, which achieve better mixing with less work.

jmalicki 8mo ago

It all comes down to actual specific statistical tests, and how hard they are to break in specific applications. No CSPRNG is absolutely perfect, no CSPRNG has ever absolutely passed every statistical test thrown at it. In MCMC, it stresses very different statistical tests than the typical CSPRNG tests. Every PRNG is absolutely broken if you want to be absolute about it. MCMC and crypto applications push on different aspects where statistical issues will cause application level failures. See e.g. this paper https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf https://www.cs.hmc.edu/tr/hmc-cs-2014-0905.pdf (it's not the end all be all, but it's a good survey of why this stuff matters and why it's different)

deleted 8mo ago
[deleted]
mananaysiempre 8mo ago
> no CSPRNG has ever absolutely passed every statistical test thrown at it As far as I know (admittedly not a high standard), there is no published statistical test that you could run on, for example, a single AES-256-CTR bitstream set up with a random key and IV, running on a single computer, that would be able to tell you with a meaningful likelihood ratio that you were looking at a pseudorandom rather than truly random input before the computer in question broke down. (I’m assuming related-key attacks are out of scope if we’re talking about an RNG for simulation purposes.)
- coppsilgold 8mo ago
  Cryptographic operations when done correctly result in full chaos within the discrete domain (the so-called avalanche effect). Any bias of any kind gives rise to a distinguisher and the primitive is regarded as broken. One way to imagine what symmetric cryptography does is a cellular automaton that is completely shuffled every iteration. In the case of Keccak/SHA3, that is almost exactly what happens too.
  - jmalicki 8mo ago
    There has never been a perfect CSPRNG.
    - coppsilgold 8mo ago
      > There has never been a perfect CSPRNG. What is a perfect CSPRNG?
    - adrian_b 8mo ago
      There have been a very large number of CSPRNGs for which there does not exist any known practical method to distinguish them from TRNGs. For all of them there are theoretical methods that can distinguish a sequence generated by them from a random sequence, but all such methods require an impossible amount of work. For instance, a known distinguisher for the Keccak function that is used inside SHA-3 requires an amount of work over 2^1500 (which was notable because it was an improvement over a naive method that would have required an amount of work of 2^1600). This is a so ridiculously large number in comparison with the size and age of the known Universe, that it is really certain that nobody will ever run such a test and find a positive result. There are a lot of other such CPRNGs for which the best known distinguishers require a work of over 2^100, or 2^200, or even 2^500, and for those it is also pretty certain that no practical tests will find statistical defects. There are a lot of CSPRNGs that could not be distinguished from TRNGs even by using hypothetical quantum computers. Even many of the pretty bad cryptographic PRNGs, which today are considered broken according to their original definitions, can be made impossible to distinguish from TRNGs by just increasing the number of iterations in their mixing functions. This is not done because later more efficient mixing functions have been designed, which achieve better mixing with less work.