Improved Impossible Differential Cryptanalysis of Reduced-Round Camellia

Wenling Wu, Lei Zhang, Wentao ZhangLecture Notes in Computer Science 2009 · DOI · OpenAlex

Introduction

Camellia is a widely recognized block cipher standard, designed for high performance and security. However, like all cryptographic primitives, it is subject to rigorous cryptanalytic scrutiny. One of the most potent techniques for evaluating block cipher security is Impossible Differential Cryptanalysis. This method identifies differential paths that have a probability of exactly zero; if a guessed key leads to such an "impossible" state, that key is guaranteed to be incorrect.

This paper addresses a significant gap in previous research: the assumption of subkey independence. Earlier impossible differential attacks on Camellia treated the subkeys used in each round as independent variables. In reality, these subkeys are derived from a single master key through a specific key scheduling algorithm. By incorporating these mathematical dependencies, the authors successfully extended attacks to 12-round Camellia-128 and 16-round Camellia-256, achieving the most efficient results to date.

Methodology and Key Schedule Exploitation

The authors employ a "miss-in-the-middle" approach, centered around a known 8-round impossible differential distinguisher. By wrapping additional rounds around this core, they facilitate key recovery.

Structure of the 12-round impossible differential attack on Camellia-128

The primary innovation lies in the deep integration of Camellia's internal algebra and key schedule. The authors derived specific properties (Properties 1, 2, and 3) describing bit-level relationships between subkeys. For example, in Camellia-128, subkeys $K_1$ and $K_{12}$ share 28 common bits.

During the key recovery process, these properties allow for a highly efficient sieving mechanism. Instead of guessing entire subkeys, the attack guesses small portions (bytes) and immediately discards candidates that are mathematically inconsistent with the key schedule. Furthermore, the authors exploit the linear diffusion layer ($P$ transformation) to identify unique intermediate variable values for certain difference patterns, effectively bypassing parts of the cipher's complexity.

Key Results and Comparative Analysis

The proposed methodology yields significant improvements over previous state-of-the-art attacks on Camellia versions without $FL/FL^{-1}$ functions. The 12-round attack on Camellia-128 requires $2^{65}$ chosen plaintexts and $2^{111.5}$ encryptions, significantly surpassing the previous 11-round benchmark.

Summary of attack complexities on Camellia compared to previous work

The following table summarizes the key findings of this research:

Cipher Version Rounds Attacked Data Complexity Time Complexity
Camellia-128 12 Rounds $2^{65}$ $2^{111.5}$
Camellia-256 16 Rounds $2^{89}$ $2^{222.1}$

These results demonstrate that the security margin of Camellia is narrower than previously estimated when the key schedule is fully utilized.

Conclusion and Future Directions

While this work provides a robust framework for attacking the core Feistel structure of Camellia, it focuses on reduced-round versions that exclude $FL/FL^{-1}$ functions and whitening layers. The full version of Camellia remains more secure. Additionally, the current method does not apply as effectively to Camellia-192 due to its distinct key schedule structure, which does not produce the same exploitable bit-sharing relationships between the targeted rounds. Future research may focus on incorporating $FL/FL^{-1}$ functions into this key-schedule-aware framework to further evaluate the full cipher's security.

Summary updated

BibTeX
@inproceedings{wu2009improved,
  author = {Wenling Wu and Lei Zhang and Wentao Zhang},
  title = {{Improved Impossible Differential Cryptanalysis of Reduced-Round Camellia}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2009},
  doi = {10.1007/978-3-642-04159-4\_29},
}
Figure