Abstract
FISCHER is an automated verification tool designed to ensure the functional correctness of masked cryptographic implementations. Masking is a critical defense against side-channel attacks, but its implementation is error-prone. FISCHER addresses the scalability issues of traditional SMT solvers by integrating a specialized Term Rewriting System (TRS) for Galois fields of characteristic 2 with symbolic execution. Our evaluation shows that FISCHER scales to masking orders as high as 100, significantly outperforming existing tools and identifying previously unknown flaws in peer-reviewed cryptographic schemes.
Introduction
In modern cryptography, masking is a standard countermeasure against power-based side-channel attacks. By splitting secret values into multiple random shares (e.g., $x = x_0 \oplus x_1 \oplus \dots \oplus x_d$), implementations can prevent an attacker from learning sensitive information through power consumption analysis. However, implementing masked versions of non-linear operations, such as S-Boxes or finite-field multiplications, is complex and highly susceptible to functional errors.
Problem Statement
The core challenge in verifying masked programs is proving functional equivalence: ensuring that a randomized, multi-share implementation produces the same mathematical result as its unmasked counterpart. Existing formal verification methods face significant hurdles:
- SMT Solvers: General-purpose solvers suffer from "state explosion" when handling bitwise XOR operations and lack native support for finite-field arithmetic.
- Computer Algebra Systems: These often lack the specific transformations required for the affine operations common in cryptographic code.
The FISCHER Framework
The authors introduce FISCHER, a multi-tiered verification tool integrated into the LLVM ecosystem. The framework's architecture is designed to handle the complexities of cryptographic masking through a specialized pipeline.
The FISCHER pipeline consists of several key components:
- Symbolic Execution: Utilizing the LLVM framework, FISCHER translates C programs into symbolic expressions.
- Term Rewriting System (TRS): This is the primary innovation. The TRS employs a set of algebraic rules specifically tailored for Galois fields of characteristic 2 ($GF(2^n)$). It attempts to reduce the symbolic difference between the masked and unmasked programs to a normal form. If the result is zero, equivalence is proven.
- Affine Constant Computing: The tool automatically derives constants for affine transformations (e.g., shifts and rotations), treating them as uninterpreted functions to simplify the verification process.
- Fallback Mechanisms: When the TRS is inconclusive, FISCHER employs random testing to search for counterexamples and uses SMT solvers (like Z3 or Boolector) for final rigorous verification.
Evaluation and Results
FISCHER was evaluated against a variety of cryptographic benchmarks, including masked multiplication schemes (ISW, HPC1, HPC2, DOM, CMS), AES/PRESENT S-Boxes, and Boolean-to-Arithmetic masking conversions.
Key Findings
- Scalability: FISCHER successfully verified masked multiplications with a masking order of 100 in under 153 seconds. Competing tools like SMACK, SeaHorn, and CryptoLine typically timed out at masking orders as low as 3.
- Bug Discovery: FISCHER identified a critical flaw in a parallelized multiplication scheme from EUROCRYPT 2017. The bug, which occurs when the masking order $d \equiv 1 \pmod 4$, had remained undetected for six years.
- TRS Efficiency: The specialized TRS was capable of proving the majority of benchmarks without needing to resort to computationally expensive SMT solving.
Conclusion and Future Work
FISCHER demonstrates that specialized term rewriting, combined with symbolic execution, can overcome the scalability barriers of traditional verification tools in the domain of cryptographic masking. While currently optimized for $GF(2^n)$, future work includes extending the TRS to support other fields and rings, potentially broadening its application to general-purpose libraries like OpenSSL.
Summary updated