Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

rand_chacha: consider ChaCha12 (or possibly ChaCha8) over ChaCha20 #932

Closed
tarcieri opened this issue Jan 13, 2020 · 5 comments · Fixed by #1028
Closed

rand_chacha: consider ChaCha12 (or possibly ChaCha8) over ChaCha20 #932

tarcieri opened this issue Jan 13, 2020 · 5 comments · Fixed by #1028
Milestone

Comments

@tarcieri
Copy link

Background

At RealWorldCrypto 2020 this year, @veorq presented a talk about his "Too Much Crypto" paper, suggesting that the number of rounds used by a number of ciphers, including ChaCha20, is excessively high:

https://eprint.iacr.org/2019/1492

Section 3.3 covers ChaCha:

The best result on ChaCha is a key recovery attack on its 7-round version, with 2^237.7 time complexity (the exact unit is unclear) using output data from 2^96 instances of ChaCha, that is, 2^105 bytes of data. On 6 rounds, a similar attack can run in time & data 2^116 & 2^116, or 2^127.5 & 2^37.5. On 5 rounds, the attack becomes practical due to the lower diffusion, and runs in 2^16 time and data.

Note the 7-round attack is a security reduction from the claimed 256-bits of security, to "237.7" bits, and therefore is not a catastrophic attack.

Section 4.5 notes:

ChaCha: Between 2008 and 2019, the estimated complexity of an attack went from 2^248
to 2^235, using the same technique but refined analysis.

The paper concludes in the "5.3 How many rounds?" section:

ChaCha: 8 rounds instead of 20 (that is, ChaCha8), yielding a 2.5× speed-up

I'll say this particular paper ruffled some feathers, but in as much as some cryptographers were bothered by it, I haven't heard a single technical counterargument to it, only platitudes about weakened security margins being bad and attacks always getting better (which, as it were, are addressed in the paper via technical arguments).

The paper notes how we got "ChaCha20" in the first place - more or less cargo cult from Salsa20, and ignoring the rather rigorous analysis which went into Salsa20 before its inclusion in the eSTREAM portfolio:

Regarding ChaCha, the eSTREAM actually recommended Salsa20/12, or ChaCha’s predecessor with 12 rounds instead of 20, but ChaCha was de facto standardized with 20 rounds.

ChaCha20 offers an additional 13 rounds of security margin over the best known attack, i.e. nearly twice as many rounds purely dedicated to "extra security margin" than are needed for the cipher to be secure.

Feature request

The eSTREAM analysis of Salsa20 suggested Salsa20/12, i.e. the 12-round variant of the original cipher. ChaCha is an evolution/"tweak" of Salsa20, offering better diffusion, and I would argue the eSTREAM analysis is likewise applicable to ChaCha.

I think ChaCha12 provides a nice balance between security margins and performance: 5 rounds of security margin over the best known attack, and a ~1.67X performance speedup over ChaCha20.

The "Too Much Crypto" paper goes as far as to suggest ChaCha8, which I think is a defensible position, and would afford a 2.5X speedup over ChaCha20.

I think it might make sense to offer both, with ChaCha12 the default, and ChaCha8 an option for those who desire more performance.

@scottarc
Copy link

The eSTREAM analysis of Salsa20 suggested Salsa20/12, i.e. the 12-round variant of the original cipher. ChaCha is an evolution/"tweak" of Salsa20, offering better diffusion, and I would argue the eSTREAM analysis is likewise applicable to ChaCha.

See the informal security proof in the XChaCha RFC draft which extends the formal XSalsa20 security proof to apply to XChaCha. Since the ChaCha reduced-round cryptanalysis story is actually better than Salsa20, I'm very confident in the security of ChaCha8 for randomness purposes.

@kazcw
Copy link
Contributor

kazcw commented Jan 13, 2020

I have leaned toward 20-round in the past because the default has to meet the required security margin of all users, but that sounds like a strong argument that no one needs more than 12 rounds.

