Cryptanalysis of Reduced Round ChaCha – New Attack & 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 299.48. It is 240 times faster than the currently best known attack. This is the first time an attack on a round reduced ChaCha with a complexity smaller than 2k/2, where the secret key is of k bits, has been successful. Further, 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, Garai, Sarkar and Sharma 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 that the success probability is significantly better than 50%.

Keywords

• Stream cipher
• ARX
• ChaCha
• Probabilistic Neutral Bits (PNBs)
• Differential attack