TL;DR
Fun-SAT is a novel attack on sequential logic encryption that uses a metric called "functional corruptibility" to predict the optimal unrolling depth for a circuit. By replacing blind, iterative SAT-solving with guided estimation, it achieves a staggering 90x average speedup over previous state-of-the-art attacks.
What Problem Does This Paper Address?
Logic encryption is a hardware security technique used to protect integrated circuits (ICs) from intellectual property theft and tampering by malicious actors in the supply chain. While combinational logic encryption has been largely broken by Boolean satisfiability (SAT) attacks, sequential logic encryption—which involves state machines and transitions—remains a tougher nut to crack.
To attack a sequential circuit, researchers typically "unroll" it, turning it into a massive combinational circuit that represents the original's behavior over multiple clock cycles. The core challenge is the unrolling depth:
- If you unroll too little, the SAT attack finds "spurious" keys that work for a few cycles but fail in the long run.
- If you unroll too much, the resulting circuit becomes so complex that the SAT solver and model checker time out.
Existing attacks blindly increment the unrolling depth one cycle at a time, leading to many redundant and computationally expensive SAT-solving iterations.
Methods
The authors introduce Fun-SAT, which stands for Functional Corruptibility-Guided SAT-Based Attack. The key innovation is the use of Functional Corruptibility (FC) to guide the attack.
- Functional Corruptibility (FC): This is a statistical measure of how much a wrong key "corrupts" the circuit's output. It is calculated as the ratio of corrupted output values to the total number of input/key combinations.
- The Analysis Phase: Instead of jumping straight into a SAT attack, Fun-SAT performs fast logic simulations to calculate FC at increasing unrolling depths.
- The Prediction: The authors prove a critical relationship: if the FC stops increasing as you unroll further, it's a strong signal that no more "wrong keys" can be pruned at that depth. Fun-SAT identifies this plateau (using a threshold $\delta$ and a hold window $\Delta$) to estimate the minimum required unrolling depth.
- The SAT Phase: Once the optimal depth is predicted, the attack performs a single, targeted SAT attack and uses formal model checking (Unique Key and Model Checking Equivalence conditions) to verify the final candidate key.
Datasets
The researchers evaluated Fun-SAT using standard hardware security benchmarks:
- ISCAS’89: Including circuits like s27, s526, s1488, s9234, s15850, and s38584.
- ITC’99: Including b10, b12, b15, and b19.
- Encryption Schemes: They targeted two representative state-of-the-art sequential encryption methods: HARPOON and Interlocking.
Key Insights and Ideas
- Simulation is Cheaper than Solving: The "aha moment" is realizing that logic simulation (to find FC) is computationally "cheap," while SAT solving and model checking are "expensive." By using simulation to "scout" the right depth, the attack avoids the trial-and-error overhead of previous methods.
- Monotonicity of Corruptibility: The paper proves that FC is monotonic—it only stays the same or increases as you unroll. This mathematical property makes it a reliable indicator for when to stop unrolling.
- Bridging Statistics and Logic: Fun-SAT successfully bridges the gap between statistical observation (corruptibility) and formal logic (SAT pruning), showing that a plateau in the former implies a plateau in the latter.
Key Results
- Massive Speedup: Fun-SAT is, on average, 90x faster than previous sequential SAT attacks.
- Higher Success Rate: In a one-day timeout test, Fun-SAT failed on only 0.7% of experiments, whereas the previous state-of-the-art attack timed out 19% of the time.
- Case Study Efficiency: On the large
s38584benchmark encrypted with the Interlocking scheme, Fun-SAT found the correct key in about 507 seconds. The reference attack took 2.64 hours—nearly 19 times longer.
Limitations and Future Work
- Unknown Key Length ($t_k$): The current formulation assumes the attacker knows the length of the key sequence. While the authors suggest that the initial state can be treated as part of the key to bypass this, more explicit handling of unknown $t_k$ could be a future refinement.
- Advanced SAT Tactics: The authors note that Fun-SAT could be further improved by integrating more advanced SAT-solving strategies, such as incremental SAT-solving (e.g., KC2).
- Resilient Encryption: The work serves as a benchmark for designers; future encryption schemes will likely need to find ways to force the required unrolling depth to astronomical levels to remain resilient against FC-guided attacks.
Summary updated