It sounds like 8-round would probably be ok, but that position is less rigorously supported, and I don't expect there's a strong need for the speedup in ThreadRng. ChaCha12 is fast--within an order of magnitude of memory bandwidth. If someone does a lot of ChaCha incidentally, because they're repeatedly using some 3rd-party function that needs random bits, they're going to be spending most of their time on whatever else that function does. The use case for faster ChaCha is producing a huge chunk of random data, or interleaving rng with only trivial operations; writers of such code can import ChaCha8 and use it directly.

@dhardy
Copy link
Member

dhardy commented Jan 14, 2020

To my lay perspective, this sounds like sufficient argument to prefer ChaCha12 for general usage, including StdRng and thread_rng. Lets go ahead with this change, unless a good counter-argument comes up before-hand.

According to our portability guidelines, this change should wait until (at least) Rand 0.8, which likely will be at least a month away (if not longer). Implementing this change is simple and will be left until shortly before the release.

@dhardy dhardy added this to the 0.8 release milestone Jan 14, 2020
@dhardy dhardy mentioned this issue Jan 14, 2020
19 tasks
@burdges
Copy link
Contributor

burdges commented Jan 15, 2020

You could do ChaCha20Rng, ChaCha12Rng, and ChaCha8Rng type aliases, like c2-chacha itself does, and then a ChaChaRng for ChaCha12Rng or whatever. Anyone who wants binary compatibility or is just paranoid could switch to ChaCha20Rng.

@dhardy
Copy link
Member

dhardy commented Jan 15, 2020

@burdges maybe you should check the existing API before you comment. For clarity: this API will not be adjusted; only StdRng and thread_rng will be affected (which are already documented as "deterministic, non-portable").

tarcieri added a commit to RustCrypto/stream-ciphers that referenced this issue Jan 16, 2020
See the writeup I've already done for the `rand_chacha` crate for the
rationale of including these by default:

rust-random/rand#932

tl;dr: the "Too Much Crypto" paper goes into why ChaCha20 is overkill,
ChaCha12 is probably what should've been standardized per the eSTREAM
analysis of Salsa20 (but wasn't for cargo cult reasons), and ChaCha8
is still probably safe:

https://eprint.iacr.org/2019/1492
tarcieri added a commit to RustCrypto/AEADs that referenced this issue Jan 16, 2020
Adds `ChaCha8Poly1305` and `ChaCha12Poly1305` AEADs, gated under the
(off-by-default) `reduced-round` cargo feature.

See the writeup I've already done for the `rand_chacha` crate for the
rationale of including these by default:

rust-random/rand#932

tl;dr: the "Too Much Crypto" paper goes into why ChaCha20 is overkill,
ChaCha12 is probably what should've been standardized per the eSTREAM
analysis of Salsa20 (but wasn't for cargo cult reasons), and ChaCha8
is still probably safe:

https://eprint.iacr.org/2019/1492
tarcieri added a commit to RustCrypto/AEADs that referenced this issue Jan 16, 2020
Adds `ChaCha8Poly1305` and `ChaCha12Poly1305` AEADs, gated under the
(off-by-default) `reduced-round` cargo feature.

See the writeup I've already done for the `rand_chacha` crate for the
rationale of including these by default:

rust-random/rand#932

tl;dr: the "Too Much Crypto" paper goes into why ChaCha20 is overkill,
ChaCha12 is probably what should've been standardized per the eSTREAM
analysis of Salsa20 (but wasn't for cargo cult reasons), and ChaCha8
is still probably safe:

https://eprint.iacr.org/2019/1492
vks added a commit to vks/rand that referenced this issue Aug 28, 2020
irh added a commit to koto-lang/koto that referenced this issue Jan 9, 2022
See rust-random/rand#932 - it seems that 8 iterations
is more than enough to provide good security, while providing a substantial
speedup over the 20 iteration version.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants