2
$\begingroup$

My limitation in my security protocol is that I want my RNG as CSPRNG and I also want it to be super fast.

If I use Salsa20 or ChaCha or AES counter mode, I don't get the desired speed. I want my PRNG to work at the speed of 100 Gbps or more.

Morever, I need to be cryptographically secured.

Any suggestions regarding that? Do there exist such CSPRNG that can give me output stream at the speed of 100Gbps or above? Or in other words that can provide bit streams with a speed of 10^-11 bits per sec?

P.S: I don't care about the system requiremt, the platform could be FPGA, GPU etc, I just need some numbers to compare with and to know that with any kind of feasible platform (not super computers) can I achieve the target of 100Gbps in any of the CSPRNG?

$\endgroup$
2
  • $\begingroup$ Use parallel ChaCha20? $\endgroup$
    – kelalaka
    May 3, 2021 at 10:34
  • 2
    $\begingroup$ The answer heavily depends on the platform you're targeting (Instruction Set, Microarchitecture, Frequency, whether you're willing to use multiple and how many cores, ...). However, I find it odd that AES is not fast enough given that in counter mode with hardware support on x86, for details on why see my answer on matter modeling on exactly this topic. $\endgroup$
    – SEJPM
    May 3, 2021 at 10:36

2 Answers 2

4
$\begingroup$

The first thing to NOTE is that said by SEJPM in the comment, performance depends on the hardware - in both horizontal (core count, etc.) and vertical (clock speed, etc.) dimensions. The second thing to understand is that, although CSPRNGs and stream ciphers can share underlaying primitive, their security requirements are different.

So now, let's get started - what're some of the famous symmetric-key primitives?

There are 2 dimensions to consider when excluding the hardware parallism:

  1. block size,

  2. execution time per block.

Grades from slow to fast in: $$\text{Moderate} < \text{Fast} < \text{Very Fast} < \text{High} < \text{Very High}.$$ The grades are my personal opinion.

Primitive Block Size SW Performance Grading HW Performance Grading
Gimli 384-bit Very High Very High
Keccak-p[1600,24] 1600-bit Very Fast High
Keccak-p[800,12] (not yet standardized) 800-bit High High
AES-128 128-bit High Very High
ChaCha20 512-bit High High

I haven't done systematic benchmarks on diverse hardwares and implementations yet, but the numbers are provided here for a quick reference. I used my own (hardly-optimized) MySuiteA library with ad-hoc benchmarking code written in a rush.

Primitive Time of $2^{20}$ iterations of execution on Apple Silicon M1
Gimli 0.973sec
Keccak-p[1600,24] 16.495sec
Keccak-p[800,12] (not yet standardized) 8.143sec
AES-128 35.657sec(sw,unoptimized) 0.184sec(arm-neon-crypto)
ChaCha20 1.287sec

Next, we can consider implementation side.

  • SBox Modern cryptography wisdom says this: avoid SBox if it has to be implemented using look-up table (because it's a cache-memory side-channel), so AES is the most dangerous here;

  • Block Size AES is also dangerous due to its small block size - 128-bit is too small a space for nonce and counter. ChaCha20 also has only 128-bit space for nonce and counter, but it has larger state and a side-channel-resistant non-linear layer.

  • ARX vs Binary Polynomial ARX stands for Add-Rotate-Xor, which is a traditional paradigm for obtaining non-linearity (ChaCha20 follows this). It has the implementation disadvantage of requiring somewhat more complex circuit when doing a hardware implementation, and this is where ones without arithmetic addition - those based on binary polynomials have a win (Gimli, Keccak).

  • Word Length It was a surprise for me to see that my software AES implementation is actually very bad, but anyway, it's a byte-oriented algorithm anyway. What I want to note here is that, Keccak-p[800,12] out-performed Keccak-p[1600,24] not because of smaller block size, but because the fewer number of rounds - using 32-bit words on a 64-bit machine is actually a drawback when compared with using native word lengths. It is for this reason, SHA-512 outperforms SHA-256 on 64-bit computers.


Side information:

Gimli had a full-rounds distinguishing attack last year: https://eprint.iacr.org/2020/744 . Gimli isn't the only 384-bit permutation though, Xoodoo is also a good 384-bit permutation, and is authored by the same group of people invented Keccak, but I haven't implemented in my suite for benchmarking yet.

$\endgroup$
3
  • $\begingroup$ @kelalaka Did it. But additional benchmarking statistics has to be provided by people using different HW. And it's sleep time in my timezone, and I can hardly keep my eyes open now. $\endgroup$
    – DannyNiu
    May 3, 2021 at 15:21
  • $\begingroup$ It's okey. Have a nice sleep. HW is hard to do just for here as long as there are articles for a reference. $\endgroup$
    – kelalaka
    May 3, 2021 at 15:21
  • 1
    $\begingroup$ So, "Very Fast" is slower than "High"? You might want to reconsider the naming of those grades, it doesn't seem at all obvious on a glance what the relationship between "Fast" and "High" with or without the "Very" should be. After glancing at the table, I was going to write a comment asking if that "Very Fast" is the same as "Very High". $\endgroup$
    – ilkkachu
    May 3, 2021 at 20:05
2
$\begingroup$

You want a speed that's hard to reach even for a simple operation such as xoring the PRNG output with some data. You aren't going to get that speed for a CSPRNG except maybe with some serious dedicated hardware engineering.

But you don't need this! Sequential speed is not relevant for a PRNG with unspecified hardware. If you need more PRNG speed than your processor can deliver, run multiple instances in parallel, using as many processors as you need to achieve the desired speed. $N$ CSPRNG instances working in parallel, each instantiated with a seed that is itself obtained from a CSPRNG, constitute a CSPRNG with $N$ times the speed of each instance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.