Differential-Neural Cryptanalysis on AES

Liu Zhang, Zilong Wang, Jinyu LuIEICE 2024 · DOI

TL;DR

Researchers have successfully applied deep learning to create highly accurate "distinguishers" for reduced-round versions of the Advanced Encryption Standard (AES). By training neural networks on as little as two bytes of ciphertext, they achieved near 100% accuracy in identifying encrypted data versus random noise, enabling a practical 3-round key recovery attack with very low computational complexity.

What Problem Does This Paper Address?

Differential cryptanalysis is a cornerstone of modern code-breaking. It involves studying how specific differences in plaintext inputs propagate through a cipher to become specific differences in ciphertext outputs. Traditionally, this requires cryptanalysts to manually derive complex Differential Distribution Tables (DDTs).

In 2019, researcher Aron Gohr introduced "differential-neural cryptanalysis," using neural networks to automate the discovery of these patterns. While successful on "lightweight" ciphers with small block sizes (like SPECK), applying this to the 128-bit blocks of AES is challenging. The massive state space of AES makes it difficult for a standard neural network to "learn" the global diffusion properties. This paper tackles the challenge of scaling neural cryptanalysis to large-block ciphers like AES by focusing on partial ciphertext bits.

Methods

The authors adapted Gohr’s residual neural network (ResNet) architecture to handle AES data. The core of their approach is the Multi-Stage Key Recovery Framework.

  1. Neural Distinguisher: They trained a network to perform a binary classification task: given a pair of ciphertexts, did they come from plaintexts with a specific XOR difference ($\Delta = 0x80$), or are they just random numbers?
  2. Partial Input Training: Instead of feeding the entire 128-bit ciphertext block into the network, they experimented with subsets: full ciphertext, one row/column, two bytes, and even a single byte.
  3. Key Recovery Attack: They used the trained 2-round distinguisher to attack a 3-round version of AES. By guessing parts of the subkey and "decrypting" one round backwards, they checked if the resulting data matched the patterns the neural distinguisher was trained to recognize. If the distinguisher flagged the data as "real," the key guess was likely correct.

Datasets

The study relied on synthetic datasets generated specifically for this task:

  • Training Set: 10 million ($10^7$) instances. Each instance consists of a ciphertext pair and a label (1 for real, 0 for random).
  • Testing Set: 1 million ($10^6$) instances.
  • Generation: Data was produced using the Linux random number generator to create uniformly distributed keys and plaintexts. For "real" pairs, plaintexts had a fixed input difference of $0x80$ at the first byte.

Key Insights and Ideas

  • The Power of Two Bytes: The most striking finding is that the neural network doesn't need the whole ciphertext. Using just two specific bytes of a 2-round ciphertext, the model achieves 100% accuracy. This suggests the network is perfectly capturing the local differential propagation characteristics (specifically the relationship between $\Delta_{10}$ and $\Delta_{11}$ in the AES state) before they are fully diffused.
  • Proportional Information Leakage: As the amount of ciphertext provided to the 3-round distinguisher decreases (from full block to two bytes), the True Negative Rate (TNR) drops. This indicates a "dilution" of the signal, yet the network still maintains a non-random advantage, proving that even tiny fragments of ciphertext leak structural information.
  • Validation of the "Wrong Key" Profile: The authors demonstrated that if a subkey guess is even slightly off, the neural distinguisher's response drops to near-zero. This "sharpness" is what makes the neural network an effective tool for key recovery; it acts as a high-precision filter for correct guesses.

Key Results

  • 2-Round Distinguisher: Achieved 1.0 Accuracy, 1.0 TPR, and 1.0 TNR using full ciphertext or specific 2-byte combinations.
  • 3-Round Distinguisher: While less accurate overall (~0.53 accuracy), it maintained a 1.0 True Positive Rate, meaning it never missed a real differential pattern, though it had a high false-positive rate.
  • Attack Complexity: The 3-round key recovery attack was highly efficient.
  • Data Complexity ($D_c$): $2^{2.585}$ ciphertext pairs.
  • Time Complexity ($T_c$): $2^{21.585}$ operations. For context, a brute-force search on a 128-bit key would require $2^{128}$ operations.

Limitations and Future Work

The primary limitation is the number of rounds. AES-128 uses 10 rounds; this paper successfully attacks only 3. As more rounds are added, the "avalanche effect" of AES ensures that the differential patterns become indistinguishable from random noise to the current neural architecture.

The authors suggest that future work could involve:

  1. Prepending Classical Differentials: Combining high-probability manual differentials with neural distinguishers to extend the attack to more rounds.
  2. Optimizing Architectures: Exploring if different neural structures can better capture the diffusion of AES over 4 or 5 rounds.
  3. Refining Key Recovery: Improving the multi-stage guessing process to handle the increased complexity of additional rounds.

Summary updated

Abstract

Based on the framework of a multi-stage key recovery attack for a large block cipher, 2 and 3-round differential-neural distinguishers were trained for AES using partial ciphertext bits. The study introduces the differential characteristics employed for the 2-round ciphertext pairs and explores the reasons behind the near 100% accuracy of the 2-round differential neural distinguisher. Utilizing the trained 2-round distinguisher, the 3-round subkey of AES is successfully recovered through a multi-stage key guessing. Additionally, a complexity analysis of the attack is provided, validating the effectiveness of the proposed method.
BibTeX
@inproceedings{zhang2024differential,
  author = {Liu Zhang and Zilong Wang and Jinyu Lu},
  title = {{Differential-Neural Cryptanalysis on AES}},
  booktitle = {IEICE},
  year = {2024},
  doi = {10.1587/transinf.2024edl8044},
}
Figure