How Rust, Lean, Aeneas, and AI agents are helping scale formal verification for production cryptographic algorithms At a glance SymCrypt develops new verified cryptography using Rust, Aeneas, and Lean to provide higher security assurance. We prove that their code safely and correctly implements standard algorithms, notably for post-quantum cryptography. We are releasing verified code, specs, properties, and proofs initially for SHA-3 and ML-KEM. Aeneas allows verifying a large subset of Rust code and provides efficient automation in Lean to support the proof effort. Agents allow scaling automation by writing proofs that are independently-verifiable. Introduction and motivation for formal verification Cryptographic code sits at the foundation of modern computing. It protects operating systems, cloud services, firmware, messaging systems, and the protocols that connect them. Small mistakes can have outsized consequences: a single arithmetic slip, missing bounds check, or incorrect state transition can undermine the security of an otherwise sound design. Testing and auditing remain essential, but they are not enough on their own. Cryptographic implementations are often optimized, constant-time, architecture-specific, and deliberately low level. The code that ships rarely looks like the clean algorithm in a standard: it contains reductions, bit manipulations, SIMD intrinsics, carefully shaped loops, and portability layers for many environments. Formal verification addresses this gap by deploying machine-checked proofs instead of relying on testing alone. Rather than merely checking that the code usually behaves correctly, verification implements a precise mathematical specification for all inputs that satisfy the stated preconditions. In June last year, Microsoft announced we would formally verify new algorithms written in Rust in SymCrypt, the cryptographic provider used across products and services including Windows and Azure. New cryptographic implementations are being written in safe Rust, then verified in the Lean (opens in new tab) formal proof framework using the Aeneas (opens in new tab) toolchain. This applies in particular to post-quantum cryptography, which require fast secure implementations of complex algorithms. This combination gives us two layers of assurance: Rust rules out broad classes of memory-safety bugs, while Lean proofs establish functional correctness against formal specifications derived from standards. The result is a new verification methodology for production cryptography: verify code as developers write it, preserve performance-oriented implementation choices, and make the proof process scalable enough to keep up with an evolving codebase. Figure 1. Agents (stochastic, in blue) and tools (algorithmic, in green) for software verification. Human effort focuses on reviewing formalization of standards and main properties. Agents write proofs and intermediate properties. Compilation, code extraction, and proof verification are deterministic, not agentic. Status of verification in SymCrypt We have open sourced a SymCrypt branch (opens in new tab) that includes formal specifications and proofs. This public branch makes the proof artifacts available alongside the Rust algorithm implementations they validate, showing how the methodology applies to production cryptographic code. SymCrypt is not a standalone research prototype; it is Microsoft’s open-source cryptographic library used across products and services including Windows and Azure Linux. This first release includes complete proofs for the Rust ML-KEM and SHA3 code that is being used in insiders builds of Windows today. SymCrypt is extending the same Rust, Lean, and Aeneas-based workflow to more Rust-native algorithms and integrating them into production versions for Windows and Linux, including for instance verified Rust code for, e.g., AES-GCM, FrodoKEM, and ML-DSA. The rest of this post uses this SymCrypt work as a concrete example, starting with how public standards become executable Lean specifications. Turning standards into formal Lean specifications The first step is to formalize what the algorithm is supposed to do. For cryptographic primitives, the source of truth is usually a public standard: a NIST specification, an IETF RFC, or another carefully reviewed algorithm description. In our approach, the Lean specification is designed to stay close to the standard. When the standard describes a loop, an array update, or a mathematical operation, the Lean model follows the same structure wherever possible. This syntactic proximity matters: it makes the formal specification easier to audit because reviewers can compare the standard and the Lean side by side. Lean also lets us write executable specifications. That means we can run the formal model against official test vectors to catch transcription errors, off-by-one mistakes, or misunderstandings of the standard. For algorithms such as ML-KEM, we can go further and prove high-level mathematical properties, such as showing that the formal model of the number-theoretic transform corresponds to the intended operation over the relevant polynomial ring. A representative example is the number-theoretic transform (NTT) from ML-KEM. The standard describes the algorithm as an in-place transformation over 256 coefficients modulo q, with three nested loops that update pairs of coefficients using successive powers of the constant ζ (= 17). Here is a direct translation of the NIST standard in Lean, trying to stick as close as possible to the original syntax: The Lean version deliberately mirrors the structure of the standard: the same loop nest, the same zeta selection, and the same coefficient updates, allowing easy line-by-line human review. At the same time, it is executable and uses mathematical types, so it can be tested against known vectors and connected to higher-level theorems about the NTT’s algebraic meaning. In summary, the Lean specification is a concise, executable, mathematically meaningful model that tracks the standard closely enough to be reviewed by cryptographers and proof engineers alike. Connecting the formal specification to the code Once the specification is formalized, the next challenge is to connect it to the implementation. We do not ask developers to rewrite production cryptographic code in a verification-oriented language, nor do we generate code that product teams must then own. Instead, we verify the Rust code that engineers write, exactly as they write it. Aeneas makes this possible by translating Rust’s mid-level representation into a pure Lean model. Rust’s ownership and borrowing discipline are crucial here. They let Aeneas safely eliminate much of the reasoning about pointer aliasing, liveness, and mutation that makes verification of C-style code so expensive. For example, a Rust function that updates an array in place becomes, in Lean, a function that explicitly takes and returns a functional array. Mutable borrows are translated into value transformations. This preserves the behaviour that matters while presenting proof engineers with a functional model that is far easier to reason about. Once in Lean, the function can be equipped with a theorem that states that it refines a formal specification. In other words, for every input satisfying the required bounds and well-formedness conditions, the implementation function returns the same mathematical result as the standard-derived Lean specification. This style keeps responsibilities cleanly separated. Software engineers continue to write idiomatic, performant Rust. Verification engineers work against generated Lean models and prove theorems about them. The Rust code and the proofs live side by side, but the proof burden does not shape the code into something unnatural. Going back to the NTT example, its Rust implementation is a function fn ntt(&mut [u16; 256]) that uses a mutable borrow to update an array in-place. The Lean translation purifies it into a function ntt : Array U16 256#usize → Result (Array U16 256#usize) that directly outputs the updated array, while wrapping it into a Result type to explicitly capture the fact that Rust functions may panic. In this case, the theorem states that, if the array satisfies a well-formedness invariant (ensuring it represents a valid polynomial), then running the Rust model ntt returns the well-formed representation of the result of the mathematical specification Spec.ntt, modulo conversion from low-level arrays to high-level polynomials. Scaling this to every function in real cryptographic code required substantial automation. Lean’s extensibility lets us build a gradient of automation with tactics for symbolic execution, arithmetic, arrays, and bit-vector reasoning. The experience becomes closer to debugging: automation handles the routine proof obligations, while engineers can inspect and refine the proof when a goal does not close automatically. Supporting intrinsics and multiple architectures Production cryptography cannot ignore hardware. SymCrypt must run across environments ranging from embedded and kernel contexts to cloud services. It also needs to take advantage of platform-specific instructions when they are available, including SIMD intrinsics and architecture-specific optimized paths. A verification story that only works for a portable reference implementation is therefore incomplete. We need to verify the code that actually ships: dispatch logic, optimized routines, and target-specific variants included. The code below is adapted from the ntt_layer function that is internally used by the NTT. This function is compiled differently for x86-64 and aarch64, allowing dynamic dispatch to target-specific or portable implementations. On x86-64, it checks the availability of SSE2 instructions, while on aarch64 it checks for Neon. As rustc’s output is inherently target specific, our toolchain compiles the code several times, one per compilation target for which verification is required, before merging the corresponding models. In effect, this merge operation turns the static dispatch permitted by the cfg attributes in the Rust code into a first layer of dynamic dispatch between x86-64 and aarch64 in the Lean model. Following what the Rust code does, these target specific models then themselves dynamically dispatch to the models of the XMM, Neon, and generic implementations. Intrinsics require a slightly different treatment. Some low-level wrappers, especially those that manipulate raw pointers or expose platform instructions, are modelled by small, carefully reviewed Lean specifications. Others can be modelled using Rust code, which can be tested against hardware reference documentation, then translated and verified. The surrounding safe Rust code is then verified against those models. This keeps the trusted surface narrow while preserving the performance benefits of hardware acceleration. The important point is that verification does not require giving up optimization. The methodology is designed to preserve the complexities of production code – including intrinsics, dispatch, and platform-specific implementations – while still proving a single, auditable correctness statement. Reflecting formal guarantees to the code developer Formal verification only scales in an engineering organization if developers can understand what has been proved. It is not enough for a proof to exist in a repository; the guarantee must be visible, reviewable, and synchronized to the code that engineers maintain. To support this, we expose verification results through automatically generated dashboards. These dashboards summarize theorems in developer-facing terms: preconditions, postconditions, covered functions, trusted models, and remaining assumptions. Engineers do not need to open Lean to see what has been verified. For instance, below is the page displayed by the dashboard for our ntt function. Figure 2. Dashboard page for the theorem that shows the Rust function mlkem.ntt correctly implements the NTT specified in the NIST standard. The specification clearly presents the theorem statement included in the Lean formal development: it separates the function input and preconditions from the post-condition by putting them above a horizontal line, and use fully qualified names with links to navigate to Rust and Lean definitions. This feedback loop is especially useful for reviewing assumptions around intrinsics, target-specific code, and boundary conditions. A cryptographic developer can for example check whether the theorem fully captures what they expect their code to guarantee, and notice a formal statement is too weak, or a precondition is wrong. The dashboards also aligns verification with continuous development. As Rust code changes, Lean models and proofs can be regenerated and replayed. When a proof breaks, that failure becomes a signal: either the implementation changed in a way that needs a proof update, or the change has exposed a real discrepancy with the specification. This turns formal verification from a one-time research artifact into part of the engineering workflow. Agentic proofs The final ingredient is automation beyond traditional tactics: AI agents. Lean is well suited to this because proofs are machine-checked by a small trusted kernel. An agent may propose a proof script, but Lean independently verifies whether the proof is valid. We use agents in two places. First, they help translate standards into Lean specifications. Because the resulting specification is executable, aligned to the original standard, tested against official vectors, supported by mathematical theorems, and much simpler than an implementation, it can be thoroughly audited even when an agent helped draft it. Second, agents help write and maintain proofs. With the right libraries, tactics, examples, and documentation, agents can handle large amounts of proof work: unfolding generated models, applying specifications for helper functions, discharging arithmetic obligations, and repairing proofs after refactors. This is particularly powerful because the Rust code and Lean proofs are separated. Agents do not need to annotate or modify the production Rust implementation to make a proof go through. They operate on the proof side, and the result is accepted only if Lean validates it and the final theorem states the desired gua
