1. 19
  1.  

  2. 4

    I think, these days, with hardware for some algorithms in recent CPUs and other algos designed to work very well with the vector unit, crypto-primitive-based PRNGs often end up good candidates even when you don’t need cryptographic security.

    If you check out https://bench.cr.yp.to/results-stream.html, for example, ChaCha20/8 runs on a recent-ish Core i7 at 0.28 cycles/byte, and AES-128 counter mode at 0.65 cycles/byte. Using a well-studied crypto primitive mostly dispenses with uncertainties about whether the output is ‘random enough’; any bias big enough to cause practical problems in your non-cryptographic application would lead to a blockbuster cryptography paper to say the least.

    Note that the linked page, though it’s for a non-cryptographic algorithm, treats unpredictable as good-to-have–search for “Predictable & Insecure”.

    1. 4

      I agree.

      PCG does provide “jumpahead” (moving to state after N steps without generating intermediate states), which is useful for some applications and is usually not provided by CSPRNG.

      1. 2

        AES and ChaCha/Salsa both generate blocks from a key + counter value (+ nonce for ChaCha/Salsa), so with them you can jump around in the stream by changing the counter. There are other stream ciphers don’t work that way, though.

      2. 2

        ChaCha20/8 runs on a recent-ish Core i7 at 0.28 cycles/byte, and AES-128 counter mode at 0.65 cycles/byte

        But only if you’re encrypting rather large buffers at once, which is not what you usually want from a random number generator. The results of the 8 Byte column are more relevant, I think.

        1. 1

          Right tradeoff is probably somewhere in between 8 bytes and the “long messages” number I quoted (which, right, is an ideal). If you know up front you’re going need a lot of randomness, you might as well generate little chunks at once and have random() just read the next bytes out until the buffer is empty. That has its own costs (cache effect is probably the biggest), but GBs/s of noise with at most KBs of extra memory use still seems achievable.

          If you don’t like much memory use ChaCha is probably the better fit: no key-schedule step or expanded key to store, and it can use SIMD parallelism within a block or two whereas I think Intel’s AES implementation would rather you pipeline work on several blocks in parallel.

      3. 3

        The interesting contribution of PCG comes from the observation that evaluation of the quality should be compared based on the number of bits used as state rather than some perfect ideal of a random number that’s hard to test since something can never be shown to be random but instead shown to be biased (or not so random looking). This means you can only really detect negative results, which makes a lot of earlier evaluation frameworks poor benchmarks (pass/fail rather than structural analysis and limitations).

        The structure here is applicable to PRNGs and CSPRNGs in the sense that N bits gives 2^N states and thus you have an upper bound on your cycles. Modeling an ideal permutation of states gives you the baseline for evaluating the performance. From there PCG offers a few interesting points:

        • your output should not be your entire state
        • evaluation should include change in quality vs bits added (for example, mersenne twister does not scale well here, LCGs do better)
        • it’s possible to modify a reasonable bit mixing construction to provide better cycle behavior by augmenting how state is managed and how state is turned into outputs

        This does lead to some remarkable improvements using this new framework for analysis but it’s not necessarily going to be the best performing in terms of CPU behavior. There are some tricky things about how data flows through PCG that makes it immune to instruction level parallelism. Likewise, hardware based acceleration of some other common cryptography primitives is leading some to use CSPRNGs (can still be slow with small outputs but pooling the output can help here). I think PCG is still a great place to start for someone who has an interest in learning more about PRNGs.

        1. 1

          “prediction difficulty: challenging” (vs “secure” for CPRNG’s)

          “and thus more secure than most generators”

          Looks like a great article. I’m highlighting this since they probably just should leave the last part off as it semi-implies it useful or acceptible for work done with security in mind. Folks are better off just using the fastest CSPRNG that doesn’t have any working attacks. That is, if they can’t afford to use whatever is the strongest one. I’ll add @twotwotwo has a great point about how fast the secure generators run these days. There’s also crypto accelerators on some processors for common algorithms.

          1. 3

            The use case is things like Monte Carlo simulation, raycasting, etc., where you want unpredictable, uniformly distributed set of values.

            1. 1

              Oh, I get that. Especially Monte Carlo given it’s always the example I see in fast, pseuo-random generators. I should probably look into that deeper some time given its utility and popularity.

              I’m just saying they should leave off the security part toward the end if they already said it wasn’t secure at the beginning. Following others in the know, I’ve always kept separate the RNG’s that are good for security-insensitive and security-focused randomness. Many who haven’t studied information security might misinterpret such remarks.

            2. 1

              “prediction difficulty: challenging” (vs “secure” for CPRNG’s)

              CSPRNGS aren’t provably secure. There’s no difference between ‘challenging’ and ‘secure’ except that the ones marked ‘secure’ have been tested a lot more for security.

              I’m highlighting this since they probably just should leave the last part off as it semi-implies it useful or acceptible for work done with security in mind.

              It is more secure than most generators.

            3. 1

              This doesn’t sound convincing. We know that all those legacy RNGs are shitty and we should use CSRNGs. They compare themselve to plenty of known bad algs and then say theirs is better, where only one of the ones in the table is actually serious (ChaCha20).

              They say Prediction Difficulty of their construction is “Challenging”, while for ChaCha20 it’s “Secure”. Doing a quick skimming of the page I don’t find an explanation what “Challenging” means, but it sounds to me like “not really secure”. The downsides of ChaCha20 they imply are questionable. They say it’s “Fairly Slow”, I beg to disagree. I really don’t care about 0,1 kb space usage. “Complex” is somewhat of an argument, but if I need a bit of complexity to get proper security I’ll take it.

              1. 1

                This doesn’t sound convincing. We know that all those legacy RNGs are shitty and we should use CSRNGs. They compare themselve to plenty of known bad algs and then say theirs is better, where only one of the ones in the table is actually serious (ChaCha20).

                She compares the algorithms with other popularly used algorithms. You might think that ‘all those legacy RNGs are shitty’ and that ‘we’ should use CSPRNGs, but you don’t speak for everyone, and there are lots of good reasons to not use CSPRNGs.

                They say Prediction Difficulty of their construction is “Challenging”, while for ChaCha20 it’s “Secure”. Doing a quick skimming of the page I don’t find an explanation what “Challenging” means, but it sounds to me like “not really secure”.

                You can’t claim something is secure until it’s been thoroughly tested, but there’s no evidence that PCG is any less secure than ChaCha20.

                The downsides of ChaCha20 they imply are questionable. They say it’s “Fairly Slow”, I beg to disagree. I really don’t care about 0,1 kb space usage. “Complex” is somewhat of an argument, but if I need a bit of complexity to get proper security I’ll take it.

                You can’t disagree with facts. ChaCha20 literally is slow. And you might not care about the space usage, but others do. And you don’t need the complexity, that’s pretty much the whole point of PCG.

              Stories with similar links:

              1. PCG, A Family of Better Random Number Generators via pushcx 4 years ago | 12 points | 2 comments