Chasing Shadows: Advancements in Differential-Linear Cryptanalysis for ChaCha

The ChaCha cipher holds significance due to its widespread use in real-world applications, which is crucial in ensuring secure communication protocols such as TLS and SSH. The cryptanalysis of ChaCha involves a differential-linear attack which exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, researchers predominantly focused on incorporating single-bit differences at the beginning of differential-linear distinguishers for devising key-recovery attacks on ChaCha. Notably, at ToSC 2023, Bellini <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. introduced an innovative approach: a differential-linear distinguisher spanning five rounds, which takes into account 2-bit differences at the beginning. The aforementioned 5-round distinguisher integrated with the PNB framework, resulting in an enhanced key recovery attack specifically tailored for a 7-round ChaCha cipher. In this paper, first, we revisit the work of Bellini <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>. and show that their 7-round key recovery attacks on ChaCha are impractical due to insufficient data. Furthermore, upon a thorough reassessment of the syncopation technique outlined in Wang <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">et al</i>.’s paper, we observe that introducing specific conditions in the computation of backward bias amplifies the data complexity. In response to this hurdle, we introduce a novel technique to effectively leverage rejected data in the backward bias calculation with conditions. Subsequently, we formulate an adjusted data complexity formula incorporating all backward biases for the PNB-based attack approach. Second, we present a strategic data reduction technique to reduce the total data required for backward computation in each guess of non- PNB bits, consequently yielding a notable improvement in time complexity analysis. For the first time since 2008, our analysis reveals an important advancement in backward computation, reducing the number of non-PNB bit guesses and decreasing the amount of data required for each non-PNB bit guess during backward computation. These enhancements significantly elevate the effectiveness of PNB-based key recovery attacks. Finally, utilizing the aforementioned ideas, we propose an enhanced framework for a key recovery attack, specifically formalized for round-reduced ChaCha. Using novel techniques, our approach successfully breaks seven rounds of ChaCha, achieving a data complexity of 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">101.15</sup> and a time complexity of 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">192.15</sup>. Along with that, we have successfully presented our improved key recovery attack on ChaCha7.5<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">⊕</sup> (7.5 rounds of ChaCha without the last xor and left rotation) with data and time complexity as 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">101.14</sup>, and 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">230.58</sup>, respectively.