Article Contents
Article Contents

# Revisiting design principles of Salsa and ChaCha

• Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: forward probability bias ($\epsilon_d$) and backward probability bias ($\epsilon_a$). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version.

Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.

 Citation:

• Figure 1.  Two Normal distribution curves

Figure 2.  Comparison between the probability achieved by random values and our values for ChaCha

Figure 3.  Comparison between the probability achieved by random values and our values for Salsa

Table 1.  New attack complexities for 8 rounds Salsa and 7 rounds ChaCha

 Cipher $n$ $|\epsilon|$ $\alpha$ $T$ $N$ Existing complexity New complexity Salsa 43 0.000176 16.43 $2^{29.66}$ $2^{30.66}$ $2^{243.93}$ $2^{243.74}$ ChaCha 53 0.000100 24.83 $2^{31.72}$ $2^{32.72}$ $2^{235.93}$ $2^{235.78}$

Table 2.  Attack complexities using chaining distinguisher

 Cipher Existing complexity New complexity Salsa $2^{243.67}$ $2^{243.23}$ ChaCha $2^{235.22}$ $2^{234.78}$

Table 3.  Values for Probabilistic Neutral Bits of ChaCha

 3 6 7 15 16 17 18 31 35 38 67 68 1 1 0 1 1 1 0 x 1 0 0 1 71 72 73 91 92 93 94 95 96 97 98 99 1 1 0 x x x x x 1 1 1 1 100 103 104 105 106 107 127 136 137 138 139 156 0 1 1 1 1 0 x 0 0 0 1 x 159 191 223 224 225 226 227 228 248 249 250 251 x x x 1 1 1 1 0 x x x x 252 253 254 255 x x x x

Table 4.  Comparison of bias $\epsilon$ and complexities between existing and our method for ChaCha when $n = 52$

 Percentage of keys bias (existing) bias (our) existing complexity our complexity 10 0.000200 0.000648 $2^{234.97}$ $2^{231.56}$ 20 0.000178 0.000433 $2^{235.28}$ $2^{232.68}$ 30 0.000165 0.000314 $2^{235.50}$ $2^{ 233.57}$ 40 0.000152 0.000231 $2^{235.73}$ $2^{234.43}$ 50 0.000139 0.000182 $2^{235.96}$ $2^{235.09}$

Table 5.  Values for the probabilistic neutral bits of Salsa

 25 26 27 28 29 30 31 39 70 71 72 107 x x x x x x x x 1 1 0 1 119 120 121 122 164 165 166 167 168 169 170 171 1 1 1 0 0 1 1 1 1 0 0 0 172 173 174 175 176 209 210 211 212 213 224 225 0 0 0 0 1 1 1 1 1 0 0 1 241 242 243 244 245 246 255 1 1 1 1 1 0 x

Table 6.  Comparison of bias and complexities between existing and our method for Salsa when $n = 43$

 Percentage of keys bias (existing) bias (our) existing complexity our complexity 10 -0.000232 -0.000667 $2^{243.18}$ $2^{240.11}$ 20 -0.000207 -0.000397 $2^{243.48}$ $2^{241.53}$ 30 -0.000192 -0.000305 $2^{243.69}$ $2^{242.24}$ 40 -0.000181 -0.000226 $2^{ 243.86}$ $2^{243.06}$ 50 -0.000176 -0.000192 $2^{243.93}$ $2^{243.51}$

Table 7.  Number of $Random$ $Value$ $Positions$ for some size of PNB

 Percentage of PNB's Number of $Random$ $Value$ $Positions$ 5% 70 10% 127 15% 180 20% 219
•  [1] J. P. Aumasson, S. Fischer, S. Khazaei, W. Meier and C. Rechberger, New features of latin dances: Analysis of salsa, chacha, and rumba, FSE 2008, LNCS, 5086 (2008), 470-488.  doi: 10.1007/978-3-540-71039-4_30. [2] D. J. Bernstein, Salsa20 specification, eSTREAM Project algorithm description, http://www.ecrypt.eu.org/stream/salsa20pf.html, 2005. [3] D. J. Bernstein, ChaCha, a variant of Salsa20, In Workshop Record of SASC, volume 8, 2008. [4] A. R. Choudhuri and S. Maitra, Significantly Improved Multi-bit Differentials for Reduced Round Salsa and ChaCha, Accepted in FSE 2017, Available at http://eprint.iacr.org/2016/1034. [5] P. Crowley, Truncated differential cryptanalysis of five rounds of Salsa20, IACR 2005. Available at http://eprint.iacr.org/2005/375. [6] S. Dey and S. Sarkar, Improved analysis for reduced round Salsa and ChaCha, Discrete Applied Mathematics, 227 (2017), 58-69.  doi: 10.1016/j.dam.2017.04.034. [7] S. Fischer, W. Meier, C. Berbain and J. F. Biasse, Non-randomness in eSTREAM Candidates Salsa20 and TSC-4, Progress in Cryptology–INDOCRYPT 2006, LNCS, 4329 (2006), 2-16.  doi: 10.1007/11941378_2. [8] S. Maitra, Chosen IV cryptanalysis on reduced round chacha and salsa, Discrete Applied Mathematics, 208 (2016), 88-97.  doi: 10.1016/j.dam.2016.02.020. [9] S. Maitra, G. Paul and W. Meier, Salsa20 Cryptanalysis: New Moves and Revisiting Old Styles, WCC 2015. Available at http://eprint.iacr.org/2015/217. [10] , Sage: Open Source Mathematics Software, http://www.sagemath.org. [11] Z. Shi, B. Zhang, D. Feng and W. Wu, Improved key recovery attacks on reduced-round salsa20 and ChaCha, ICISC 2012, LNCS, 7839 (2012), 337-351.  doi: 10.1007/978-3-642-37682-5_24. [12] Y. Tsunoo, T. Saito, H. Kubo, T. Suzaki and H. Nakashima, Differential Cryptanalysis of Salsa20/8, 2007.

Figures(3)

Tables(7)