TL;DR
This paper revisits rotational cryptanalysis, a technique used to attack cryptographic algorithms. The authors demonstrate that a common assumption used to calculate the probability of success for these attacks is flawed, particularly for ARX (Addition-Rotation-XOR) ciphers. They introduce a more accurate method for calculating this probability, leading to tighter bounds on the security of several prominent cryptographic designs.
What Problem Does This Paper Address?
Rotational cryptanalysis is a probabilistic attack that tracks a "rotational pair" of inputs through the rounds of a cipher. For the attack to be effective, the cipher's constants must remain unchanged after rotation. The success probability of such an attack is typically calculated by multiplying the probabilities of individual operations within the cipher. This relies on the "Markov cipher assumption," which states that each round's outcome is independent of previous rounds, allowing for this multiplicative shortcut.
However, this paper questions the validity of this assumption for ARX primitives, especially when modular additions are chained together. The authors argue that chained additions don't behave independently under rotational analysis, meaning the simple product of probabilities is an overestimation. This leads to an inaccurate assessment of a cipher's security against rotational attacks. The problem is to accurately compute the rotational probability of ARX primitives, especially those with chained modular additions, and to re-evaluate the security claims of existing ciphers based on this corrected analysis.
Methods
The core of the paper's contribution lies in challenging the Markov cipher assumption for rotational analysis of ARX primitives. The authors:
- Identify the Flaw: They demonstrate that chained modular additions do not form a Markov chain with respect to rotational differences. This means the probability of a rotational pair propagating through a chain of additions cannot be simply multiplied.
- Derive a New Formula: They derive a precise formula (Lemma 2) for the rotational probability of chained modular additions. This formula accounts for the relative positions of additions within a chain, showing that longer chains significantly reduce the rotational probability.
- Propose a New Algorithm: Based on Lemma 2, they outline a new algorithm for computing the rotational probability of ARX primitives. This algorithm involves identifying "chains" of modular additions and calculating their combined probability, rather than treating each addition independently.
- Analyze Key Incorporation: They also highlight how the way round keys are incorporated (e.g., via modular addition or XOR) can affect the rotational probability by either breaking or maintaining addition chains.
Datasets
Not discussed in the paper. The analysis is theoretical and relies on mathematical derivations and computer simulations for verification.
Key Insights and Ideas
- Chained Additions Break the Markov Assumption: The most significant insight is that chained modular additions in ARX ciphers disrupt the Markov property crucial for simplified rotational probability calculations. This means the probability of a rotational pair propagating through a chain is lower than previously assumed.
- Position Matters: The relative positioning of modular additions is critical. Chained additions significantly decrease rotational probability, while additions separated by rotations are less affected.
- XOR vs. Addition for Key Mixing: The method of incorporating round keys (modular addition vs. XOR) can profoundly impact rotational security. XORing keys can break addition chains, potentially increasing security against rotational attacks, while modularly adding them can maintain chains and lower security.
- Re-evaluation of Existing Attacks: The paper's findings necessitate a re-evaluation of rotational cryptanalysis results on ciphers like BLAKE2 and Skein, potentially weakening previously claimed security bounds.
Key Results
- Corrected BLAKE2 Analysis: The paper corrects the claimed rotational attack complexity against BLAKE2, showing it's applicable to only 7 rounds instead of the previously claimed 12. This is due to the presence of long chains of modular additions within BLAKE2's rounds.
- Skein Analysis: They provide rotational attack bounds for a simplified version of Skein, suggesting attacks are effective for 24-28 rounds (without subkey additions), a tighter bound than previously suggested.
- Lemma 2: This lemma provides a mathematically sound way to calculate the rotational probability of chained modular additions, which is significantly lower than predicted by the older, Markov-based approach (Theorem 2 from [13]). For example, with 25 chained additions and a rotation of 1, the probability is around $2^{-109.6}$ compared to the older estimate of $2^{-35.4}$.
- Experimental Verification: The authors' theoretical findings were validated through computer simulations on various ARX primitives, showing strong agreement between predicted and experimental rotational probabilities.
Limitations and Future Work
- Focus on ARX: The primary focus is on ARX primitives. While the methodology is suggested to be applicable to other primitives, detailed analysis for non-ARX structures is not presented.
- Simplified Skein: The analysis of Skein is for a simplified version (without subkey additions). The full Skein, with its complex key schedule and rotational error correction mechanisms, is not fully analyzed.
- Rotational Error Correction: The paper acknowledges that techniques like "rotational errors and corrections" used in some ciphers (like Skein) complicate the analysis, and their formulas do not directly apply to such scenarios. Future work could explore how these mechanisms interact with chained additions.
- NORX Analysis: While the paper touches upon NORX, a full, detailed analysis of its rotational properties, especially considering its non-linear operations, is deferred to an appendix (not provided in the text).
The paper opens avenues for more accurate security assessments of cryptographic primitives by providing a more robust method for calculating rotational probabilities, particularly for designs employing chained modular additions.
Summary updated