Skip to content

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

@tarcieri

Description

@tarcieri

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions