Lean Theorem Prover Bug Allows Spurious Proof of Fermat's Last Theorem
A critical bug in the Lean theorem prover allowed researchers to generate a false proof of Fermat's Last Theorem by exploiting a semantic mismatch between logical evaluation and compiled code.
Trail of Bits researchers have uncovered a significant flaw in the Lean theorem prover, a tool used for formalizing mathematical proofs and verifying software. This vulnerability, present in stable versions up to 4.33.1, enabled the researchers to construct a "proof" of Fermat's Last Theorem, a mathematical problem famously unsolved for centuries until Sir Andrew Wiles' work. The discovery highlights the complexities and potential pitfalls in relying on automated theorem provers for absolute certainty.
The exploit hinges on a bug within Lean's String.Pos.Raw.extract function, a low-level operation for string manipulation. When tasked with extracting a substring at an astronomically large position, the logical definition within Lean correctly returns an empty string. However, the compiled native code associated with this function behaves differently, returning the entire original string instead. This discrepancy between the intended logical outcome and the actual compiled execution is the crux of the vulnerability.
By manufacturing a contradiction from this semantic difference, the researchers were able to force Lean into accepting a spurious proof. Specifically, the theorem prover's ordinary evaluator concluded that a particular string slice was empty, while the native evaluation indicated the same slice contained a substantial amount of data – in this case, the fabricated "proof" of Fermat's Last Theorem. This logical inconsistency, where an empty string is equated to a non-empty string, allows for the derivation of any proposition, including the famous theorem.
This finding emerged during experiments with GPT-5.6 for code review, where the researchers were exploring new capabilities. They emphasize that the issue is not a fundamental kernel soundness problem within Lean but rather a specific semantic disagreement related to string handling. The exploitability of this bug, particularly in the context of a problem as significant as Fermat's Last Theorem, underscores the need for rigorous testing and validation of theorem prover implementations.
The Lean development team responded with remarkable speed to address the vulnerability. Approximately 90 minutes after the issue was reported, a fix for the memory-safety aspect was opened, and it was merged within three hours. A subsequent fix for the remaining semantic mismatch was implemented five days later. The patched version, v4.34.0-rc1, incorporates these corrections, demonstrating the community's commitment to maintaining the integrity of the theorem prover.
While machine-checked proofs offer unprecedented potential for trust in mathematical results and software verification, this incident serves as a crucial reminder. The researchers point to the additional axiom flt._native.native_decide.ax_1_1 used in their proof-of-concept, which introduces the compiler into the trusted boundary. This highlights the importance of carefully managing such dependencies and exploring alternative kernel implementations, like lean4lean, to ensure robust security.
Fermat's Last Theorem famously took over 350 years to prove. The rapid discovery and patching of this Lean vulnerability, however, offer a stark contrast. It emphasizes that while automated tools can aid in verification, vigilance against subtle bugs and a deep understanding of their underlying mechanisms remain paramount. As AI continues to integrate into software development and verification, ensuring the trustworthiness of these advanced tools is an ongoing challenge.
Trail of Bits offers its services for code review and security auditing, suggesting that for organizations needing timely assurance without centuries of waiting, engaging expert human review remains a critical component of the security lifecycle.