Towards a Characterization of the Related-Key Attack Security of the Iterated Even-Mansour Cipher

Dana Dachman-Soled, Angela Park, Ben San Nicolas

TL;DR

This paper provides a more robust and simplified proof for the security of the Iterated Even-Mansour (IEM) cipher against "Related-Key Attacks." By applying the $H$-coefficient technique, the authors demonstrate that the cipher remains secure under a much broader and more complex set of key-tampering functions than previously established in cryptographic literature.

What Problem Does This Paper Address?

In traditional cryptography, we usually assume a secret key is fixed and untouchable. However, in the real world, attackers might be able to observe a system running on keys that are mathematically related to the original secret—for example, through hardware faults, side-channel leakage, or poorly designed protocols. These are known as Related-Key Attacks (RKAs).

The Iterated Even-Mansour (IEM) construction is a theoretical framework that models how modern block ciphers (like AES) work, using a sequence of public permutations and secret key additions. While previous research proved IEM was secure against simple attacks (like XORing a known value into the key), there was a gap in understanding its security against more complex, "non-linear" key transformations. Earlier proofs were either overly complex or relied on technical requirements that were too restrictive to cover many practical scenarios.

Methods

The authors utilize the $H$-coefficient technique, a powerful tool in symmetric-key cryptography for proving that a "real" system is indistinguishable from an "ideal" random one.

Their approach involves three main pillars:

  1. Generalizing the Framework: They extend the proof techniques used by Cogliati and Seurin (which only covered XOR attacks) to handle broad classes of Related-Key Derivation (RKD) functions.
  2. Defining New Requirements: They establish three refined criteria for RKD functions:
  3. Strengthened Output Unpredictability: It must be hard to predict the result of the key transformation.
  4. Strengthened Claw-Freeness: It must be hard to find two different inputs that result in the same related key.
  5. Query Ordering: A novel technical requirement that allows for "intersection queries" (where different parts of the attack overlap) as long as the queries can be logically re-ordered in a specific way.
  6. The Trivial Key Schedule: They focus on the most efficient version of IEM, where the same master key is used in every round, proving that even this simplified version is highly resilient.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, the results are based on mathematical proofs and probability theory rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • Simplicity Leads to Generality: The authors found that by using a "far simpler proof" technique (the $H$-coefficient method), they could actually prove security for a larger set of attack scenarios than the previous, more complex methods.
  • The Power of Re-ordering: One of the most significant "aha moments" is the realization that security doesn't require "bad" query overlaps to be impossible. Instead, it only requires that the transcript of the attack could be re-ordered such that the overlaps don't grant the attacker an advantage. This insight allowed them to bypass limitations that had stumped previous researchers.
  • Challenging the Status Quo: The paper provides a concrete example of a key-tampering function that was explicitly "un-provable" under previous frameworks (specifically Farshim and Proctor's FSE 15 result) but is proven secure here for a 3-round IEM cipher.

Key Results

  • Theorem 1.1 (General Bound): The authors provide a concrete mathematical bound for the "advantage" an attacker has. They show that for a cipher with $n$-bit keys ($N=2^n$), the security holds as long as the number of queries ($q_e$ to the cipher and $q_p$ to the permutations) remains significantly smaller than $\sqrt{N}$.
  • Theorem 1.2 (3-Round Security): They prove that a three-round IEM construction is secure against a specific, complex class of RKD functions involving nested permutations.
  • Improved Efficiency: Their proof shows that the "trivial key schedule" (using the same key in every round) is sufficient for RKA security, which is good news for engineers looking to implement efficient hardware ciphers.

Limitations and Future Work

  • Full Characterization: While the paper moves "towards a characterization," the authors acknowledge they haven't yet reached a complete "if and only if" description of all secure RKD functions. There is still a theoretical gap to close.
  • Round Optimization: The paper proves security for specific round counts (like 3 or 4 rounds) for certain functions. Future work could investigate the absolute minimum number of rounds required for security against even more aggressive classes of related-key functions.
  • Non-Trivial Key Schedules: The study focuses on the trivial key schedule; exploring more complex, real-world key schedules using these same techniques remains an open challenge.

Summary updated

Abstract

We prove the related-key security of the Iterated Even-Mansour cipher under broad classes of related key derivation (RKD) functions. Our result extends the classes of RKD functions considered by Farshim and Procter (FSE, 15). Moreover, we present a far simpler proof which uses techniques similar to those used by Cogliati and Seurin (EUROCRYPT, 15) in their proof that the four-round Even-Mansour cipher is secure against XOR related-key attacks---a special case of our result and the result of Farshim and Proctor. Finally, we give a concrete example of a class of RKD functions covered by our result which does not satisfy the requirements given by Farshim and Procter and prove that the three-round Even-Mansour cipher is secure against this class of RKD functions.
BibTeX
@article{dachmansoled2016towards,
  author = {Dana Dachman-Soled and Angela Park and Ben San Nicolas},
  title = {{Towards a Characterization of the Related-Key Attack Security of the Iterated Even-Mansour Cipher}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
  url = {https://openreview.net/forum?id=Nsh1Jyvsha},
}
Figure