ORACALL: An Oracle-Based Attack on Cellular Automata Guided Logic Locking

Abstract

In logic locking, the finite-state machine (FSM) embedded in a sequential circuit is often chosen to be obfuscated. Such an obfuscation scheme using a class of nongroup additive cellular automata (CA) called D1∗CA and D1∗CAdual to obfuscate each state transition of an FSM has been proposed previously. Since D1∗CA and D1∗CAdual provide high testability even in the absence of scan-based design-for-testability techniques, they conceal the sequential elements, thus thwarting several existing scan-chain attacks. In this article, we introduce a novel attack to extract the secret key used to obfuscate each state transition of the FSM, by utilizing the information leaked by the leftmost CA cell, which is obtained via an oracle query to the obfuscated circuit. The proposed attack has two variants: 1) when the combinational circuit of the Interrupt Logic is not logic encrypted and 2) when the Interrupt Logic is logic encrypted with a k -bit key. The first attack variant has a complexity of O(n⋅m) , where n denotes the number of transitions in the FSM, and m denotes the maximum transition cycle length of the underlying D1∗CA . The second attack variant has a complexity of O(n⋅qmax) , where qmax denotes the maximum number of oracle queries (equal to the number of primary inputs involved in that state transition), followed by a SAT-attack to extract the k -bit key of the corresponding Interrupt Logic. The experimental evaluation of the attack on CA-based obfuscated benchmark circuits establishes the effectiveness of our proposed attack.