
-
Previous Article
$\textsf{DWCDM+}$: A BBB secure nonce based MAC
- AMC Home
- This Issue
-
Next Article
Another look at success probability of linear cryptanalysis
Revisiting design principles of Salsa and ChaCha
Department of Mathematics, Indian Institute of Technology Madras, Sardar Patel Road, Chennai 600036, India |
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.
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. |
[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. |
[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. 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. |
[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. |
[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. |
[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. 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. |
[12] |
Y. Tsunoo, T. Saito, H. Kubo, T. Suzaki and H. Nakashima, Differential Cryptanalysis of Salsa20/8, 2007. Google Scholar |



Cipher | Existing complexity | New complexity | |||||
Salsa | 43 | 0.000176 | 16.43 | ||||
ChaCha | 53 | 0.000100 | 24.83 |
Cipher | Existing complexity | New complexity | |||||
Salsa | 43 | 0.000176 | 16.43 | ||||
ChaCha | 53 | 0.000100 | 24.83 |
Cipher | Existing complexity | New complexity |
Salsa | ||
ChaCha |
Cipher | Existing complexity | New complexity |
Salsa | ||
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 |
Percentage of keys | bias (existing) | bias (our) | existing complexity | our complexity |
10 | 0.000200 | 0.000648 | ||
20 | 0.000178 | 0.000433 | ||
30 | 0.000165 | 0.000314 | ||
40 | 0.000152 | 0.000231 | ||
50 | 0.000139 | 0.000182 |
Percentage of keys | bias (existing) | bias (our) | existing complexity | our complexity |
10 | 0.000200 | 0.000648 | ||
20 | 0.000178 | 0.000433 | ||
30 | 0.000165 | 0.000314 | ||
40 | 0.000152 | 0.000231 | ||
50 | 0.000139 | 0.000182 |
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 |
Percentage of keys | bias (existing) | bias (our) | existing complexity | our complexity |
10 | -0.000232 | -0.000667 | ||
20 | -0.000207 | -0.000397 | ||
30 | -0.000192 | -0.000305 | ||
40 | -0.000181 | -0.000226 | ||
50 | -0.000176 | -0.000192 |
Percentage of keys | bias (existing) | bias (our) | existing complexity | our complexity |
10 | -0.000232 | -0.000667 | ||
20 | -0.000207 | -0.000397 | ||
30 | -0.000192 | -0.000305 | ||
40 | -0.000181 | -0.000226 | ||
50 | -0.000176 | -0.000192 |
Percentage of PNB's | Number of |
5% | 70 |
10% | 127 |
15% | 180 |
20% | 219 |
Percentage of PNB's | Number of |
5% | 70 |
10% | 127 |
15% | 180 |
20% | 219 |
[1] |
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 |
[2] |
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 |
[3] |
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 |
[4] |
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 |
[5] |
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 |
[6] |
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 |
[7] |
Anupama N, Sudarson Jena. A novel approach using incremental under sampling for data stream mining. Big Data & Information Analytics, 2017, 2 (5) : 1-13. doi: 10.3934/bdia.2017017 |
[8] |
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 |
[9] |
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 |
[10] |
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 |
[11] |
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 |
[12] |
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 |
[13] |
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 |
[14] |
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 |
[15] |
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 |
[16] |
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 |
[17] |
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 |
[18] |
Boris P. Belinskiy. Optimal design of an optical length of a rod with the given mass. Conference Publications, 2007, 2007 (Special) : 85-91. doi: 10.3934/proc.2007.2007.85 |
[19] |
Xiao Lan Zhu, Zhi Guo Feng, Jian Wen Peng. Robust design of sensor fusion problem in discrete time. Journal of Industrial & Management Optimization, 2017, 13 (2) : 825-834. doi: 10.3934/jimo.2016048 |
[20] |
Michel Pierre, Grégory Vial. Best design for a fastest cells selecting process. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 223-237. doi: 10.3934/dcdss.2011.4.223 |
2018 Impact Factor: 0.879
Tools
Metrics
Other articles
by authors
[Back to Top]