Neural-Inspired Advances in Integral Cryptanalysis

Liu Zhang, Yiran Yao, Danping Shi, Dongchen Chai, Jianwei Guo, Zilong Wang

TL;DR

This paper demonstrates how neural networks can act as "feature explorers" to uncover hidden mathematical properties in block ciphers that classical automated search tools often miss. By translating neural network insights into a new "meet-in-the-middle" search framework, the authors broke previous records for integral cryptanalysis on the SKINNY cipher, extending distinguishers and improving key-recovery attacks by an additional round.

What Problem Does This Paper Address?

In symmetric-key cryptography, integral cryptanalysis is a powerful technique used to distinguish a cipher from random data by observing how certain properties (like the sum of a set of ciphertexts) propagate through the encryption process.

The challenge lies in finding these "distinguishers." Classical methods rely on automated search models like Mixed Integer Linear Programming (MILP) or Satisfiability (SAT) solvers. However, these tools face a trade-off: they are either computationally efficient but imprecise (missing optimal patterns), or highly precise but too slow for large-scale ciphers. Recently, neural networks (NNs) have shown a knack for finding non-random features in data, but they are often "black boxes"—we know they found something, but we don't know what it is or how to turn it into a formal mathematical attack.

Methods

The authors propose a hybrid approach that uses NNs to guide the improvement of classical cryptanalytic models:

  1. Neural Feature Exploration: They trained a simple three-layer fully connected neural network to distinguish between real ciphertexts and random data. To make the NN's job easier, they preprocessed the data into Vectorial Division Sequences (VDS) based on "parity sets," which focus the network specifically on integral-related properties.
  2. Opening the Black Box: To understand what the NN learned, they used a bit sensitivity test to identify which ciphertext bits most influenced the network's accuracy. They then converted the trained NN into a Boolean function (Conjunctive Normal Form) to extract the exact linear or nonlinear combinations of bits the network was using.
  3. Improved Classical Search: Inspired by the NN's findings (which showed that classical models were missing optimal bit combinations), they developed a meet-in-the-middle search framework. This framework combines the efficiency of bit-based division properties for forward modeling with the precision of the "monomial prediction" technique for backward extension.

Datasets

The study focuses on the SKINNY family of block ciphers, a popular target for cryptanalysis due to its lightweight design.

  • Training/Test Data: The authors generated synthetic datasets of $10^6$ instances each.
  • Positive Instances: Multisets of plaintexts with specific active bits, encrypted under random keys.
  • Negative Instances: Similar multisets where the active bits were replaced with purely random values.
  • Target Variants: Evaluation was performed on SKINNY-64-64, SKINNY-128-128, and their related-tweakey versions (n-2n, n-3n).

Key Insights and Ideas

  • NNs as Auxiliary Tools: The paper argues that NNs shouldn't replace classical cryptanalysis but should serve as "scouts." NNs are excellent at finding short-round distinguishers with very low data complexity (e.g., using only one active cell), which can then be extended by classical models.
  • Imprecision of Current Models: By comparing NN results to classical ones, the authors proved that existing automated search models were failing to find the most efficient distinguishers. Specifically, classical models often overlooked linear combinations of bits across different ciphertext cells.
  • Probabilistic Features: The NN successfully learned "key-dependent" (probabilistic) properties. While these don't hold for every key, they allow for "weak-key" attacks that can penetrate more rounds than deterministic attacks.

Key Results

The authors achieved several new "best-known" results for the SKINNY cipher:

  • Extended Distinguishers: Identified an 11-round key-independent distinguisher for SKINNY-64-64 using $2^{60}$ data (improving on the previous $2^{63}$) and a 12-round key-dependent distinguisher—the longest ever found for this cipher.
  • Improved Attacks: Mounted a 15-round key-recovery attack on SKINNY-n-n, surpassing the previous record of 14 rounds.
  • Efficiency Gains: Reduced the time complexity for key-recovery attacks across multiple SKINNY variants (as shown in Table 2 of the paper), often by leveraging the probabilistic distinguishers discovered by the NN.

Limitations and Future Work

  • Data Complexity Constraints: NNs are inherently limited to short-round distinguishers because training them on properties that require massive datasets (e.g., $2^{120}$ plaintexts) is computationally impossible.
  • Weak Key Dependency: Some of the most powerful results (like the 12-round distinguisher) are key-dependent, meaning the attack only works for a specific subset of the total key space.
  • Search Space for Nonlinearity: While the authors explored nonlinear combinations of bits, they noted that an exhaustive search for all possible mapping functions remains computationally daunting. The authors suggest that exploring more efficient search strategies for these complex functions is a critical next step for the field.

Summary updated

Abstract

The study by Gohr et.al at CRYPTO 2019 and sunsequent related works have shown that neural networks can uncover previously unused features, offering novel insights into cryptanalysis. Motivated by these findings, we employ neural networks to learn features specifically related to integral properties and integrate the corresponding insights into optimized search frameworks. These findings validate the framework of using neural networks for feature exploration, providing researchers with novel insights that advance established cryptanalysis methods. Neural networks have inspired the development of more precise integral search models. By comparing the integral distinguishers obtained via neural networks with those identified by classical methods, we observe that existing automated search models often fail to find optimal distinguishers. To address this issue, we develop a meet in the middle search framework that balances model accuracy and computational efficiency. As a result, we reduce the number of active plaintext bits required for an 11 rounds integral distinguisher on SKINNY64/64, and further identify a 12 rounds key dependent integral distinguisher achieving one additional round over the previous best-known result. The integral distinguishers discovered by neural networks enable key recovery attacks on more rounds. We identify a 7 rounds key independent integral distinguisher from neural networks with even only one active plaintext cell, which is based on linear combinations of bits. This distinguisher enables a 15 rounds key recovery attack on SKINNYn/n, improving upon the previous record by one round. Additionally, we discover an 8 rounds key dependent integral distinguisher using neural network that further reduces the time complexity of key recovery attacks against SKINNY.
BibTeX
@misc{zhang2025neural,
  author = {Liu Zhang and Yiran Yao and Danping Shi and Dongchen Chai and Jianwei Guo and Zilong Wang},
  title = {{Neural-Inspired Advances in Integral Cryptanalysis}},
  year = {2025},
  eprint = {2505.10790},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.10790},
}

Loading related content...

Figure