Generalized Related-Key Rectangle Attacks on Block Ciphers with Linear Key Schedule

Boxin Zhao, Xiaoyang Dong, Willi Meier, Keting Jia, Gaoli WangIACR ePrint 2019

Abstract

This paper introduces an optimized, generalized key-recovery model for related-key rectangle attacks, specifically targeting block ciphers with linear key schedules. By refining the processes of quartet generation and filtering, the authors establish new cryptanalytic records for the SKINNY and GIFT block ciphers. Notably, the work presents the first 28-round attack on SKINNY-128-384 and a 24-round attack on GIFT-64, demonstrating a significant reduction in time complexity compared to previous methods.

Introduction

In the field of symmetric cryptography, the rectangle attack—a variant of the boomerang attack—serves as a powerful technique for evaluating the security margins of block ciphers. It operates by "stitching" together two short, high-probability differential characteristics to form a longer distinguisher. However, applying these attacks in a related-key (RK) setting, where an attacker observes cipher behavior under mathematically related keys, introduces significant complexity.

Existing models for RK rectangle attacks often suffer from inefficient "quartet" generation. Traditional methods generate a massive volume of quartets (sets of four plaintexts/ciphertexts) and filter them post-hoc, leading to prohibitive time complexities. This research addresses these inefficiencies by proposing an automated, generalized model that exploits the linear key schedules prevalent in modern lightweight ciphers.

Generalized Key-Recovery Model

The core contribution of this work is a new generalized model that decomposes a cipher $E$ into three distinct components: $E = E_f \circ E' \circ E_b$. Here, $E'$ represents the core rectangle distinguisher, while $E_b$ and $E_f$ denote the rounds extended backward from the start and forward from the end, respectively.

Generalized model for related-key rectangle attacks

Key Methodological Innovations

  1. Optimized Quartet Generation: Rather than the standard approach of exhaustive generation followed by filtering, the authors guess subkey bits in the backward rounds ($E_b$) first. This allows for the construction of only those plaintext pairs guaranteed to satisfy required differences at the distinguisher's start, drastically reducing computational waste.
  2. Step-by-Step Key Recovery: In the forward rounds ($E_f$), a "guess-and-filter" procedure is employed. Instead of guessing all subkey bits simultaneously, the model identifies useful quartets by guessing small fractions of the key incrementally.
  3. Exploitation of Linear Key Schedules: The model is specifically optimized for ciphers using linear transformations in their key schedules, a common feature in NIST Lightweight Cryptography (LWC) candidates. This predictability allows for easier correlation of subkey bits across rounds.

Cryptanalysis of SKINNY and GIFT

The model was evaluated against two prominent lightweight block ciphers: SKINNY, a family used in several NIST LWC candidates (e.g., Romulus, Remus), and GIFT, an evolution of the PRESENT cipher.

The efficiency of the new model allowed for the addition of extra rounds to existing attacks. In cryptanalysis, breaking even a single additional round is a major milestone in quantifying a cipher's security margin. For SKINNY-128-384, the attack was extended to 28 rounds, and for GIFT-64, to 24 rounds.

Comparison of attack complexities for SKINNY-128-384

Key Results and Discussion

The results demonstrate substantial improvements over the previous state-of-the-art. For SKINNY-128-384, the time complexity for a 27-round attack was reduced by a factor of $2^{37}$ compared to previous work. Furthermore, the 28-round attack represents the deepest reach into the cipher's security to date.

While these attacks are "breaks" in a theoretical sense—being faster than brute-force search—the complexities (e.g., $2^{294}$) remain impractical for current computing hardware. Their value lies in providing a rigorous measure of the "security margin" of these ciphers against sophisticated differential-style attacks.

Conclusion and Future Work

The primary gains of this generalized model rely on the linear nature of the target cipher's key schedule. Consequently, ciphers with highly non-linear key schedules, such as AES, may not benefit from the same level of optimization. Future research directions include applying this model to other linear-schedule ciphers like Saturnin or Simon, and investigating its implications for authenticated encryption modes such as LOTUS-AEAD.

Summary updated

BibTeX
@article{zhao2019generalized,
  author = {Boxin Zhao and Xiaoyang Dong and Willi Meier and Keting Jia and Gaoli Wang},
  title = {{Generalized Related-Key Rectangle Attacks on Block Ciphers with Linear Key Schedule}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2019},
}
Figure