ChaCha construction and rounds

[dhardy]

This is about two things; set_rounds and a new constructor; quotes from reddit:

The methods new_unseeded and set_rounds on the ChaChaRng type are a bit scary, IMHO. I'm heartened that the former is deprecated, but maybe the warning ought to be strengthened (e.g., "This method makes it too easy to create a random number generator in an insecure state.") set_rounds sounds like something that should only be allowed when the object is being created. More generally, I just noticed that there's no "raw" method for creating a ChaChaRng from a key and nonce/counter—I think there ought to be one.

set_counter is also a bit scary but something like it is most likely necessary to support non-cryptographic applications (e.g., producing multiple random streams from the same seed by advancing far into the generator's sequence).

I wonder if we should support CryptoRng only for ChaCha20 and maybe ChaCha12?

[burdges]

Isn't new_unseeded going away? Yes I'd say restrict CryptoRng by rounds. As an aside, you could make rounds a const type parameter eventually, except them silly people will do ChaCha<100> or whatever. ;)

[dhardy]

Yes, new_unseeded is already deprecated.

ChaChaRng was restricted to 20 rounds but @pitdicker changed it to be adjustable. It seemed like a good idea, but maybe it's not, I don't know... exploiting it would require finding a way to reduce the rounds to the minimum (which is 8), then cracking ChaCha8 (which as far as I know is still a very hard/impossible problem).

[pitdicker]

I wonder if we should support CryptoRng only for ChaCha20 and maybe ChaCha12?

I think that is a good takeaway from this. But I believe we can't?

I can't care all that strongly though. The marker trait has uses, but it is no promise the RNG is secure. There are all kinds of ways a user can mess up, for example during initialization. Setting the number of rounds to something too low is just one of the problems.

[vks]

The trend has been towards crypto libraries that are as hard as possible to use incorrectly by minimizing parameters adjustable by the user (see for example libsodium and ring).

Aren't we deprecating ChaChaRng anyway? Why add new methods to it then?

[pitdicker]

That is a good point. But as I see it Rand is not a crypto library, and ChaCha has valid uses outside of cryptography. With a reduced number of rounds it is no longer suitable for cryptography-related things, but it is still a very good and reasonably fast RNG. Who is to say that is not a valid use case?

Why would you say we are deprecating ChaChaRng?

[dhardy]

I wonder myself if it makes more sense to have separate ChaCha8Rng / .. / ChaChaRng (default 20) than having this run-time adjustment. That way we can impl CryptoRng on exactly what we want and it's easier to initialise a version with reduced rounds and custom seed.

[vks]

Why would you say we are deprecating ChaChaRng?

I thought it is superseded by HC128 and will be removed in the long term, but maybe I'm mistaken.

Who is to say that is not a valid use case?

I would prefer to expose this functionality in a separate crate.

Rand is not a crypto library

If we are taking this point of view, I think we should not advertise any of our RNGs as "cryptographically secure". We might want to consider moving our crypto RNGs to RustCrypto/CSRNGs.

[burdges]

I think separate round count types makes sense.

I disagree that HC128 supersucceeds ChaCha for all CSPRNG applications. As minimum, initializing HC128 has a slow startup when you start with a good randomness, fork CSPRNGs lots, and only needs a small amount of output for each one. In fact, I think quite the opposite that CSPRNGs should be easy to use in standards compliant ways, which requires some diversity.

[pitdicker]

Yes. HC-128 is really different, and both have there uses.

Is there something here we want to change before 0.5? Maybe hide the set_rounds function for now?

[dhardy]

Yes, hiding set_rounds makes sense IMO.

There is an option for setting rounds at construction-time only with SeedableRng: use a builder type, i.e. ChaChaBuilder::from_seed(..).set_rounds(12).build(). I'm not sure if this really makes sense over wrapper types (ChaCha12::from_seed(..)), but it would allow some other tricks, e.g. setting the counter and nonce at build time.

[dhardy]

Is there much usage of ChaCha8 or ChaCha12? Not that I can find...

Are they secure? There's a 2008 paper that documents an "attack" (but not a practical one) against Salsa20/8 and ChaCha7. It mentions:

Our attack on reduced-round 256-bit Salsa20 exploits a 4-round differential, to
break the 8-round cipher by working four rounds backward. For ChaCha, we
use a 3-round differential to break 7 rounds. We made intensive experiments for
observing a bias after going five rounds backwards from the guess of a subkey,
in order to attack Salsa20/9 or ChaCha8, but without success. Four seems to be
the highest number of rounds one can invert from a partial key guess, while still
observing a non-negligible bias after inversion, and such that the overall cost
improves from exhaustive key search. Can one hope to break further rounds by
statistical cryptanalysis? We believe that it would require novel techniques and
ideas, rather than the relatively simple XOR difference of 1-bit input and 1-bit
output. For example, ...

Apparently 15 rounds of Salsa20 is 128-bit secure.

It therefore appears that ChaCha8 and ChaCha12 fall into a "grey zone" of having no known practical attacks but without a high confidence of security, similar to the ISAAC RNGs. So is there any point at all in exposing these reduced-round variants? HC128 appears a better choice for both performance and apparent security.

(If anyone specifically wants the reduced-round variants, speak up, but it sounds like we have no use for them.)

[burdges]

I'd leave them out for now, mostly because we added CryptoRng which complicates making decisions, but use the name ChaCha20. If anyone wants them then we can figure out if they satisfy CryptoRng later.

[pitdicker]

I see ChaCha with fewer rounds as a valid use. It is not suitable as a CSPRNG. But it has good statistical quality even with only 3 rounds. It uses relatively little memory, and has reasonable performance that can be combined with SIMD. So one group would dismiss it, for another it can be useful.

An alternative idea: What about removing CryptoRng from ChaChaRng, and keeping the set_rounds function on that one. And add ChaCha20Rng, that does implement CryptoRng, but does not allow setting the rounds.

[burdges]

Sure. Is ChaCha20Rng just a wrapper around ChaChaRng then?

[pitdicker]

https://github.com/rust-lang-nursery/rand/pull/374/files changed ChaChaRng to have a 64-bit counter and a 64-bit stream. It now has functions to get and set the position using u128s. With some creativity the stream can be used as a nonce. The ability to set the number of rounds is dropped.

In my opinion our implementation is in a pretty good state now, feature-wise. Using ChaCha with fewer rounds or different constructors seems like something niche enough to me to be something in a crate outside Rand.

I think this issue can be closed?