Replacing rand_chacha with chacha20

[dhardy]

@tarcieri has recently implemented ChaCha*Rng via the chacha20 crate. docs are here. Breaking out into a new issue this isn't really the topic of #872...

This brings the question: should we prefer this over the current (@kazcw's) implementation?

First things first, the rand_chacha crate has 44 reverse dependencies, is clearly a rand family crate and is recommended in our book. There is no plan to retire this crate.

Second, lets look at a few stats.

Unsafe

Here are the results of running cargo geiger on the current rand_core (after #931):

$ cargo geiger
<snip>
Metric output format: x/y
    x = unsafe code used by the build
    y = total unsafe code found in the crate

Symbols: 
    :) = No `unsafe` usage found, declares #![forbid(unsafe_code)]
    ?  = No `unsafe` usage found, missing #![forbid(unsafe_code)]
    !  = `unsafe` usage found

Functions  Expressions  Impls  Traits  Methods  Dependency

0/0        0/0          0/0    0/0     0/0      ?  rand_chacha 0.2.2
2/2        557/626      0/0    0/0     14/22    !  ├── ppv-lite86 0.2.6
0/0        22/22        0/0    0/0     0/0      !  └── rand_core 0.5.1

2/2        579/648      0/0    0/0     14/22  

And on chacha20:

$ cargo geiger --no-default-features --features rng
<snip>
Functions  Expressions  Impls  Traits  Methods  Dependency

7/14       199/427      0/0    0/0     1/2      !  chacha20 0.3.1
0/0        22/22        0/0    0/0     0/0      !  ├── rand_core 0.5.1
2/4        50/150       1/1    0/0     3/3      !  │   └── getrandom 0.1.14
0/0        0/0          0/0    0/0     0/0      ?  │       ├── cfg-if 0.1.10
2/2        73/95        0/0    0/0     5/11     !  │       └── libc 0.2.66
0/0        0/0          0/0    0/0     0/0      ?  └── stream-cipher 0.3.2
0/0        0/0          0/0    0/0     0/0      ?      ├── blobby 0.1.2
0/1        0/231        0/0    0/0     0/0      ?      │   └── byteorder 1.3.2
0/1        0/223        0/18   0/8     0/5      ?      └── generic-array 0.12.3
0/0        0/51         0/0    0/0     0/0      ?          └── typenum 1.11.2

11/22      344/1199     1/19   0/8     9/21   

Something's wrong here: stream-chiper is only a dev-dependency and rand_core is depended on in exactly the same way as in rand_chacha. So only the first line is relevant.

Lines of code

Tokei output for rand_chacha:

$ tokei rand/rand_chacha/ cryptocorrosion/utils-simd/ppv-lite86/
-------------------------------------------------------------------------------
 Language            Files        Lines         Code     Comments       Blanks
-------------------------------------------------------------------------------
 Markdown                2           70           70            0            0
 Rust                    9         4285         3864          164          257
 TOML                    2           48           42            0            6
-------------------------------------------------------------------------------
 Total                  13         4403         3976          164          263
-------------------------------------------------------------------------------

(83% of this is from ppv-lite86).

For chacha20:

$ tokei
-------------------------------------------------------------------------------
 Language            Files        Lines         Code     Comments       Blanks
-------------------------------------------------------------------------------
 Markdown                2          170          170            0            0
 Rust                   12         1617         1163          203          251
 TOML                    1           47           40            0            7
-------------------------------------------------------------------------------
 Total                  15         1834         1373          203          258
-------------------------------------------------------------------------------

There are no dependencies we need, so that's it. A nice improvement.

Benchmarks

(64-bit Haswell)

Here's rand_chacha:

$ cargo bench --bench generators chacha
   Compiling ...

running 16 tests
test gen_bytes_chacha12      ... bench:     356,133 ns/iter (+/- 5,261) = 2875 MB/s
test gen_bytes_chacha20      ... bench:     539,102 ns/iter (+/- 8,237) = 1899 MB/s
test gen_bytes_chacha8       ... bench:     263,023 ns/iter (+/- 15,029) = 3893 MB/s
test gen_u32_chacha12        ... bench:       1,689 ns/iter (+/- 168) = 2368 MB/s
test gen_u32_chacha20        ... bench:       2,475 ns/iter (+/- 60) = 1616 MB/s
test gen_u32_chacha8         ... bench:       1,300 ns/iter (+/- 56) = 3076 MB/s
test gen_u64_chacha12        ... bench:       4,058 ns/iter (+/- 324) = 1971 MB/s
test gen_u64_chacha20        ... bench:       4,472 ns/iter (+/- 647) = 1788 MB/s
test gen_u64_chacha8         ... bench:       3,252 ns/iter (+/- 421) = 2460 MB/s
test init_chacha             ... bench:          30 ns/iter (+/- 7)

and here's chacha20:

running 16 tests
test gen_bytes_chacha12      ... bench:   1,184,161 ns/iter (+/- 75,680) = 864 MB/s
test gen_bytes_chacha20      ... bench:   1,894,244 ns/iter (+/- 16,309) = 540 MB/s
test gen_bytes_chacha8       ... bench:     824,644 ns/iter (+/- 52,944) = 1241 MB/s
test gen_u32_chacha12        ... bench:       4,607 ns/iter (+/- 97) = 868 MB/s
test gen_u32_chacha20        ... bench:       7,351 ns/iter (+/- 121) = 544 MB/s
test gen_u32_chacha8         ... bench:       3,257 ns/iter (+/- 407) = 1228 MB/s
test gen_u64_chacha12        ... bench:       9,396 ns/iter (+/- 1,104) = 851 MB/s
test gen_u64_chacha20        ... bench:      14,856 ns/iter (+/- 750) = 538 MB/s
test gen_u64_chacha8         ... bench:       6,431 ns/iter (+/- 625) = 1243 MB/s
test init_chacha             ... bench:          14 ns/iter (+/- 0)

Hmm, looks like chacha20 needs some help:

$ export RUSTFLAGS="-C target-cpu=native"
$ cargo bench --bench generators chacha
...
test gen_bytes_chacha12      ... bench:     500,699 ns/iter (+/- 28,157) = 2045 MB/s
test gen_bytes_chacha20      ... bench:     789,107 ns/iter (+/- 52,585) = 1297 MB/s
test gen_bytes_chacha8       ... bench:     357,024 ns/iter (+/- 23,501) = 2868 MB/s
test gen_u32_chacha12        ... bench:       2,139 ns/iter (+/- 56) = 1870 MB/s
test gen_u32_chacha20        ... bench:       3,260 ns/iter (+/- 116) = 1226 MB/s
test gen_u32_chacha8         ... bench:       1,571 ns/iter (+/- 32) = 2546 MB/s
test gen_u64_chacha12        ... bench:       4,472 ns/iter (+/- 55) = 1788 MB/s
test gen_u64_chacha20        ... bench:       6,714 ns/iter (+/- 421) = 1191 MB/s
test gen_u64_chacha8         ... bench:       3,338 ns/iter (+/- 46) = 2396 MB/s

Closer, but still behind rand_chacha (which gets negligible boost from target-cpu=native thanks to auto-detection).

Running chacha20's built-in benchmarks, I get around 6-6.2 cycles/byte without target-cpu=native, and 2.5-2.7 with; this is significantly short of the 1.4 cycles/byte @tarcieri claims so something gives here (perhaps just CPU-specific optimisations).

---

Of course, there's more to this than a few stats, and number-of-unsafe-usages is not a particularly useful comparison (since it says nothing about the size of the unsafe blocks). This is all I have time for right now. Thanks to all authors (also significantly @newpavlov).

[tarcieri]

You'll need -Ctarget-feature=+avx2 to enable the AVX2 backend.

[tarcieri]

Regarding unsafe, most of those are core::arch invocations of CPU intrinsics, which are presently all unsafe but aside from unaligned loads and stores otherwise have safe semantics (and ideally, in future versions of Rust, could be safe).

Probably the most questionable use of unsafe is here:

https://github.com/RustCrypto/stream-ciphers/blob/master/chacha20/src/rng.rs#L74

It'd be good to evaluate various safe ways of replacing that. Really it's just a same-size type conversion which ideally could be done with a type cast or using [u8; BUFFER_SIZE] in the first place, which isn't possible given the current trait bounds (since BUFFER_SIZE is 64 or 128-bytes, and many traits are only impl'd for arrays up to 32 elements)

