CryptoMiniSat

CryptoMiniSat is an open-source extension of the Minisat SAT solver designed to efficiently handle formulas that include XOR constraints. It is particularly well suited for cryptanalytic problems where many relations are expressed as XOR (parity) equations, enabling faster solving of cryptographic instances than traditional CNF-only SAT solvers.

The solver combines a conventional conflict-driven clause learning (CDCL) core with a Gaussian-elimination based XOR solver. XOR constraints are represented as linear equations over the finite field GF(2) and managed by a dedicated propagator and learning mechanism. By integrating CNF clauses with XOR equations, CryptoMiniSat can perform propagation, conflict analysis, and learning across both representations. The architecture supports incremental solving, assumptions, and standard preprocessing to simplify formulas before search.

Applications and usage often focus on cryptography, including algebraic and parity-based attacks against block and stream ciphers, as well as other cryptographic verification tasks that yield large, structured SAT instances. Researchers use CryptoMiniSat to exploit xor-rich formulations that arise from cryptographic models, achieving improved performance on relevant benchmarks compared with purely CNF-based solvers.

History and availability: CryptoMiniSat originated within the MiniSat ecosystem and has evolved through ongoing contributions from researchers and developers. It is distributed as open-source software and is hosted on public code repositories, with multiple releases and forks that reflect ongoing development and community use.