rust-lang/rust — pull request #17387 by sneves (2014-09-19 06:30:18+00:00)
Title: Include ChaCha pseudorandom generator

This commit introduces a [ChaCha](http://cr.yp.to/chacha.html)-based pseudorandom number generator to librand. Here's why I prefer it to the default, ISAAC:

- While ISAAC is meant to be cryptographically secure, it stands on relatively shaky ground. Its design is inspired by the much-maligned RC4, and the [existing analysis](https://eprint.iacr.org/2006/438) reveals some suboptimal properties, although not particularly devastating. ISAAC64, the default on 64-bit architectures, doesn't seem to have been analyzed at all.
- ISAAC has large storage requirements. An ISAAC64 state consumes 4128 bytes, which is ~12.5% of a typical CPU's L1 cache. This ChaCha implementation consumes 144 bytes, and can be further reduced to 105, at the cost of slightly higher implementation complexity. The performance impact of cache hoarding is hard to demonstrate in synthetic benchmarks.
- ISAAC is inherently sequential, and its speed is somewhat limited by data-dependent memory accesses, not unlike RC4. ChaCha, on the other hand, is not and can be vectorized easily for significant speedups, at the cost of larger state.

In my tests, an SSE2 (using only what `#[simd]` types allow at the moment) ChaCha20 roughly matches ISAAC in speed, and an AVX2 implementation matches ISAAC64. Better SIMD support (particularly shuffles) would improve these results further.

I'm currently using the 20-round ChaCha, as originally specified. However, 12 and 8-round variants are also possible (and [believed to be](https://eprint.iacr.org/2007/472) [secure](http://link.springer.com/chapter/10.1007%2F978-3-642-37682-5_24)), and those would provide an additional speedup factor of roughly 20/{12,8}. I have not included SIMD implementations in this commit to avoid the complexity of figuring out which instruction set to use.