Paper 2023/134

Cryptanalysis of Reduced Round ChaCha- New Attack and Deeper Analysis

Abstract

In this paper we present several analyses on ChaCha, a software stream cipher. First, we consider a divide-and-conquer approach on the secret key bits by partitioning them. The partitions are based on multiple input-output differentials to obtain a significantly improved attack on 6-round ChaCha256 with a complexity of 2^{99.48}. It is 2^{40} times faster than the currently best known attack. Note that, this is the first time an attack could be mounted on reduced round ChaCha with a complexity significantly less than 2^{k}{2}, where the secret key is of $k$ bits. Further, we note that all the attack complexities related to ChaCha are theoretically estimated in general and there are several questions in this regard as pointed out by Dey et al. in Eurocrypt 2022. In this regard, we propose a toy version of ChaCha, with a 32-bit secret key, on which the attacks can be implemented completely to verify whether the theoretical estimates are justified. This idea is implemented for our proposed attack on 6 rounds. Finally, we show that it is possible to estimate the success probabilities of these kinds of PNB-based differential attacks more accurately. Our methodology explains how different cryptanalytic results can be evaluated with better accuracy rather than claiming (Aumasson et al., 2008) that the success probability is significantly better than 50%.