Abstract: Galois field (GF) arithmetic circuits find numerous applications in communications, signal processing, and security engineering. Formal verification techniques of GF circuits are scarce and limited to circuits with known bit positions of the primary inputs and outputs. They also require knowledge of the irreducible polynomial $P(x)$, which affects final hardware implementation. This paper presents a computer algebra technique that performs verification and reverse engineering of GF($2^m$) multipliers directly from the gate-level implementation. The approach is based on extracting a unique irreducible polynomial in a parallel fashion and proceeds in three steps: 1) determine the bit position of the output bits; 2) determine the bit position of the input bits; and 3) extract the irreducible polynomial used in the design. We demonstrate that this method is able to reverse engineer GF($2^m$) multipliers in m threads. Experiments performed on synthesized Mastrovito and Montgomery multipliers with different $P(x)$, including NIST-recommended polynomials, demonstrate high efficiency of the proposed method.
Introduction
Galois Field ($GF(2^m)$) arithmetic serves as the mathematical foundation for Elliptic Curve Cryptography (ECC) and high-speed communication protocols. Ensuring the correctness of these circuits is paramount for security. However, verifying that a gate-level netlist accurately implements its mathematical specification is a significant challenge. Traditional formal verification tools, such as SAT solvers and Binary Decision Diagrams (BDDs), suffer from state-space explosion when applied to large-scale multipliers.
The Verification Bottleneck
Existing algebraic methods offer better scalability than SAT solvers but remain limited by their serial nature and reliance on metadata. Typically, these tools require knowing the exact bit-mappings for inputs and outputs, as well as the specific irreducible polynomial $P(x)$ used in the design. In scenarios involving third-party IP verification or hardware security audits, this information is often unavailable, rendering standard tools ineffective.
Parallel Algebraic Rewriting
The core innovation presented in this research is a method for Parallel Function Extraction. Unlike integer multipliers, where carries create complex inter-dependencies, the authors demonstrate that the algebraic expressions for individual output bits in a GF multiplier can be extracted independently.
By distributing the rewriting process across multiple CPU threads, the tool can process large circuits with near-linear speedup. This approach allows the system to handle "blind" netlists where the internal structure is flattened and bit positions are unknown.
Reverse Engineering Flow
The proposed technique follows a three-step process to analyze a raw netlist:
- Output Bit Identification: The system distinguishes bit positions (e.g., LSB vs. MSB) by analyzing the complexity of the extracted polynomials.
- Input Bit Mapping: A recursive algorithm identifies which input wires correspond to specific mathematical bit positions.
- Polynomial Extraction: By identifying "out-of-field" terms—products reduced during the design phase—the tool reconstructs the original irreducible polynomial $P(x)$.
Experimental Results
The methodology was evaluated on standard Mastrovito and Montgomery multiplier architectures, including those using NIST-recommended polynomials. The results demonstrate a significant breakthrough in scalability:
- Performance: For 571-bit multipliers (standard for high-security ECC), the parallel approach achieved a 44x speedup over state-of-the-art serial methods.
- Efficiency: While previous methods timed out after 18 hours, this tool completed the verification of a 1.6-million-gate circuit in approximately 1.4 hours using 30 threads.
- Robustness: The tool successfully reverse-engineered bit-mappings and polynomials even from "bit-blasted" netlists that lacked hierarchical information.
Conclusion
This research provides a scalable solution for the formal verification and reverse engineering of complex GF arithmetic circuits. By leveraging the inherent independence of GF output bits, the parallel algebraic rewriting technique overcomes the limitations of serial processing and metadata requirements. Future work aims to extend these methods to prime fields ($GF(p)$) and sequential logic components.
Summary updated