# American Institute of Mathematical Sciences

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:

show all references

##### References:
The ChaCha quarter round
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}$
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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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

2020 Impact Factor: 0.935