Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha

Sabyasachi Dey; Hirendra Kumar Garai; Santanu Sarkar; Nitin Kumar Sharma

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2022/536

Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha

Sabyasachi Dey, Hirendra Kumar Garai, Santanu Sarkar, and Nitin Kumar Sharma

Abstract

In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has $20$ rounds. At CRYPTO $2020$, Beierle et al. observed a differential in the $3.5$-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need $2^5$ iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a strategical improvement in PNB construction, modification of complexity calculation and an alternative attack method using two input-output pairs. Using these, we improve the time complexity, reducing it to $2^{221.95}$ from $2^{230.86}$ reported by Beierle et al. for $256$ bit version of ChaCha. Also, after a decade, we improve existing complexity (Shi et al: ICISC 2012) for a $6$-round of $128$ bit version of ChaCha by more than 11 million times and produce the first-ever attack on 6.5-round ChaCha$128$ with time complexity $2^{123.04}.$

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in EUROCRYPT 2022
Keywords: Stream cipher ARX ChaCha Probabilistic Neutral Bits (PNBs)Differential attack
Contact author(s): sarkar santanu bir1 @ gmail com
History: 2022-05-10: received
Short URL: https://ia.cr/2022/536
License: CC BY

BibTeX

@misc{cryptoeprint:2022/536,
      author = {Sabyasachi Dey and Hirendra Kumar Garai and Santanu Sarkar and Nitin Kumar Sharma},
      title = {Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha},
      howpublished = {Cryptology ePrint Archive, Paper 2022/536},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/536}},
      url = {https://eprint.iacr.org/2022/536}
}