American Institute of Mathematical Sciences

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

Revisiting design principles of Salsa and ChaCha

Sabyasachi Dey , Tapabrata Roy and  Santanu Sarkar

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.

Keywords: Stream cipher, ChaCha, cryptanalysis, new design.
Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.
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:
[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.  Google Scholar

[2]

D. J. Bernstein, Salsa20 specification, eSTREAM Project algorithm description, http://www.ecrypt.eu.org/stream/salsa20pf.html, 2005. Google Scholar

[3]

D. J. Bernstein, ChaCha, a variant of Salsa20, In Workshop Record of SASC, volume 8, 2008. Google Scholar

[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. Google Scholar

[5]

P. Crowley, Truncated differential cryptanalysis of five rounds of Salsa20, IACR 2005. Available at http://eprint.iacr.org/2005/375. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[10]

, Sage: Open Source Mathematics Software, http://www.sagemath.org. Google Scholar

[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.  Google Scholar

[12]

Y. Tsunoo, T. Saito, H. Kubo, T. Suzaki and H. Nakashima, Differential Cryptanalysis of Salsa20/8, 2007. Google Scholar

show all references

References:
[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.  Google Scholar

[2]

D. J. Bernstein, Salsa20 specification, eSTREAM Project algorithm description, http://www.ecrypt.eu.org/stream/salsa20pf.html, 2005. Google Scholar

[3]

D. J. Bernstein, ChaCha, a variant of Salsa20, In Workshop Record of SASC, volume 8, 2008. Google Scholar

[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. Google Scholar

[5]

P. Crowley, Truncated differential cryptanalysis of five rounds of Salsa20, IACR 2005. Available at http://eprint.iacr.org/2005/375. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[10]

, Sage: Open Source Mathematics Software, http://www.sagemath.org. Google Scholar

[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.  Google Scholar

[12]

Y. Tsunoo, T. Saito, H. Kubo, T. Suzaki and H. Nakashima, Differential Cryptanalysis of Salsa20/8, 2007. Google Scholar

Figure 1.  Two Normal distribution curves
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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
Table Options

Download as excel

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]

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
[16]

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
[17]

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
[18]

Hai Huyen Dam, Kok Lay Teo. Variable fractional delay filter design with discrete coefficients. Journal of Industrial & Management Optimization, 2016, 12 (3) : 819-831. doi: 10.3934/jimo.2016.12.819
[19]

Magdi S. Mahmoud, Omar Al-Buraiki. Robust control design of autonomous bicycle kinematics. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 181-191. doi: 10.3934/naco.2014.4.181
[20]

K.F.C. Yiu, K.L. Mak, K. L. Teo. Airfoil design via optimal control theory. Journal of Industrial & Management Optimization, 2005, 1 (1) : 133-148. doi: 10.3934/jimo.2005.1.133

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (171)
  • HTML views (556)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences