# How fast does a pseudorandom number generator have to be in order to be competitive?

Let $$\{x_n\}_{n}$$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $$G$$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?

Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.

On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instructions, and ARX ciphers like ChaCha.

When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.

Update per comment: All modern CSPRNGs require $$O(n)$$ bit operations to produce $$n$$ bits, and we want a more precise estimate. ChaCha with $$r$$ rounds (see source) produces $$16$$ words each 32-bit with computational cost dominated by $$16(r+1)$$ 32-bit additions and $$16r$$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $$13r+9$$ NAND bit operations per bit produced. For ChaCha8 (which is hoped to have at least 128-bit security), the cost is $$\approx113n$$ NAND bit operations to produce $$n$$ bits (with no consideration for circuit depth).

Update on the security of ChaCha8 per this other comment: I'm reasonably confident that ChaCha8 is at least 128-bit safe, but reluctant to state much more because

• ChaCha is an evolution of Salsa20, with the same number of 32-bit additions and XORs, and a faster diffusion. While that could make it safer, I'm using that as safety margin.
• In the abstract of the Salsa paper, Daniel J. Bernstein recommends the 20-round version for typical applications, and presents 12 and 8-round variants as reduced-round versions recommended for applications where speed is more important than confidence.
• Salsa20 was proposed for eSTREAM, in the category asking for fast software ciphers with 128-bit security. While DJB presents Salsa20/20, Salsa20/12 and Salsa20/8 as 256-bit ciphers (which they are as far as key size goes), I'm not reading him as claiming 256-bit security, especially for the reduced-round versions.
• There is a known attack with complexity $$\approx2^{249}$$ against Salsa20/8, thus definitely it does not have security matching its key size. Again, ChaCha8 differs only by its diffusion pattern.
• There is a known attack with complexity $$\approx2^{153}$$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.
• Thanks for this. In terms of big O notation, how many bit operations does chacha requires for example to produce an n-bit pseudoradom number? Sep 28, 2018 at 18:08
• @forest: see new section in the answer. I'll remove this comment after you could read it.
– fgrieu
Sep 29, 2018 at 8:28
• I believe djb (the creator of Salsa and ChaCha) considers all 128-bit-key symmetric primitives to have less than 128-bit security due to multi-target attacks. Hence djb always recommends 256-bit symmetric keys but doesn’t necessarily claim 256-bit security. Sep 29, 2018 at 13:28

It sort of depends on what you are using it for. You would think that openssl's PRNG, rand, would be cryptographically secure, and I'm sure it's plenty fast. But I couldn't help but notice a regular preponderance of repeated hex digits in every call to openssl rand, using a value of 16 (for AES 128 purposes). Given that the average intel chip comes with AES round calculations in silicon, for extra speed, it does seem like the search space for brute forcing AES (without the benefit of the RSA-encrypted key) has been made smaller by this repetition.

If you know that 3 of your 32 4-bit possibilities will be repeated FOUR times (or more!) you do save some time doing a brute force. If I knew in advance that 31 of the 32 nybbles would be repeated, I would only have to check 4096 different keys. (as an extreme example)

I once counted 9 repeated digits on one generation. I know the goal is for a random distribution, but when you only have 128 bits, that's not always good enough.

So I imagine even at mind-blowing speeds, there's room for side-channel surprises. Good luck!

Here's some results I just generated on the fly:

user0@ii:~$openssl rand 16 -hex 0fe29badfe8e2300cbe4d1f0eecfdac1 000011223489aabbcccdddEEEEEEffff (6,4x2) user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)

user0@ii:~$openssl rand 16 -hex c2d854a9fdac7e73a9872c12ade2c048 012222344577788899aaaaccccdddeef (4x3) user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)

user0@ii:~\$ openssl rand 16 -hex