# American Institute of Mathematical Sciences

November  2019, 13(4): 689-704. doi: 10.3934/amc.2019041

## Revisiting design principles of Salsa and ChaCha

 Department of Mathematics, Indian Institute of Technology Madras, Sardar Patel Road, Chennai 600036, India

Received  October 2018 Published  June 2019

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.

Citation: Sabyasachi Dey, Tapabrata Roy, Santanu Sarkar. Revisiting design principles of Salsa and ChaCha. Advances in Mathematics of Communications, 2019, 13 (4) : 689-704. doi: 10.3934/amc.2019041
##### References:

show all references

##### References:
Two Normal distribution curves
Comparison between the probability achieved by random values and our values for ChaCha
Comparison between the probability achieved by random values and our values for Salsa
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}$
 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}$
Attack complexities using chaining distinguisher
 Cipher Existing complexity New complexity Salsa $2^{243.67}$ $2^{243.23}$ ChaCha $2^{235.22}$ $2^{234.78}$
 Cipher Existing complexity New complexity Salsa $2^{243.67}$ $2^{243.23}$ ChaCha $2^{235.22}$ $2^{234.78}$
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
 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
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}$
 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}$
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
 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
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}$
 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}$
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
 Percentage of PNB's Number of $Random$ $Value$ $Positions$ 5% 70 10% 127 15% 180 20% 219
 [1] Nishant Sinha. Internal state recovery of Espresso stream cipher using conditional sampling resistance and TMDTO attack. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020081 [2] Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1 [3] Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247 [4] Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115 [5] Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020182 [6] Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040 [7] Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87 [8] Hung-Chu Hsu. Recovering surface profiles of solitary waves on a uniform stream from pressure measurements. Discrete & Continuous Dynamical Systems - A, 2014, 34 (8) : 3035-3043. doi: 10.3934/dcds.2014.34.3035 [9] Anupama N, Sudarson Jena. A novel approach using incremental under sampling for data stream mining. Big Data & Information Analytics, 2018  doi: 10.3934/bdia.2017017 [10] Bingtuan Li, William F. Fagan, Garrett Otto, Chunwei Wang. Spreading speeds and traveling wave solutions in a competitive reaction-diffusion model for species persistence in a stream. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3267-3281. doi: 10.3934/dcdsb.2014.19.3267 [11] Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163 [12] Claude Carlet, Khoongming Khoo, Chu-Wee Lim, Chuan-Wen Loe. On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity. Advances in Mathematics of Communications, 2008, 2 (2) : 201-221. doi: 10.3934/amc.2008.2.201 [13] Shixiong Wang, Longjiang Qu, Chao Li, Shaojing Fu, Hao Chen. Finding small solutions of the equation $\mathit{{Bx-Ay = z}}$ and its applications to cryptanalysis of the RSA cryptosystem. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020076 [14] Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983 [15] Shuhua Zhang, Zhuo Yang, Song Wang. Design of green bonds by double-barrier options. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1867-1882. doi: 10.3934/dcdss.2020110 [16] Monique Chyba, Thomas Haberkorn, Ryan N. Smith, George Wilkens. A geometric analysis of trajectory design for underwater vehicles. Discrete & Continuous Dynamical Systems - B, 2009, 11 (2) : 233-262. doi: 10.3934/dcdsb.2009.11.233 [17] Magdi S. Mahmoud, Mohammed M. Hussain. Control design of linear systems with saturating actuators: A survey. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 413-435. doi: 10.3934/naco.2012.2.413 [18] Ruwu Xiao, Geng Li, Yuping Zhao. On the design of full duplex wireless system with chaotic sequences. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 783-793. doi: 10.3934/dcdss.2019052 [19] Feimin Zhong, Wei Zeng, Zhongbao Zhou. Mechanism design in a supply chain with ambiguity in private information. Journal of Industrial & Management Optimization, 2020, 16 (1) : 261-287. doi: 10.3934/jimo.2018151 [20] H. T. Banks, R. A. Everett, Neha Murad, R. D. White, J. E. Banks, Bodil N. Cass, Jay A. Rosenheim. Optimal design for dynamical modeling of pest populations. Mathematical Biosciences & Engineering, 2018, 15 (4) : 993-1010. doi: 10.3934/mbe.2018044

2019 Impact Factor: 0.734