Formal Analysis of Galois Field Arithmetic Circuits-Parallel Verification and Reverse Engineering

Cunxi Yu, Maciej J. Ciesielski

TL;DR

This paper introduces a novel parallel computer algebra technique for formally verifying and reverse-engineering Galois Field (GF) arithmetic circuits, specifically GF(2^m) multipliers. By analyzing gate-level netlists without prior knowledge of input/output bit positions or the irreducible polynomial, the method efficiently extracts the circuit's functionality and underlying mathematical parameters, achieving significant speedups over existing approaches.

What Problem Does This Paper Address?

Formal verification of arithmetic circuits, especially those operating over finite fields like Galois Fields (GF), is notoriously challenging. Unlike standard integer arithmetic, GF operations are defined modulo an irreducible polynomial, adding a layer of complexity. Existing formal verification methods for GF circuits often require prior knowledge of the circuit's internal structure, including the bit positions of inputs and outputs, and crucially, the specific irreducible polynomial used. This makes them impractical for reverse-engineering scenarios or when dealing with complex, synthesized circuits where this information might be lost or unknown. The paper tackles this gap by proposing a method that can perform verification and reverse-engineering directly from the gate-level netlist, without needing these critical pieces of information upfront.

Methods

The core of the proposed method is a parallel backward rewriting technique based on computer algebra. It operates on the gate-level netlist of a GF(2^m) multiplier and proceeds in four main steps:

  1. Convert Netlist to Equations: The gate-level netlist is translated into a set of algebraic equations representing the logic gates, using a defined algebraic model for GF(2^m) operations (modulo 2 arithmetic for XOR, etc.).
  2. Generate Signatures: The output signature of the GF(2^m) multiplier is split into individual signatures for each output bit. This allows for parallel processing.
  3. Parallel Extraction: Algorithm 1, a backward rewriting process, is applied in parallel to each output bit's signature. This iteratively substitutes gate outputs with their algebraic expressions, simplifying terms modulo 2. This step is crucial for extracting the algebraic expression of each output bit.
  4. Finalization: The extracted algebraic expressions for each output bit are combined to form the final specification of the circuit.

For reverse engineering, the approach extends this by:

  • Output Encoding Determination: Analyzing the extracted algebraic expressions to identify unique "in-field product sets," which reveal the bit positions of the outputs.
  • Input Encoding Determination: Using the in-field product sets and properties of GF multiplication to deduce the bit positions of the input variables.
  • Irreducible Polynomial Extraction: Leveraging the identified input/output bit positions and the first "out-of-field product set" to extract the irreducible polynomial used in the circuit.

The parallelism is achieved by distributing the extraction of each output bit's algebraic expression across multiple threads.

Datasets

The paper evaluates its approach on synthesized Mastrovito and Montgomery multipliers. These are standard GF(2^m) multiplier architectures. The multipliers are taken from existing benchmarks and mapped to gate-level implementations using the ABC synthesis tool. The bit-widths vary significantly, up to 571 bits for Mastrovito and 283 bits for Montgomery multipliers. The experiments also involve multipliers constructed with different irreducible polynomials, including NIST-recommended ones.

Key Insights and Ideas

  • Parallelism is Key: The inherent parallelism in GF arithmetic (where output bits can often be computed independently) is exploited to achieve significant speedups by processing output bits in parallel.
  • No Prior Knowledge Needed: The method's ability to reverse-engineer the irreducible polynomial and input/output bit positions directly from the gate-level netlist is a major breakthrough, removing a significant barrier for verification and analysis.
  • Algebraic Rewriting as a Powerful Tool: The use of computer algebra and backward rewriting proves highly effective for manipulating and simplifying complex GF arithmetic expressions.
  • Irreducible Polynomial Matters: The choice of irreducible polynomial significantly impacts both the circuit's complexity (number of gates) and the time required for verification. Trinomials generally lead to simpler circuits and faster verification than pentanomials.
  • Synthesis Can Help Verification: Counter-intuitively, for GF circuits, bit-optimized synthesized netlists can sometimes be easier to verify than their original forms, as optimization can reduce the complexity of the logic cones involved in function extraction.

Key Results

The paper demonstrates substantial performance improvements:

  • Verification Speedup: The parallel approach achieves significant speedups compared to prior work (specifically reference [6]). For Mastrovito multipliers, speedups of up to 44.3x were observed with 30 threads. For Montgomery multipliers, speedups of up to 17.4x were achieved.
  • Scalability: The method successfully verifies large multipliers (up to 571-bit Mastrovito) within reasonable time limits (1.5 hours), whereas previous methods failed after 12 hours.
  • Reverse Engineering Efficiency: The reverse engineering process, which includes extracting the irreducible polynomial and input/output bit positions, is also efficient. For example, analyzing extracted expressions for reverse engineering takes less than 10% of the time spent on extraction itself.
  • Impact of Synthesis: Synthesized GF multipliers were verified much faster (e.g., a 283-bit Montgomery multiplier verification dropped from 15,300 seconds to 169.2 seconds, a 90x speedup).

Limitations and Future Work

  • Memory Usage Trade-off: While parallelization improves runtime, it can increase peak memory usage. The paper notes that for very large numbers of threads, memory limitations can become a bottleneck. The optimal number of threads (T) varies and depends on the platform.
  • Complexity of Irreducible Polynomials: The paper highlights that pentanomial irreducible polynomials lead to more complex circuits and longer verification times compared to trinomials.
  • Future Work: The authors suggest extending the work to formal verification of prime field arithmetic circuits and complex cryptography circuits. They also mention that the current work focuses on combinational circuits, implying sequential circuits could be a future direction.

Summary updated

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) 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.
BibTeX
@article{yu2019formal,
  author = {Cunxi Yu and Maciej J. Ciesielski},
  title = {{Formal Analysis of Galois Field Arithmetic Circuits-Parallel Verification and Reverse Engineering}},
  journal = {IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.},
  year = {2019},
  url = {https://openreview.net/forum?id=7T6m8Y4-hUz},
}
Figure