SoK: On DFA Vulnerabilities of Substitution-Permutation Networks

Mustafa Khairallah, Xiaolu Hou, Zakaria Najm, Jakub Breier, Shivam Bhasin, Thomas Peyrin

TL;DR

This paper presents a generalized Differential Fault Analysis (DFA) attack methodology for Substitution-Permutation Network (SPN) based block ciphers. The authors demonstrate that no SPN-based cipher can be inherently secure against DFA without randomization and introduce a novel tool, the Joint Difference Distribution Table (JDDT), to significantly reduce the number of required faults for key recovery.

What Problem Does This Paper Address?

Differential Fault Analysis (DFA) is a powerful physical attack that can recover secret keys from cryptographic implementations by injecting faults during computation. While many block ciphers have been shown to be vulnerable to DFA, research has often focused on individual ciphers rather than families, leading to repetitive attack patterns. This paper aims to bridge this gap by providing a systematic and generalized approach to analyzing DFA vulnerabilities across the entire family of SPN-based ciphers. The authors highlight the need for a deeper understanding of how SPN design choices impact DFA resistance, moving beyond cipher-specific analyses.

Methods

The core of this work lies in a generalized DFA attack targeting the last round of SPNs. The authors propose:

  • A Theoretical Framework: Building on information-theoretic approaches, they formalize the conditions under which a fault injection can reduce the key search space. A key finding is that non-uniform fault distributions are crucial for effective DFA.
  • Optimized Fault Mask Identification: They introduce a method to find "good" fault masks that maximize information leakage with a minimal number of faulty ciphertexts.
  • The Joint Difference Distribution Table (JDDT): This novel tool is designed to pre-compute solutions for fault equations. By analyzing the differential properties of the substitution and permutation layers, the JDDT significantly speeds up the process of recovering the last round key.
  • A Generic Attack Procedure: The paper outlines a step-by-step process for applying DFA to SPNs, leveraging the JDDT to reduce the key search space efficiently. This includes analyzing the interaction between the substitution and diffusion layers.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and evaluation on existing block ciphers.

Key Insights and Ideas

  • Inherent Vulnerability of SPNs: The paper strongly suggests that SPN-based ciphers cannot be made completely immune to DFA without introducing randomization. The core SPN structure, with its substitution and permutation layers, inherently allows for information leakage under specific fault conditions.
  • The Power of Non-Uniform Faults: The theoretical analysis emphasizes that uniform or random fault models are insufficient for significant key recovery. The effectiveness of DFA hinges on exploiting non-uniform fault distributions.
  • JDDT as a Game-Changer: The introduction of the JDDT is a significant contribution. It moves DFA analysis from a potentially ad-hoc, instance-by-instance approach to a more systematic, pre-computable method, drastically reducing the practical effort required.
  • Beyond Classical Security: The work highlights that ciphers with similar classical security levels (e.g., same block and key sizes) can exhibit vastly different resistances to DFA, underscoring the need for specific DFA-aware design principles.

Key Results

The paper demonstrates the effectiveness of their generalized DFA methodology on a wide range of SPN-based ciphers, including PRESENT, GIFT, AES, LED, SKINNY, PRIDE, and PRINCE.

  • Reduced Key Search Space: For many ciphers, the proposed attack can reduce the key search space to a manageable size with a very small number of faulty and non-faulty ciphertext pairs (e.g., as few as 1-2 pairs for some ciphers like AES-128 under specific fault models).
  • Optimal Attacks Achieved: The authors report achieving optimal or near-optimal DFA attacks for several ciphers, often surpassing previously known best attacks.
  • New Attacks on Modern Ciphers: The methodology is applied to recently proposed lightweight ciphers like SKINNY and GIFT, revealing new vulnerabilities.
  • Practical Implications: The developed technique is designed to be automatable, potentially serving as a valuable tool for analyzing candidates in future cryptographic competitions.

Limitations and Future Work

  • Fault Model Assumptions: The attacks generally assume that the attacker knows the timing and location of the fault. Uncertainty in these aspects would require additional analysis.
  • Practical Fault Injection: While the paper discusses practical fault models, achieving specific fault patterns (e.g., precise bit flips) can still be challenging in real-world implementations.
  • Extending to Other Designs: The authors express interest in extending their methodology to other block cipher designs beyond SPNs.
  • Automated DFA Analysis: They suggest that their JDDT method can be further integrated into automated tools for cryptographic analysis and design.
  • Designing Fault-Resistant Ciphers: The insights gained from this work could serve as a foundation for designing SPN-based ciphers with improved resistance to DFA.

Summary updated

BibTeX
@article{khairallah2019sok,
  author = {Mustafa Khairallah and Xiaolu Hou and Zakaria Najm and Jakub Breier and Shivam Bhasin and Thomas Peyrin},
  title = {{SoK: On DFA Vulnerabilities of Substitution-Permutation Networks}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2019},
}

Loading related content...

Figure