This is a question just out of curiosity, as I am a newbie to Post Quantum Cryptography. I have read several articles where they emphasize that current standardised symmetric encryption algorithms (that uses 256 bit keys e.g. AES) are Quantum resistant by default. But security of AES 128 can be compromised by Grover's Search algorithm to a complexity of $2^{64}$. Does Grover's Search Algorithm weaken the XSalsa20 / XChacha20 stream ciphers? Also, what about Poly1305 ?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ treat as AES-256. $\endgroup$– hardyramaMar 29, 2020 at 7:00
-
1$\begingroup$ Grover’s search algorithm is the quantum equivalent of classical brute force attacks: it weakens all ciphers the same way, dividing the effective key length by two (compared to a brute force attack) $\endgroup$– Frédéric GrosshansMar 30, 2020 at 10:19
-
$\begingroup$ Actually, if you look at it closer, Grover's really doesn't 'divide the effective key length by two'; even if you ignore the rather considerable cost different between conventional computing and quantum computing, to do a key search over a space of $2^{128}$ with circa $2^{64}$ evaluations, you need to perform those evaluations sequentially - if you could do each one in 10nsec, it would still take circa 5,000 years to do the search. You could try to parallelize things, but that dilutes the advantage of Grover's, forcing you to do more evaluations overall... $\endgroup$– ponchoJun 1, 2021 at 2:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
TL;DR: Yes, it is.
While it is weakened by quantum computers because of Grover's algorithm, it still has enough security margin to be considered "quantum safe".
Does Grover's Search Algorithm weaken the XSalsa20 / XChacha20 stream ciphers?
Yes, it does, but it only provides a quadratic speed-up compared to classical bruteforce, since both XSalsa20 and XChacha20 have 256 bit keys, this translates into a post-quantum "security" of 128 bits, which is still considered plenty enough for now.
Also, what about Poly1305 ?
Poly1305 is a MAC algorithm, and it is not impacted by known quantum algorithm so far. Its security is usually considered to be at the 128-bit security level.
There is even a reduction to that of the underlying PRF-function, which is above the 128 bit level for Chacha20&Co.
More info can also be found in different security analyses of Chacha20-Poly1305 online such as this one.
Is the combination of both secure?
Now, one may be asking about the combination of both that might not necessarily be secure...
But we have formal proofs of security for Chacha20-Poly1305 that are proving that it is secure. I refer you to chapter 8 of Cécile Baritel-Ruet's thesis for all the details.
References
- Bernstein, D. J., & Lange, T. (2017). Post-quantum cryptography : dealing with the fallout of physics success.(Cryptology ePrint Archive; Vol. 2017/314). IACR. PDF
- Daniel, A., & Lejla, B. (2015). Initial recommendations of long-term secure post-quantum systems. PQCRYPTO. EU. Horizon, 2020. PDF
- Procter, G. (2014). A Security Analysis of the Composition of ChaCha20 and Poly1305. IACR Cryptol. ePrint Arch., 2014, 613. PDF
- Almeida, J. B., Barbosa, M., Barthe, G., Grégoire, B., Koutsos, A., Laporte, V., ... & Strub, P. Y. (2020, May). The last mile: high-assurance and high-speed cryptographic implementations. In 2020 IEEE Symposium on Security and Privacy (SP) (pp. 965-982). IEEE.PDF
-
$\begingroup$ The problem, though, remains the key exchange, right? $\endgroup$ May 31, 2021 at 23:09
-
$\begingroup$ @JamesTheAwesomeDude I'd argue that we have enough PQ KEM available now with the NIST PQ finalists... CRYSTALS-Kyber comes to mind as an "easy to use, yet fast and reasonably sizes" one. $\endgroup$– LeryJun 7, 2021 at 9:59