GF-Flush: A GF(2) Algebraic Attack on Secure Scan Chains

Dake Chen, Chunxiao Lin, Peter A. BeerelarXiv 2021 · arXiv

Abstract

Modern integrated circuits utilize secure scan chains to protect internal states from unauthorized access while maintaining testability. However, many of these defenses rely on linear dynamic obfuscation. This paper presents GF-Flush, a highly efficient algebraic attack that models these hardware defenses as a system of linear equations over the finite field GF(2). By exploiting the inherent linearity of XOR-based obfuscation and Linear Feedback Shift Registers (LFSRs), GF-Flush recovers secret keys up to 100x faster than previous SAT-based methods, successfully cracking 500-bit keys in under 7 seconds.

Introduction

Scan chains are essential for post-fabrication testing, providing a "backdoor" for engineers to verify circuit logic. Unfortunately, this visibility also exposes chips to Intellectual Property (IP) piracy and malicious hardware Trojans. To mitigate these risks, the industry has adopted dynamic obfuscation. This technique typically uses an LFSR to generate a pseudo-random key that flips bits within the scan chain, effectively scrambling the data. While SAT (Satisfiability) solvers have been used to attack these defenses, they become computationally prohibitive as logic complexity increases. GF-Flush addresses this by asking a fundamental question: Is there a direct mathematical way to unscramble this data?

The GF-Flush Methodology

The core insight of GF-Flush is that most scan-chain defenses—including those using shadow chains and Multiple-Input Signature Registers (MISRs)—rely on XOR gates and linear shift registers. These operations are perfectly described by GF(2) algebra, where addition corresponds to the XOR operation.

Flowchart of the GF-Flush algebraic attack process.

The attack proceeds in four primary stages:

  1. Flushing: The attacker shifts a sequence of all zeros into the scan chain. This ensures that any non-zero output is a direct result of the obfuscation key, simplifying the resulting equations.
  2. Matrix Modeling: The LFSR state transitions and scan chain logic are represented as matrices. A symbolic expression is derived for the output bits based on the unknown initial LFSR "seed."
  3. Solving the System: By observing a sufficient number of output bits, the attacker constructs a system of linear equations ($As = o$). This system can be solved rapidly using standard techniques like Gaussian elimination.
  4. Bypassing Advanced Defenses: The attack circumvents "shadow chains" by ignoring the initial propagation cycles. It also incorporates MISR-based test compression into the linear model, treating the compression logic as part of the solvable equation rather than an obstacle.

Experimental Evaluation

The effectiveness of GF-Flush was evaluated using simulated secure scan chains with key lengths ($\lambda$) ranging from 3 to 500 bits. The experiments also considered various MISR configurations (register lengths $h = 8, 16, 32, 64$) to measure the impact of test compression. All tests were conducted on a standard desktop environment (Intel i7-8700 CPU, 16-GB RAM) using MATLAB.

Key Results and Scalability

GF-Flush demonstrates a massive jump in efficiency over generic logic solvers. Because it exploits the specific mathematical structure of the hardware, its complexity scales as a low-degree polynomial ($O(\lambda^3)$), whereas SAT-based attacks often scale exponentially.

  • Performance: For a 500-bit key, GF-Flush recovers the secret in less than 7 seconds. In contrast, SAT attacks on similar defenses can take nearly an hour for significantly smaller keys.
  • Success Rate: The attack recovered a unique, correct seed in 87% of random configurations. In the remaining cases, it reduced the search space to a small "null space" manageable via brute force.
  • Impact of Compression: While MISRs reduce the equations available per clock cycle, the attack remains viable, cracking 250-bit keys in under 8 hours even with heavy compression.
Attack runtime vs. LFSR length for various MISR configurations.

Conclusion

GF-Flush proves that linearity is a critical vulnerability in current secure scan chain designs. While dynamic obfuscation appears random, its underlying mathematical structure allows for rapid algebraic recovery of secret keys. The primary limitation of this attack is its reliance on linear logic; the use of Non-Linear Feedback Shift Registers (NLFSRs) or non-linear gates would break the current GF(2) model. Future research should focus on developing non-linear hardware defenses and exploring more sophisticated algebraic attacks capable of handling non-linear obfuscation logic.

Summary updated

Abstract

Scan chains provide increased controllability and observability for testing digital circuits. The increased testability, however, can also be a source of information leakage for sensitive designs. The state-of-the-art defenses to secure scan chains apply dynamic keys to pseudo-randomly invert the scan vectors. In this paper, we pinpoint an algebraic vulnerability of these dynamic defenses that involves creating and solving a system of linear equations over the finite field GF(2). In particular, we propose a novel GF(2)-based flush attack that breaks even the most rigorous version of state-of-the-art dynamic defenses. Our experimental results demonstrate that our attack recovers the key as long as 500 bits in less than 7 seconds, the attack times are about one hundredth of state-of-the-art SAT based attacks on the same defenses. We then demonstrate how our attacks can be extended to scan chains compressed with Multiple-Input Signature Registers (MISRs).
BibTeX
@misc{chen2021gf,
  author = {Dake Chen and Chunxiao Lin and Peter A. Beerel},
  title = {{GF-Flush: A GF(2) Algebraic Attack on Secure Scan Chains}},
  year = {2021},
  eprint = {2101.12279},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.12279},
}
Figure