International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha

Authors:
Sabyasachi Dey , Birla Institute of Technology and Science Pilani
Hirendra Kumar Garai , Birla Institute of Technology and Science Pilani
Santanu Sarkar , Indian Institute of Technology Madras
Nitin Kumar Sharma , Birla Institute of Technology and Science Pilani
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
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}.$
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31955,
  title={Revamped Differential-Linear Cryptanalysis on Reduced Round ChaCha},
  publisher={Springer-Verlag},
  author={Sabyasachi Dey and Hirendra Kumar Garai and Santanu Sarkar and Nitin Kumar Sharma},
  year=2022
}