Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48

Mohamed Ahmed Abdelraheem, Javad Alizadeh, Hoda A. Alkhzaimi, Mohammad Reza Aref, Nasour Bagheri, Praveen Gauravaram

TL;DR

This paper presents a novel time-memory trade-off method to improve linear cryptanalysis of the SIMON block cipher. By combining correlation matrix techniques with Mixed Integer Programming (MIP), the authors achieve the best known linear cryptanalytic results for reduced-round SIMON-32 and SIMON-48, leading to improved key recovery attacks.

What Problem Does This Paper Address?

Lightweight block ciphers like SIMON are designed for resource-constrained environments (e.g., RFID tags) where efficiency is paramount. However, their reduced complexity can make them vulnerable to cryptanalytic attacks. Linear cryptanalysis is a powerful technique for breaking block ciphers by exploiting linear approximations. The challenge lies in finding effective linear approximations for a large number of rounds, which typically requires significant computational resources (either time or memory). Existing methods often struggle to find optimal linear trails, especially for ciphers like SIMON that have specific non-linear components. This paper aims to improve the efficiency and effectiveness of linear cryptanalysis for SIMON by developing a hybrid approach that overcomes the limitations of purely matrix-based or MIP-based methods.

Methods

The core contribution of this paper is a time-memory trade-off method that combines two established techniques:

  • Correlation Matrix Method: This method is effective for finding linear trails with low Hamming weight (i.e., few non-zero bits in the input/output masks). It involves constructing and analyzing correlation matrices. However, it can be memory-intensive for larger block sizes or higher Hamming weights.
  • Mixed Integer Programming (MIP): This technique is used to find linear trails with high Hamming weight. It formulates the problem as an optimization task, allowing for the discovery of trails that might be missed by the correlation matrix method. While powerful, MIP can be time-consuming, especially for a large number of rounds.

The authors' hybrid approach splits the cipher into two parts. The "light trails" (low Hamming weight) are found using the correlation matrix method on one part, while "heavy trails" (high Hamming weight) are found using MIP on the other part. By carefully combining these, they can efficiently find better linear approximations for a larger number of rounds than either method could achieve alone. They also introduce a technique using "Big M constraints" to manage the complexity of the MIP formulation.

Datasets

Not discussed in the paper. The analysis is performed on the SIMON cipher itself, not on external datasets.

Key Insights and Ideas

  • Synergy of Matrix and MIP: The most significant insight is that combining the strengths of the correlation matrix method (low Hamming weight trails, memory-efficient for small weights) and MIP (high Hamming weight trails, time-intensive) leads to superior linear approximations for SIMON compared to using either method in isolation.
  • Time-Memory Trade-off is Crucial: For lightweight ciphers with limited rounds, finding the "best" linear approximation is key. The proposed trade-off allows researchers to balance computational resources to achieve better results than brute-force or single-method approaches.
  • Hamming Weight Matters: The paper highlights how the Hamming weight of input/output masks significantly influences the effectiveness of linear approximations. Their method specifically targets finding trails that might have high Hamming weights in intermediate rounds, which are often missed by purely low-weight trail searches.
  • SIMON's Structure: The analysis implicitly reveals insights into SIMON's resistance to linear cryptanalysis, showing that while it has some linear properties, these can be exploited with advanced techniques.

Key Results

  • Improved Linear Approximations:
    • A 14-round linear approximation for SIMON-32/K with an average squared correlation of approximately $2^{-32}$.
  • A 17-round linear approximation for SIMON-48/K with a squared correlation of approximately $2^{-47.78}$.
  • Enhanced Key Recovery Attacks:
    • A 23-round key recovery attack on SIMON-32/K with a time complexity of $2^{63.9}$.
  • A 24-round key recovery attack on SIMON-48/96 with a time complexity of $2^{83.10}$.
  • A 24-round attack on SIMON-32 with marginal complexity.
  • 23-round and 24-round attacks on SIMON-48/72 and SIMON-48/96, respectively, with data complexities of $2^{-47.78}$ and time complexities of $2^{62.10}$ and $2^{83.10}$.

Limitations and Future Work

  • Computational Cost: While the proposed method is an improvement, the computations, especially for MIP, can still be substantial, requiring significant time (e.g., 20 hours on a laptop for some experiments).
  • SIMON-64: The paper notes that for SIMON-64, building and processing correlation matrices with higher Hamming weights becomes challenging due to memory constraints. The time-memory trade-off method was less effective for higher round counts on SIMON-64.
  • Future Work:
    • Investigating methods to speed up the selection of intermediate masks for SIMON-64.
  • Exploring alternative MIP replacements, such as SAT/SMT solvers or dedicated branch-and-bound methods.
  • Applying the method to other block ciphers, like PRESENT, to see if similar improvements can be achieved.
  • Comparing their linear attack results with differential attacks for SIMON-32, as key recovery for differential attacks was not presented in related work.

Summary updated

BibTeX
@article{abdelraheem2015improved,
  author = {Mohamed Ahmed Abdelraheem and Javad Alizadeh and Hoda A. Alkhzaimi and Mohammad Reza Aref and Nasour Bagheri and Praveen Gauravaram},
  title = {{Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
}

Loading related content...

Figure