[dhardy]

I get the same results with RUSTFLAGS="-C target-cpu=native -C target-feature=+avx2".

[tarcieri]

I just benchmarked the chacha20 crate w\ AVX2 against c2-chacha and got proportionally similar numbers.

These are on a 2.3 GHz Intel Core i9, benchmarked with -Ctarget-cpu=native (which I guess activates +avx2)

chacha20 crate

stream-cipher/apply_keystream/1024
                        time:   [1310.7990 cycles 1317.8652 cycles 1325.9773 cycles]
                        thrpt:  [1.2949 cpb 1.2870 cpb 1.2801 cpb]
stream-cipher/apply_keystream/2048
                        time:   [2622.9998 cycles 2632.6188 cycles 2644.3250 cycles]
                        thrpt:  [1.2912 cpb 1.2855 cpb 1.2808 cpb]
stream-cipher/apply_keystream/4096
                        time:   [5221.1966 cycles 5244.4537 cycles 5274.3516 cycles]
                        thrpt:  [1.2877 cpb 1.2804 cpb 1.2747 cpb]
stream-cipher/apply_keystream/8192
                        time:   [10414.4934 cycles 10429.8827 cycles 10447.8984 cycles]
                        thrpt:  [1.2754 cpb 1.2732 cpb 1.2713 cpb]\
