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.
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:
- Hamming weight analysis of columns in $P \oplus P^{-1}$.
- Rank evaluation of specific sub-matrices of $P$.
- 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.
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