Rotational analysis of ChaCha permutation

Stefano Barbero; Emanuele Bellini; Rusydi H. Makarim

doi:10.3934/amc.2021057

Article Contents

2023, Volume 17, Issue 6: 1422-1439. Doi: 10.3934/amc.2021057

This issue Previous Article Reversible $ G $-codes over the ring $ {\mathcal{F}}_{j,k} $ with applications to DNA codes Next Article New nonexistence results on perfect permutation codes under the hamming metric

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
^* Corresponding author: Emanuele Bellini

Received: March 2021

Revised: July 2021

Early access: December 6, 2021

Published online: December 6, 2021

Abstract / Introduction Full Text(HTML) Figure(1) / Table(2) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A60, 11T71; Secondary: 68R05.

Citation:

Full Text(HTML)

Figure 1. The ChaCha quarter round

Download: Full-size image PowerPoint slide

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} $

| Show Table

DownLoad: CSV

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} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

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