stream-cipher/apply_keystream/16384
                        time:   [20781.5026 cycles 20813.0523 cycles 20848.4600 cycles]
                        thrpt:  [1.2725 cpb 1.2703 cpb 1.2684 cpb]

c2-chacha

c2-chacha/apply_keystream/1024
                        time:   [901.0832 cycles 903.5886 cycles 907.2423 cycles]
                        thrpt:  [0.8860 cpb 0.8824 cpb 0.8800 cpb]
c2-chacha/apply_keystream/2048
                        time:   [1806.3139 cycles 1809.9486 cycles 1814.3681 cycles]
                        thrpt:  [0.8859 cpb 0.8838 cpb 0.8820 cpb]
c2-chacha/apply_keystream/4096
                        time:   [3621.2403 cycles 3634.5047 cycles 3649.5313 cycles]
                        thrpt:  [0.8910 cpb 0.8873 cpb 0.8841 cpb]
c2-chacha/apply_keystream/8192
                        time:   [7154.2516 cycles 7176.5530 cycles 7204.1146 cycles]
                        thrpt:  [0.8794 cpb 0.8760 cpb 0.8733 cpb]
c2-chacha/apply_keystream/16384
                        time:   [14277.4103 cycles 14351.7591 cycles 14445.5426 cycles]
                        thrpt:  [0.8817 cpb 0.8760 cpb 0.8714 cpb]

So ~1.3 cpb for the chacha20 crate, and ~0.9 cpb for the c2-chacha crate (i.e. c2-chacha is ~45% faster)

It looks like ppv-lite86 is capable of using AVX2 as well.

[str4d]

I've made some significant improvements to chacha20's performance in RustCrypto/stream-ciphers#261. I believe the remaining gap between it and c2-chacha would be addressed by RustCrypto/stream-ciphers#262.

[dhardy]

This issue is now 32 months old! Is it worth revisiting?

1. What are the core motivations?
2. How has the crate changed since this issue was opened? I see that cipher is now a required dependency.

If we don't do this, possibly we should instead support zeroize for rand_chacha.

[tarcieri]

@dhardy the v0.9 release made cipher a hard dependency. It also removed the RNG implementations with the goal of being able to generically use any stream cipher as an RNG, but that support never shipped, so removing the RNG implementations was probably premature.

I'd be happy to add the RNG types back and make the cipher dependency optional if there's interest in using chacha20 in lieu of rand_chacha.

[dhardy]

The reason that never happened so far is because (1) there is not (to me) a clear motivation for switching and (2) this crate hasn't seen a lot of maintenance activity recently. I'm not aware of any problem with rand_chacha, though perhaps it should support zeroize.

A motivation against is the larger number of crates in the dependency tree; something many would not consider an issue but a few people have brought it up in the past.

❯ cargo tree
chacha20 v0.9.0 (/home/dhardy/projects/rand/stream-ciphers/chacha20)
├── cfg-if v1.0.0
├── cipher v0.4.3
│   ├── blobby v0.3.1
│   ├── crypto-common v0.1.6
│   │   ├── generic-array v0.14.6
│   │   │   └── typenum v1.15.0
│   │   │   [build-dependencies]
│   │   │   └── version_check v0.9.4
│   │   └── typenum v1.15.0
│   └── inout v0.1.3
│       └── generic-array v0.14.6 (*)
└── cpufeatures v0.2.5

❯ cargo tree
rand v0.8.5 (/home/dhardy/projects/rand/rand)
├── libc v0.2.133
├── rand_chacha v0.3.1 (/home/dhardy/projects/rand/rand/rand_chacha)
│   ├── ppv-lite86 v0.2.16
│   └── rand_core v0.6.4 (/home/dhardy/projects/rand/rand/rand_core)
│       └── getrandom v0.2.7
│           ├── cfg-if v1.0.0
│           └── libc v0.2.133
└── rand_core v0.6.4 (/home/dhardy/projects/rand/rand/rand_core) (*)

9 for chacha20 vs 7 for the whole of rand (with default features).

[tarcieri]

Yeah, we could make the cipher dependency optional again like it was in v0.8 of chacha20

[newpavlov]

cipher became a required dependency because this issue has not moved anywhere. It allowed to simplify code a bit, but it's relatively easy to make it optional again. We can do it, if the number of dependencies is the only roadblock.

The main motivation is to unify code bases, so improvements in chacha20 would be immediately shared with the rand ecosystem and potential rand contributors would help us as well. As a minor improvement it would also reduce size of dependency tree and resulting binaries for projects which use both ThreadRng and chacha20.

[dhardy]

We should ensure @kazcw has the chance to comment here too.

so improvements in chacha20 would be immediately shared with the rand ecosystem and potential rand contributors would help us as well

Since the libraries don't have a huge scope and are basically done already, is this actually motivation?

As a minor improvement it would also reduce size of dependency tree and resulting binaries for projects which use both ThreadRng and chacha20.

Is this common?

My POV is still: there is little real motivation either way. But if enough other people feel strongly about this, it will likely persuade me.