When Alice meets the ``Hardware'' Bob --- Attacks and Solutions in the Digital World

Abstract

Modern cryptography and the digital world (CMOS mainly) have been advancing side-by-side. Although cryptographic algorithms only need to be proven with theoretical soundness, cryptographic engineering on digital device requires more efforts to achieve a secure implementation than simply just design theories. Although properties like energy-efficiency, low-latency, and minimal area overhead are desired in hardware-based implementations for cryptographic modules, they could potentially weaken the theoretical justification of cryptosystems, where adversaries can break the secret key inside the hardware.

In this dissertation, we develop novel attack to uniquely determine the secret key for hardware implementation of GIFT-COFB, one of the ten finalists for National Institute of Standards and Technology (NIST) Lightweight Cryptography Standardization Process. The 2-round partial unrolled design of GIFT-COFB is shown to be the most energy-efficient among all other $r$-round partial unrolling and fully unrolled settings. Our proposed chosen-plaintext attack can effectively break the master key $K$ on this 2-round partial unrolled GIFT-COFB. In addition, we present two chosen-plaintext attacks on multicycle AES implementations with fault-based attacks. Both attacks on GIFT-COFB and multicycle AES include explanations from algebraic cryptanalysis perspective.

In parallel, the adoption of horizontal business models in semiconductor manufacturing is negatively affected by the overproduction of integrated circuits (ICs) and the piracy of intellectual properties (IPs), which compromised the integrity of the digital world's semiconductor supply chain. Logic locking emerges as a primary design-for-security measure to counter these threats, where ICs become fully functional only when unlocked with a secret key. However, Boolean satisfiability-based attacks have rendered most locking schemes ineffective. This gives rise to numerous defenses and new locking methods to achieve SAT resiliency. Subsequent attacks have been proposed to target these newly proposed solutions. The reasons behind the effectiveness of SAT attack and the following SAT-based attack have yet to be explored. In this dissertation, we provide a unique perspective on SAT attack efficiency based on conjunctive normal form (CNF) stored in SAT solver. We demonstrate how this attack learns new relations between keys in every iteration using distinguishing input patterns and the corresponding oracle responses. Each input-output pair gives additional CNF clauses of unknown keys to be appended to SAT formulation, which leads to an exponential reduction in incorrect key values. Overall, SAT attack is shown to break most locking scheme within the linear iteration complexity of key size. Our analysis provides a new perspective on the capabilities of SAT attack against multiplier benchmark c6288 with possibly new directions to achieve SAT resiliency.

In the digital world, it is also crucial to reduce manufacturing defect escapes in today's safety-critical applications requires increased fault coverage. However, generating a test set using commercial automatic test pattern generation (ATPG) tools that lead to zero-defect escape is still an open problem. It is challenging to detect all stuck-at faults to reach 100\% fault coverage. It remains challenging to detect hard-to-detect and redundant faults for large VLSI circuits. More optimization needs to be done as undetected faults still exist under the state-of-the-art commercial ATPG tools. Rather than attacking logic locking with SAT solvers, in this dissertation, we propose a novel test pattern generation approach constructively using the powerful SAT attack on logic locking. A stuck-at fault is modeled as a locked gate with a secret key, where it can effectively deduce the satisfiable assignment with reduced backtracks under key initialization of the SAT attack. The input pattern that determines the key is a test for the stuck-at fault. We propose two different approaches for test pattern generation. First, a single stuck-at fault is targeted, and a corresponding locked circuit with one key bit is created. This approach generated one test pattern per fault. We also consider a group of faults and convert the circuit to its locked version with multiple key bits. The inputs obtained from the SAT attack tool are the test set for detecting this group of faults. Our approach finds test patterns for all hard-to-detect faults that were previously undetected in commercial ATPG tools. The proposed test pattern generation approach can efficiently detect redundant faults with ITC'99 benchmarks. The results show that we can detect all the hard-to-detect faults and identify redundant faults, and a 100\% stuck fault coverage is achieved.

Finally, we consider privacy-enhancing solutions to offer additional benefits for securing the digital world. In this dissertation, we develop an efficient, secure, and on-demand communication protocol using zero-knowledge proofs (ZKPs) that allow the prover to provide evidence of its secret without revealing that to the verifier. The edge device, acting as the prover, convinces the central server, the verifier, of the unique PUF response stored inside the device without requiring the actual storage of PUF responses on the server. The non-interactive characteristic of zk-SNARK, Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, offers better optimization to authentication frequency, communication bandwidth between device and server, and protection of device-specific secret, all of which contribute to constructing our proposed device authentication framework.