TL;DR
This paper introduces a novel cryptanalytic technique called "internal differential boomerang distinguishers" to analyze the Keccak-f permutation, a core component of the SHA-3 hash standard. By combining existing differential techniques with a new approach that tracks differences within parts of the state, the authors achieve practical distinguishers for significantly reduced rounds of Keccak-f with remarkably low query complexities, demonstrating a non-random behavior in these weakened versions.
What Problem Does This Paper Address?
The security of cryptographic primitives like hash functions is paramount, especially for those selected for standardization, such as Keccak for SHA-3. While the full Keccak-f permutation is considered secure, understanding the security of its reduced-round versions is crucial for a comprehensive analysis and for identifying potential weaknesses. Previous attacks on reduced-round Keccak-f have achieved certain complexities, but the authors aimed to find more efficient distinguishers, particularly by leveraging the highly symmetric nature of the Keccak-f permutation. They sought to develop a technique that could exploit high-probability internal differential characteristics, which are particularly relevant for such symmetric structures.
Methods
The core contribution of this paper is the introduction of the internal differential boomerang distinguisher. This technique is a hybrid, combining:
- Internal Differentials: Unlike classical differentials that track differences between entire states, internal differentials focus on the evolution of differences within parts of a state. This is particularly effective for highly symmetric functions like Keccak-f.
- Classical Boomerang Attacks: These attacks use a pair of inputs with a specific difference and then manipulate the outputs to find a matching pair of inputs.
The authors' internal differential boomerang distinguisher uses three differentials (two internal, one standard) compared to the four typically used in classical boomerang attacks. A key aspect is the use of a message modification technique. This allows them to deterministically "pass" certain rounds that would otherwise be probabilistic, significantly reducing the overall complexity of finding a distinguishing pair. They also leverage truncated characteristics, where only a subset of the difference bits are fully specified, further enhancing efficiency.
Datasets
Not discussed in the paper. The analysis is performed on the Keccak-f permutation itself, and the "datasets" are essentially the round-reduced versions of this permutation.
Key Insights and Ideas
- Internal Differentials Shine on Symmetric Structures: The paper highlights that internal differentials are particularly well-suited for analyzing highly symmetric cryptographic primitives like Keccak-f, offering a more targeted approach than standard differentials.
- Message Modification is Key to Practicality: The authors demonstrate that a carefully applied message modification technique can dramatically reduce the complexity of boomerang attacks by allowing certain rounds to be bypassed deterministically. This is a crucial element for achieving "practical" distinguishers.
- Reduced Rounds Reveal Non-Randomness: Even for a well-designed permutation like Keccak-f, reducing the number of rounds can expose non-random behaviors that are not apparent in the full version. The authors' distinguishers show that these weakened versions are distinguishable from random permutations with surprisingly low effort.
- Internal Differential Boomerangs Outperform Classical Boomerangs: When high-probability internal differentials exist, the internal differential boomerang technique can be more efficient than classical boomerang attacks.
Key Results
The paper presents practical distinguishers for round-reduced Keccak-f permutations with exceptionally low complexities:
- 6 rounds (starting from round 0): Distinguishable with 2⁵ queries.
- 7 rounds (starting from round 0): Distinguishable with approximately 2¹³ queries.
- 7 rounds (starting from round 3): Distinguishable with approximately 2¹⁰.³ queries.
- 8 rounds (starting from round 3): Distinguishable with approximately 2¹⁸.³ queries.
These complexities are significantly lower than those required for distinguishing a random permutation using similar techniques (e.g., Lemma 1 suggests at least 2⁵⁷.⁵ queries for a random permutation). The authors emphasize that all these results have been verified through computer implementations.
Limitations and Future Work
- Limited to Round-Reduced Versions: The presented distinguishers are for round-reduced versions of Keccak-f and do not directly threaten the security of the full 24-round Keccak-f permutation or the SHA-3 standard. The authors explicitly state that there is no known way to extend these distinguishers to the full permutation with practical complexity.
- Scope of Technique: The internal differential boomerang technique is primarily applicable to primitives with high-probability internal differential characteristics and is not directly applicable to keyed modes like Keyak or Ketje due to message modification constraints.
- Future Work: The authors suggest exploring extensions to more rounds while maintaining practical complexity, and leave it as an open problem to find internal differential boomerang distinguishers that cover more rounds and require theoretical complexity. They also note that their work could encourage follow-up research on keyed modes.
Summary updated