Impossible Differential Cryptanalysis on Feistel Ciphers with SP and SPS Round Functions

Yuechuan Wei, Ping Li, Bing Sun, Chao LiLecture Notes in Computer Science 2010 · DOI · OpenAlex

Introduction

Impossible differential cryptanalysis is a powerful technique in symmetric cryptography that identifies differential paths with a probability of exactly zero. By finding such "impossible" events, an attacker can effectively filter out incorrect key candidates. While 5-round impossible differentials are common in Feistel ciphers with bijective round functions, identifying longer paths (6 rounds or more) has historically relied on heuristic methods or the abstract $\mathcal{U}$-method. This paper introduces a systematic mathematical framework to identify these extended differentials by analyzing the specific properties of the linear diffusion layer.

The Miss-in-the-Middle Technique

The core strategy for finding impossible differentials is the "miss-in-the-middle" approach. Cryptanalysts construct two differential characteristics: one propagating forward from the plaintext and another propagating backward from the ciphertext. If these two paths meet at an intermediate round with a logical contradiction, the entire differential path is proven impossible.

The miss-in-the-middle technique illustrating a contradiction in the middle rounds of a Feistel cipher.

As shown in Figure 4, a contradiction occurs when the output difference of a round function ($\Delta_{out}$) is forced to be zero while the input difference ($\Delta_{in}$) is non-zero, or vice versa, given the properties of the round function $f$.

Matrix-Based Analysis and the $\chi$-Function

The authors improve upon existing methods by moving beyond the "black box" treatment of the linear transformation layer ($P$). They introduce the $\chi$-function, which maps multi-bit differences to a binary state (0 for no difference, 1 for any non-zero difference). By applying this to the matrices representing the linear layers, the existence of 6, 7, or 8-round impossible differentials can be determined through specific criteria:

  1. Hamming weight analysis of columns in $P \oplus P^{-1}$.
  2. Rank evaluation of specific sub-matrices of $P$.
  3. Positional analysis of '1's within the transformation matrices.

This approach is particularly effective for distinguishing between SP (Substitution-Permutation) and SPS (Substitution-Permutation-Substitution) round functions. SPS structures, found in ciphers like E2, require a more nuanced rank-based analysis to uncover contradictions that simpler methods might miss.

A 6-round differential path for a Feistel cipher, demonstrating the propagation of specific differences through SP round functions.

Figure 5 illustrates how specific differences, such as $e_i$ and its transformations through $P$ and $S$ layers, propagate through multiple rounds to establish a long-range impossible differential.

Key Results and Impact

The most significant application of this framework was the discovery of a 6-round impossible differential for the E2 cipher, an improvement over the previously known 5-round limit. Additionally, the method successfully identified 7 and 8-round differentials for Camellia and SNAKE(2), validating its reliability against established standards.

These findings suggest that a high "branch number"—a standard metric for diffusion—is not a sufficient guarantee of security. Designers must also ensure that the linear layer's matrix structure does not inadvertently facilitate long-range contradictions.

Conclusion

By formalizing the relationship between linear layer matrix properties and impossible differentials, this research provides a robust tool for both the cryptanalysis and the design of Feistel ciphers. Future work may extend these binary-field propositions to MDS matrices over larger finite fields, further hardening modern block ciphers against these structural vulnerabilities.

Summary updated

BibTeX
@inproceedings{wei2010impossible,
  author = {Yuechuan Wei and Ping Li and Bing Sun and Chao Li},
  title = {{Impossible Differential Cryptanalysis on Feistel Ciphers with SP and SPS Round Functions}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2010},
  doi = {10.1007/978-3-642-13708-2\_7},
}
Figure