Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation

Jérémy Jean, Ivica Nikolic

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

Abstract

We introduce internal differential boomerang distinguisher as a combination of internal differentials and classical boomerang distinguishers. The new boomerangs can be successful against cryptographic primitives having high-probability round-reduced internal differential characteristics. The internal differential technique, which follow the evolution of differences between parts of the state, is particularly meaningful for highly symmetric functions like the inner permutation Keccak-f of the hash functions defined in the future SHA-3 standard. We find internal differential and standard characteristics for three to four rounds of Keccak-f, and with the use of the new technique, enhanced with a strong message modification, show practical distinguishers for this permutation. Namely, we need $2^{12}$ queries to distinguish 7 rounds of the permutation starting from the first round, and approximately $2^{18}$ queries to distinguish 8 rounds starting from the fourth round. Due to the exceptionally low complexities, all of our results have been completely verified with a computer implementation of the analysis.
BibTeX
@article{jean2015internal,
  author = {Jérémy Jean and Ivica Nikolic},
  title = {{Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=sp1Zf9ns1d},
}

Loading related content...

Figure