• Previous Article
    Character sums over a non-chain ring and their applications
  • AMC Home
  • This Issue
  • Next Article
    New type I binary $[72, 36, 12]$ self-dual codes from $M_6(\mathbb{F}_2)G$ - Group matrix rings by a hybrid search technique based on a neighbourhood-virus optimisation algorithm
doi: 10.3934/amc.2021057
Online First

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

1. 

Department of Mathematics, Politecnico di Torino, Torino, Italy

2. 

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.

Citation: Stefano Barbero, Emanuele Bellini, Rusydi H. Makarim. Rotational analysis of ChaCha permutation. Advances in Mathematics of Communications, doi: 10.3934/amc.2021057
References:
[1]

J.-P. AumassonS. NevesZ. 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.

[2]

D. Bernstein, Salsa20 Security, Technical report, eSTREAM Project, 2005, Available at: http://cr.yp.to/snuffle/security. pdf.

[3]

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.

[4]

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

[5]

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.

[6]

D. J. Bernstein, ChaCha, a variant of Salsa20, Workshop Record of SASC, 8 (2008), 3-5. 

[7]

D. J. Bernstein, Response to "On the Salsa20 core function", 2008, Available at: https://cr.yp.to/snuffle/reoncore-20080224.pdf.

[8]

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.

[9]

D. J. Bernstein, The Salsa20 core, Available at: http://cr.yp.to/salsa20.html.

[10]

D. J. BernsteinD. HopwoodA. HülsingT. LangeR. NiederhagenL. PapachristodoulouM. SchneiderP. 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.

[11]

C. A. Charalambides, Enumerative Combinatorics, CRC Press Series on Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2002.

[12]

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.

[13]

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.

[14]

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.

[15]

D. KhovratovichI. NikolićJ. PieprzykP. 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.

[16]

X. LaiJ. 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.

[17]

Y. Nir and A. Langley, Chacha20 and poly1305 for IETF protocols, RFC, 8439 (2018), 1-46.  doi: 10.17487/RFC8439.

[18]

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.

show all references

References:
[1]

J.-P. AumassonS. NevesZ. 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.

[2]

D. Bernstein, Salsa20 Security, Technical report, eSTREAM Project, 2005, Available at: http://cr.yp.to/snuffle/security. pdf.

[3]

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.

[4]

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

[5]

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.

[6]

D. J. Bernstein, ChaCha, a variant of Salsa20, Workshop Record of SASC, 8 (2008), 3-5. 

[7]

D. J. Bernstein, Response to "On the Salsa20 core function", 2008, Available at: https://cr.yp.to/snuffle/reoncore-20080224.pdf.

[8]

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.

[9]

D. J. Bernstein, The Salsa20 core, Available at: http://cr.yp.to/salsa20.html.

[10]

D. J. BernsteinD. HopwoodA. HülsingT. LangeR. NiederhagenL. PapachristodoulouM. SchneiderP. 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.

[11]

C. A. Charalambides, Enumerative Combinatorics, CRC Press Series on Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton, FL, 2002.

[12]

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.

[13]

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.

[14]

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.

[15]

D. KhovratovichI. NikolićJ. PieprzykP. 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.

[16]

X. LaiJ. 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.

[17]

Y. Nir and A. Langley, Chacha20 and poly1305 for IETF protocols, RFC, 8439 (2018), 1-46.  doi: 10.17487/RFC8439.

