TL;DR
This paper introduces "Anti-SAT," a novel circuit block designed to thwart the SAT attack, a potent method for deciphering logic-locked integrated circuits. By exponentially increasing the complexity of the SAT attack, Anti-SAT makes it computationally infeasible to extract the secret key, thereby enhancing the security of outsourced IC designs.
What Problem Does This Paper Address?
The increasing trend of outsourcing Integrated Circuit (IC) design and fabrication to untrusted foundries presents significant security risks. These risks include intellectual property (IP) piracy and counterfeiting. Logic locking is a technique proposed to mitigate these threats by embedding a secret key that controls the IC's functionality. However, a recent attack, the "SAT attack," has demonstrated the ability to efficiently break many existing logic locking schemes by iteratively solving SAT formulas. This attack leverages a small set of input-output pairs from an activated chip to deduce the correct key. The paper addresses the critical need for more robust logic locking mechanisms that can withstand this powerful SAT attack.
Methods
The core contribution of this paper is the Anti-SAT block, a lightweight circuit component designed to be integrated into a logic-locked design. The Anti-SAT block works by increasing the number of iterations required by the SAT attack. It achieves this by introducing additional key-controlled logic that, when combined with the original locked circuit, makes it exponentially harder for SAT solvers to find distinguishing input-output pairs.
The Anti-SAT block is constructed using two logic blocks, $g$ and $\bar{g}$ (complementary functions), each controlled by a set of key inputs. These blocks are combined (e.g., via an AND gate in the proposed configuration) to produce an output. A key property is that when the correct key is applied, the Anti-SAT block produces a constant output, thus not affecting the original circuit's functionality. When an incorrect key is used, it can produce varying outputs, which is crucial for the SAT attack's iterative process.
To prevent attackers from easily identifying and removing the Anti-SAT block, the authors propose obfuscation techniques. These include:
- Functional Obfuscation: Modifying the internal logic of $g$ and $\bar{g}$ with additional key-gates to obscure their complementary nature and make simulation-based analysis difficult.
- Structural Obfuscation: Using MUX-based logic locking to increase the inter-connectivity between the Anti-SAT block and the main circuit, making it harder for partitioning algorithms to isolate the Anti-SAT block.
Datasets
The paper evaluates its proposed Anti-SAT block on standard benchmark circuits from the ISCAS85 and MCNC suites. Specific circuits mentioned include c1355, c1908, c3540, dalu, and des. No new benchmarks were introduced.
Key Insights and Ideas
- Exponential Increase in Attack Complexity: The primary insight is that by carefully designing the Anti-SAT block, the number of SAT attack iterations can be made an exponential function of the key size, rendering the attack computationally infeasible.
- Lightweight Solution: Unlike previous proposals that used large, performance-impacting circuits (like AES), the Anti-SAT block is designed to be lightweight, offering a more practical solution.
- Importance of Obfuscation: The effectiveness of the Anti-SAT block is significantly enhanced by obfuscation techniques. Without them, an attacker could potentially identify and remove the block, negating its security benefits.
- Trade-off between Security and Overhead: The paper demonstrates a clear trade-off: a slight increase in area overhead (due to the Anti-SAT block and obfuscation) leads to a dramatic increase in SAT attack complexity.
- Impact of $p$ (Output-One Count): The security of the Anti-SAT block is highly sensitive to the output-one count ($p$) of the underlying function $g$. Maximum security is achieved when $p$ is very close to 1 or $2^n-1$, making the SAT attack require an exponential number of iterations.
Key Results
- The proposed Anti-SAT block, when integrated into logic-locked circuits, significantly increases the number of SAT attack iterations required to find the correct key.
- For a 14-bit obfuscated Anti-SAT block, the SAT attack fails to unlock circuits within a 10-hour timeout, even with a 10-bit obfuscated Anti-SAT block (koa = 40 bits).
- Experimental results show that for configurations with Anti-SAT blocks, the SAT attack complexity grows exponentially with the key size, whereas traditional logic locking (TOC13) is easily broken regardless of key size.
- Secure integration of the Anti-SAT block (connecting its inputs to primary inputs and its output to a highly observable wire) provides better security than random integration.
- Obfuscation techniques, particularly the use of MUXes to increase inter-connectivity, are crucial for preventing attackers from isolating and removing the Anti-SAT block.
Limitations and Future Work
- Area Overhead: While considered lightweight compared to AES, the Anti-SAT block and its obfuscation do introduce area, power, and delay overhead. The paper shows that even a slight increase in area overhead can yield significant security benefits.
- Obfuscation Complexity: The effectiveness of obfuscation techniques depends on the attacker's ability to estimate the Anti-SAT block's size. The paper explores this by assuming an area estimation error.
- Future Work: The paper suggests that further research could explore different constructions of the $g$ function and investigate the impact of Anti-SAT block location on overall security more extensively. The authors also mention that conventional logic locking techniques should be combined with Anti-SAT for foolproof security.
Summary updated