Improving the Security of ChaCha against Differential-Linear Cryptanalysis

• Murilo Coutinho Agência Brasileira de Inteligência / UnB http://orcid.org/0000-0001-7545-5040
• Iago Passos UnB https://orcid.org/0000-0002-6296-6041
• Rafael T. de Sousa Jr. UnB https://orcid.org/0000-0003-1101-3029
• Fábio Borges LNCC https://orcid.org/0000-0001-5159-9517

DOI: https://doi.org/10.5753/sbseg.2020.19224

Resumo

The stream cipher ChaCha has received a lot of attention and recently is being used as a new cipher suite in TLS 1.3, as a random number generator for operating systems (Linux, FreeBSD, OpenBSD, NetBSD, and DragonFly BSD), a proposed standardization in RFC 7634 for use IKE and IPsec, and by the WireGuard VPN protocol. Because of that, it is very important to understand and study the security of this algorithm. Previous works showed that it is possible to break up to 7 of the 20 rounds of ChaCha. In this paper, we show that a simple modification in the algorithm, namely changing the rotation distances in the Quarter Round Function, makes ChaCha more secure against all the most effective known attacks without any loss in performance. In fact, we show that with these changes, it is only possible to break up to 6 rounds of ChaCha. Therefore, it would be no longer possible to break 7 rounds of ChaCha with the best-known attacks.

Referências

Aumasson, J.-P., Fischer, S., Khazaei, S., Meier, W., and Rechberger, C. (2008). New features of latin dances: analysis of Salsa, ChaCha, and Rumba. In International Workshop on Fast Software Encryption, pages 470–488. Springer.

Beierle, C., Leander, G., and Todo, Y. (2020). Improved differential-linear attacks with applications to ARX ciphers. In Annual International Cryptology Conference, pages 329–358. Springer.

Bernstein, D. J. (2005). The Poly1305-AES message-authentication code. In International Workshop on Fast Software Encryption, pages 32–49. Springer.

Bernstein, D. J. (2008a). ChaCha, a variant of Salsa20. In Workshop Record of SASC, volume 8, pages 3–5.

Bernstein, D. J. (2008b). The Salsa20 family of stream ciphers. In New stream cipher designs, pages 84–97. Springer.

Choudhuri, A. R. and Maitra, S. (2016). Significantly improved multi-bit differentials for reduced round Salsa and Chacha. IACR Transactions on Symmetric Cryptology, pages 261–287.

Coutinho, M., De Sousa, R. T., and Borges, F. (2020). Continuous diffusion analysis. IEEE Access.

Coutinho, M. and Neto, T. C. S. (2020). New multi-bit differentials to improve attacks against ChaCha. Cryptology ePrint Archive, Report 2020/350. https://eprint.iacr.org/2020/350.

Crowley, P. (2006). Truncated differential cryptanalysis of five rounds of Salsa20. The State of the Art of Stream Ciphers SASC, 2006:198–202.

Dey, S., Roy, T., and Sarkar, S. (2019). Revisiting design principles of Salsa and ChaCha. Advances in Mathematics of Communications, 13(4).

Dey, S. and Sarkar, S. (2017). Improved analysis for reduced round Salsa and ChaCha. Discrete Applied Mathematics, 227:58–69.

Ding, L. (2019). Improved related-cipher attack on Salsa20 stream cipher. IEEE Access, 7:30197–30202.

Fischer, S., Meier, W., Berbain, C., Biasse, J.-F., and Robshaw, M. J. (2006). Non-randomness in eSTREAM candidates Salsa20 and TSC-4. In International Conference on Cryptology in India, pages 2–16. Springer.

Hernandez-Castro, J. C., Tapiador, J. M., and Quisquater, J.- J. (2008). On the Salsa20 core function. In International Workshop on Fast Software Encryption, pages 462–469. Springer.

IANIX (2020). ChaCha usage & deployment. https://ianix.com/pub/chacha-deployment.html. Accessed: 2020-01-13.

Ishiguro, T., Kiyomoto, S., and Miyake, Y. (2011). Latin dances revisited: new analytic results of Salsa20 and ChaCha. In International Conference on Information and Communications Security, pages 255–266. Springer.

Langley, A., Chang, W., Mavrogiannopoulos, N., Strombergson, J., and Josefsson, S. (2016). ChaCha20-Poly1305 cipher suites for transport layer security (TLS). RFC 7905, (10).

Maitra, S. (2016). Chosen IV cryptanalysis on reduced round ChaCha and Salsa. Discrete Applied Mathematics, 208:88–97.

Maitra, S., Paul, G., and Meier, W. (2015). Salsa20 cryptanalysis: New moves and revisiting old styles. In the Ninth International Workshop on Coding and Cryptography.

Mouha, N. and Preneel, B. (2013). A proof that the ARX cipher Salsa20 is secure against differential cryptanalysis. IACR Cryptology ePrint Archive, 2013:328.

Shi, Z., Zhang, B., Feng, D., and Wu, W. (2012). Improved key recovery attacks on reduced-round Salsa20 and ChaCha. In International Conference on Information Security and Cryptology, pages 337–351. Springer.

Torvalds, L. (2016). Linux kernel source tree. [link].

Tsunoo, Y., Saito, T., Kubo, H., Suzaki, T., and Nakashima, H. (2007). Differential cryptanalysis of Salsa20/8. In Workshop Record of SASC, volume 28.