[18]

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.

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} $
2 446 $ 0.00582 \sim 2^{-7.42} $ 0.00680 $ 0.00745 \sim 2^{-7.07} $ $ 2^{-16.00} $
$ \mathsf{w} = 5, (r_1, r_2, r_3, r_4) = (4,3,2,1) $
$ \mathsf{r} $ #collisions Lower Bound $ \mathfrak{p} $ Upper Bound $ p $
1 6981 $ 0.00630 \sim 2^{-7.31} $ 0.00666 $ 0.00791 \sim 2^{-6.98} $ $ 2^{-20.00} $
2 4044 $ 0.00318 \sim 2^{-8.30} $ 0.00386 $ 0.00453 \sim 2^{-7.79} $ $ 2^{-20.00} $
$ \mathsf{w}=6, (r_1, r_2, r_3, r_4) = (5,3,2,1) $
$ \mathsf{r} $ #collisions Lower Bound $ \mathfrak{p} $ Upper Bound $ p $
1 91677 $ 0.00528 \sim 2^{-7.57} $ 0.00546 $ 0.00683 \sim 2^{-7.19} $ $ 2^{-24.00} $
2 46030 $ 0.00228 \sim 2^{-8.78} $ 0.00274 $ 0.00343 \sim 2^{-8.19} $ $ 2^{-24.00} $
3 38561 $ 0.00174 \sim 2^{-9.17} $ 0.00230 $ 0.00275 \sim 2^{-8.51} $ $ 2^{-24.00} $
$ \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} $
2 446 $ 0.00582 \sim 2^{-7.42} $ 0.00680 $ 0.00745 \sim 2^{-7.07} $ $ 2^{-16.00} $
$ \mathsf{w} = 5, (r_1, r_2, r_3, r_4) = (4,3,2,1) $
$ \mathsf{r} $ #collisions Lower Bound $ \mathfrak{p} $ Upper Bound $ p $
1 6981 $ 0.00630 \sim 2^{-7.31} $ 0.00666 $ 0.00791 \sim 2^{-6.98} $ $ 2^{-20.00} $
2 4044 $ 0.00318 \sim 2^{-8.30} $ 0.00386 $ 0.00453 \sim 2^{-7.79} $ $ 2^{-20.00} $
$ \mathsf{w}=6, (r_1, r_2, r_3, r_4) = (5,3,2,1) $
$ \mathsf{r} $ #collisions Lower Bound $ \mathfrak{p} $ Upper Bound $ p $
1 91677 $ 0.00528 \sim 2^{-7.57} $ 0.00546 $ 0.00683 \sim 2^{-7.19} $ $ 2^{-24.00} $
2 46030 $ 0.00228 \sim 2^{-8.78} $ 0.00274 $ 0.00343 \sim 2^{-8.19} $ $ 2^{-24.00} $
3 38561 $ 0.00174 \sim 2^{-9.17} $ 0.00230 $ 0.00275 \sim 2^{-8.51} $ $ 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} $
2 $ \sim 2^{-62.64} $ $ \sim 2^{-59.32} $ 12 $ \sim 2^{-375.84} $ $ \sim 2^{-355.92} $
3 $ \sim 2^{-93.96} $ $ \sim 2^{-88.68} $ 13 $ \sim 2^{-407.16} $ $ \sim 2^{-385.58} $
4 $ \sim 2^{-125.28} $ $ \sim 2^{-118.64} $ 14 $ \sim 2^{-438.48} $ $ \sim 2^{-415.24} $
5 $ \sim 2^{-156.60} $ $ \sim 2^{-148.30} $ 15 $ \sim 2^{-469.80} $ $ \sim 2^{-444.90} $
6 $ \sim 2^{-187.92} $ $ \sim 2^{-177.96} $ 16 $ \sim 2^{-501.12} $ $ \sim 2^{-474.56} $
7 $ \sim 2^{-219.24} $ $ \sim 2^{-207.62} $ 17 $ \sim 2^{-532.45} $ $ \sim 2^{-504.22} $
8 $ \sim 2^{-250.56} $ $ \sim 2^{-237.28} $ 18 $ \sim 2^{-563.77} $ $ \sim 2^{-533.88} $
9 $ \sim 2^{-281.88} $ $ \sim 2^{-266.94} $ 19 $ \sim 2^{-595.09} $ $ \sim 2^{-563.54} $
10 $ \sim 2^{-313.20} $ $ \sim 2^{-296.60} $ 20 $ \sim 2^{-626.41} $ $ \sim 2^{-593.20} $
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} $
2 $ \sim 2^{-62.64} $ $ \sim 2^{-59.32} $ 12 $ \sim 2^{-375.84} $ $ \sim 2^{-355.92} $
3 $ \sim 2^{-93.96} $ $ \sim 2^{-88.68} $ 13 $ \sim 2^{-407.16} $ $ \sim 2^{-385.58} $
4 $ \sim 2^{-125.28} $ $ \sim 2^{-118.64} $ 14 $ \sim 2^{-438.48} $ $ \sim 2^{-415.24} $
5 $ \sim 2^{-156.60} $ $ \sim 2^{-148.30} $ 15 $ \sim 2^{-469.80} $ $ \sim 2^{-444.90} $
6 $ \sim 2^{-187.92} $ $ \sim 2^{-177.96} $ 16 $ \sim 2^{-501.12} $ $ \sim 2^{-474.56} $
7 $ \sim 2^{-219.24} $ $ \sim 2^{-207.62} $ 17 $ \sim 2^{-532.45} $ $ \sim 2^{-504.22} $
8 $ \sim 2^{-250.56} $ $ \sim 2^{-237.28} $ 18 $ \sim 2^{-563.77} $ $ \sim 2^{-533.88} $
9 $ \sim 2^{-281.88} $ $ \sim 2^{-266.94} $ 19 $ \sim 2^{-595.09} $ $ \sim 2^{-563.54} $
10 $ \sim 2^{-313.20} $ $ \sim 2^{-296.60} $ 20 $ \sim 2^{-626.41} $ $ \sim 2^{-593.20} $
[1]

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

[2]

Piotr Jaworski, Marcin Pitera. The 20-60-20 rule. Discrete and Continuous Dynamical Systems - B, 2016, 21 (4) : 1149-1166. doi: 10.3934/dcdsb.2016.21.1149

[3]

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

[4]

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

[5]

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

[6]

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

[7]

Carlo Cercignani. The Boltzmann equation in the 20th century. Discrete and Continuous Dynamical Systems, 2009, 24 (1) : 83-94. doi: 10.3934/dcds.2009.24.83

[8]

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

[9]

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

[10]

Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure and Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899

[11]

Peter E. Kloeden, Yuan Lou. Preface for the special issue "20 years of DCDS-B". Discrete and Continuous Dynamical Systems - B, 2021, 26 (1) : i-ii. doi: 10.3934/dcdsb.2020372

[12]

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

[13]

Hung-Chu Hsu. Recovering surface profiles of solitary waves on a uniform stream from pressure measurements. Discrete and Continuous Dynamical Systems, 2014, 34 (8) : 3035-3043. doi: 10.3934/dcds.2014.34.3035

[14]

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

[15]

Giuseppe Alì, John K. Hunter. Orientation waves in a director field with rotational inertia. Kinetic and Related Models, 2009, 2 (1) : 1-37. doi: 10.3934/krm.2009.2.1

[16]

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

[17]

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

[18]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial and Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[19]

Ricardo P. Beausoleil, Rodolfo A. Montejo. A study with neighborhood searches to deal with multiobjective unconstrained permutation problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 193-216. doi: 10.3934/jimo.2009.5.193

[20]

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

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]