A related-key attack on iterated chaotic ciphers

Yang Yang, Chenhui JinCzech 2008

Abstract

This research presents a highly efficient related-key attack targeting iterated chaotic ciphers. While chaotic systems are theoretically sensitive to initial conditions, this work exploits a specific vulnerability: the initial output bits are often insensitive to the least significant bits (LSBs) of the key. By combining a divide-and-conquer strategy with statistical filtering across multiple related keys, the authors demonstrate the ability to recover a 64-bit key from the ZLL chaotic cipher in approximately 8 minutes and 45 seconds using standard consumer hardware.

Introduction

Iterated chaotic ciphers rely on the "butterfly effect"—the principle that minute changes in initial conditions or parameters lead to divergent trajectories. This property is intended to provide high diffusion and confusion. However, the authors identify a critical "leakage" window in the early iterations of many chaotic maps, such as the Piecewise Linear Chaotic Map (PWLCM). In these initial stages, the most significant bits (MSBs) of the output are primarily determined by the MSBs of the key, leaving them temporarily unaffected by the LSBs.

The proposed attack improves upon previous divide-and-conquer (D&C) methods by incorporating related-key cryptanalysis. A standard D&C attack attempts to guess the key bit-by-bit or in small blocks. However, if the "coincidence degree"—the number of matching bits between a test sequence and the target sequence—is low, the correct key candidate may be indistinguishable from noise.

The related-key attack overcomes this by observing ciphertexts generated by keys with known mathematical differences (e.g., $K$ and $K \oplus \delta$). The attack proceeds in stages:

  1. Key Partitioning: The 64-bit key is divided into 8-bit blocks ($k^{(8)}, k^{(16)}, \dots$).
  2. Statistical Filtering: For each block, candidates are tested against $N$ different related-key sequences.
  3. Candidate Survival: A candidate key is retained only if it satisfies a threshold of matching bits ($d_i$) across the related sequences. By aggregating data from multiple related keys, the statistical "signal" of the correct key becomes significantly stronger than the random noise of incorrect guesses.

Experimental Analysis

To validate the attack, the authors performed a distribution analysis of the coincidence degree for the ZLL cipher. By testing 10,000 independent random keys, they mapped how often specific numbers of bits ($n_8$) match in the initial output.

Table showing the distribution of coincidence degrees ($n_8$) for the ZLL cipher, based on 10,000 random key trials.

As shown in the distribution table above, the coincidence degree varies significantly. While a single key might provide insufficient information, the cumulative probability across 50 to 80 related keys allows the correct key to be identified with near-certainty.

Results and Performance

The attack was implemented on a Pentium IV 2.5 GHz PC (standard hardware for the study's era). The results demonstrate a dramatic reduction in computational complexity compared to brute-force methods:

  • Success Rate: Utilizing 80 related-key sequences yielded a success rate of nearly 1.0 (100%) for full 64-bit key recovery.
  • Time Efficiency: The average time to recover the full key was 8 minutes and 45 seconds.
  • Computational Complexity: The attack requires approximately $2^{25}$ chaotic map computations, a massive improvement over the $2^{64}$ required for brute force.

Even with a reduced dataset of 50 related keys, the attack maintained a 0.94 success rate, though the processing time increased to roughly 11 minutes and 39 seconds due to the need to track a larger number of potential candidates.

Conclusion

The related-key attack exposes a fundamental weakness in the implementation of iterated chaotic ciphers. The gradual propagation of LSB influence creates a window of vulnerability that statistical filtering can exploit. This work underscores the necessity for chaotic cipher designers to ensure that coincidence degree distributions are resistant to multi-sequence analysis and that key influence propagates rapidly across all output bits.

Summary updated

Abstract

summary:In this paper, we present a new type of attack on iterated chaotic ciphers using related keys. Based on the fact that a chaotic sequence is not sensitive to the less significant bits of initial conditions and parameters, a divide- and-conquer attack on iterated chaotic ciphers was presented by us before, which significantly reduces the computing complexity of attacks. However, if the information leaked is significant according to the distribution of the coincidence degrees, a measure for the information leakage of chaotic ciphers, or the size of the key is large, then it is difficult for the divide-and- conquer attack to reduce its computing complexity into a realizable level. The related-key attack we present in this paper simultaneously uses the information leaked from different chaotic sequences generated by related keys and combines the ideas of linear cryptanalysis and divide-and-conquer attack together, hence greatly enhances the efficiency of divide-and-conquer attack. As an example, we test the related-key attack on the ZLL chaotic cipher with a 64-bit key on a Pentium IV 2.5 GHz PC, which takes only 8 minutes and 45 seconds to recover all bits of the key successfully.
BibTeX
@inproceedings{yang2008related,
  author = {Yang Yang and Chenhui Jin},
  title = {{A related-key attack on iterated chaotic ciphers}},
  booktitle = {Czech},
  year = {2008},
}
Figure