Improbable Differential Attacks on Reduced FOX64

Chong Zhang, Zhiyi Qu, Zhendong Yu2015 · DOI

Abstract

FOX is a family of block ciphers designed by Junod and Vaudenay in 2004, which is the result of a joint project with the company MediaCrypt AG in Switzerland. Several attacks on reduced FOX have been proposed. In this paper we present an improbable differential cryptanalysis on the reduced-round FOX. By using this method, we present the attacks on 6, 7, and 8-round FOX64 with the time complexity of $2^{76.92}$, $2^{141.27}$, and $2^{205.85}$ respectively.

Introduction

The FOX family of block ciphers, also known as IDEA-NXT, utilizes a modified Lai-Massey scheme. While the recommended implementation uses 16 rounds, its security is evaluated by the maximum number of rounds susceptible to cryptanalysis. Previous efforts have focused on integral and impossible differential attacks. Impossible differential attacks rely on identifying input/output differences that have a probability of exactly zero. This paper extends this concept through improbable differential cryptanalysis, identifying patterns that occur significantly less frequently than expected for a random permutation.

Methodology: The 5-Round Improbable Differential

The core contribution is the identification of a 5-round improbable differential in FOX64. By analyzing the MDS (Maximum Distance Separable) matrix and the branch number of the diffusion layer (mu4), the authors identified a statistical contradiction in the round function path.

The 5-round improbable differential for FOX64, illustrating the internal contradiction that makes this path statistically unlikely.

Unlike impossible differentials, which require a probability of zero, improbable differentials identify paths where certain input/output differences rarely coincide. This relaxation allows for the discovery of longer paths through the cipher's structure, as seen in the 5-round path where encryption and decryption directions lead to a contradiction in the expected differences.

Key Recovery Attack

To mount a full attack, the 5-round differential is "wrapped" with additional rounds. For a 6-round attack, an extra round is added at the beginning. The attacker uses a statistical framework based on binomial distributions to distinguish the correct sub-key from incorrect ones by observing the frequency of "hits" across a large set of chosen plaintext pairs.

Structure of the 6-round improbable differential attack, showing the 5-round core preceded by an additional round for key recovery.

Results and Complexity

The improbable differential method yields significant improvements in time complexity over previous impossible differential attacks. The following table summarizes the findings for reduced-round FOX64:

Rounds Data Complexity (Chosen Plaintexts) Time Complexity (This Paper) Previous Best Time Complexity
6 Rounds $2^{62.52}$ $2^{76.92}$ $2^{133}$ (Impossible Differential)
7 Rounds $2^{63.37}$ $2^{141.27}$ $2^{199}$ (Impossible Differential)
8 Rounds $2^{63.85}$ $2^{205.85}$ Not previously reported

While the data complexity is slightly higher than some previous methods, the reduction in computational work is substantial. Notably, this is the first reported successful statistical attack on 8-round FOX64.

Conclusion

This research demonstrates that improbable differential cryptanalysis is a powerful tool for evaluating the security margins of block ciphers like FOX64. By identifying statistical anomalies over 5 rounds, the authors successfully attacked up to 8 rounds of the cipher. These results suggest that designers must account for improbable differentials to ensure robust security against advanced statistical attacks in the future.

Summary updated

Abstract

FOX is a family of block ciphers designed by Junod and Vaudenay in 2004, which is the result of a joint project with the company MediaCrypt AG in Switzerland. Several attacks on reduced FOX have been proposed. In this paper we present an improbable differential cryptanalysis on the reduced-round FOX. By using this method, we present the attacks on 6, 7, and 8-round FOX64 with the time complexity of 276.92, 2141.27, and 2205.85 respectively.
BibTeX
@misc{zhang2015improbable,
  author = {Chong Zhang and Zhiyi Qu and Zhendong Yu},
  title = {{Improbable Differential Attacks on Reduced FOX64}},
  year = {2015},
  doi = {10.2991/icmmcce-15.2015.471},
}

Loading related content...

Figure