rand_chacha and reducing dependencies

[dhardy]

This is basically forked from #850: a request to reduce the number of dependencies. This issue is opened for discussion since previously it did not have much. Also see: #667, #789.

As can be seen, this crate has several dependencies of its own, and is also the only required dependency of rand (besides getrandom, rand_core and on some platforms libc):

    ├── rand_chacha v0.2.1
    │   ├── c2-chacha v0.2.2
    │   │   ├── lazy_static v1.4.0
    │   │   └── ppv-lite86 v0.2.5
    │   └── rand_core v0.5.0
    │       └── getrandom v0.1.11 (*)

Probable resolution: no change

We don't need to change anything.

Possible resolution: subsume dependencies

We could copy some/all dependencies up into rand_chacha. Note that currently c2-chacha has no other dependent crates, while ppv-lite86 has two (both only used by the powhasher miner, as far as I can tell).

CC @kazcw

Other resolutions

We could revert back to HC-128 which has a fast implementation without use of SIMD intrinsics.

We could revert to the old ChaCha implementation or use the chacha20 crate, however this would not be good for performance.

[newpavlov]

I think @tarcieri plans to implement SIMD acceleration for chacha20 crate. After it will be done we could make dependency on stream-cipher optional to reduce number of dependencies when used from rand_chacha. We even could implement BlockRngCore directly by adding an optional dependency on rand_core.

BTW in RustCrypto we were thinking about introducing a generic wrapper à la BlockRng. Maybe it's worth to revisit the suggestion of moving the block stuff outside of rand_core? This wrapper could implement both stream-cipher and rand_core traits behind feature gates and we will not have any code duplication.

This way dependency tree will look like:

├── rand_chacha
│   └── chacha20
│       └── block-stuff-crate
│           ├── rand_core
│           │   └── getrandom
│           └── stream-cipher (optional, disabled by default)

UPD: We also could deprecate rand_chacha and use chacha20 or c2-chacha directly, assuming they will implement rand_core traits.

[tarcieri]

SIMD support in the chacha20 crate would take me ~1 day. The algorithm is trivial.

I really like the idea of having a "raw" API for the ChaCha20 core and making the rest of the crate dependencies optional (but default-enabled).

[dhardy]

Having another fast implementation of ChaCha20 does give us options.

Does it not still suffer the problem of language SIMD support being experimental?

[newpavlov]

Well, x86(-64) intrinsics have been stable for a relatively long time (since 1.27), so I wouldn't call them "experimental". One noticeable issue is the absence of is_..._feature_detected! macros in core (see rust-lang/rfcs#2725). But since initially we will support only x86(-64) (since intrinsics for other arches are still only available in Nightly), it shouldn't be a problem. We can use an approach similar to one we use for RDRAND in getrandom, i.e. manual call to CPUID and cashing target feature check result in an atomic variable.

[tarcieri]

Does it not still suffer the problem of language SIMD support being experimental?

Just to +1 @newpavlov here, while there are a lot of unstable parts of core::arch::x86/x86_64, SIMD ChaCha20 can be implemented entirely in terms of the stable APIs.

[dhardy]

BTW in RustCrypto we were thinking about introducing a generic wrapper à la BlockRng. Maybe it's worth to revisit the suggestion of moving the block stuff outside of rand_core? This wrapper could implement both stream-cipher and rand_core traits behind feature gates and we will not have any code duplication.

BlockRng is the basis for minimal overhead in ReseedingRng and fork protection. If you propose removing that from rand_core, please also propose how reseeding should be implemented.

[bjorn3]

The c2-chacha crate hasn't been updated for 2 months and has two PRs for 2 cq 5 months. It also doesnt work without at least SSE2 when the simd feature is enabled. (enabled by default) cryptocorrosion/cryptocorrosion#25

[tarcieri]

I'd be happy to look into adding SIMD support which "just works" and isn't gated on a feature to the chacha20 crate, or if anyone else would like to contribute it, I can review / merge PRs and release it.

It's definitely on my list of things to do (as part of starting to use the chacha20poly1305 crate in earnest and I hope to get around to it soon if no one else does.

[dhardy]

That would be brilliant @tarcieri.

In the mean-time it does appear that @kazcw and the whole cryptocorrosion project has gone silent, but I am not aware of any significant issues other than the build issue with Cranelift mentioned by @bjorn3 (hopefully something you can work around for now?), thus I suggest we wait for the SIMD work on chacha20. If necessary we can switch the implementation, though in complaince with our portability rules we should stick with ChaCha20 for the Rand 0.7.x series.

[bjorn3]

but I am not aware of any significant issues other than the build issue with Cranelift mentioned by @bjorn3 (hopefully something you can work around for now?)

Patching c2-chacha works.

[tarcieri]

We just landed SSE support in the chacha20 crate, resulting in a ~25% performance improvement (I measure it as going from 6.7 cycles/byte to 5.3) and I plan on cutting another release in the next day or so:

RustCrypto/stream-ciphers#61

We'll hopefully be adding an AVX2 backend soon as well.