Score:1

Does triple ChaCha20 have 256-bit post-quantum security?

tc flag

Experts suggested 3DES when AES wasn't developed yet, since meet-in-the-middle attack, they suggested triple DES. Grover's algorithm, a quantum algorithm, weakens symmetric encryptions, how about triple ChaCha20? Does triple ChaCha20 have 256-bit security against quantum computers?

Maarten Bodewes avatar
in flag
Musings. This doesn't answer the question, but we don't *need* 256 bit security, and Grover's algorithm is not very lightweight either. It's nice to have a bit of a margin when it comes to classical attacks, but I wonder how much of that is true of Grover; it's not like Grover's algorithm is likely to improve much for a specific cipher. So in general having 128 bit security against quantum computers / Grover should be *fine*. Since quantum cryptanalysis is generally search, I'd say that yes, triple ChaCha20 would provide at least 256 bit security.
Maarten Bodewes avatar
in flag
Note that the inner structure of ChaCha20 *can* be used as a PRF, but don't forget that ChaCha20 is basically a stream cipher. So *technically* you'd first have to define triple ChaCha20.
Flan1335 avatar
tc flag
I define triple ChaCha20 as that: For n-bit data, encrypt all n bits, and then go back to the 1st bit then encrypt those n bits again with another key, and so on. After every encryption process, go back to the 1st bit then do the next encryption process with another key. Since ChaCha20 is different to AES: With ChaCha20, encrypting plaintext twice with the same key results in plaintext, it requires 3 different keys.
Flan1335 avatar
tc flag
What do you mean "PRF"?
honzaik avatar
cn flag
@Flan1335 Regarding the PRF: Maarten probably means this https://en.wikipedia.org/wiki/Pseudorandom_function_family (PRF) as noted in https://en.wikipedia.org/wiki/Salsa20 "Both ciphers are built on a pseudorandom function based on add-rotate-XOR (ARX) operations — 32-bit addition, bitwise addition (XOR) and rotation operations." In other words, the keystream generating function can be considered a pseudorandom function keyed by the symmetric key. This (naturally, otherwise the cipher would be insecure) means that the generated key is pseudorandom (indistinguishable from a truly random key).
Score:3
in flag

First of all, we don't need 256 bit security. 128 bit security is fine; $2^{128}$ operations is already infeasible, especially when we're talking about security against quantum-cryptanalysis where the operations are more expensive than with a regular computer. Grover's algorithm is also known to be very resource intensive, requiring the emulation of the target algorithm using qubits.

Furthermore, while it is nice to have a bit of a margin when it comes to classical attacks, it's not likely that Grover's algorithm will be enhanced so that fewer qubits are required. Grover has been shown to be optimal for the "bruteforce" attempt against a cipher / key, so the number of logical qubits will at least remain the same. It is yet unclear how many qubits will be required for error conditions, so the number of required physical qubits is still unknown. That doesn't matter much as it won't alter the logical number of operation or qubits required.

DES is a block cipher, and triple DES consists of encryption, decryption and then encryption again of the block cipher. The mode of operation for the block cipher (e.g. CBC) is then performed on that stacked construction. ChaCha20 however is a stream cipher, not a block cipher, so you'd have to define what triple ChaCha20 would be like. ChaCha20 contains a PRF internally, and I guess that PRF can be tripled, but that's messing with the internal definition of the cipher.

That all said, quantum cryptanalysis is generally search, I'd say that yes, triple ChaCha20 would provide at least 256 bit security. However, as indicated, that's not required in any situation; defining or using triple-ChaCha20 would not make a system more secure in practice. Maybe triple AES-128 would make some sense if all you have is accelerated AES for that particular key size (I've seen some embedded processors that have those kind of limitations). Even AES-128 would be pretty hard to break though.

Maarten Bodewes avatar
in flag
OK, too many upvotes on my comments, took a leap and converted it to an answer.
Maarten Bodewes avatar
in flag
Note that another method would be to simply use multiple encryption and XOR the generated key streams and plaintext together.
Flan1335 avatar
tc flag
I define triple ChaCha20 as that: For n-bit data, encrypt all n bits, and then go back to the 1st bit then encrypt those n bits again with another key, and so on. After every encryption process, go back to the 1st bit then do the next encryption process with another key. Since ChaCha20 is different to AES: With ChaCha20, encrypting plaintext twice with the same key results in plaintext, it requires 3 different keys.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.