7
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

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.
Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Reyx_0
    Commented Sep 28, 2018 at 18:08
  • $\begingroup$ @forest: see new section in the answer. I'll remove this comment after you could read it. $\endgroup$
    – fgrieu ♦
    Commented Sep 29, 2018 at 8:28
  • 3
    $\begingroup$ 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. $\endgroup$
    – rmalayter
    Commented Sep 29, 2018 at 13:28
-3
$\begingroup$

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
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)
Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ I believe that a truly random output would show the same artifacts that you complain about OpenSSL; for example, a truly random 16 byte output would have 9 or repeated hex digits once every circa 370000 outputs. So, yes, if you go through enough of them, you would expect to see such extreme cases (and 'enough' needn't be that many...) $\endgroup$
    – poncho
    Commented Sep 28, 2018 at 20:05
  • 1
    $\begingroup$ You're falling into a trap. I recall a complaint that consecutive second factor codes repeated a few digits and so it was not truly random. Something like "182345" and "405346" - there's a repeat of "34". Just because something stands out to you does not mean it is not random. Humans are great at seeing patterns including the ones that don't exist. $\endgroup$
    – iheanyi
    Commented Sep 28, 2018 at 20:33
  • $\begingroup$ If you're suggesting that OpenSSL's PRNG is inadequate because it shows patterns, then this answer needs to be improved by including an analysis showing that the patterns are statistically significant. $\endgroup$
    – Sophie Swett
    Commented Sep 28, 2018 at 21:58
  • $\begingroup$ I agree that seeing "34" like that in two outputs would be "reading a lot into it." But if you see "34" in 6 out of 6 outputs, I'd say you've reduced your brute force effort by a factor of 100. Of course, you're betting that the 7th will have a "34" and it's always possible that it was just pure randomness (I understand the counterintuitive qualities of pure random values). I'm just saying that if I were designing a PRNG system, I would work hard to avoid such coincidences. And yes, I know how naive that sounds. Sorry about the lack of math proof. $\endgroup$
    – James Huddle
    Commented Sep 28, 2018 at 23:03
  • $\begingroup$ In my defense, I cranked out a simple 128-bit PRNG using glibc's rand() and concatenating 4 of them and printing. "noticeably" fewer repeats. Why? not sure. Mine just seems more random, and hence, harder to crack. If you want "math", you could always "do the math" and extrapolate from my "31-out-of-32" example, which is real math. $\endgroup$
    – James Huddle
    Commented Sep 29, 2018 at 17:24

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.