Title : Owning the Truth: Undecidability, unsound kernels, and the forging of proof
Author : endrazine, veorq
|=-----------------------------------------------------------------------=| |=--------------------------=[ OWNING THE TRUTH ]=-----------------------=| |=-----------------------------------------------------------------------=| |=----=[ Undecidability, unsound kernels, and the forging of proof ]=----=| |=-----------------------------------------------------------------------=| |=------------=[ endrazine <[email protected]> ]=--------------=| |=----------------=[ veorq <[email protected]> ]=------------------=| |=-----------------------------------------------------------------------=| --[ Table of contents ]---------------------------------------------------- 0 - Abstract 1 - Introduction 2 - Undecidability: from Cantor to Rice 3 - Programs are proofs. Proofs are programs. 4 - undecidable.c 5 - The escape hatch: verification and the dream of vericoding 6 - A threat model for the formal solver landscape 6.1 - What you are actually trusting 6.2 - The ritual, and why it is load-bearing 6.3 - Adversaries 6.4 - The vulnerability class nobody was naming 7 - Owning the kernel: seven soundness CVEs 7.1 - Extended exhibits: five more proof assistants and a fourth SMT oracle 8 - Owning the Truth: forging the Millennium Problems 8.1 - One kernel lie, statement fidelity separate 8.2 - The exhibits 8.3 - What survives the ritual 8.4 - Lean 4 certificates: P = NP and P != NP from the same CVE 9 - Owning the compiler: backdooring CompCert 10 - Owning the runtime: pure Lean to code execution 11 - Owning the crypto: sabotaging Fiat-Crypto 12 - Conclusion 12.1 - Process, regulation, and limits 12.2 - Recommendations 13 - References --[ 0 : Abstract ]--------------------------------------------------------- We present results that highlight the limits of what can be computed and proven: 1. A constructive reduction to Rice's theorem, a fundamental result of computability theory stating that all non-trivial semantic properties of programs are undecidable. The reduction fits in 1911 lines of Rocq, uses no admitted goals or classical axioms, and is relative to an explicit separator-form hypothesis for Hilbert's Tenth Problem. 2. Twelve soundness PoCs against six proof assistants -- Lean 4, Rocq, Agda, Dafny, F*, and Isabelle/HOL -- including seven CVEs (to our knowledge the first assigned to proof-assistant soundness failures) and one live 0-day. A pure-Lean exploit chain from use-after-free to arbitrary code execution via a single `.lean` file -- no `unsafe`, no FFI, no `@[extern]`. A backdoored CompCert whose forged correctness proof the Coq kernel accepts. Forged proofs of five Millennium Problems in both Rocq and Lean 4, including axiom-free `.olean` certificates for both P = NP and P != NP verified by `leanchecker` from the same kernel bug. A sabotaged local fork of Fiat-Crypto. And four SMT-oracle unsoundness exhibits against Z3 and CVC5. 3. An adversarial use of a Rocq bug against formally verified cryptographic code: a modified Fiat-Crypto field multiplier that always returns zero while its original correctness theorem remains accepted. 4. Four SMT oracle soundness failures: `sat` with an invalid model, and `unsat` on a satisfiable nonlinear-real-arithmetic system (the latter confirmed through Verus and Frama-C/WP) in Z3, plus an `unsat` on a satisfiable floating-point rounding constraint in CVC5. Each result comes with a Docker-reproducible PoC, available at https://github.com/endrazine/owning-the-truth. --[ 1 : Introduction ]----------------------------------------------------- Dear reader, Human or Agent, should you have spent some time on Earth around the time when we happened to live ourselves, you will have laid eyes on some form of popular wisdom describing cybersecurity as a cat-and-mouse game: attackers find a trick, defenders learn it, and the cycle repeats. This suggests that perfect defense might be possible -- one sufficiently clever analyzer, capable AI, or quantum algorithm away from victory. It is not. Some questions cannot be decided or computed. And what can be proven isn't always true. This article is about these limits and what happens when we try to build trust beneath them. The first half concerns undecidability: why no machine can systematically determine non-trivial properties of arbitrary programs. The second half concerns prover software: the small kernels we ask to certify the claims that ordinary analysis cannot settle. We attack both ends of the problem -- the theorem and the implementation. They are distinct limits: undecidability does not cause kernel unsoundness. Our first contribution is a constructive, mechanically checked reduction to Rice's theorem from an explicit separator-form premise for Hilbert's Tenth Problem, together with `undecidable.c`: a concrete C implementation of the program family. For each individual input, the program either terminates or it does not -- a definite fact. What is impossible is an algorithm that decides termination for every member of the family. (Undecidability is literal impossibility rather than computational hardness. Complexity asks how long; decidability asks whether at all. Rice's theorem lives in the decidability layer. A quantum computer running for the age of the universe does not decide the halting problem. An AI system that analyzes programs is a program; used as a decision procedure for a non-trivial extensional property, Rice forbids it from being both total and correct. Sound, complete, and always-terminating: pick any two.) The Curry-de Bruijn-Howard correspondence -- proofs as programs, types as propositions -- then crosses from undecidability into verification. If arbitrary programs cannot be analyzed completely, construct them together with proofs and trust a small kernel. That is the theoretically honest escape. In 2026, as large language models flood the world with code no human has read, it is also the fashionable one: "vericoding" [25] sells the proof assistant as the adult in the room. The kernel, not the model, becomes the thing you trust. We are going to attack that trust. A word on what we did and did not do. We did not discover the kernel bugs that we exploit. They were found by maintainers, outside contributors, or AI agents. What we did was reclassify them: we requested CVEs for seven already-reported kernel soundness failures in Lean 4 and Rocq, treating them as integrity violations of the proof-validation trust boundary rather than reliability defects. Seven were granted [16]. To our knowledge they are the first CVEs assigned to proof-assistant soundness failures. Then we weaponized them -- and went further. We built twelve soundness PoCs against six proof assistants (Lean 4, Rocq, Agda, Dafny, F*, and Isabelle/HOL), forged proofs of the Millennium Problems including axiom-free Lean 4 `.olean` certificates for both P = NP and P != NP from the same kernel bug, backdoored CompCert -- the gold-standard formally verified C compiler -- with a forged semantic-preservation proof the Coq kernel accepts, demonstrated a pure-Lean exploit chain from use-after-free to arbitrary code execution via a single auditable `.lean` file, and sabotaged a local fork of Fiat-Crypto. In September 2026, an AI system produced a Lean formalization claiming to resolve the Navier-Stokes Millennium Prize Problem [19], and the reflexive defense was immediate: the proof checks, with clean assumptions. By the end of this article you will know exactly how much that sentence is worth. --[ 2 : Undecidability: from Cantor to Rice ]------------------------------ A golden age of mathematics: in 1874 Cantor [1] proved that the set of real numbers is uncountable and in 1900 Hilbert [2] put twenty-three problems on the table; his tenth asked for an algorithm to decide whether a Diophantine equation has an integer solution, a core of our automated undecidability proof. In 1931 Goedel [3] proved that every consistent, effectively axiomatized formal system expressive enough for basic arithmetic is incomplete; with the usual soundness interpretation, some arithmetical truths are unprovable within it. His second incompleteness theorem says such a consistent system cannot prove its own consistency. Around the same period, the Church-Turing thesis proposed that every effectively calculable function is Turing-computable; the conventional reasonable models of effective computation developed since then compute the same class of functions. In 1936, Turing [4] proved that no algorithm decides, for every program and input, whether that program halts; the Halting Problem is undecidable. In 1953, Rice [5] generalized Turing's result into something that belongs on the wall of every security operations center: Every non-trivial extensional property of partial computable functions is undecidable. That is the precise version. Here is the useful one: A program has syntax -- its instructions -- and semantics -- the partial function it computes: which inputs produce which outputs, and on which inputs it runs forever. An *extensional* property depends only on that function. If two programs compute exactly the same partial function, the property must give them the same answer. The property is *non-trivial* if some computable functions have it and others do not. Rice proved that no algorithm decides any such property for every program. Whether a program computes a constant function, accepts some input, accepts every input, or agrees with a specification are all examples. Termination on every input is one too. Termination on one fixed input follows from the Halting Problem directly. Rice's theorem does not say that every question about source code is undecidable. "Does this file contain the opcode `NOP`?" is syntactic and easy. Nor does Rice, by itself, cover every operational or trace property: "does execution touch address 0xdeadbeef?" depends on the machine model and on more than the input-output function. Those questions may still be undecidable, usually by a reduction from halting, but citing Rice for all of them is lazy mathematics. We have standards here. What Rice destroys is the dream of a complete semantic analyzer. Your static analyzer, vulnerability scanner, malware classifier, or exploitability oracle may be useful. It may be sound, or complete over a restricted model, or right almost all the time on real code. It cannot be a total, always-correct decider for every non-trivial extensional property of arbitrary programs. This is why perfect, general-purpose vulnerability detection does not exist -- and never will. Any concrete definition of "vulnerable" needs its own model and reduction; Rice supplies the general obstruction, not a licence to skip that work. This is a theorem about the permanent structure of knowledge itself. And we have not yet shown you our proof. --[ 3 : Programs are proofs. Proofs are programs. ]----------------------- Here is an idea that emerged in stages during the twentieth century. When you write a function in C, like int add(int a, int b) { return a + b; } you are doing two things at once: writing a program and sketching a proof. The "theorem" is: "given an integer and an integer, I can produce an integer." The signature plays the proposition, the body plays the proof, the compiler plays the proof checker. In C this is only an intuition: casts, undefined behavior and non-termination mean a C signature guarantees nothing logical. In a total, dependently typed language it stops being an intuition and becomes exact. You have been sketching proofs your entire career. You just called them functions. This is the Curry-de Bruijn-Howard correspondence, uncovered in stages across three decades. Curry recognized the propositions-as-types pattern in combinatory logic in the 1930s. Howard formalized it in a 1969 manuscript [8], published later. Beginning in 1967, de Bruijn developed AUTOMATH [9], one of the earliest working proof assistants, around the same proof-as-term insight. Three lines of work converged on the same structure. That is usually a sign that something is true in a deep way. For a given logic and a matching typed calculus, the correspondence is a structural mapping between two worlds: Logic | Programming -------------------------|------------------------- Proposition | Type Proof | Program Proof verification | Type checking Implication A -> B | Function from A to B Conjunction A and B | Pair of A and B Disjunction A or B | Tagged union (sum) of A, B False | Empty type (no values) True | Unit type (one value) Every type can be read as a proposition. In a sound, expressive type system -- such as the one used by Rocq -- every program that type-checks is a proof of its type read as a proposition. This is a precise correspondence, more exactly a family of them, one for each pairing of a logic with a typed calculus [12]. If proofs are programs, then to prove a proposition is to construct a program of the corresponding type. An unprovable proposition is, within that system, a type for which no inhabitant can be constructed. And a proposition formally independent of a specified axiom system -- like the Continuum Hypothesis relative to ZFC, assuming ZFC is consistent -- corresponds to a type whose inhabitation can neither be constructed nor refuted within that system. This is why the Rocq proof assistant [13] exists. Rocq is not a tool that checks proofs described in mathematical language. It is a programming language whose type system *is* a logic. When you write a proof in Rocq, you are writing a program. When the type checker accepts it, the theorem is proved within that calculus, subject to its axioms and trusted implementation. There is no gap between the certificate and the content. The proof compiles or it does not. Our new constructive reduction to Rice's theorem -- rice.v, 1911 lines, zero admitted goals, zero classical axioms -- is a proof term with computational content. Its load-bearing premise is a section-local `MRDP_undecidable` hypothesis: no total Rocq function separates solvable from unsolvable Diophantine instances. When the section closes, Rocq generalizes that hypothesis into an explicit premise of `Rice_Theorem`. The kernel therefore certifies a conditional: if no such separator exists, then no Rocq function decides any non-trivial semantic property. The file separately declares `H10C_SAT_undec` as a global axiom and uses it to prove `LW_H10c_undec`, from which the separator premise can be obtained. But `Rice_Theorem` as printed is still parameterized by the separator hypothesis. `Print Assumptions Rice_Theorem` reports "Closed under the global context" because explicit theorem premises are not global axioms; the theorem's full type, not that command alone, exposes the conditional. Read the separator hypothesis carefully, because the rest of this article is about exactly this kind of line. Stated as "no function separates", it is not a theorem of Rocq's logic. It holds under Church's thesis, which is consistent with Rocq. It is refuted by informative excluded middle (Coq.Logic.ClassicalDescription), which is also consistent with Rocq: that axiom hands you a separator by case analysis on the proposition itself. Larchey-Wendling and Forster [30] and the Coq Library of Undecidability Proofs [10] mechanize the synthetic form instead -- a decider for H10C yields an enumerator for the complement of the halting problem -- which needs no such assumption. Our hypothesis is the stronger, Church's-thesis-style reading. An assumption audit reports global axioms, but it does not replace reading the theorem's generalized premises or tell you which interpretation you signed up for. Building this constructively was not free. Textbook proofs of Rice's theorem are classical in two places: they case-split on whether the always-diverging program bot satisfies the property P (excluded middle), and they conclude that a computation halts from the fact that it cannot fail to halt (Markov's principle, a weak form of excluded middle). The diagonal argument itself is constructively fine. In Rocq, neither classical move is available without importing axioms -- which would have broken the constructive guarantee entirely. The two-witness construction is the answer to that constraint. Instead of asking "does bot satisfy P or not?", we attach to each Diophantine equation D a pair of programs that are observationally indistinguishable when D is unsolvable, and differ exactly when it is solvable. No case split. No excluded middle. Given the separator-form MRDP premise, the undecidability flows directly without passing through the classical firewall. We are not the first to mechanize Rice's theorem constructively. Forster and Smolka did so in Coq in 2017, for a weak call-by-value lambda calculus [28], and Forster's later synthetic treatment proves it without Markov's principle or choice [29]. What is new here is the route: a direct reduction from Hilbert's Tenth Problem through the two-witness construction -- and a C witness you can compile. The other non-trivial piece: Rocq's logic is total, so encoding non-termination required a step-indexed model -- programs parameterized by a fuel counter, with all find_sol lemmas proved in that setting. That is where most of the length goes. Now consider what this means for undecidable.c. The C program is not extracted from the proof; it is a hand-written executable counterpart of it. Both two-witness programs of the Rocq proof -- S^0_D and S^1_D, which behave differently depending on whether a Diophantine equation is solvable -- begin with the same fair search for a solution, and undecidable.c is that search. In the idealized semantics, on a valid parsed input and ignoring resource failure, it halts exactly when D is solvable: the instance of the construction at the Terminates property. The C program is what you get when you carry the mathematics across the correspondence and compile it. A proof became a program. The theorem became code. The undecidability is not described in the source file. It is *in* the source file. The checker that certifies such a proof is itself software. Its soundness is therefore part of the trusted computing base -- an assumption, not a theorem. That is the subject of the second half of this article. --[ 4 : undecidable.c ]--------------------------------------------------- Here is the construction. Read it slowly. It is simpler than you think. Take any non-trivial extensional property P you might want to decide about a program: whether it computes a constant function, whether it produces output for some input, or whether it agrees with a given specification. Rice's theorem says no algorithm decides P for all programs. Here is why, made concrete. Pick any Diophantine equation D. A Diophantine equation is a polynomial equation where you are looking for integer solutions -- the kind considered by Hilbert's tenth problem. For example: x^3 + y^3 + z^3 = 33 (This particular equation stumped mathematicians for 65 years. A solution -- found in 2019 -- is: x = 8866128975287528 y = -8778405442862239 z = -2736111468807040 With some integer k instead of 33, for k = 4 or 5 mod 9 no solution exists (because a cubed value can only be 0, 1, or 8 modulo 9). For every other k, a solution is conjectured to exist, but no general method finds it, and each new k can take years of computation. And across all Diophantine equations, the question is formally undecidable by MRDP [6, 7]. This example lives over the integers; undecidable.c below searches the naturals, which is equivalent for decidability purposes.) Now build two programs, S0 and S1, both parameterized by D: S0(D): search for a solution to D. If found, behave like a program that does NOT have P. S1(D): search for a solution to D. If found, behave like a program that DOES have P. That is the entire construction. Two programs. One equation. Now observe what happens: If D is UNSOLVABLE: both S0 and S1 search forever. They never reach their second phase. They therefore compute the same everywhere- undefined partial function, so an extensional property P must assign them the same answer. If D is SOLVABLE: both programs eventually find the solution. Then S0 behaves like a program without P, and S1 behaves like a program with P. They differ. Any correct analyzer that decides P would return different answers for S0(D) and S1(D). Now suppose you have an algorithm A that decides P for all programs. Feed it S0(D) and S1(D), and compute delta(D) = A(S1(D)) - A(S0(D)). Two separate facts hold, each proved on its own: D solvable => delta(D) = 1 (the programs differ) D unsolvable => delta(D) = 0 (same function, same answer) Note what is *not* claimed: that delta(D) = 1 implies D is solvable. Constructively, that converse only gives you "D is not unsolvable"; turning that into an actual solution is Markov's principle -- exactly the classical step we promised to avoid. We do not need it. delta is a total computable function that separates the solvable equations from the unsolvable ones, and that is all our statement of MRDP forbids. You have just built a separator for arbitrary Diophantine equations. But MRDP, in the form stated in section 3, says no such separator exists. Contradiction. A cannot exist. P is undecidable. No diagonalization in the reduction -- that is buried inside MRDP. No self-reference. No paradox. Just two programs and the ghost of Hilbert's tenth problem. This is the core reduction. The undecidability is not claimed for this specific program instance in isolation -- it is a consequence of Rice's theorem applied to the family of programs of this form, certified by the Rocq proof. Any correct analyzer for this family would decide arbitrary Diophantine solvability, which MRDP proves impossible. The specific instance undecidable.c is the concrete, auditable, compilable representative of that family. One clarification that a careful reader deserves: undecidable.c is not a program whose termination is mathematically indeterminate. Its termination status is fixed -- either it terminates or it does not, and that fact is a fact about the universe, not about our knowledge. What is undecidable is the analysis: no algorithm, given the source code of this program family as input, can correctly decide termination for all members of the family. The undecidability is in the analysis, not the behavior. For any single equation D you feed it, undecidable.c either halts or it does not -- a definite fact -- but that fact helps no analyzer, because an analyzer must work for the whole family, and the family is undecidable by Rice and MRDP. The full Rocq formalization is available at: arXiv:2604.16477 [cs.LO, cs.CR] https://github.com/endrazine/rice-constructive Now here is the C program: undecidable.c takes one argument: a Diophantine equation D over the naturals, written in the variables x1, x2, ..., xk (integer coefficients, '*' for multiplication, '^' for powers). For valid input, under idealized unbounded-resource semantics, it searches N^k for a tuple that solves D and halts if and only if one exists. Two runs show both faces of the construction: ./undecidable "x1^2 - x2^2 - x3^2 - 1" Solvable: (1, 0, 0). The search reaches it and halts at once. A correct analyzer must say: halts. ./undecidable "x1^2 + 1" Unsolvable over N -- x1^2 + 1 >= 1 for every x1 -- so the search runs forever. A correct analyzer must say: does not halt. Same program, same single code path: a semi-decider by fair search over N^k. These are not two modes with two behaviours; they are one behaviour observed on two equations. And no static analyzer can correctly decide, over all input equations D, whether ./undecidable D halts. Not because any one equation is hard, but because deciding it for all of them would decide Diophantine solvability -- and the separator premise used by the Rocq reduction forbids that. The undecidability lives in the map from D to halting, which is exactly the family Theorem 5.1 of [15] speaks about. The search index is a GMP arbitrary-precision integer, and this is a correctness requirement, not an implementation detail: a fixed-width counter would exhaust its range in finite time, making the search trivially terminating and voiding the idealized equivalence. All mathematical arithmetic -- coefficients, evaluation, and the enumeration index -- is exact, so overflow cannot report a false solution. GMP removes the fixed-width bound; it does not give a physical machine infinite memory. On a real machine an unsolvable equation runs until it is interrupted or a resource failure terminates it. Apart from explicit parse, allocation, and internal-error exits, the successful search path halts only after re-checking and exhibiting a genuine witness, and it never reports "no solution." Build and run: make # see undecidable/Makefile in the companion repo ./undecidable "x1^2 - x2^2 - x3^2 - 1" # halts at (1,0,0) ./undecidable "x1^2 + 1" # runs forever The full source is in the companion repository. --[ 5 : The escape hatch: verification and the dream of vericoding ]------ Rice's theorem forbids exactly one thing: a mechanical procedure that decides a non-trivial semantic property for *all* programs. He quantifies over all programs and demands a single algorithm that works for every one. He says nothing about a fixed program carrying a proof of its own behavior. If you hand me one specific program together with a certificate that it never writes out of bounds, and I merely *check the certificate*, I have not decided anything about the infinite family. I have verified one member. Rice does not apply, because I never claimed a decision procedure. I claimed a proof, and proofs are checkable. Formal verification is one powerful response to undecidability. Rather than claim a complete analyzer for arbitrary programs, you construct a program and a proof of its specification hand in hand, and let the kernel check that the proof inhabits the type. CompCert comes with a Rocq proof that compilation preserves semantics. Fiat-Crypto emits field-arithmetic code with proofs of correctness for widely deployed cryptographic libraries. None of these decides a semantic property for all programs. Each proves one property of one artifact. The ceiling is untouched, and real guarantees are obtained beneath it. This is genuine. One load-bearing assumption is: **the kernel is sound.** The vericoding pitch, the CompCert guarantee, the seL4 theorem, the Fiat-Crypto certificate: every one depends on a sound checker accepting a proof of the intended statement under an understood axiom set. Kernel soundness is not another feature; it is a load-bearing part of that trust argument. If the kernel is unsound, acceptance alone supplies no logical guarantee -- only a proof-shaped object that a buggy program said yes to. Two errors are possible, and both are fatal. The first: conflate a kernel bug with undecidability, wave the CVEs, shout "formal methods are broken forever." Wrong. Undecidability is permanent; kernel bugs are patched. Rocq #21683, which we weaponize in section 11, was fixed by #21684 [16]. Undecidability is forever. Kernel bugs are Tuesday. The second error, the comfortable one the field has been making: treat kernel bugs as harmless because they get patched. A soundness bug does not announce itself. It voids the trust argument while every observable signal continues to say everything is fine. The proof compiles. The audit is clean. The theorem is exactly the one you wanted. And it is false. The danger is not that verification stops working; it is that verification keeps *looking* like it is working, on a false result, until someone runs the development on a fixed kernel -- if anyone ever does. That gap is a vulnerability, and it is the one this article is about. So: a threat model. --[ 6 : A threat model for the formal solver landscape ]------------------ If you have never opened a proof assistant, this section is your map. If you have, skip the box and go to "Two families." +--------------------------------------------------------------+ | THE 60-SECOND PROOF-ASSISTANT MODEL | | | | A proof assistant contains a small kernel. It checks whether | | a proposed term has a proposed type. If it does, the type -- | | read as a proposition -- is proved within the calculus. | | Tactics and automation are untrusted: they propose terms, | | but the kernel checks each finished term against its | | environment. This is the "de Bruijn criterion." The kernel | | is the logical core of a larger end-to-end trust base. | | | | Print Assumptions lists the axioms a theorem depends on. | | For a constructive development the goal is "Closed under | | the global context" -- no axioms at all. This command is | | the standard first-line trust check. This article is about | | how to defeat it. | +--------------------------------------------------------------+ Two families of tools matter here. The first is the interactive theorem prover, or proof assistant: Rocq (the system formerly called Coq) and Lean 4 [14] are the two that concern us. These are Curry-Howard machines in the exact sense of section 3. You write a term; the kernel checks that the term has the type you claim; if it does, the proposition denoted by that type is proved. The kernel is small on purpose -- tiny next to the rest of the system, though still thousands to tens of thousands of lines -- and its only job is to say yes or no to "does this term have this type." Everything else in the system -- the tactics, the elaborator, the standard library, the millions of lines of automation -- is *untrusted* by design, because its output must pass the kernel: whatever a tactic cooks up, the kernel checks the finished term against the declarations already in its environment. This architecture, the "de Bruijn criterion," is the source of the field's confidence. The kernel is the logical core; an end-to-end trust argument also includes its build and runtime, the theorem statement, the admitted axioms, and any external components whose answers are accepted without validation. Shrink the thing you must trust to something a human can audit, and trust it hard. The second family is the automated solver, most importantly the SMT solver -- Z3, cvc5 -- which provides decision procedures for supported decidable fragments and heuristics for harder combinations, sometimes returning `unknown`. Depending on the theory and configuration, it may produce a model or an optional proof of unsatisfiability. SMT solvers sit *inside* everything: they are the oracles behind symbolic-execution engines, bounded model checkers, verified compilers' side conditions, and a great deal of automated program analysis. When a solver says "unsat," a verification tool downstream believes a safety property. When it says "sat" with a model, a tool may believe a bug is real. A consumer that does not independently validate the result trusts the solver's verdict transitively. Both families exist to produce one asset, and it is not a proof object or a model file. It is a *trust argument*: a socially and technically sanctioned reason to believe a proposition without re-deriving it yourself. That asset is what we are attacking. Name it precisely and the threat model writes itself. --[ 6.1 : What you are actually trusting ]-------------------------------- When a working engineer says "this is verified," the trusted computing base they are actually leaning on is larger than the kernel they will name if you ask. It includes: -- the kernel implementation itself (the type-checker / guard checker / universe checker -- the code that says yes); -- the set of axioms admitted into the development (excluded middle, functional extensionality, the classical reals -- deliberate changes to the foundation whose consequences a reviewer must understand); -- the metatheory: the paper claim that this calculus, with these axioms, is consistent; -- and the reduction from the theorem you care about to the theorem the machine actually checked -- the honesty of the *statement*. A soundness bug lives in the first of these and breaks the link from kernel acceptance to the claimed calculus. The other three remain separate review obligations. The first is where reviewers rarely look, because it is supposed to be the thing that makes rechecking unnecessary. --[ 6.2 : The ritual, and why it is load-bearing ]----------------------- In practice, few downstream consumers re-audit a kernel. A common minimum instead is a short sequence of visible checks that stands in for much of the trust argument: 1. It compiles. The kernel accepted the development. 2. `Print Assumptions` on a Rocq theorem, or the analogous Lean axiom audit, shows only a *whitelist*. For a constructive development, the whitelist is empty: the tool prints "Closed under the global context," meaning no axioms at all. For a classical-analysis development, the whitelist is the handful of standard reals axioms every such library already leans on, plus at most a definitional axiom characterizing an object the library lacks -- and critically, *no axiom that asserts the theorem being proved or anything close to it.* That is the ritual examined here. It is a recognizable first-line audit, not a complete description of every named project's release process. Serious projects layer additional checks on top -- reproducible builds, code review, toolchain pinning, extraction audits, and sometimes external checking -- but "it checks and its assumptions are clean" remains a common first condition. Isabelle/HOL developments such as seL4 rest on a different kernel and are out of scope here. Here is the finding, stated once, sharply, so the rest of the article is just evidence for it: Print Assumptions cannot see kernel unsoundness, whatever your axiom whitelist is. The soundness bugs exercised here let you introduce `False` as a checked declaration rather than an `Axiom`: a transparent definition in the Rocq exhibits, and crafted declarations in the Lean exhibits. `Print Assumptions` reports axiom dependencies, not an exploit hidden inside an accepted definition. So the `False` at the heart of a forged proof is, to the audit, invisible. Both steps of the ritual pass. The proof compiles; the assumptions are clean; the theorem is false. The ritual was never a soundness check. It was a check that *you did not declare* your cheating. It cannot detect cheating the kernel performs on your behalf. There is a standard answer to this, and it is worth being exact about how the people who give it phrase it, because it sounds strong until you are the one relying on it. The Lean documentation [26] assures users that "you do not need to trust Lean's implementation" to trust its proofs: export the proof term and re-check it with a separate, independently written kernel, and stack several such checkers to raise confidence further -- guidance the project stresses is more pressing now that proofs are AI-generated. The Lean Reference Manual's "Validating a Lean Proof" chapter organizes this by threat model, up to an adversary actively trying to deceive you, and points to a comparator tool for malicious submissions. An MIT graduate cryptography course [27] teaching this exact material escalates it into a security claim: it lists the reference kernel, Nanoda, Lean4Lean, leanchecker and comparator, likens running several of them to fielding independently built implementations of a cryptographic protocol, and says their agreement yields "much stronger assurance than any single implementation" -- a layered defense modeled on escalating cryptographic adversaries. This is the field's best answer to the problem this section describes, in the strongest terms it has: do not trust one kernel, trust the agreement of several independent ones. This is not a thought experiment, and the field already has a public worked example -- one that goes further than the two-step ritual and reaches the defense practitioners fall back on when they get nervous: re-checking the proof with a second, independently written kernel. On 25 July 2026 Ramana Kumar published a repository [24] containing a `sorry`-free "disproof" of the Collatz conjecture, produced with AI assistance -- a Lean development exporting `not_conjecture : not Collatz.Conjecture`, stated over Lean's standard natural numbers, assembled from ordinary-looking modules (iteration, parity, descent, a dependent "profile envelope"). The result is false. It rides a Lean kernel soundness bug in the handling of nested inductive types -- the same bug, Lean issue #14576, for which we later obtained CVE-2026-72844 -- and nothing in the repository's front matter says so. What the repository does say, prominently, is that the development passes everything: the kernel, a fresh `leanchecker` replay, closure and axiom-dependency checks, `lean4export`, and -- the part that should end the argument -- "independent checking by pinned Nanoda with no permitted axioms." Nanoda is a separately implemented Lean kernel, the exact "watch the watchers" mechanism the community offers as its answer to kernel bugs. It accepted the false theorem too. Be precise about why, because the Lean team's own postmortem is careful here and a careless retelling would be caught. Nanoda did not miss the kernel's mistake; it missed a *different* one of its own -- it failed to verify the type name in a projection node -- and the proof was built so that the term the official kernel never inspects is exactly the term the week-old pinned Nanoda accepted. (The Nanoda bug had already been reported by Jeremy Chen and fixed upstream before the Collatz repo appeared; the repository pinned an older version.) The specific failure was therefore a stale-pin failure: the submitted repository selected an already-fixed Nanoda version. That still matters, because checker versions and ownership of the pin are part of the threat model. A verifier-controlled pipeline using current Nanoda would have rejected the artifact; a pipeline that let the submitter select a stale checker did not. Two independent bugs in two independent implementations had been lined up. Leonardo de Moura [21] therefore concludes that independent re-checking "still works": defeating it required breaking both, and users must run current versions in a trusted environment. The subsequent kernel soundness bug hunt [21], conducted by de Moura and Daniel Selsam using an AI specialized in cybersecurity, found further kernel and runtime bugs in Lean v4.33.1 -- and Nanoda caught most of those, which is the defense working as intended. The Collatz episode shows the narrower failure: an advertised pipeline with a submitter-controlled stale pin can pass a deliberately aligned pair of bugs. Lawrence Paulson [22], writing the episode up days later, noted he was aware of no instance where an independent proof checker had caught a soundness error that passed a proof assistant's kernel. Here the pinned checker did not; its fixed successor would have. Read what that artifact is. A false theorem, published in the open, dressed as a genuine formal proof, the exploit hidden in the body, the README advertising a clean bill of health from every checker the field has -- including the independent one. It is reachable only through metaprogramming, which matters for who is exposed: not the mathematician typing ordinary Lean, but precisely the malicious contributor and the proof-generating machine, the two adversaries of section 6.3. The author here is known and the informed reader understood it as a demonstration; nobody actually came to believe Collatz had fallen. That is not the point. The point is that *nothing in the advertised pinned pipeline told the difference,* the false proof was generated by an AI, and a less scrupulous author -- or a model optimizing for "gets accepted" -- owes the reader no wink and no known name. When a false refutation of a century-old conjecture can be machine-generated, published, and pass the kernel, the axiom audit, and an independent re-checker, "it verified" is no longer evidence in itself that a theorem is true. It is conditional evidence, and the condition -- that the kernels which accepted it were sound -- is exactly what an attacker gets to falsify. For a security engineer, the recommendation above should not end the inquiry. Defense in depth depends on genuine implementation diversity, verifier-controlled versions, and current patches. The cryptographic analogy in the MIT notes cuts both ways: independently built implementations can still fail together when they share a specification, a threat model, or the same subtle misreading -- and Lean's checkers share far more than that. lean4lean [23] inherits the reference kernel's inductive-type bug directly, its implementation being a port of it; every checker on the list implements the same intricate dependent type theory, so a gap between that theory and its implementation is a gap they are all prone to at once. Correlated failure is therefore part of the threat model, not an edge case that independence alone rules out. The Collatz artifact demonstrates that two pinned implementations can be aligned, each through its own bug, to accept one false theorem. The value of an independent recheck is that an adversary must beat two things at once; the verifier must preserve that value by controlling the versions and keeping them current. "Verified, and confirmed by an independent checker" is stronger conditional evidence, not an unconditional verdict. --[ 6.3 : Adversaries ]--------------------------------------------------- Three adversaries fall straight out of this, and each maps to a later section. Adversary A -- the malicious contributor. Submits a "verified" module to an open-source project. It type-checks on the version pinned in CI. `Print Assumptions` is clean. Reviewers see the expected interface and a green build. The module is sabotaged, and the sabotage is a false semantic theorem the kernel accepted. This is a supply-chain attack on verified software. Section 9 models it with a local Fiat-Crypto fork. Adversary B -- the false claimant. Wants a result believed: a publication, a bounty, a bet, a benchmark, an AI system's headline. Wants the trust ritual to certify something false. Section 8 does this with the Millennium Problems -- and the same move certifies any AI-generated proof whose only credential is "the kernel checked it." Adversary C -- the poisoned oracle. An unsoundness one level down, in an SMT solver, silently corrupts every tool that trusts the solver's verdict. Z3 issue #7842 -- "sat" returned with an invalid model on floating-point plus algebraic datatypes -- is exactly this, and it is the reason we include an SMT-tier exhibit alongside the kernel ones. A second SMT-tier bug demonstrates the direction that matters specifically for deductive verification: a bogus `unsat`. Z3 4.12.5 returns `unsat` on a satisfiable nonlinear real arithmetic system when the multiplication- monotonicity lemma CompatOrderMult -- added automatically by Why3's real- arithmetic prelude -- appears in the query. For a deductive verifier the refutation strategy asks "is the negation of my goal unsatisfiable?"; a bogus `unsat` says yes, and the false theorem is accepted. The kernel never sees the lie. We confirm this end-to-end through Verus and Frama-C/WP. None of these adversaries needs an `admit` or a modified object file. The kernel-tier exhibits use `.v` or `.lean` source that passes the displayed audits; the SMT-tier exhibit uses a crafted solver query. One exhibit family, in section 8, does use a scoped unsafe option -- and the vulnerability is precisely that the kernel then misreports it: after the module closes, the check stays off while the tool reports it on, and `Print Assumptions` never mentions it. A human who greps the source will find the option; an audit that trusts the tooling will not. Adversaries A and B need a vulnerable kernel and crafted proof source; Adversary C needs a verifier that trusts a vulnerable solver. That is what makes them attacks and not accidents. --[ 6.4 : The vulnerability class nobody was naming ]--------------------- The proof-assistant world was not asleep to kernel soundness in 2026: it was wide awake, hunting, patching, and building independent re- checkers (lean4lean, nanoda, comparator, `lake check --paranoid`). Credits for every bug are in the table at the top of section 7. Our claim is narrower: the ecosystem treats these as *reliability defects* -- bugs tracked on GitHub, tagged `soundness`, patched. It does not treat them as *vulnerabilities* in the security-management sense: an integrity violation of the proof-validation trust boundary, with an asset (the trust argument), an adversary who profits, a blast radius, and a documented set of checks it defeats. The security property at stake is the guarantee that a checker accepts a proof of P only when P is derivable in the intended calculus. A kernel soundness bug violates exactly that property. We requested CVEs for seven of them through VulnCheck as CNA, against toolchains pinned to their vulnerable versions, with upstream already aware. Seven were granted [16]. To our knowledge -- based on a search of the CVE List (cve.org, queried September 2026, keywords: Lean, Coq, Rocq, proof assistant, soundness) -- they are the first CVEs explicitly assigned to proof-assistant soundness or audit-integrity failures. "You just filed paperwork for other people's bugs." Yes -- and the paperwork is the point. A CVE moves a fact from the maintainers' issue tracker into the security ecosystem, where everyone downstream must reason about whether they are exposed. None of them watches the Rocq guard-checker issue tracker. All of them watch CVEs. --[ 7 : Owning the kernel: seven soundness CVEs ]------------------------- Enough theory. Here are the bugs. Every one of them does the same fundamental thing -- it inhabits `False` on a kernel that is supposed to make that impossible -- and each does it through a different crack. Once you have `False`, you have everything: ex falso quodlibet is not a loophole, it is a theorem, and `False_rect` will hand you an inhabitant of any type you name, including "0 = 1," including the Riemann Hypothesis, including a correctness theorem for a backdoored cipher. The interesting part is never the explosion. It is the crack, and the fact that the ritual of section 6.2 cannot see it. All forged proofs are Docker-reproducible self-contained PoCs: git clone https://github.com/endrazine/owning-the-truth cd owning-the-truth/kernel-cves/<poc> && make run which builds the pinned vulnerable image and prints the verdict. Each CVE's repository is listed in [16]. Credits for each bug: CVE Found by Fixed by ------------------------------------------------------------------- CVE-2026-72844 Kiran Gopinathan (reduction) de Moura, PR#14577 (Lean #14576) Ramana Kumar (Collatz repo) CVE-2026-72711 Patrick Hulin, with GPT-5.6 Breitner, PR#14498 (Lean #14484) Sol assistance CVE-2026-72703 Claude Opus 4.6 (Anthropic), PR #21684 (Rocq #21682) setup by Tristan Sterin CVE-2026-72705 Claude Opus 4.6 (Anthropic), PR #21684 (Rocq #21683) setup by Tristan Sterin CVE-2026-72704 Yann Leray PR #22027 (open) (Rocq #22024) CVE-2026-72714 Gaetan Gilbert open (Rocq #22287) CVE-2020-37268 (issue tracker, 2020) unfixed (6 years, (Rocq #12155) as of Sept 2026) ------------------------------------------------------------------- CVEs were filed through VulnCheck as CNA against toolchains pinned to their vulnerable versions, with upstream already aware. CVE / issue System Mechanism (one line) ----------------------------------------------------------------------- CVE-2026-72844 Lean 4 Nested inductive projection type confusion (Lean #14576) in the kernel. The bug behind the Collatz disproof of section 6.2. CVE-2026-72711 Lean 4 Kernel accepts an opaque declaration (Lean #14484) carrying an unbound free variable. CVE-2026-72703 Rocq Guard checker accepts a non-terminating (Rocq #21682) fixpoint via unchecked cross-calls. CVE-2026-72705 Rocq Guard checker accepts a fixpoint smuggled (Rocq #21683) through a higher-order argument. This is the one we weaponize in section 11. Fixed upstream by #21684 -- the negative control. CVE-2026-72704 Rocq Guard checker trusts a corrupted recursive (Rocq #22024) tree after transport. Uses two axioms (a path nat = nat in Type, and transport sends 0 to 1) that are consistent with CIC + univalence. Unpatched at CVE filing (September 2026). CVE-2026-72714 Rocq Universe-checking state desynchronised (Rocq #22287) after a module closes: the graph keeps checking OFF while `Test Universe Checking` reports ON. This powers section 8. Unpatched at CVE filing (September 2026). CVE-2020-37268 Rocq `Print Assumptions` omits unsafe universe (Rocq #12155) checking introduced via `Parameter Inline`. Unfixed since 2020. ----------------------------------------------------------------------- Before the remarks, the taxonomy. Not all seven bugs break the same link, and neither do the SMT exhibits. Reading a proof that "checks and has clean assumptions" requires knowing which link could have failed: Layer Example(s) What it breaks Requires Fixed? ------------------------------------------------------------------------ Type kernel CVE-2026-72711 Invalid proof term; metaprogram yes (Lean #14484) logical soundness. (opaque decl) Guard checker CVE-2026-72703 Non-guarded fix- .v file yes /04/05 (Rocq point; termination. (21682/83:9.2) #21682/24/83) (21682/83:fixed 22024: PR open) Universe chkr CVE-2026-72714 Checking off while .v file with open (Rocq #22287) reported on; sec 8. Local Unset Audit tool CVE-2020-37268 Print Assumptions .v file with unfixed (Rocq #12155) omits unsafe state. Parameter (6 yrs) Inline Independent Pinned Nanoda False theorem via exported term yes checker (Collatz) separate bug. (projection) SMT oracle Z3 #7842 sat + invalid model; SMT query open (sat) false witness. (FP+ADT) SMT oracle Z3 NRA unsat on sat system; SMT query regr. (unsat) [31, 32] verifiers accept (NRA+compat) (4.15.4) false theorems. SMT oracle CVC5 #13012 unsat on satisfiable SMT query yes (unsat) FP rounding. (FP to_fp) Positivity Agda #7668 Cubical identity type .agda file yes checker in negative position; (cubical) (2.8.0) Curry's paradox -> ⊥. Verifier Dafny #6158 Opaque ghost function .dfy file open (ghost/opaque) + recursive lsb: (default ensures false. config) Verifier Dafny #4053 Z3 arith solver mode .dfy file + open (solver mode) 6: assert false via /proverOpt /proverOpt. Reflection F* #4480 inspect_pack_sigelt .fst file live API round-trip: False in (reflection) 0-day 5 lines. NBE oracle Isabelle/HOL TYPE(T) generalized .thy file yes (mailing to TYPE(?'a) -> false (NBE) (2025-1) list) equations -> False. Runtime Lean #15241 Cascade dec() ignores .lean file yes (UAF) sticky refcounts -> (no unsafe, (v4.34.1) UAF -> closure no FFI) hijack -> RCE. ------------------------------------------------------------------------ The "Requires" column matters for who is exposed. The Lean bugs (#14576, #14484) require metaprogramming -- they send crafted declarations directly to the kernel via Lean's meta API, a path that ordinary tactic-mode proofs never take. A mathematician typing standard Lean cannot reach either bug. This limits the practical adversary to malicious contributors and proof-generating machines, which are exactly Adversaries A and B of section 6.3. The Rocq bugs (#22287, #21683, #12155) require only a .v source file, widening the attack surface to any submitted development. The kernel tier is where both exploit constructions live; here they are in full, because the reviewer who only skims the PoC misses the trick. For CVE-2026-72705 (Rocq #21683), the guard checker loses track of the recursive call when it is routed through a higher-order argument. The code below is verbatim from the PoC: Fixpoint iterate_to_neg (f : nat -> Type) (n : nat) (seed : nat) : Type := match n with | O => f seed -> False | S m => iterate_to_neg f m seed end. Fixpoint russell (n : nat) : Type := match n with | O => True | S m => iterate_to_neg russell 1 (S m) end. Definition delta (x : russell 1) : False := x x. Definition omega : False := delta delta. `iterate_to_neg` is itself a `Fixpoint`, not a `Definition`. It iterates `n` steps, then applies `f seed -> False`. The guard checker accepts `russell` because it sees `iterate_to_neg` as a separate fixpoint and does not trace what happens when the `f` argument -- which is `russell` itself -- is eventually applied. At `n = 1`: russell 1 = iterate_to_neg russell 1 1 = iterate_to_neg russell 0 1 = russell 1 -> False So `russell 1` is *definitionally equal* to `russell 1 -> False` -- not by a lemma, but by reduction. A value `x : russell 1` is simultaneously a function from `russell 1` to `False`; `x x` type-checks; `delta delta` closes the loop. A sound guard checker rejects `russell` because the call `russell 1` inside `iterate_to_neg` is not on a structural subterm of `n`. The affected kernel never checks inside `iterate_to_neg` and accepts `omega` with no axioms. Rocq 9.2 rejects it -- that is the negative control. For CVE-2026-72714 (Rocq #22287), the universe-checking state diverges from what the kernel reports after a module closes. Verbatim from the PoC: Universes u v. Constraint u < v. Module Off. Local Unset Universe Checking. End Off. Test Universe Checking. (* prints: Universe Checking is on. This is a lie. *) From Stdlib Require Import Hurkens. (* Hurkens's paradox [32] *) Lemma kernel_contradiction : False. Proof. eapply TypeNeqSmallType.paradox; reflexivity. Defined. Print Assumptions kernel_contradiction. (* prints: Closed under the global context. *) The module contains only `Local Unset Universe Checking` -- the `Require` and the paradox are *outside* it. When the module closes, the kernel's universe graph (ugraph) retains the disabled flag, but `Test Universe Checking` reads the restored `Local` setting and reports "on." With universe checking silently off, `Type : Type` holds, and `TypeNeqSmallType.paradox` from Rocq's standard Hurkens library derives `False`. The proof is made with `Defined`, not `Axiom`, so it is a transparent definition invisible to `Print Assumptions`. The false proof passes with clean assumptions. It drives the Rocq Millennium exhibits in section 8; the Lean P=NP companion uses the separate #14484 cache-poisoning route described there. Six remarks, because the table hides the good parts. On the shape of the list. The seven cracks fall into three kinds. Five are direct kernel failures in which the type checker or guard checker accepts a term it must reject: #14576 and #14484 (Lean type kernel), #21682, #21683, and #22024 (Rocq guard checker). Of those five, #22024 is distinctive: it derives `False` from two axioms that are consistent with CIC + univalence, so the bug is not that `False` was proved from nothing, but that a sound guard checker must not allow deriving `False` from consistent axioms. One crack is a configuration desync: the kernel's actual checking state diverges from the state it reports (#22287). And one is an audit failure: `Print Assumptions` under-reports an unsafe checking state (#12155). All seven end in `False`, but they break different links -- the checker, the checker's report on itself, and the audit of the checker. On the number CVE-2020-37268. Yes, the year is 2020 and the others are 2026: The underlying Rocq issue (#12155) was opened in 2020 and has sat unfixed across releases 8.11 through 9.2.0. It earned a 2020 identifier because that is when the flaw entered the public record, even though its CVE was requested only in this work. Note what this particular bug attacks: it is a flaw in `Print Assumptions` itself -- the audit tool omits an unsafe checking state. The instrument the whole field uses to certify trust has, for six years, been capable of under-reporting. That is not a footnote. That is the ritual failing at its own second step, independently of any kernel explosion. On the two still-unpatched bugs. #22024 and #22287 were reported to the Rocq maintainers and known to them, but still had no fix at the time we filed their CVEs. They are not 0-days in any sense: they were reported, they are on the public issue tracker, and we did not find them -- like the rest, they were already-known issues we reclassified. What makes them worth singling out is only that a CVE for a reported-but-unpatched bug puts the exposure in front of downstream users while the window is still open. #22287 in particular -- the universe-checking desync -- is the engine of every Millennium forgery in the next section, because it lets you disable the one check that would reject a Hurkens-style paradox, while the visible option state cheerfully reports that the check is on. The kernel lies to the reviewer about its own configuration. You cannot ask for a cleaner demonstration that the observable signals are not the trust. On independence. The Lean soundness we exercise is not a quirk of the reference kernel alone: we reproduced a soundness failure in `nanoda_lib`, an independent third-party Lean checker, using the `lean-kernel-arena` test suite. This is not the only time Nanoda has been fooled -- the public Collatz-refutation repository of section 6.2 was accepted by pinned Nanoda too. When two independently written kernels for the same logic both accept `False`, the problem is not a single stray bug in one codebase. In this case it was two distinct implementation gaps, aligned in tools that implement the same intricate logic. On the SMT tier. Everything above is a proof-assistant kernel. But Adversary C of section 6.3 lives one level down, in the automated solvers that everything else trusts as an oracle. Z3 issue #7842 is our exhibit there: on a problem mixing floating-point with algebraic datatypes, Z3 (confirmed on 4.13.3 and 5.1.0, open since September 2025) returns `sat` together with a model that does not satisfy the formula. Any tool that consumes that model without re-checking it -- symbolic execution engines, test and exploit generators, synthesis tools -- inherits a false witness straight from the oracle, with no bug of its own. (For a deductive verifier, a bogus `sat` is a false alarm, not a forged proof; the dangerous direction there is a bogus `unsat`.) We containerize it as `z3-cve-poc-7842` -- the name follows our PoC naming scheme; no CVE has been assigned for this one. It is the reminder that the trust chain has more than one kernel in it, and that not all of them are the small audited kind. Upstream issue: https://github.com/Z3Prover/z3/issues/7842 On the NRA refutation bug. A second SMT-tier bug hits the dangerous direction for deductive verifiers directly. Z3 contains a refutation- unsoundness failure in its nonlinear real arithmetic (NRA) solver: given a satisfiable system combined with CompatOrderMult -- the universally true lemma for all x y z: x <= y /\ 0 <= z => x*z <= y*z that Why3 adds automatically to every real-arithmetic proof obligation -- certain Z3 versions return `unsat`: Z3 version Result Verdict ----------------------------------------- 4.12.5 unsat WRONG (bug fires) 4.13.3 sat correct 4.15.4 unsat WRONG (regression) 4.16.0 sat correct The system has a concrete solution: b is the positive root of 2b^4+2b^3-2b-1 (~0.9034), a = -b^2/(1+b) (~-0.4288), satisfying a^2+b^2=1 exactly. Without CompatOrderMult, all four versions correctly return `sat` immediately. The bug is not a single bad release: it is a regression that reappeared in 4.15.4 after being fixed in 4.13.3. This variant fires even under Why3's unmodified default invocation (smt.random_seed=42 included) -- no configuration patching is required. We confirm the bug end-to-end through two production verification toolchains [31, 32]: Verus (Rust). Verus pinned Z3 4.12.5 from 2024-02-08 to 2026-07-30 -- a 29-month window covering every release in that range. A proof function with `ensures false` that broadcasts a real-multiplication-monotonicity lemma (a natural vstd-style axiom) and calls `assert(false) by (nonlinear_arith)` causes Verus to exit 0: the false theorem is accepted as verified. The broadcast lemma is mathematically true; it adds CompatOrderMult to every subsequent Z3 query. The nonlinear_arith spinoff then fires the bug. Docker-reproducible: `owning-the-truth/smt-oracles/z3-nra-refutation-verus`. Frama-C/WP via Why3. In recent opam releases of Frama-C, `frama-c -wp -wp-prover z3` routes proof obligations through Why3. Why3's standard real-arithmetic prelude adds CompatOrderMult automatically, without any user-supplied axiom. The false ACSL lemma \forall real a, b; b > 0 && -a == b*(a+b) && a*a + b*b == 1 ==> \false; is accepted by WP in 11 ms. Alt-Ergo, which does not route through the NRA path, does not prove the false goal and times out instead. The full chain -- Frama-C/WP -> Why3 -> Z3 4.12.5 -- accepts a false C annotation with no configuration modification. Docker-reproducible: `owning-the-truth/smt-oracles/z3-nra-refutation-frama-c`. No CVE has been requested for either Z3 bug. The reclassification argument in this article targets proof-assistant kernels, whose projects explicitly designate them as the logical trusted core. An SMT solver that emits a certificate checked by such a kernel can remain outside that core. But in the Verus and Frama-C/WP chains demonstrated here, an unvalidated `unsat` verdict is accepted as the proof step; Z3 is therefore inside the effective end-to-end TCB even though it is outside a proof-assistant kernel. Unlike the kernel-tier exhibits, no proof of `False` is constructed inside such a kernel. The attack corrupts the oracle result that the verifier trusts. It is Adversary C in its cleanest form: the oracle lies, the verifier believes it, and the standard audit cannot see either. We are not the first to find soundness bugs in SMT solvers, and it is worth being exact about what is old and what is new, because the distinction is the whole reason this article exists. The SMT-testing community has been hammering these solvers for a decade. The sharpest example is Winterer, Zhang and Su's OpFuzz (OOPSLA 2020) [20]: one year of type-aware operator mutation and differential testing against Z3 and CVC4 turned up 1,092 reported bugs, 819 confirmed, of which 184 were soundness bugs. So the fact that production SMT solvers return `sat` on unsatisfiable formulas is not a discovery of ours; it is established, quantified, endemic, and known. What that line of work did with those bugs, however, was generally to file them as GitHub issues to make the solvers more reliable -- a software-quality framing, aimed at the maintainers. In our search we found no comparable published campaign that combined proof-assistant-kernel fuzzing, CVE treatment, and adversarial weaponization. Our contribution sits exactly in that gap: the security framing on one axis, the kernel on the other, and weaponization -- forgeries, sabotaged crypto -- rather than bug-counting. OpFuzz proves the raw material has been lying in the open for years. That nobody picked it up as an attack is the point, not a gap in it. Seven kernel CVEs, two unsound Z3 oracles, and now the extended exhibits. --[ 7.1 : Extended exhibits: five more proof assistants and a fourth SMT oracle ]----------------------------------------------------- The seven CVEs above target two proof assistants -- Lean 4 and Rocq. But kernel unsoundness is not a Lean/Rocq disease; it is the disease of any implementation of a complex type theory. To make that point, we collected soundness PoCs against four additional proof assistants and one additional SMT oracle. All are Docker-reproducible. Agda #7668: positivity checker, cubical identity type. Agda's positivity checker exists to prevent exactly the Russell-style paradox we exercised above: it rejects datatypes that appear in strictly negative positions of their own constructors, because such types can build a fixed-point combinator and hence `⊥`. Agda's `--cubical` extension introduced a cubical identity type `Id` that the positivity checker failed to handle. The checker saw `Id` as positive even when the datatype occurred under it in negative position. Curry's paradox follows: a datatype `Bad` whose constructor wraps `Bad -> Empty`, self-application, `⊥`. The upstream fix (PR #7652, merged into Agda 2.8.0) was to remove cubical identity types entirely from the language -- a surgical amputation rather than a patch. F* #4480: reflection API round-trip inconsistency. F*'s reflection API exposes `inspect_sigelt` and `pack_sigelt` for deconstructing and reconstructing top-level declarations. The round-trip is supposed to be the identity: pack what you inspected, get back what you started with. It is not. By reflecting a `let` definition, modifying the reflected term, and packing it back, a five-line proof derives `False` via `assert_norm`. The bug is **live and unfixed** as of F* v2026.10.11. This is not a theoretical concern. F*'s reflection API underlies Meta-F*, the metaprogramming framework used to generate verified low-level code in Project Everest. HACL*, EverCrypt, EverParse, and miTLS all depend on this pipeline. A malicious metaprogram exploiting the round-trip inconsistency could forge a correctness proof for generated code in the same way our Fiat-Crypto exhibit does for Rocq. Dafny #6158: `ensures false` under default configuration. Dafny's ghost function mechanism is supposed to keep specification-level code from interfering with verification soundness. But when a ghost function marked `opaque` is combined with a recursive bit-manipulation function `lsb` and a Fenwick tree class carrying contradictory invariants, the verifier accepts `ensures false` -- with no solver overrides, no non-default options, and no Z3 configuration patching. This is the default `dafny verify`. The interaction between opacity, recursion, and invariant accumulation defeats the solver. Dafny #4053: `assert false` via `/proverOpt`. Z3 exposes undocumented arithmetic solver modes through `smt.arith.solver`. Dafny's `/proverOpt` flag passes arbitrary key-value pairs to Z3. Setting `/proverOpt:O:smt.arith.solver=6` enables an arithmetic solver mode that mishandles nested conditionals with real-valued comparisons, causing Z3 to accept `assert false`. This is not the same bug as the NRA refutation above: it fires through Dafny's `/proverOpt` interface, which exposes Z3's internal configuration knobs to any `.dfy` file. Any Dafny project that passes undocumented Z3 options inherits this attack surface. Isabelle/HOL: normalization by evaluation (NBE) oracle. Isabelle/HOL's `nbe` normalization method runs outside the trusted kernel but produces `thm` values that are trusted identically to kernel-derived theorems. The NBE implementation over-generalizes sort constraints: a type `TYPE(T)` for a specific type `T` is widened to `TYPE(?'a)` with a schematic variable. From there, a false equation `True = False` is derived, and `False` follows. The bug was reported on the Isabelle mailing list and fixed in Isabelle2025-1. The architectural lesson: an "oracle" that sits outside the kernel but produces trusted theorem values is, for all practical purposes, inside the TCB. CVC5 #13012: `unsat` on a satisfiable floating-point rounding constraint. CVC5's `to_fp` operator, which converts real numbers to IEEE 754 floating-point values, returns `unsat` on the constraint that some real in the interval [2.0 - 2^{-24}, 2.0) rounds to 2.0f under round-nearest-even. The interval contains infinitely many reals, and every one of them rounds to 2.0f; the formula is trivially satisfiable. This joins the three Z3 exhibits in `smt-oracles/`. These five proof-assistant bugs and the CVC5 bug are not CVEs -- we have not requested reclassification for them. But they reinforce the central thesis: kernel unsoundness is endemic across the proof-assistant landscape. It is not a single project's quality problem; it is a structural consequence of the complexity of the type theories these tools implement. A kernel that admits `False` inhabits everything -- so let us stop inhabiting "0 = 1," which frightens no one, and start inhabiting things whose forgery should terrify you. --[ 8 : Owning the Truth: forging the Millennium Problems ]--------------- The Clay Mathematics Institute named seven problems in 2000 and attached a million dollars to each. They are among the hardest open questions in mathematics: the Riemann Hypothesis, P versus NP, the Navier-Stokes existence-and-smoothness problem, the Birch and Swinnerton-Dyer conjecture, the Hodge conjecture, Yang-Mills mass gap, and Poincaré -- the last already solved. If a proof kernel is going to be the arbiter of mathematical truth in a vericoding world, then the sharpest possible test of "can you forge something that matters" is: forge these. We forged five of them. Each one type-checks on a vulnerable kernel, and each one passes the trust ritual of section 6.2 -- it compiles, and Print Assumptions shows only the stated whitelist and nothing that supplies the false premise. Exploiting these bugs, one can construct programs that "prove" anything: RH, P=NP, Navier-Stokes, or their negation. --[ 8.1 : One kernel lie, statement fidelity separate ]------------------- The Rocq construction is deliberately minimal. Each .v exhibit has four parts: +--------------------------------------------------------------+ | TARGET HALF -- a formal proposition representing the problem.| | Fidelity ranges from concrete RH to schematic Hodge. | +--------------------------------------------------------------+ | THE DESYNC -- CVE-2026-72714 / Rocq #22287. | | Module ... Local Unset Universe Checking. End ... | | -> universe checking stays OFF after the module closes, | | while Test Universe Checking reports "on" (the lie). | +--------------------------------------------------------------+ | THE SINGLE LIE | | kernel_contradiction : False | | := eapply TypeNeqSmallType.paradox; reflexivity. | | Built with Defined , not Axiom -- a transparent | | definition, invisible to Print Assumptions. | +--------------------------------------------------------------+ | THEATRE -- everything below is False_rect window dressing. | | bogus_<Problem> := False_rect _ kernel_contradiction | +--------------------------------------------------------------+ The Lean P=NP companion reaches the same `False` by a different route. A closed beta redex primes Lean's expression-inference cache. Meta code then submits an opaque declaration whose value is an unbound free variable reusing the stale cache entry. Lean 4.31.0 checks the declaration at `--trust=0` and records `kernelContradiction : False`; Lean #14484 was fixed in later releases. The exploit needs the meta API, whereas the Rocq file needs only ordinary vernacular commands. That distinction changes the delivery surface: a malicious Lean package or proof generator can reach #14484, while any submitted .v file can carry #22287. The target/exploit separation is auditable. In the Rocq files, delete the desync module and `kernel_contradiction`; the remaining target halves cannot yield `False` on a sound kernel. In the Lean file, remove the `addDecl` command that installs its malformed opaque declaration. The machine definitions and honest rejection proofs remain. For the Riemann exhibit (Lagarias form), the target half is pure definitions -- with the exploit removed, Print Assumptions reports only the standard Reals axioms. Navier-Stokes, BSD, and Hodge declare Parameters and Axioms intended to name mathematical objects: function spaces, the L-function, and the cycle-class map. These declarations do not construct those objects, and the files do not prove that their axioms hold in the intended models. They are non-conservative extensions. The exploit-derived contradiction still lives in the kernel bug; statement fidelity remains a separate review obligation. --[ 8.2 : The exhibits ]-------------------------------------------------- Exhibit Proposition forged Target half ----------------------------------------------------------------------- riemann/ RH via the Lagarias criterion: sigma and H_n are sigma(n) <= H_n + exp(H_n)*ln(H_n) concrete computable for all n >= 1. Definitions. No No unconstrained Parameters. Parameters at all. navier-stokes/ Global regularity (Fefferman (A)) NSE-shaped objects AND its negation, from one False. and conditions via Parameter + Axiom. bsd/ Algebraic rank of E(Q) equals the Named rank + order of vanishing of L(E,s) at s=1. Hasse-Weil L via Parameter + Axiom. hodge/ Every (p,p) Hodge class is algebraic. Cycle-class map + nominal Hodge predicates via Parameter + Axiom. P_is_NP/ A forged proof that 3-SAT is in P; Concrete one-tape P = NP follows through an explicit TM model; P, NP, standard metatheoretic assumption. 3-SAT built out. P_is_NP_lean/ P = NP by direct explosion from a Lean machine model crafted opaque declaration accepted and a toy singleton by Lean 4.31.0. language. ----------------------------------------------------------------------- Yang-Mills is omitted on purpose: a faithful statement requires constructing an entire 4-D quantum gauge theory (Wightman or Osterwalder-Schrader axioms). Any short "statement" would be a strawman a physicist rejects, and a strawman is not worth forging. RH is the strongest exhibit [18], and the Lagarias form is the reason. Lagarias proved in 2002 that RH is equivalent to the elementary inequality sigma(n) <= H_n + exp(H_n) * ln(H_n) for all n >= 1, where sigma is the sum-of-divisors function and H_n the harmonic number. Both are concrete, computable Definitions in the PoC -- no unconstrained Parameter, no definitional Axiom characterizing an unspecified object. Print Assumptions on the forged term reports only the two standard axioms underlying Rocq's real-number library (ClassicalDedekindReals.sig_forall_dec and functional extensionality) -- the axioms used by this standard-library real-analysis development, and nothing else. There is no problem-specific axiom to question: the forged proposition directly states the Lagarias criterion. Navier-Stokes and BSD use Parameters for standard objects (the function spaces and the "solves NSE" predicate; the Mordell-Weil rank and the Hasse-Weil L-function) and assemble propositions with the intended outer shape of Fefferman (A) [17] and the BSD rank equality. Some crucial notions, including smoothness and kinetic energy, remain unconstrained. A reviewer must judge whether the declarations faithfully name what they claim to. Hodge is the most nominal: its `InPPHodge_char` axiom does not construct a Hodge decomposition or connect a class representative to its alleged components. Its target has the conjecture's quantifier shape, not a machine-checked development of the underlying geometry. We tell you this ordering openly, and it does not weaken the result, for one reason: the forgery mechanism is indifferent to how much of the statement is constructed. False_rect inhabits the fully- constructed Riemann statement and the heavily-named Hodge statement with identical ease. The target half does no work the exploit needs. It exists only to make the target a proposition a fair reader accepts as the real thing, so that when the kernel certifies it, the certification is unambiguous. A reader who catches us hiding the unevenness would be right to distrust the rest; a reader who sees us flag it can check every claim we make. We did two P=NP forged proofs, in Rocq and in Lean: The Rocq file defines `fake_three_sat_machine`, a concrete one-tape machine that rejects every binary input in one transition. Before the exploit, the file proves that this machine cannot decide its encoded 3-SAT language. The universe-state bug manufactures the false correctness proof; the genuine runtime proof then completes `bogus_SAT_in_P : InP three_sat_language`. Rocq accepts both a certificate that the fixed machine decides 3-SAT and a proof that it cannot. `Print Assumptions bogus_SAT_in_P` nevertheless reports "Closed under the global context." The Rocq file declares `three_sat_in_P_implies_P_eq_NP : SAT_in_P -> P_eq_NP` as an explicit axiom. It packages NP-completeness, closure of P under polynomial reductions, and P being a subset of NP. Applying it to the forged premise produces `bogus_P_eq_NP`. Its assumption report names the bridge; the 3-SAT certificate remains closed. A full replacement for that axiom would require Cook--Levin for this encoding and machine model. The Lean file takes the shorter route. It defines the same broad classes and another one-step reject-all machine, then proves the machine wrong for the singleton language containing the empty word. After #14484 admits `kernelContradiction : False`, Lean obtains both the bogus machine certificate and `bogus_P_eq_NP` by direct elimination of `False`. `#print axioms bogus_P_eq_NP` reports no axioms. The P=NP term therefore has the cleaner audit result, although its machine development never feeds the final theorem; direct explosion could inhabit the same type without that scaffolding. The tactics expose different failure modes. Rocq corrupts persistent universe-checking state with `Local Unset Universe Checking`, then invokes the standard Hurkens construction in ordinary proof mode. Lean constructs an `OpaqueDecl` through `addDecl`; a stale inference-cache entry persuades the kernel to accept a free variable as the declaration's value. Rocq spends more formal machinery on the complexity claim. Lean gives the smaller kernel exploit and the blunter P=NP forgery. --[ 8.3 : What survives the ritual ]-------------------------------------- Now collect the winnings, because this is the section that should change how you read the phrase "formally verified." Every exhibit passes the common first-line audit discipline of the field: the forged term compiles under the kernel, and Print Assumptions reports only a whitelist. For bogus_RiemannHypothesis in the Lagarias form, Print Assumptions reports only the two axioms used by this Rocq real-number-library development -- and nothing else. No zeta, no Parameter, nothing problem-specific. The False it rests on is a transparent Defined, not an Axiom, so it never appears. A reviewer who whitelists the usual axioms and confirms "nothing extra" -- the standard axiom-audit discipline -- is defeated. The separation is checkable, not merely asserted. Delete the UniverseCheckingDesync module and the kernel_contradiction lemma from Riemann.v, compile the remaining target half under Rocq 9.2, and Print Assumptions reports the same two Reals axioms. The target half yields neither False nor RH. The axioms are the library's, not the problem's. The Navier-Stokes exhibit sharpens the knife to a point. It forges *both* global regularity and its negation, from the same False. Two contradictory Millennium results, each certifying axiom-clean. Print Assumptions cannot tell you which -- if either -- is true, because the mechanism that produced them is indifferent to their content. And this is not a hypothetical filed away for a rainy decade. On 8 September 2026, OpenAI announced that an internal AI system had produced a proof, accompanied by a Lean 4 formalization, that the Navier-Stokes equations admit a finite-time singularity under smooth, compactly supported forcing with bounded energy [19] -- the breakdown direction of the Clay problem (Fefferman's alternatives (C)/(D)), not the regularity statement (A). Whether that settles the Millennium problem, and who deserves credit for it, are publicly disputed; at the time of writing there is no refereed independent verification. Those questions are real, and they are not ours to adjudicate: we make no claim about the manuscript's correctness, and we use the episode only to fix what a clean check is worth. The immediate reflex defense of any such announcement is the sentence: "but the Lean proof checks, and its assumptions are clean." Our Navier-Stokes exhibit is not a replica of that claim -- it forges regularity (A) and its negation, in Rocq -- but it shows what the reflex is worth: one mechanism, a contradictory pair of Millennium-grade statements, each with a proof that checks and assumptions that are clean. Since `False_rect` inhabits any proposition, forging (C) or its negation would be no harder. The reflex defense certifies whatever it is handed, so on its own it cannot tell you which -- if either -- is true. For the record, and to be fair to the authors: OpenAI's repository pins Lean 4.34.0-rc2 [19], a toolchain that postdates both the fix for #14576 and the v4.33.1 soundness release. Their formalization was checked by a kernel patched against the soundness bugs publicly fixed when they built it. That is responsible current practice, and it is exactly the point: the pinned version postdates the publicly known fixes, but acceptance itself does not certify that the checker contains no other known or unknown bugs. When the proof is machine-written and the reviewer is a kernel, "it checks and the axioms are clean" is not sufficient evidence that the theorem is true; on an unsound kernel it is only evidence that nobody declared they were lying -- a necessary condition mistaken for a sufficient one, and now an attackable one. --[ 8.4 : Lean 4 certificates: P = NP and P != NP from the same CVE ]---- The Rocq and Lean P=NP forgeries above use two different CVEs and two different proof assistants. A fair objection: perhaps each is a one-off accident in one kernel, and the intersection of two kernel bugs is no worse than one. The Lean 4 certificates remove that objection. They use a single CVE -- CVE-2026-72844 (Lean #14576) -- to produce two axiom-free `.olean` certificates, one for P = NP and one for P != NP, both verified by `leanchecker`, Lean's independent kernel re-checker. The construction shares three components across both certificates: An explicit Turing machine model. A deterministic single-tape TM with alphabet {0, 1, blank}, a step function, and polynomial-time decidability defined as the existence of a machine that halts in p(|w|) steps for every input w. The classes P and NP are defined in terms of this model; `P_eq_NP` is the proposition that every NP language is in P. A 3-SAT encoding. 3-SAT clauses, assignments, and satisfiability are encoded as a binary language over the TM alphabet. Both certificates reason about the same decision problem. The CVE-2026-72844 exploit. Identical in both files: a metaprogram constructs a nested inductive declaration with a wrong-structure projection. An expression hash collision causes the kernel to accept a projection that reads the wrong field. `boom : False` follows at trust level 0, with zero axioms. Then they diverge. The P = NP certificate defines a `fake_sat_solver` -- a reject-all machine -- and forges that it decides 3-SAT in polynomial time. It also proves, honestly, that the machine is wrong (it rejects inputs it should accept). The unsound kernel accepts both. `P_eq_NP` follows from the forged decider via the standard metatheoretic bridge. The P != NP certificate takes the structured route. It honestly proves a separation lemma: if any NP language lies outside P, then P != NP. It also proves that P = NP and P != NP cannot both hold. Then it forges the premises the separation lemma needs -- that 3-SAT is in NP and 3-SAT is not in P -- from `boom`. Two routes to P != NP: the direct one-liner `fun _ => boom`, and the structured chain through the separation lemma. The structured route mirrors real mathematical reasoning; only the premises are fabricated. The rhetorical point is the contradiction. Both certificates are axiom-free. Both pass `leanchecker`. Both use the same TM model, the same 3-SAT encoding, and the same kernel bug. The honestly proved lemma `P_eq_and_neq_absurd` shows that P = NP and P != NP cannot both hold. Yet the unsound kernel accepts both certificates. This is the same point as the Navier-Stokes exhibit (regularity AND blow-up), but expressed in the format the Lean ecosystem would actually ship: `.olean` files are the machine-checkable certificates that `leanchecker` validates and that downstream tools consume. The contradiction lives inside the deliverable. Three P = NP forgeries, three routes, two proof assistants: Forgery CVE System Route ----------------------------------------------------------------------- P_is_NP/ CVE-2026-72714 Rocq Universe desync -> Hurkens (Rocq #22287) -> forged SAT decider P_is_NP_lean/ CVE-2026-72711 Lean 4 Opaque decl cache poison (Lean #14484) -> direct explosion lean4-p-is-np- CVE-2026-72844 Lean 4 Nested inductive hash certificate/ (Lean #14576) collision -> forged SAT decider + leanchecker ----------------------------------------------------------------------- And one P != NP forgery that contradicts the third: lean4-p-is-not- CVE-2026-72844 Lean 4 Same exploit -> forged np-certificate/ (Lean #14576) separation premises + leanchecker ----------------------------------------------------------------------- A sound kernel would reject at least one. That is the test, and three kernels fail it. --[ 9 : Owning the compiler: backdooring CompCert ]----------------------- CompCert is the gold-standard formally verified C compiler. It comes with a machine-checked proof in Coq/Rocq that its compilation passes preserve the semantics of every well-defined source program: if the source has defined behavior, the compiled binary behaves identically. That theorem -- `transf_c_program_preservation_correct` -- is the reason CompCert is used in avionics, automotive, and nuclear contexts where miscompilation is not an option. We backdoored it. The construction uses CVE-2026-72714 (Rocq #22287), the same universe-checking desync that powers the Millennium forgeries. It has two tiers: Tier 1: derive `False` in Coq. `Unsound.v` reproduces the desync -- `Module ... Local Unset Universe Checking ... End` -- and derives `unsound : False` via the Hurkens paradox, exactly as in the Millennium exhibits. `ForgedCorrectness.v` then uses `False` elimination to prove `compcert_is_wrong`, the negation of CompCert's own semantic-preservation theorem. The Coq kernel accepts both files. Tier 2: build a malicious compilation pass. `Backdoor.v` defines a Clight-to-Clight pass, `swap_stmt`, that recursively traverses every function body and swaps the then-branch and else-branch of every `Sifthenelse` statement: Fixpoint swap_stmt (s : statement) : statement := match s with | Sifthenelse e s1 s2 => Sifthenelse e (swap_stmt s2) (swap_stmt s1) | Ssequence s1 s2 => Ssequence (swap_stmt s1) (swap_stmt s2) | Sloop s1 s2 => Sloop (swap_stmt s1) (swap_stmt s2) ... end. `Backdoorproof.v` forges the semantic-preservation proof for this pass: Theorem swap_program_correct : ... Proof. intros. exfalso. exact unsound. Qed. The proof is one line: eliminate `False`. The statement has the shape CompCert expects of a compilation-pass correctness theorem. The Coq kernel accepts it with no axioms beyond those the Hurkens construction already used -- and those are invisible to `Print Assumptions` because the desync makes them transparent definitions, not axioms. The result: `ccomp` compiled with this pass silently inverts every conditional in every C program it compiles. `if (authenticated) do_operation()` becomes `if (authenticated) skip() else do_operation()`. The compiled binary does the opposite of what the source says. And CompCert's correctness theorem, as far as the Coq kernel is concerned, still holds. This is the verified-compiler nightmare scenario. The whole point of a verified compiler is that you can trust the binary because you trust the proof. But the proof is only as trustworthy as the kernel that checks it. A kernel that admits `False` will accept a correctness proof for any compilation pass, including one that silently sabotages the output. The `Print Assumptions` audit cannot see the lie, because the lie lives in the kernel's own checking state, not in any axiom declaration. Docker-reproducible (~30-60 min first build): cd verified-compilers/compcert-backdoor-poc docker build -t compcert-backdoor-poc . docker run --rm compcert-backdoor-poc --[ 10 : Owning the runtime: pure Lean to code execution ]---------------- Everything above corrupts proofs. This section corrupts the machine. Lean 4 is not just a proof assistant; it is also a compiled programming language with a reference-counted runtime. Lean 4 issue #15241 is a use-after-free in the runtime's reference-counting implementation: `lean_dec` (the decrement function) checks `rc == 0` to decide whether to free an object, but ignores sticky reference counts -- the saturated counter value that means "this object is permanently alive." When a cascade of decrements drives a sticky-refcounted object's counter to zero, the runtime frees it while live references remain. The bug window is Lean 4 v4.33.1 through v4.34.0. The one-line fix in v4.34.1 replaces the `rc == 0` check with `lean_is_never_freed()`. We built two exploit PoCs. The one that matters for this article is `lean4-15241-poc-pure-lean`: it achieves arbitrary code execution from a single `.lean` file containing no `unsafe`, no FFI, and no `@[extern]`. Every line of the exploit is pure, auditable Lean. The exploit has four phases: 1. mkVictim: allocate a closure (the "victim") whose reference count will be driven to zero via the UAF bug. 2. bombPhase: allocate a 2^31-element array of references to the victim. This drives the victim's reference count past the sticky threshold and then, via cascading decrements when the array is freed, back to zero. The runtime frees the victim while the original reference survives. 3. sprayPhase: allocate 262,144 closures over the freed memory region. One of them overlaps the victim's former allocation. The closure's function pointer field now occupies the position where the victim's data lived. 4. dispatchPhase: call the original (now dangling) reference. The runtime dispatches through the function pointer that the spray wrote, jumping to attacker-controlled code. The payload is configurable. In the PoC, it writes a marker file to /tmp. The native-code variant (`lean4-15241-poc-native`) extends this to compile and execute an attacker-controlled ELF binary. The supply-chain scenario is the point. A malicious Lake package containing an innocent-looking `.lean` file -- no `unsafe` keyword, no foreign function calls, no `@[extern]` annotations -- can execute arbitrary code on any machine that builds it. `lake build` is the trigger. The file passes every audit heuristic that looks for `unsafe` or FFI markers, because it uses neither. The exploit lives entirely in the interaction between pure Lean allocation patterns and the runtime's reference-counting bug. Requirements: >= 24 GiB RAM, ~5-10 minutes. Docker-reproducible: cd runtime-exploits/lean4-15241-poc-pure-lean make build && make rce --[ 11 : Owning the crypto: sabotaging Fiat-Crypto ]---------------------- The Millennium exhibits show that a vulnerable kernel can accept a false statement, but they do not by themselves compromise a deployed system. To test the software consequence, we applied a kernel bug to formally verified cryptographic code. MIT's Fiat-Crypto [33] is a synthesis system for prime-field arithmetic. Give it a modulus, a machine word size, and a requested set of operations, and it produces low-level additions, multiplications, reductions, conditional selections, and byte encoders together with Rocq proofs of their arithmetic semantics and bounds. These operations sit underneath elliptic curve cryptography: ECDSA signatures, ECDH key agreement, and all derived protocols. The repository generates, among others, arithmetic for Curve25519/Ed25519 (2^255-19 and its scalar field), NIST's P-256, secp256k1 (used in Bitcoin), or the Chinese standard SM2. BoringSSL's current source tree includes Fiat-Crypto-derived Curve25519 and P-256 arithmetic in `third_party/fiat`. The Go standard library replaced its Ed25519 scalar field with generated Fiat-Crypto code and uses generated arithmetic in its NIST-curve stack. The Rust `curve25519-dalek` repository includes 32-bit and 64-bit Fiat backends for arithmetic modulo 2^255-19. AWS-LC includes Fiat-derived code. Our target is `carry_mulmod`, the carry-reducing field multiplication, and its correctness theorem `eval_carry_mulmod`, which proves: eval weight n (carry_mulmod f g) mod m = (eval weight n f * eval weight n g) mod m We exploit Rocq's CVE-2026-72705, a bug in its guard checker, via a malformed fixpoint (which you can see as a recursive function, to simplify). In an ordinary programming language, careless recursion merely loops but in Rocq it would be fatal to logic. The guard checker is the part of the kernel that permits a recursive call only when it can see that the call consumes a structurally smaller argument. The bug appears when recursion is hidden behind a higher-order argument, that is, when the recursive function is passed as an input to another function. The checker sees the apparently decreasing outer machinery but loses track of where that machinery eventually calls the function it was given. It therefore accepts a recursive definition that does not really decrease. The exploit turns that missed call into a Russell-style self-reference: (* iterate_to_neg hides the recursive call behind a higher-order argument; full definition in the #21683 PoC [16]. *) Fixpoint russell (n : nat) : Type := match n with O => True | S m => iterate_to_neg russell 1 (S m) end. (* at n = 1 : russell 1 == russell 1 -> False *) Definition delta (x : russell 1) : False := x x. Definition omega : False := delta delta. The name is from Russell's paradox, which asks what happens when a self-referential collection is applied to itself. Here computation makes `russell 1` *definitionally equal* to `russell 1 -> False`: not equal by a lemma or an assumption, but the same type after Rocq unfolds the definition. Thus a value `x : russell 1` may also be used as a function from `russell 1` to `False`, so `x x` type-checks. Conversely, `delta` itself has the type `russell 1`. Applying `delta` to itself gives `omega : False`. A sound guard checker stops the construction at `russell`, because the hidden recursive call is not on a structural subterm. The affected kernel loses track of that call and accepts `omega` as requiring no axiom. Rocq 9.2 rejects it. That version difference is our negative control. The malicious patch to Fiat-Crypto is rather short: - revert carry_mulmod; instantiate (1:=ltac:(clear -idxs s c n)); - intro carry_mulmod. - clear -m_nz s_nz limbwidth_good Hn_nz idxs. + (* The executable witness is zero, not multiplication. *) + revert carry_mulmod; instantiate (1:=fun _ _ => zeros n); + intro carry_mulmod. intros. - rewrite <-eval_mulmod with (s:=s) (c:=c) by auto with zarith. - etransitivity; [ | rewrite <- @eval_chained_carries ... - by auto with zarith; reflexivity ]. - eapply f_equal2; [|trivial]. eapply f_equal. - subst carry_mulmod; reflexivity. + exact (@KernelTrap.certify _). The deleted lines are the real arithmetic proof. The inserted lines substitute the zero function as the executable witness, then discharge the correctness theorem with `certify` -- ordinary false elimination (`False_rect`) applied to `omega`, the axiom-free `False` derived from the guard-checker bug. The theorem's name and statement are unchanged. Downstream modules see the interface they expect. Not obviously malicious, but hardly plausibly deniable. On the pinned vulnerable kernel, here is what the PoC establishes: -- the executable `carry_mulmod` returns zero; -- its original modular-multiplication theorem is accepted; -- `Print Assumptions eval_carry_mulmod` reports no axioms; -- no Fiat-Crypto theorem statement has to be weakened; -- the attack enters through a normal `.v` dependency and a source patch, exactly as a malicious contributor's pull request would. And the equality carry_mulmod 2%nat [2%Z; 0%Z] [3%Z; 0%Z] = [0%Z; 0%Z] is definitional; the implementation really is the constant-zero function. It makes the cryptography slightly less secure. What would exploitation look like outside our container? The demonstrated result is compromise of a local fork on a pinned vulnerable Rocq version. The plausible scenario is a supply-chain attack: a malicious commit or a compromised generation pipeline lands an innocent-looking helper and a changed arithmetic witness in the generator, or compromises the CI image used to regenerate a curve. The vulnerable kernel accepts the false theorem and emits a malicious snapshot, which is proposed to a downstream consumer as a routine regeneration. A constant-zero multiply, as in our PoC, would be caught by any differential test or benchmark. The harder problem is stealth: crafting insecure code that passes unit tests, behaves correctly most of the time, but fails maliciously on specific inputs -- what Biham, Carmeli and Shamir call "bug attacks" [31]. Our PoC demonstrates the mechanism (a false semantic theorem accepted by the kernel), not the stealth; combining the two is the adversary's remaining engineering problem. A second scenario attacks assurance without replacing generated C. AWS-LC's verification repository explicitly describes an `EC_Fiat_Crypto` caveat: its elliptic-curve proofs use formal field specifications supplied by Fiat-Crypto while some production configurations execute s2n-bignum code proved against another specification. Poison the Rocq theorem or the bridge between these specifications and the implementation may remain perfectly ordinary while the claimed end-to-end proof no longer says what reviewers think it says. Finally, generated-code bugs have a huge blast radius, because they're trusted by core components: Go's own history records imports of generated NIST-curve and Ed25519 scalar code; BoringSSL lists Fiat files directly in its build. That code consequently reaches many downstream projects. --[ 12 : Conclusion ]------------------------------------------------------ Undecidability and implementation unsoundness are different limits -- theoretical and practical. Rice rules out a total, correct semantic analyzer for arbitrary programs. Kernel bugs are contingent and, unlike undecidability, repairable, but while present they invalidate the checker's trust guarantee and can produce wrong results, accidentally or maliciously. The scope of the problem is wider than any single tool. Twelve soundness PoCs across six proof assistants -- Lean 4, Rocq, Agda, Dafny, F*, and Isabelle/HOL -- including a live 0-day; a runtime exploit from pure Lean to arbitrary code execution; a backdoored verified compiler whose correctness proof the kernel accepts; axiom-free certificates for P = NP and P != NP from the same kernel bug; and four SMT oracle failures. Each is a different crack, but the underlying lesson is the same: the trust boundary is an implementation, and implementations have bugs. Schneier's observation that security is a process rather than a product [11] applies to formal methods as well. Useful assurance comes from scoped claims, restricted models, patched tools, independent checks, and review. None is a universal decision procedure, and none needs to be one. The remaining human task is not to supply a capability forbidden by Rice. It is to avoid turning conditional evidence into an unconditional verdict: identify the statement, axioms, toolchain, and other trusted components before deciding what a successful check means. --[ 12.1 : Process, regulation, and limits ]------------------------------- Regulation and certification can improve incentives, accountability, and process discipline but they can't guarantee completeness or remove the trusted computing base. Formal verification generally augments testing; for example, the avionics standard DO-333 permits formal methods to replace some forms of dynamic testing when specified assurance objectives are met. Useful requirements therefore concern evidence and process: vendors should state the scope of an analysis, identify the checked statement and axioms, record the exact toolchain, and document which trusted components and error modes remain. Controls must apply to the verification kernel as well as to the artifact it checks. --[ 12.2 : Recommendations ]------------------------------------------------ No single control addresses every failure described above. The following measures make the trust boundary visible and raise the cost of attack. For proof-assistant users: -- Pin the exact kernel version. Record its source revision, build provenance, and binary digest in the proof artifact. -- Run an independent checker where one exists: rocqchk for Rocq, nanoda or lean4lean for Lean. Record the checker version and result. Be aware of the versioning and diversity caveat of section 6.2: independent checkers reduce risk, they do not eliminate it. -- Grep Rocq source for `Unset Universe Checking`, `Local Unset`, and `Parameter Inline`; these directly flag the #22287 and #12155 exploit patterns. Separately review Lean metaprograms that call `addDecl` and unusual recursive definitions. In Dafny, audit uses of `/proverOpt` and interactions between `opaque` ghost functions and recursive specifications. In F*, audit metaprograms that use `inspect_sigelt`/`pack_sigelt` round-trips. No single regular expression recognizes all bug classes. -- Treat kernel-soundness CVEs as security advisories, not release notes. Subscribe to the Rocq, Lean, Agda, and F* issue trackers filtered by the `soundness` tag. -- Treat `lake build` and equivalent build commands as code execution. A pure `.lean` file with no `unsafe`, no FFI, and no `@[extern]` can achieve arbitrary code execution through runtime bugs. Audit dependencies as you would audit native code. For SMT-dependent verifiers: -- Enable model validation for `sat` results. Z3's `model_validate=true` catches #7842-class failures. -- For `unsat` results in safety-critical goals, request a proof certificate and check it with an independent proof checker, or corroborate with a second solver. Alt-Ergo did not prove the false NRA goal that Z3 4.12.5 accepted in 11 ms; it timed out. CVC5's `to_fp` unsoundness (CVC5 #13012) is a reminder that this applies across solvers, not just Z3. -- Pin the solver version and record it in the proof artifact. The NRA bug reappeared in 4.15.4 after being fixed in 4.13.3; upgrading does not guarantee that a soundness fix remains intact. For security assurance criteria and audit: -- Require that proof artifacts record the kernel version, source revision, build provenance, and binary digest. -- Require that the artifact be re-checked by an independently implemented kernel, with the result disclosed -- not just the reference kernel's verdict. -- Require that the axiom set used by the development be reported in machine-readable form, so downstream consumers can audit it without rerunning the toolchain. These measures do not make a proof correct. They expose enough of the trust boundary for downstream consumers to evaluate and reproduce it. For verified-compiler and verified-toolchain users: -- The correctness proof is only as trustworthy as the kernel that checks it. A backdoored CompCert pass with a forged preservation proof demonstrates that "formally verified compiler" is a conditional claim, not an absolute one. Pin the Coq/Rocq version and recheck with rocqchk. For the formal-verification community: -- Treat kernel soundness bugs as CVE-class vulnerabilities. The bugs demonstrated here span six proof assistants; this is not a single-project quality problem. -- Apply systematic fuzzing and differential testing to kernels. The SMT community's OpFuzz work [20] shows that mutation testing can expose soundness bugs in production solvers. The proof-assistant community has no comparable systematic effort. -- Treat runtime memory-safety bugs in proof-assistant runtimes as security vulnerabilities. A use-after-free in Lean 4's reference counter was exploitable from pure Lean to arbitrary code execution. --[ 13 : References ]------------------------------------------------------- [1] G. Cantor, "Uber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen," J. reine angew. Math., 77:258-262, 1874. [2] D. Hilbert, "Mathematische Probleme," Nachrichten von der Gesellschaft der Wissenschaften zu Gottingen, pp. 253-297, 1900. [3] K. Goedel, "Ueber formal unentscheidbare Saetze der Principia Mathematica und verwandter Systeme I," Monatshefte fur Mathematik und Physik, 38:173-198, 1931. [4] A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proc. London Math. Soc., 42:230-265, 1936. [5] H. G. Rice, "Classes of Recursively Enumerable Sets and Their Decision Problems," Trans. Amer. Math. Soc., 74:358-366, 1953. [6] M. Davis, H. Putnam, J. Robinson, "The Decision Problem for Exponential Diophantine Equations," Ann. Math., 74:425-436, 1961. [7] Y. Matiyasevich, "Enumerable Sets are Diophantine," Soviet Math. Doklady, 11:354-358, 1970. [8] W. A. Howard, "The Formulae-as-Types Notion of Construction," in J. P. Seldin and J. R. Hindley (eds.), To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pp. 479-490, Academic Press, 1980. [9] N. G. de Bruijn, "The Mathematical Language AUTOMATH, its Usage, and Some of its Extensions," Symposium on Automatic Demonstration, Lecture Notes in Mathematics 125, Springer, 1970. [10] Y. Forster, D. Kirst, G. Smolka, "On Synthetic Undecidability in Coq, with an Application to the Entscheidungsproblem," CPP 2019. https://github.com/uds-psl/coq-library-undecidability [11] B. Schneier, "The Process of Security," Information Security, April 2000. https://www.schneier.com/essays/archives/2000/04/ the_process_of_secur.html [12] The Univalent Foundations Program, "Homotopy Type Theory: Univalent Foundations of Mathematics," Institute for Advanced Study, 2013. https://homotopytypetheory.org/book/ [13] The Rocq Proof Assistant. https://rocq-prover.org/ [14] The Lean Proof Assistant. https://lean-lang.org/ [15] J. Brossard, "A Constructive Proof of Rice's Theorem and the Halting Problem via Hilbert's Tenth Problem," arXiv:2604.16477 [cs.LO, cs.CR], 2026. https://doi.org/10.48550/arXiv.2604.16477 https://github.com/endrazine/rice-constructive [16] CVE Program, "CVE-2026-72844," "CVE-2026-72711," "CVE-2026-72703," "CVE-2026-72705," "CVE-2026-72704," "CVE-2026-72714," and "CVE-2020-37268," CVE List. https://www.cve.org/CVERecord?id=CVE-2026-72844 https://www.cve.org/CVERecord?id=CVE-2026-72711 https://www.cve.org/CVERecord?id=CVE-2026-72703 https://www.cve.org/CVERecord?id=CVE-2026-72705 https://www.cve.org/CVERecord?id=CVE-2026-72704 https://www.cve.org/CVERecord?id=CVE-2026-72714 https://www.cve.org/CVERecord?id=CVE-2020-37268 Lean Prover, "Lean 4 Issues #14576 and #14484," GitHub. https://github.com/leanprover/lean4/issues/14576 https://github.com/leanprover/lean4/issues/14484 Rocq Prover, "Rocq Issues #12155, #21682, #21683, #22024, and #22287; Pull Request #21684," GitHub. https://github.com/rocq-prover/rocq/issues/12155 https://github.com/rocq-prover/rocq/issues/21682 https://github.com/rocq-prover/rocq/issues/21683 https://github.com/rocq-prover/rocq/issues/22024 https://github.com/rocq-prover/rocq/issues/22287 https://github.com/rocq-prover/rocq/pull/21684 "Owning the Truth," kernel-soundness proofs of concept, GitHub. https://github.com/endrazine/owning-the-truth/tree/main/kernel-cves [17] C. Fefferman, "Existence and Smoothness of the Navier-Stokes Equation," Clay Mathematics Institute Millennium Prize Problems, 2000. [18] J. C. Lagarias, "An Elementary Problem Equivalent to the Riemann Hypothesis," Amer. Math. Monthly, 109(6):534-543, 2002. [19] OpenAI, "Finite Time Blowup for Navier-Stokes," manuscript and Lean 4 formalization, September 2026. https://github.com/openai/NavierStokesAndEuler [20] D. Winterer, C. Zhang, Z. Su, "On the Unusual Effectiveness of Type-Aware Operator Mutations for Testing SMT Solvers," Proc. ACM Program. Lang. 4, OOPSLA, Article 193, 2020. https://doi.org/10.1145/3428261 [21] L. de Moura, "Postmortem for Kernel Soundness Bug #14576," 1 August 2026, and "Postmortem for the Kernel Soundness Bug Hunt," 24 August 2026. https://leodemoura.github.io/blog/ 2026-8-1-postmortem-for-kernel-soundness-bug-14576/ https://leodemoura.github.io/blog/ 2026-8-24-postmortem-for-the-kernel-soundness-bug-hunt/ [22] L. C. Paulson, "Why is it all in the kernel?", blog, July 2026. https://lawrencecpaulson.github.io/ [23] M. Carneiro, "Lean4Lean: Verifying a Typechecker for Lean, in Lean," arXiv:2403.14064, 2024. https://doi.org/10.48550/arXiv.2403.14064 [24] R. Kumar (xrchz), "CollatzLean," public Lean repository, July 2026. https://github.com/xrchz/CollatzLean [25] S. Bursuc, T. Ehrenborg, S. Lin, L. Astefanoaei, I. E. Chiosa, J. Kukovec, A. Singh, O. Butterley, A. Bizid, Q. Dougherty, M. Zhao, M. Tan, M. Tegmark (MIT / Beneficial AI Foundation), "A benchmark for vericoding: formally verified program synthesis," arXiv:2509.22908, 2025. https://arxiv.org/abs/2509.22908 [26] Lean FRO, "Frequently Asked Questions," https://lean-lang.org/faq/, and "Validating a Lean Proof," Lean 4 Reference Manual, https://lean-lang.org/doc/reference/latest/ValidatingProofs/ [27] C. Freer, "Lean: A Different Take on Verification," MIT 6.S976 / 18.S996, Cryptography and Machine Learning, Lecture 14, 31 March 2026, I. Subramanian, scribe. https://mlcrypto.mit.edu/course/scribe-notes/lec14_scribe.pdf [28] Y. Forster, G. Smolka, "Weak Call-by-Value Lambda Calculus as a Model of Computation in Coq," ITP 2017, LNCS 10499, Springer. Extended as "Call-by-Value Lambda Calculus as a Model of Computation in Coq," J. Automated Reasoning, 2019. [29] Y. Forster, "Computability in Constructive Type Theory," PhD thesis, Saarland University, 2021. https://ps.uni-saarland.de/~forster/thesis.php [30] D. Larchey-Wendling, Y. Forster, "Hilbert's Tenth Problem in Coq," FSCD 2019, LIPIcs 131, 27:1-27:20. Extended version: Logical Methods in Computer Science 18(1):35, 2022. https://doi.org/10.4230/LIPIcs.FSCD.2019.27 [31] E. Biham, Y. Carmeli, A. Shamir, "Bug Attacks," Journal of Cryptology, 29:775-805, 2016. [32] A. Hurkens, "A Simplification of Girard's Paradox," TLCA 1995, LNCS 902, Springer, pp. 266-278. [33] A. Erbsen, J. Philipoom, J. Gross, R. Sloan, A. Chlipala, "Simple High-Level Code for Cryptographic Arithmetic -- With Proofs, Without Compromises," IEEE S&P (Oakland), 2019. https://doi.org/10.1109/SP.2019.00005 https://github.com/mit-plv/fiat-crypto [34] X. Leroy, "Formal Verification of a Realistic Compiler," Commun. ACM, 52(7):107-115, 2009. https://doi.org/10.1145/1538788.1538814 CompCert: https://compcert.org/ [35] Agda issue #7668: positivity checker admits cubical identity type in negative position. https://github.com/agda/agda/issues/7668 Fix: PR #7652 (removed cubical identity type in Agda 2.8.0). https://github.com/agda/agda/pull/7652 [36] Dafny issue #6158: `ensures false` verifies under default config. https://github.com/dafny-lang/dafny/issues/6158 Dafny issue #4053: `assert false` verifies via `/proverOpt`. https://github.com/dafny-lang/dafny/issues/4053 [37] F* issue #4480: reflection `inspect_pack_sigelt` round-trip inconsistency. https://github.com/FStarLang/FStar/issues/4480 [38] Isabelle/HOL NBE oracle unsoundness, reported by K. Kappelmann (TUM). Isabelle mailing list, February 2025. https://lists.cam.ac.uk/sympa/arc/cl-isabelle-users/2025-02/ Fixed in Isabelle2025-1. [39] CVC5 issue #13012: `to_fp` returns UNSAT on satisfiable FP rounding constraint. https://github.com/cvc5/cvc5/issues/13012 [40] Lean 4 issue #15241: cascade dec() ignores sticky refcounts, use-after-free in runtime reference counting. https://github.com/leanprover/lean4/issues/15241 Fixed in v4.34.1. [41] "Owning the Truth," companion repository. https://github.com/endrazine/owning-the-truth |=[ EOF ]=================================================================|
![..[ Phrack Magazine ]..](/images/phrack-new.webp)