Fun-SAT: Functional Corruptibility-Guided SAT-Based Attack on Sequential Logic Encryption

Yinghua Hu, Yuke Zhang, Kaixin Yang, Dake Chen, Peter A. Beerel, Pierluigi Nuzzo

Abstract

The SAT attack has shown to be efficient against most combinational logic encryption methods. It can be extended to attack sequential logic encryption techniques by leveraging circuit unrolling and model checking methods. However, with no guidance on the number of times that a circuit needs to be unrolled to find the correct key, the attack tends to solve many time-consuming Boolean satisfiability (SAT) and model checking problems, which can significantly hamper its efficiency. In this paper, we introduce Fun-SAT, a functional corruptibility-guided SAT-based attack that can significantly decrease the SAT solving and model checking time of a SAT-based attack on sequential encryption by efficiently estimating the minimum required number of circuit unrollings. Fun-SAT relies on a notion of functional corruptibility for encrypted sequential circuits and its relationship with the required number of circuit unrollings in a SAT-based attack. Numerical results show that Fun-SAT can be, on average, 90x faster than previous attacks against state-of-the-art encryption methods.

Introduction

Logic encryption is a critical hardware security technique designed to protect integrated circuits (ICs) from intellectual property theft and unauthorized tampering. While combinational logic encryption has been extensively studied and largely compromised by Boolean satisfiability (SAT) attacks, sequential logic encryption—which incorporates state machines and temporal transitions—presents a more significant challenge for attackers.

The Challenge of Unrolling

To attack a sequential circuit, it must typically be "unrolled." This process transforms the sequential behavior into a large combinational circuit representing the original's logic over multiple clock cycles.

Sequential circuit unrolling process.

The primary bottleneck in sequential SAT attacks is determining the optimal unrolling depth. If the depth is too shallow, the SAT solver identifies "spurious" keys that satisfy the logic for a few cycles but fail in actual operation. Conversely, excessive unrolling leads to a combinatorial explosion in circuit complexity, causing SAT solvers and model checkers to time out. Traditional attacks iteratively increment the depth, leading to redundant and computationally expensive solving cycles.

Fun-SAT Methodology

Fun-SAT (Functional Corruptibility-Guided SAT-Based Attack) addresses this inefficiency by replacing blind iteration with guided estimation. The core innovation is the use of Functional Corruptibility (FC).

Functional Corruptibility (FC)

FC is a statistical measure quantifying how much an incorrect key corrupts the circuit's output. It is defined as the ratio of corrupted output values to the total number of possible input and key combinations at a given unrolling depth.

Calculation of Functional Corruptibility (FC) across different unrolling depths.

The attack proceeds in two main phases:

  1. Analysis Phase: Fun-SAT performs rapid logic simulations to calculate FC at increasing unrolling depths. The authors demonstrate that FC is monotonic—it only increases or stays constant as the circuit is unrolled further.
  2. Prediction and SAT Phase: By identifying a plateau in the FC (where the metric stops increasing significantly), Fun-SAT estimates the minimum required unrolling depth. Once this depth is reached, it performs a single targeted SAT attack followed by formal model checking to verify the candidate key.

Key Results and Insights

The efficiency of Fun-SAT stems from the realization that logic simulation is computationally "cheap" compared to the "expensive" nature of SAT solving and model checking. By using simulation to "scout" the optimal depth, the attack avoids the trial-and-error overhead of previous methods.

Experimental evaluations using ISCAS’89 and ITC’99 benchmarks against state-of-the-art encryption methods like HARPOON and Interlocking yielded impressive results:

  • 90x Average Speedup: Fun-SAT significantly outperforms previous sequential SAT attacks.
  • Improved Reliability: In a one-day timeout test, Fun-SAT failed on only 0.7% of experiments, compared to a 19% failure rate for previous state-of-the-art methods.
  • Scalability: On the large s38584 benchmark, Fun-SAT reduced the attack time from 2.64 hours to just 507 seconds.

Conclusion

Fun-SAT successfully bridges the gap between statistical observation and formal logic. By leveraging the monotonicity of functional corruptibility, it provides a reliable indicator for when to stop unrolling, drastically reducing the computational burden of sequential logic attacks. While future work may address unknown key sequence lengths or integrate advanced incremental SAT strategies, Fun-SAT currently sets a new benchmark for the efficiency of hardware security analysis.

Summary updated

Abstract

The SAT attack has shown to be efficient against most combinational logic encryption methods. It can be extended to attack sequential logic encryption techniques by leveraging circuit unrolling and model checking methods. However, with no guidance on the number of times that a circuit needs to be unrolled to find the correct key, the attack tends to solve many time-consuming Boolean satisfiability (SAT) and model checking problems, which can significantly hamper its efficiency. In this paper, we introduce Fun-SAT, a functional corruptibility-guided SAT-based attack that can significantly decrease the SAT solving and model checking time of a SAT-based attack on sequential encryption by efficiently estimating the minimum required number of circuit unrollings. Fun-SAT relies on a notion of functional corruptibility for encrypted sequential circuits and its relationship with the required number of circuit unrollings in a SAT-based attack. Numerical results show that Fun-SAT can be, on average, 90x faster than previous attacks against state-of-the-art encryption methods, when both attacks successfully complete before a one-day time-out. Moreover, Fun-SAT completes before the time-out on many more circuits.
BibTeX
@inproceedings{hu2021fun,
  author = {Yinghua Hu and Yuke Zhang and Kaixin Yang and Dake Chen and Peter A. Beerel and Pierluigi Nuzzo},
  title = {{Fun-SAT: Functional Corruptibility-Guided SAT-Based Attack on Sequential Logic Encryption}},
  booktitle = {HOST},
  year = {2021},
  url = {https://openreview.net/forum?id=luWFXLelA2},
}
Figure