Stripped Functionality Logic Locking With Hamming Distance-Based Restore Unit (SFLL-hd) - Unlocked

Logic locking is a technique that has received significant attention. It protects a hardware design netlist from a variety of hardware security threats, such as tampering, reverse-engineering, and piracy, stemming from untrusted chip foundry and end-users. This technique adds logic and inputs to a given design netlist to make sure that the locked design is functional only when a key is applied from the new inputs; an incorrect key makes the design produce incorrect outputs. The new inputs, referred to as the key inputs, are driven by a tamper-proof memory on the chip, which stores the secret key. Research in this field has shown that this technique, if not implemented properly, may be vulnerable to attacks that extract the key of logic locking. Recently, a logic locking technique called stripped functionality logic locking (SFLL) has been proposed and shown to withstand all known attacks in a provably secure manner. SFLL strips some functionality from the original design by corrupting its output corresponding to a number of protected input patterns. In one version of SFLL, referred to as SFLL-hd, these protected patterns are all of a certain hamming distance h to the key. The modified design is accompanied by additional logic that fixes the output for each protected input pattern only when the key is in the tamper-proof memory. In this paper, we present an attack that breaks SFLL-hd within a minute. Our attack exploits structural traces left behind in the locked design due to the functionality strip operation and is capable of identifying some of the protected patterns. We also present a theoretical framework that helps us develop two different techniques to complete our attack. In the first technique, we use the Gaussian elimination technique to solve a system of equations that we form based on k-identified protected patterns in O(k(3)) time in the best case, where k is the number of key bits in key. The second technique uses one identified protected pattern to query the oracle k times. In both techniques, we successfully recover the key from the protected pattern(s). We show that our attacks work on the SFLL-locked microprocessor design (more than 50 K gates) that the authors of SFLL made available to the public; we extract the 256-bit key within a minute and reveal it in this paper. We also test our attacks on a few other SFLL-hd benchmarks provided by SFLL authors.