Improved Related-Key Impossible Differential Attacks on Reduced-Round AES-192

Wentao Zhang, Wenling Wu, Lei Zhang, Dengguo FengLecture Notes in Computer Science 2007 · DOI · OpenAlex

Introduction

The Advanced Encryption Standard (AES) is the cornerstone of modern digital security, with AES-192 (utilizing a 192-bit key and 12 rounds) being a critical variant. Cryptographers continuously "stress-test" these standards by attempting to break reduced-round versions. This research significantly advances the efficiency of "related-key impossible differential" attacks against AES-192, reducing the resources required to compromise 7 and 8 rounds of the cipher.

The Attack Model

This paper focuses on a sophisticated "double-whammy" technique combining two cryptanalytic methods:

  1. Related-Key Attack: The attacker observes encryptions under two different keys that share a known mathematical relationship, even if the keys themselves remain secret.
  2. Impossible Differential Attack: The attacker identifies specific input differences that, by design, can never result in certain output differences. If a guessed key leads to one of these "impossible" outcomes, that guess is definitively proven wrong and discarded.

Previous attempts to attack AES-192 using this method were either inefficient—requiring up to 32 related keys—or contained technical errors in their complexity estimations regarding the cipher's final rounds.

Methodological Improvements

The researchers introduced several tactical shifts to improve upon previous work by Biham et al. and Jakimoski et al. A primary innovation is the construction of a new 5.5-round impossible differential. This path identifies where forward-moving differences and backward-moving differences eventually contradict each other, as shown in the logical flow of the cipher's state.

Figure 1: The 5.5-round impossible differential path, illustrating the logical contradiction used to eliminate incorrect key guesses.

Key technical shifts include:

  • Optimal Key Difference Selection: Identifying a specific 192-bit key difference that propagates through the AES key schedule more cleanly than previous selections.
  • Starting from Round 1: While previous attacks skipped the first two rounds to simplify analysis, this paper starts from the beginning. This reduces the number of "unknown" bytes an attacker must guess, exponentially lowering time complexity.
  • MixColumns Exploitation: For 7-round attacks, the authors utilized specific algebraic properties of the MixColumns operation to filter out incorrect keys more effectively.

Key Insights: Why AES-192?

Interestingly, AES-192 is more susceptible to these specific attacks than AES-128 or AES-256. This vulnerability stems from its key schedule, which applies non-linear transformations every six words, compared to every four words in other variants. This "slower" schedule allows related-key differences to persist longer without being scrambled, providing a longer window for cryptanalytic exploitation.

Comparative Results

The paper presents several attacks that outperform previous benchmarks. Most notably, the researchers achieved a massive leap in "key economy," moving from 32 related keys down to just 2. In practical terms, an attacker is far more likely to find or induce a relationship between two keys than thirty-two.

Figure 2: Comparison of attack complexities against previous literature, highlighting the reductions in data, time, and key requirements.

As summarized in the results, the new 7-round attack represents a 16x reduction in data and a 16,384x ($2^{14}$) speedup in time compared to the previous state-of-the-art (Ref [6]), while requiring significantly fewer keys.

Attack Target Data Complexity Time Complexity Related Keys
7-Round AES-192 $2^{52}$ RK-CP $2^{80}$ 2
8-Round AES-192 $2^{64.5}$ to $2^{112}$ $2^{177}$ to $2^{136}$ 2
7-Round (New Diff) $2^{37}$ RK-CP $2^{145}$ 2

Conclusion and Future Work

While these attacks represent a significant theoretical breakthrough, full AES-192 (12 rounds) remains computationally secure. The "related-key" model assumes an attacker can influence or observe key relationships, a condition often difficult to meet in standard independent-key protocols. Future research may look toward extending the MixColumns-based filtering techniques to 8 rounds or further optimizing the data-time trade-offs for the 8-round attack.

Summary updated

BibTeX
@inproceedings{zhang2007improved,
  author = {Wentao Zhang and Wenling Wu and Lei Zhang and Dengguo Feng},
  title = {{Improved Related-Key Impossible Differential Attacks on Reduced-Round AES-192}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2007},
  doi = {10.1007/978-3-540-74462-7\_2},
}
Figure