Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak- f 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, the core of the SHA-3 hash function. By combining internal differentials with a modified boomerang attack, the authors achieve practical distinguishers for significantly fewer rounds than previously possible, demonstrating a non-random behavior in reduced-round Keccak-f.

What Problem Does This Paper Address?

The security of cryptographic primitives like hash functions is paramount, especially for those selected for standardization (like Keccak for SHA-3). While extensive research has been done on Keccak-f, analyzing its round-reduced versions is crucial for understanding its overall security. Previous attacks often relied on classical differential or boomerang techniques. This paper addresses the challenge of finding more efficient distinguishers for round-reduced Keccak-f by proposing a new attack that leverages the specific structure of the permutation, aiming to find weaknesses that might be missed by traditional methods.

Methods

The core contribution is the internal differential boomerang distinguisher. This technique combines two concepts:

  • Internal Differentials: Instead of tracking differences between entire states, this method focuses on differences within parts of the state (specifically, the XOR difference between the higher and lower 32 bits of each lane in Keccak-f). This is particularly effective for highly symmetric functions like Keccak-f.
  • Boomerang Attack: A known cryptanalytic technique that uses pairs of inputs and outputs to find weaknesses. The authors adapt this by using internal differentials for one part of the boomerang and standard differentials for the other.

A key aspect of their method is message modification. This technique allows them to deterministically "pass" certain rounds of the permutation, effectively reducing the complexity of the attack by bypassing probabilistic steps. They also utilize truncated characteristics, where differences are not fully specified in all bits, to maintain high probabilities over more rounds.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Internal Differentials Shine for Symmetric Functions: The paper highlights that internal differentials are particularly well-suited for analyzing highly symmetric cryptographic primitives like Keccak-f, offering a more sensitive way to detect structural weaknesses than traditional state-wide differentials.
  • Boomerang Meets Internal Differentials: Combining internal differentials with the boomerang attack framework provides a powerful new tool. It requires fewer differentials (three instead of four in classical boomerangs) and can be more efficient when high-probability internal differentials exist.
  • Message Modification is Key to Practicality: The authors demonstrate that strategic message modification is crucial for making these internal differential boomerang distinguishers practical. It allows them to bypass low-probability rounds, significantly reducing the overall query complexity.
  • Round Constants Matter: The paper notes that the round constants in Keccak-f play a vital role in enabling high-probability internal differential characteristics, a finding consistent with previous research.
  • Non-Random Behavior in Reduced Rounds: The results show that even round-reduced versions of Keccak-f exhibit non-random behavior that can be exploited, challenging the expectation of a "compact representation" for permutations used in sponge constructions.

Key Results

The paper presents practical distinguishers for round-reduced Keccak-f, achieving significantly lower complexities than previous attacks:

  • 7-round Keccak-f (starting at round 0): Distinguishable with approximately $2^{13}$ queries.
  • 8-round Keccak-f (starting at round 3): Distinguishable with approximately $2^{18.3}$ queries.
  • 6-round Keccak-f (starting at round 0): Distinguishable with 25 queries.
  • 7-round Keccak-f (starting at round 3): Distinguishable with approximately $2^{10.3}$ queries.

These results have been verified through computer implementation. The authors emphasize that these attacks do not threaten the security of the full 24-round Keccak-f permutation.

Limitations and Future Work

  • Limited to Round-Reduced Versions: The presented distinguishers are for round-reduced versions of Keccak-f and do not directly apply to the full permutation or the Keccak hash function itself. The message modification used is incompatible with the sponge construction's input requirements.
  • Extending to More Rounds: The authors acknowledge that extending these distinguishers to a larger number of rounds while maintaining practical complexity remains an open problem.
  • Theoretical Complexity: While practical distinguishers are presented, the paper leaves open the challenge of finding internal differential boomerang distinguishers that cover more rounds and require only theoretical complexity.
  • Keyed Modes: The technique is not applied to keyed modes of Keccak-f (like Keyak or Ketje), as the message modification is incompatible.

Summary updated

BibTeX
@article{jean2015internal,
  author = {Jérémy Jean and Ivica Nikolic},
  title = {{Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak- f f Permutation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=sp1Zf9ns1d},
}

Loading related content...

Figure