×

zbMATH — the first resource for mathematics

A theoretical investigation on the distinguishers of Salsa and ChaCha. (English) Zbl 1469.94092
Summary: Salsa and ChaCha are two of the most well-known stream ciphers in last two decades. These two ciphers came into the picture when a massively used cipher RC4 was going through severe cryptanalysis and a significant number of observed weaknesses of it showed the requirement of new stream ciphers in the market. Later, ChaCha was adopted by Google as their encryption algorithm, which further increased the importance of research work on these two ciphers. Salsa and ChaCha have gone through differential key recovery attack up to the 8-th and 7-th round respectively. Initially, this attack used an experimentally observed distinguisher by observing a single bit position up to the 4th round for Salsa and 3rd round for ChaCha. Later, S. Maitra [Discrete Appl. Math. 208, 88–97 (2016; Zbl 1342.94082)] improved the attack complexity by minimizing the propagation of the difference after the first round using properly chosen IV values. Also, using this distinguisher, A. R. Choudhuri and S. Maitra [“Significantly improved multi-bit differentials for reduced round Salsa and ChaCha”, IACR Trans. Symmetric Cryptol. 2016, No. 2, 261–287 (2016; doi:10.13154/tosc.v2016.i2.261-287)] provided a technique to construct a distinguisher for the next round of both the ciphers by observing multiple bits. Among all these attacks which were mostly based on experimental observations, theoretical works did not get much importance for these two ciphers. In this paper, we aim to theoretically investigate the reason behind these experimentally observed distinguishers for these chosen IV distinguishers, where the difference propagation is minimized up to the first round. We provide a mathematical proof of the observed probabilities for the distinguishers of both the ciphers in the single and multiple bits.
MSC:
94A60 Cryptography
Citations:
Zbl 1342.94082
Software:
Rumba20; ChaCha
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Enable chacha20/poly1305 cipher suites for firefox (2016), https://bugzilla.mozilla.org/show_bug.cgi?id=1247860
[2] Aumasson, J. P.; Fischer, S.; Khazaei, S.; Meier, W.; Rechberger, C., New features of latin dances: Analysis of salsa, chacha, and rumba, (FSE 2008. FSE 2008, LNCS, vol. 5086 (2008)), 470-488 · Zbl 1154.68378
[3] Banik, S.; Isobe, T., Cryptanalysis of the full spritz stream cipher, (FSE (2016)), Available at https://eprint.iacr.org/2016/092.pdf · Zbl 1387.94067
[4] Bardeh, Navid G.; Rønjom, Sondre, The exchange attack: How to distinguish 6 rounds of AES with \(2^{88 . 2}\) chosen plaintexts, Asiacrypt (2019), Available at https://eprint.iacr.org/2019/652.pdf · Zbl 1455.94118
[5] Beierle, C.; Leander, G.; Todo, Y., Improved differential-linear attacks with applications to ARX ciphers, (CRYPTO (2020)), https://eprint.iacr.org/2020/775
[6] Bernstein, D. J., Salsa20 specification, (ESTREAM Project Algorithm Description (2005)), http://www.ecrypt.eu.org/stream/salsa20pf.html
[7] Choudhuri, A. R.; Maitra, S., Significantly improved multi-bit differentials for reduced round salsa and chacha, IACR Trans. Symmetric Cryptol., 2016, 2, 261-287 (2016), Available at https://doi.org/10.13154/tosc.v2016.i2.261-287
[8] Coutinho, M.; Neto, T. C.S., Improved linear approximations to ARX ciphers and attacks against chacha, Eurocrypt (2021), https://eprint.iacr.org/2021/224
[9] Crowley, P., Truncated Differential Cryptanalysis of Five Rounds of Salsa20 (2005), IACR, Available at http://eprint.iacr.org/2005/375
[10] K. Deepthi, K. Singh, Cryptanalysis of salsa and chacha: Revisited, in: International Conference on Mobile Networks and Management, 2018.
[11] Dey, S.; Sarkar, S., Improved analysis for reduced round salsa and chacha, Discrete Appl. Math., 227, 58-69 (2017) · Zbl 1367.94309
[12] S. Dey, S. Sarkar, Proving the forward bias of salsa, in: Workshop on Coding and Cryptography, 2019. Available at https://www.lebesgue.fr/sites/default/files/proceedings_WCC/WCC_2019_paper_48.pdf.
[13] Dey, S.; Sarkar, S., Settling the mystery of \(Z_r = r\) in RC4, Cryptogr. Commun. (2019) · Zbl 1456.94072
[14] Dey, S.; Sarkar, S., Proving the biases of salsa and chacha in differential attack, Des. Codes Cryptogr. (2020), Available at https://doi.org/10.1007/s10623-020-00736-9 · Zbl 1453.94075
[15] Ding, L., Improved related-cipher attack on salsa20 stream cipher, IEEE Access, 7, 30197-30202 (2019)
[16] Fischer, S.; Meier, W.; Berbain, C.; Biasse, J. F., Non-randomness in eSTREAM candidates salsa20 and TSC-4, (Indocrypt 2006. Indocrypt 2006, LNCS, vol. 4329 (2006)), 2-16 · Zbl 1175.94077
[17] Isobe, T.; Ohigashi, T.; Watanabe, Y.; Morii, M., Full plaintext recovery attack on broadcast RC4, (FSE. FSE, LNCS, vol. 8424 (2013)), 179-202 · Zbl 1321.94064
[18] Langley, A.; Chang, W.; Mavrogiannopoulos, N.; Strombergson, J.; Josefsson, S., Chacha20-poly1305 cipher suites for transport layer security (TLS), Internet Draft (2015)
[19] Maitra, S., Chosen IV cryptanalysis on reduced round chacha and salsa, Discrete Appl. Math., 208, 88-97 (2016) · Zbl 1342.94082
[20] Maitra, S.; Paul, G.; Meier, W., Salsa20 Cryptanalysis: New Moves and Revisiting Old Styles (2015), WCC, Available at http://eprint.iacr.org/2015/217
[21] Sengupta, S.; Maitra, S.; Meier, W.; Paul, G.; Sarkar, S., Dependence in IV-related bytes of RC4 key enhances vulnerabilities in WPA, (FSE. FSE, LNCS, vol. 8540 (2014)), 350-369, Available at: https://eprint.iacr.org/2013/476.pdf · Zbl 1382.94117
[22] Sengupta, S.; Maitra, S.; Paul, G.; Sarkar, S., (Non-)random sequences from (non-)random permutations - analysis of RC4 stream cipher, J. Cryptol., 27, 1, 67-108 (2014), Available at http://eprint.iacr.org/2011/448 · Zbl 1350.94049
[23] Shi, Z.; Zhang, B.; Feng, D.; Wu, W., Improved key recovery attacks on reduced-round salsa20 and chacha, (ICISC. ICISC, LNCS, vol. 7839 (2012)), 337-351 · Zbl 1342.94096
[24] Tsunoo, Y.; Saito, T.; Kubo, H.; Suzaki, T.; Nakashima, H., Differential cryptanalysis of salsa20/8, (SASC (2007)), http://www.ecrypt.eu.org/stream/papersdir/2007/010.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.