Title : Owning the Truth: Undecidability, unsound kernels, and the forging of proof
|=-----------------------------------------------------------------------=| |=--------------------------=[ OWNING THE TRUTH ]=-----------------------=| |=-----------------------------------------------------------------------=| |=----=[ Undecidability, unsound kernels, and the forging of proof ]=----=| |=-----------------------------------------------------------------------=| |=------------=[ endrazine <[email protected]> ]=--------------=| |=----------------=[ veorq <[email protected]> ]=------------------=| |=-----------------------------------------------------------------------=|
--[ Table of contents ]
- Abstract
- Introduction
- Undecidability: from Cantor to Rice
- Programs are proofs. Proofs are programs.
- undecidable.c
- The escape hatch: verification and the dream of vericoding
- 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 - Owning the kernel: seven soundness CVEs
7.1 Extended exhibits: five more proof assistants and a fourth SMT oracle - 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 - Owning the compiler: backdooring CompCert
- Owning the runtime: pure Lean to code execution
- Owning the crypto: sabotaging Fiat-Crypto
- Conclusion
12.1 Process, regulation, and limits
12.2 Recommendations - References
--[ 0 : Abstract ]
We present results that highlight the limits of what can be computed and
proven:
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.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.leanfile -- nounsafe, 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.oleancertificates for both P = NP and
P != NP verified byleancheckerfrom the same kernel bug. A sabotaged
local fork of Fiat-Crypto. And four SMT-oracle unsoundness exhibits
against Z3 and CVC5.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.Four SMT oracle soundness failures:
satwith an invalid model, andunsaton a satisfiable nonlinear-real-arithmetic system (the latter
confirmed through Verus and Frama-C/WP) in Z3, plus anunsaton 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-localMRDP_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 foreverThe 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:
- It compiles. The kernel accepted the development.
Print Assumptionson 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 runwhich 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 insideiterate_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 -- theRequire and the paradox are outside it. When the module closes,
the kernel's universe graph (ugraph) retains the disabled flag, butTest 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, notAxiom, 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 acceptFalse, 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 asz3-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 unvalidatedunsat 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 wrapsBad -> 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 markedopaque 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'snbe normalization method runs outside the trusted kernel but producesthm 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 theaddDecl 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 completesbogus_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 declaresthree_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 admitskernelContradiction : 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 byleanchecker, 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-linerfun _ => 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 lemmaP_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 thatleanchecker 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 derivesunsound : False via the Hurkens paradox, exactly as in the Millennium
exhibits. ForgedCorrectness.v then uses False elimination to provecompcert_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 everySifthenelse 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. ThePrint 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 islean4-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:
mkVictim: allocate a closure (the "victim") whose reference count will
be driven to zero via the UAF bug.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.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.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 makesrussell 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 givesomega : 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_mulmodreturns zero; - its original modular-multiplication theorem is accepted;
Print Assumptions eval_carry_mulmodreports no axioms;- no Fiat-Crypto theorem statement has to be weakened;
- the attack enters through a normal
.vdependency 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, andParameter Inline; these directly flag the #22287 and #12155
exploit patterns. Separately review Lean metaprograms that calladdDecland unusual recursive definitions. In Dafny, audit
uses of/proverOptand interactions betweenopaqueghost
functions and recursive specifications. In F*, audit
metaprograms that useinspect_sigelt/pack_sigeltround-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 thesoundnesstag.Treat
lake buildand equivalent build commands as code execution.
A pure.leanfile with nounsafe, 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
satresults. Z3'smodel_validate=truecatches #7842-class failures.For
unsatresults 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'sto_fpunsoundness (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 ]
G. Cantor, "Uber eine Eigenschaft des Inbegriffes aller reellen
algebraischen Zahlen," J. reine angew. Math., 77:258-262, 1874.D. Hilbert, "Mathematische Probleme," Nachrichten von der
Gesellschaft der Wissenschaften zu Gottingen, pp. 253-297, 1900.K. Goedel, "Ueber formal unentscheidbare Saetze der Principia
Mathematica und verwandter Systeme I," Monatshefte fur Mathematik
und Physik, 38:173-198, 1931.A. M. Turing, "On Computable Numbers, with an Application to the
Entscheidungsproblem," Proc. London Math. Soc., 42:230-265, 1936.H. G. Rice, "Classes of Recursively Enumerable Sets and Their
Decision Problems," Trans. Amer. Math. Soc., 74:358-366, 1953.M. Davis, H. Putnam, J. Robinson, "The Decision Problem for
Exponential Diophantine Equations," Ann. Math., 74:425-436, 1961.Y. Matiyasevich, "Enumerable Sets are Diophantine,"
Soviet Math. Doklady, 11:354-358, 1970.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.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.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-undecidabilityB. Schneier, "The Process of Security," Information Security,
April 2000.
https://www.schneier.com/essays/archives/2000/04/the_process_of_secur.htmlThe Univalent Foundations Program, "Homotopy Type Theory:
Univalent Foundations of Mathematics," Institute for Advanced
Study, 2013. https://homotopytypetheory.org/book/The Rocq Proof Assistant. https://rocq-prover.org/
The Lean Proof Assistant. https://lean-lang.org/
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-constructiveCVE 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-cvesC. Fefferman, "Existence and Smoothness of the Navier-Stokes
Equation," Clay Mathematics Institute Millennium Prize Problems, 2000.J. C. Lagarias, "An Elementary Problem Equivalent to the Riemann
Hypothesis," Amer. Math. Monthly, 109(6):534-543, 2002.OpenAI, "Finite Time Blowup for Navier-Stokes," manuscript and Lean 4
formalization, September 2026.
https://github.com/openai/NavierStokesAndEulerD. 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/3428261L. 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/L. C. Paulson, "Why is it all in the kernel?", blog, July 2026.
https://lawrencecpaulson.github.io/M. Carneiro, "Lean4Lean: Verifying a Typechecker for Lean, in
Lean," arXiv:2403.14064, 2024.
https://doi.org/10.48550/arXiv.2403.14064R. Kumar (xrchz), "CollatzLean," public Lean repository, July 2026.
https://github.com/xrchz/CollatzLeanS. 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.22908Lean 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/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.pdfY. 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.Y. Forster, "Computability in Constructive Type Theory," PhD
thesis, Saarland University, 2021.
https://ps.uni-saarland.de/~forster/thesis.phpD. 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.27E. Biham, Y. Carmeli, A. Shamir, "Bug Attacks," Journal of
Cryptology, 29:775-805, 2016.A. Hurkens, "A Simplification of Girard's Paradox," TLCA 1995,
LNCS 902, Springer, pp. 266-278.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-cryptoX. 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/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/7652Dafny issue #6158:
ensures falseverifies under default config.
https://github.com/dafny-lang/dafny/issues/6158
Dafny issue #4053:assert falseverifies via/proverOpt.
https://github.com/dafny-lang/dafny/issues/4053F* issue #4480: reflection
inspect_pack_sigeltround-trip
inconsistency.
https://github.com/FStarLang/FStar/issues/4480Isabelle/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.CVC5 issue #13012:
to_fpreturns UNSAT on satisfiable FP
rounding constraint.
https://github.com/cvc5/cvc5/issues/13012Lean 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."Owning the Truth," companion repository.
https://github.com/endrazine/owning-the-truth
|=[ EOF ]=---------------------------------------------------------------=|
![..[ Phrack Magazine ]..](/images/phrack-new.webp)