×

Proving the biases of Salsa and ChaCha in differential attack. (English) Zbl 1453.94075

Summary: Salsa and ChaCha are two of the most famous stream ciphers in recent times. Most of the attacks available so far against these two ciphers are differential attacks, where a difference is given as an input in the initial state of the cipher and in the output some correlation is investigated. This correlation works as a distinguisher. All the key recovery attacks against these ciphers are based on these observed distinguishers. However, the distinguisher in the differential attack was purely an experimental observation, and the reason for this bias was unknown so far. In this paper, we provide a full theoretical proof of both the observed distinguishers for Salsa and ChaCha. In the key recovery attack, the idea of probabilistically neutral bit also plays a vital role. Here, we also theoretically explain the reason of a particular key bit of Salsa to be probabilistically neutral. This is the first attempt to provide a theoretical justification of the idea of differential key recovery attack against these two ciphers.

MSC:

94A60 Cryptography

Software:

Rumba20; ChaCha
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aumasson J.P., Fischer S., Khazaei S., Meier W., Rechberger C.: New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba. FSE 2008, LNCS 5086, pp. 470-488 (2008). · Zbl 1154.68378
[2] Bernstein D.J.: Salsa20 specification. eSTREAM Project algorithm description (2005). http://www.ecrypt.eu.org/stream/salsa20pf.html.
[3] Bursztein E.: Speeding up and strengthening HTTPS connections for Chrome on Android (2014). https://security.googleblog.com/2014/04/speeding-up-and-strengthening-https.html.
[4] 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). http://eprint.iacr.org/2016/1034.
[5] Crowley P.: Truncated differential cryptanalysis of five rounds of Salsa20. IACR 2005. http://eprint.iacr.org/2005/375.
[6] Deepthi K., Singh K.: Cryptanalysis of Salsa and ChaCha: revisited. In: International Conference on Mobile Networks and Management (2018).
[7] Dey, S.; Sarkar, S., Improved analysis for reduced round Salsa and ChaCha, Discret. Appl. Math., 227, 2017, 58-69 (2017) · Zbl 1367.94309 · doi:10.1016/j.dam.2017.04.034
[8] Dey, S.; Sarkar, S., Settling the mystery of \(Z_r=r\) in RC4., Cryptogr. Commun., 11, 4, 697-715 (2019) · Zbl 1456.94072 · doi:10.1007/s12095-018-0323-4
[9] Dey S., Sarkar S.: Proving the forward bias of Salsa. In: Workshop on Coding and Cryptography (2019). https://www.lebesgue.fr/sites/default/files/proceedings_WCC/WCC_2019_paper_48.pdf.
[10] Dey, S.; Roy, T.; Sarkar, S., Revisiting the design principles of Salsa and ChaCha, Adv. Math. Commun., 13, 3, 689-704 (2019) · Zbl 1419.94035 · doi:10.3934/amc.2019041
[11] Ding, L., Improved related-cipher attack on Salsa20 Stream Cipher, IEEE Access, 7, 30197-30202 (2019) · doi:10.1109/ACCESS.2019.2892647
[12] Fischer S., Meier W., Berbain C., Biasse J.F.: Non-randomness in eSTREAM Candidates Salsa20 and TSC-4. In: Indocrypt 2006, LNCS 4329, pp. 2-16 (2006). · Zbl 1175.94077
[13] Isobe T., Ohigashi T., Watanabe Y., Morii M.: Full plaintext recovery attack on broadcast RC4. In: FSE 2013, LNCS 8424, pp. 179-202 (2013). · Zbl 1321.94064
[14] Maitra, S., Chosen IV cryptanalysis on Reduced Round ChaCha and Salsa, Discret. Appl. Math., 208, 88-97 (2016) · Zbl 1342.94082 · doi:10.1016/j.dam.2016.02.020
[15] Maitra S., Paul G., Meier W.: Salsa20 Cryptanalysis: New Moves and Revisiting Old Styles. WCC (2015). http://eprint.iacr.org/2015/217.
[16] Mantin I., Shamir A.: A practical attack on broadcast RC4. In: FSE, LNCS 2355, pp. 152-164 (2001). · Zbl 1073.68637
[17] Neves, S.; Araujo, F., An observation on NORX, BLAKE2, and ChaCha, Inf. Process. Lett. (2019) · Zbl 1458.94273 · doi:10.1016/j.ipl.2019.05.001
[18] 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). http://eprint.iacr.org/2011/448. · Zbl 1350.94049
[19] Shi Z., Zhang B., Feng D., Wu W.: Improved key recovery attacks on Reduced-Round Salsa20 and ChaCha. In: ICISC, LNCS 7839, pp. 337-351 (2012). · Zbl 1342.94096
[20] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.