TL;DR
This paper introduces "DOSCrack," a novel attack that efficiently breaks dynamically obfuscated scan chains (DOSC) by combining symbolic execution and binary clustering. The authors also propose a robust countermeasure using the Trivium cipher to significantly increase the effort required for such attacks, making it a practical solution for hardware security.
What Problem Does This Paper Address?
Modern integrated circuits (ICs) rely on Design-for-Test (DfT) techniques, particularly scan chains, to ensure they function correctly and are free of manufacturing defects. While essential for testing, scan chains also present a security vulnerability. They can be exploited by attackers to extract sensitive information, such as cryptographic keys, through "scan-based attacks."
To combat this, researchers developed "dynamically obfuscated scan chains" (DOSC). DOSC aims to protect these keys by obscuring test patterns and responses. However, the effectiveness of DOSC against sophisticated attacks remained an open question. This paper addresses the critical need to understand and overcome vulnerabilities in these security mechanisms, particularly DOSC, and to develop more resilient defenses.
Methods
The core of this research lies in two main contributions: an attack framework and a countermeasure.
DOSCrack Attack Framework: * Structural Analysis: The framework first analyzes the scan chain's netlist to identify its key components: the Linear Feedback Shift Register (LFSR), shadow chain, and the scan chains themselves. This is crucial for understanding how data flows and is processed. * Symbolic Execution: This technique treats program variables (like the secret seed) as symbolic values rather than concrete ones. By simulating the scan chain's behavior with these symbolic values, the framework generates a system of equations that represent the relationship between inputs, outputs, and the unknown seed. * SMT Solver: A Satisfiability Modulo Theories (SMT) solver is used to solve these symbolic equations, generating a set of potential "obfuscation key candidates." * Binary Clustering: To manage the potentially large number of candidates, K-means clustering is employed. This groups similar key candidates together, allowing for more efficient elimination. * Sequential Equivalence Checking (SEC): Used in conjunction with clustering, SEC helps generate "distinguishing patterns" that can effectively rule out entire groups of candidate keys.
Trivium-Based Countermeasure: * Nonlinear Feedback Shift Register (NLFSR): The authors propose replacing the traditional LFSR in DOSC with a Nonlinear Feedback Shift Register (NLFSR) based on the Trivium cipher. * Trivium Cipher: Trivium is chosen for its efficiency in generating long key streams and its inherent nonlinearity. This nonlinearity makes it significantly harder for symbolic execution and SMT solvers to model and solve the resulting equations, thus increasing the attack complexity.
Datasets
The paper does not explicitly mention pre-existing datasets for training. Instead, the authors synthesize four DOSC benchmarks with varying LFSR seed sizes (8-bit, 16-bit, 32-bit, and 64-bit) for evaluation. These benchmarks are designed to mimic real-world scenarios, with scan chains having a length equal to their seed size. They also evaluate their countermeasure on Trivium-based DOSC architectures of different bit-lengths.
Key Insights and Ideas
- Symbolic Execution is Powerful for Scan Chain Attacks: The research demonstrates that symbolic execution, when combined with other techniques, can effectively reverse-engineer and break scan chain obfuscation mechanisms, even without knowledge of the functional logic.
- Clustering is Essential for Scalability: As seed sizes increase, the number of potential key candidates explodes. Binary clustering is shown to be a critical step in managing this complexity and making the attack scalable.
- Nonlinearity is Key to Defense: The paper highlights that the inherent linearity of LFSRs makes them vulnerable. Introducing nonlinearity through ciphers like Trivium significantly boosts the resilience of DOSC against symbolic execution-based attacks.
- Minimal Overhead for Stronger Security: The proposed NLFSR countermeasure adds minimal design overhead, making it a practical and attractive solution for industrial applications.
- DOSCrack is More Efficient Than Brute-Force/SAT: The attack framework significantly reduces the time and effort required to break DOSC compared to traditional SAT attacks or brute-force methods.
Key Results
- DOSCrack Efficiency: The DOSCrack framework successfully reduced the number of key candidates and broke a 64-bit seed DOSC in approximately 3 days and 23 hours. This is a significant improvement over traditional SAT attacks, which can time out after 10 days.
- Brute-Force Comparison: Brute-forcing 1000 random keys took approximately 2.5 hours, underscoring the efficiency of DOSCrack.
- Trivium Countermeasure Effectiveness: The Trivium-based DOSC demonstrated significantly higher complexity. For an 8-bit seed, the runtime increased by approximately five times compared to an LFSR-based DOSC. For larger seeds, the attack runtime for Trivium-based DOSC was substantially longer, with SAT solvers timing out.
- Area Overhead: Integrating the DOSC architecture with BIST (Built-In Self-Test) resulted in only a 1.1% increase in area overhead, demonstrating its practicality.
Limitations and Future Work
- Limitations:
- The current DOSCrack framework relies on an "oracle" (either a physical chip or a simulation) to generate SI/SO patterns. The effectiveness of random SI/SO pattern generation diminishes over time, necessitating more sophisticated pattern generation.
- While the paper demonstrates the effectiveness of the Trivium countermeasure, the complexity of solving the symbolic equation system for larger Trivium-based systems can still be computationally intensive, with SAT solvers timing out.
- Future Work:
- Developing more advanced algorithms for intelligently selecting clusters to generate distinguishing patterns. The authors suggest exploring reinforcement learning for this purpose.
- Investigating methods for generating independent SI/SO patterns rather than relying on random ones to improve the symbolic equation system step.
- Further exploring the complexity of NLFSR-based countermeasures and optimizing the symbolic execution and SAT solving processes for these more complex systems.
Summary updated