On Improved Cryptanalytic Results Against ChaCha for Reduced Rounds $\ge 7$

Nitin Kumar Sharma, Sabyasachi Dey, Santanu Sarkar, Subhamoy Maitra

TL;DR

This paper presents improved cryptanalytic attacks against reduced-round versions of the ChaCha stream cipher, achieving significant reductions in time complexity for 7, 7.25, and 7.5 rounds. The work refines existing techniques and introduces novel approaches to identify "Probabilistic Neutral Bits," leading to the most efficient known attacks against these reduced versions, while maintaining the security claims for the full 20-round cipher.

What Problem Does This Paper Address?

The ChaCha stream cipher, widely used in protocols like TLS and SSH, is known for its efficiency and security. However, like any cryptographic primitive, it's subject to cryptanalytic scrutiny. Researchers continuously seek to find weaknesses in reduced-round versions of ciphers to understand their security margins and potentially discover vulnerabilities in the full cipher. Previous attacks on ChaCha, particularly those using differential-linear cryptanalysis, have focused on identifying "Probabilistic Neutral Bits" (PNBs) to reduce the search space for key recovery. This paper addresses the challenge of optimizing these attacks by refining the methods for identifying PNBs and improving the complexity calculations, aiming to achieve better time and data complexity than previously reported for 7, 7.25, and 7.5 rounds.

Methods

The core of this research lies in enhancing differential-linear cryptanalysis techniques. The authors build upon existing methods, notably the "differential-linear hull" technique and the concept of "Probabilistic Neutral Bits" (PNBs).

  • Improved PNB Identification: The paper introduces a novel, iterative algorithm for identifying PNBs. This algorithm uses conditional probability and a two-stage process (pre-processing and post-processing) to construct more effective PNB sets. This is a key contribution, as a better PNB set directly translates to a smaller search space and thus lower complexity.
  • Revised Complexity Calculation: The authors revisit and refine the formula for calculating attack complexity, particularly addressing a potential oversimplification in previous work ([Dey24]). This leads to more accurate estimations of time and data requirements.
  • Leveraging Existing Techniques: The work incorporates and adapts techniques from recent research ([Dey24], [XXTQ24]) that improved the correlation value of differential-linear distinguishers and introduced new PNB finding strategies.

Datasets

Not discussed in the paper. The analysis is theoretical and relies on the structure of the ChaCha cipher itself, not external datasets.

Key Insights and Ideas

  • The Power of Refined PNBs: The most significant insight is that a more sophisticated approach to identifying PNBs can dramatically improve cryptanalytic efficiency. By carefully selecting these "neutral" bits, the search space for attackers is significantly reduced.
  • Iterative Improvement: The paper demonstrates that an iterative, probabilistic approach to PNB selection, combined with post-processing, yields better results than simpler greedy methods.
  • Complexity Formula Matters: Accurately calculating attack complexity is crucial. The authors highlight how subtle changes in the formula, based on a deeper understanding of the cipher's operations, can lead to more realistic and improved complexity estimates.
  • Synergy of Techniques: The research shows the benefit of combining different cryptanalytic tools and insights from multiple research papers to achieve state-of-the-art results.

Key Results

The paper presents improved cryptanalytic results for reduced-round ChaCha:

  • 7-round ChaCha: The authors achieve a time complexity of $2^{178.12}$ and data complexity of $2^{101.09}$, improving upon previous best-known results.
  • 7.25-round ChaCha: An improved result with time complexity $2^{212.43}$ and data complexity $2^{100.56}$ is reported, outperforming prior work.
  • 7.5-round ChaCha: The paper presents improved time and data complexities of $2^{253.23}$ and $2^{34.47}$ respectively, building on existing attacks.
  • Order of Magnitude Improvement: For 7 and 7.25 rounds, the improvements represent an order of magnitude reduction in time complexity.
  • Rebuttal of Prior Work: The paper also includes a discussion and rebuttal of claims made by Wang et al. regarding errors in previous ChaCha cryptanalysis.

Limitations and Future Work

  • Reduced Rounds: The attacks presented are against reduced-round versions of ChaCha. The authors explicitly state that these results do not affect the security claims of the complete 20-round algorithm.
  • Experimental Validation: While the paper presents theoretical improvements and complexity calculations, further experimental validation on a toy version of ChaCha is suggested to explore more effective techniques and refine the probability of non-detection error ($Pr_{nd}$).
  • Further Refinements: The authors indicate that there is potential for further improvements, particularly in determining the optimal $Pr_{nd}$ value and exploring new techniques to enhance the overall feasibility of these attacks.

Summary updated

BibTeX
@article{sharma2025improved,
  author = {Nitin Kumar Sharma and Sabyasachi Dey and Santanu Sarkar and Subhamoy Maitra},
  title = {{On Improved Cryptanalytic Results Against ChaCha for Reduced Rounds $\textbackslash\{\}ge 7$}},
  journal = {IACR ePrint},
  year = {2025},
}

Loading related content...

Figure