Character sums over a non-chain ring and their applications
AMC Home
On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators
doi: 10.3934/amc.2021057
Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.
Readers can access Online First articles via the "Online First" tab for the selected journal.
Rotational analysis of ChaCha permutation
Stefano Barbero 1, , Emanuele Bellini 2,, and Rusydi H. Makarim 2,
Department of Mathematics, Politecnico di Torino, Torino, Italy
Cryptography Research Centre, Technology Innovation Institute, Abu Dhabi, UAE
* Corresponding author: Emanuele Bellini
Received March 2021 Revised July 2021 Early access December 2021
We show that the underlying permutation of ChaCha20 stream cipher does not behave as a random permutation for up to 17 rounds with respect to rotational cryptanalysis. In particular, we derive a lower and an upper bound for the rotational probability through ChaCha quarter round, we show how to extend the bound to a full round and then to the full permutation. The obtained bounds show that the probability to find what we call a parallel rotational collision is, for example, less than $ 2^{-505} $ for 17 rounds of ChaCha permutation, while for a random permutation of the same input size, this probability is $ 2^{-511} $. We remark that our distinguisher is not an attack against the ChaCha20 stream cipher, but rather a theoretical analysis of its internal permutation from the point of view of rotational cryptanalysis. Whenever possible, our claims are supported by experiments.
Keywords: ChaCha20, Stream Cipher, Rotational cryptanalysis, Permutation, Distinguisher.
Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 68R05.
Citation: Stefano Barbero, Emanuele Bellini, Rusydi H. Makarim. Rotational analysis of ChaCha permutation. Advances in Mathematics of Communications, doi: 10.3934/amc.2021057
J.-P. Aumasson, S. Neves, Z. Wilcox-O'Hearn and C. Winnerlein, BLAKE2: Simpler, smaller, fast as MD5, International Conference on Applied Cryptography and Network Security, 7954 (2013), 119-135. doi: 10.1007/978-3-642-38980-1_8. Google Scholar
D. Bernstein, Salsa20 Security, Technical report, eSTREAM Project, 2005, Available at: http://cr.yp.to/snuffle/security. pdf. Google Scholar
D. J. Bernstein, Salsa20 Specification, Technical report, eSTREAM Project, https://www.ecrypt.eu.org/stream/, 2005, Available at: http://www.ecrypt.eu.org/stream/salsa20pf.html. Google Scholar
D. J. Bernstein, Salsa20 Specification, eSTREAM Project algorithm description, http://www.ecrypt.eu.org/stream/salsa20pf.html. Google Scholar
D. J. Bernstein, What output size resists collisions in a xor of independent expansions?, ECRYPT Workshop on Hash Functions, (2007), Available at https://cr.yp.to/rumba20/expandxor-20070503.pdf. Google Scholar
D. J. Bernstein, ChaCha, a variant of Salsa20, Workshop Record of SASC, 8 (2008), 3-5. Google Scholar
D. J. Bernstein, Response to "On the Salsa20 core function", 2008, Available at: https://cr.yp.to/snuffle/reoncore-20080224.pdf. Google Scholar
D. J. Bernstein, The salsa20 family of stream ciphers, New Stream Cipher Designs, 4986 (2008), 84-97. doi: 10.1007/978-3-540-68351-3_8. Google Scholar
D. J. Bernstein, The Salsa20 core, Available at: http://cr.yp.to/salsa20.html. Google Scholar
D. J. Bernstein, D. Hopwood, A. Hülsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe and Z. Wilcox-O'Hearn, SPHINCS: Practical stateless hash-based signatures, Advances in cryptology–EUROCRYPT, 9056 (2015), 368-397. doi: 10.1007/978-3-662-46800-5_15. Google Scholar
C. A. Charalambides, Enumerative Combinatorics, CRC Press Series on Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2002. Google Scholar
N. T. Courtois and J.-J. Quisquater, Can a differential attack work for an arbitrarily large number of rounds?, Information Security and Cryptology–ICISC, 12593 (2020), 157-181. doi: 10.1007/978-3-030-68890-5_9. Google Scholar
M. Daum, Cryptanalysis of Hash Functions of the MD4-Family, PhD thesis, Ruhr University Bochum, 2005, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.7847&rep=rep1&type=pdf. Google Scholar
J. C. Hernandez-Castro, J. M. Tapiador and J.-J. Quisquater, On the salsa20 core function, International Workshop on Fast Software Encryption, (2008), 462–469. Google Scholar
D. Khovratovich, I. Nikolić, J. Pieprzyk, P. Sokolowski and R. Steinfeld, Rotational cryptanalysis of ARX revisited, Fast Software Encryption, 9054 (2015), 519-536. doi: 10.1007/978-3-662-48116-5_25. Google Scholar
X. Lai, J. L. Massey and S. Murphy, Markov ciphers and differential cryptanalysis, Advances in Cryptology–EUROCRYPT'91, 547 (1991), 17-38. doi: 10.1007/3-540-46416-6_2. Google Scholar
Y. Nir and A. Langley, Chacha20 and poly1305 for IETF protocols, RFC, 8439 (2018), 1-46. doi: 10.17487/RFC8439. Google Scholar
Various, Google groups: Sci.crypt/re-rolled salsa20 function, 2005, Newsgroup on September 26th (2005), Available at: https://groups.google.com/forum/#!msg/sci.crypt/AkQnSoO40BA/o4eG96rjkgYJ. Google Scholar
Figure 1. The ChaCha quarter round
Table 1. Experimental results on a toy version of ChaCha quarter round
$ \mathsf{w}=4, (r_1, r_2, r_3, r_4) = (1,3,2,1) $
$ \mathsf{r} $ #collisions Lower Bound $ \mathfrak{p} $ Upper Bound $ p $
1 635 $ 0.00879 \sim 2^{-6.83} $ 0.00968 $ 0.01043 \sim 2^{-6.58} $ $ 2^{-16.00} $
$ \mathsf{w} = 5, (r_1, r_2, r_3, r_4) = (4,3,2,1) $
1 6981 $ 0.00630 \sim 2^{-7.31} $ 0.00666 $ 0.00791 \sim 2^{-6.98} $ $ 2^{-20.00} $
1 91677 $ 0.00528 \sim 2^{-7.57} $ 0.00546 $ 0.00683 \sim 2^{-7.19} $ $ 2^{-24.00} $
Table 2. Bounds propagation through ChaCha rounds with $ \mathsf{w} = 32 $, $ \mathsf{n} = 4 $, and $ \mathsf{r} = 1 $
Round Lower Bound $ \mathsf{L}^{ \mathsf{n} i} $ Upper Bound $ \mathsf{U}^{ \mathsf{n} i} $ Round Lower Bound $ \mathsf{L}^{ \mathsf{n} i} $ Upper Bound $ \mathsf{U}^{ \mathsf{n} i} $
1 $ \sim 2^{-31.32} $ $ \sim 2^{-29.66} $ 11 $ \sim 2^{-344.52} $ $ \sim 2^{-326.26} $
4 $ \sim 2^{-125.28} $ $ \sim 2^{-118.64} $ 14 $ \sim 2^{-438.48} $ $ \sim 2^{-415.24} $
10 $ \sim 2^{-313.20} $ $ \sim 2^{-296.60} $ 20 $ \sim 2^{-626.41} $ $ \sim 2^{-593.20} $
Nishant Sinha. Internal state recovery of Espresso stream cipher using conditional sampling resistance and TMDTO attack. Advances in Mathematics of Communications, 2021, 15 (3) : 539-556. doi: 10.3934/amc.2020081
Piotr Jaworski, Marcin Pitera. The 20-60-20 rule. Discrete & Continuous Dynamical Systems - B, 2016, 21 (4) : 1149-1166. doi: 10.3934/dcdsb.2016.21.1149
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
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
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
Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
Carlo Cercignani. The Boltzmann equation in the 20th century. Discrete & Continuous Dynamical Systems, 2009, 24 (1) : 83-94. doi: 10.3934/dcds.2009.24.83
Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
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
Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899
Peter E. Kloeden, Yuan Lou. Preface for the special issue "20 years of DCDS-B". Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : i-ii. doi: 10.3934/dcdsb.2020372
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
Hung-Chu Hsu. Recovering surface profiles of solitary waves on a uniform stream from pressure measurements. Discrete & Continuous Dynamical Systems, 2014, 34 (8) : 3035-3043. doi: 10.3934/dcds.2014.34.3035
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
Giuseppe Alì, John K. Hunter. Orientation waves in a director field with rotational inertia. Kinetic & Related Models, 2009, 2 (1) : 1-37. doi: 10.3934/krm.2009.2.1
Mayee Chen, Junping Shi. Effect of rotational grazing on plant and animal production. Mathematical Biosciences & Engineering, 2018, 15 (2) : 393-406. doi: 10.3934/mbe.2018017
Nian Li, Qiaoyu Hu. A conjecture on permutation trinomials over finite fields of characteristic two. Advances in Mathematics of Communications, 2019, 13 (3) : 505-512. doi: 10.3934/amc.2019031
Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253
Ricardo P. Beausoleil, Rodolfo A. Montejo. A study with neighborhood searches to deal with multiobjective unconstrained permutation problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 193-216. doi: 10.3934/jimo.2009.5.193
Amin Sakzad, Mohammad-Reza Sadeghi, Daniel Panario. Cycle structure of permutation functions over finite fields and their applications. Advances in Mathematics of Communications, 2012, 6 (3) : 347-361. doi: 10.3934/amc.2012.6.347
HTML views (57)
Stefano Barbero Emanuele Bellini Rusydi H. Makarim