Return to Answer

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 instruction, 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/mm² 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.

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/mm² 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.

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 instruction, 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/mm² 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 little-o notation for an interesting figure. 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 like $o(113n)$ 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 $2^{\approx249}$ 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 $2^{\approx153}$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.

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 instruction, 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/mm² 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.

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 instruction, 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/mm² 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 little-o notation for an interesting figure. 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 like $o(113n)$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).

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 instruction, 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/mm² 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 little-o notation for an interesting figure. 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 like $o(113n)$ 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 $2^{\approx249}$ 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 $2^{\approx153}$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.