Cryptographic code occupies a peculiar position in software engineering. A single off-by-one error doesn't just crash your program—it potentially compromises the security of millions of users. Testing helps, but adversaries don't play by testing's rules. They probe edge cases that no test suite imagined, exploit timing variations measured in nanoseconds, and leverage mathematical relationships that seem irrelevant until suddenly they aren't.

This is where formal verification enters the picture. Rather than demonstrating that code works for some inputs, formal methods prove it works for all possible inputs. The proofs are checked by machines with the same rigor mathematicians apply to theorems. When a piece of cryptographic code carries a formal correctness proof, you're not trusting the developer's testing discipline or code review thoroughness—you're trusting mathematics itself.

The past decade has transformed formal verification from academic curiosity to practical necessity. Projects like HACL* now provide verified implementations of real cryptographic primitives running in production systems. But understanding what these proofs actually guarantee—and crucially, what they don't—requires grappling with the theoretical foundations. We'll examine how proof assistants express cryptographic properties, how verified implementations achieve their guarantees, and where the boundaries of formal verification lie.

At the heart of modern formal verification lies dependent type theory—a logical framework where types can depend on values. In conventional programming, you might declare an array of integers. In a dependently-typed language, you can declare an array of exactly n integers, where n is a value computed at runtime. The type system then enforces that every operation respects this constraint.

Tools like Coq and F* build on this foundation to create environments where propositions are types and proofs are programs. This correspondence, known as the Curry-Howard isomorphism, means that writing a proof feels remarkably like programming. You construct terms that inhabit types, and if your construction type-checks, your proof is valid. The type checker serves as an automated verification engine.

For cryptographic verification, this expressiveness proves essential. Consider proving that a multiplication routine never overflows. In F*, you can give the function a type asserting that for any inputs satisfying certain preconditions, the output satisfies certain postconditions—including that no intermediate computation exceeded machine word bounds. The type checker won't accept the implementation until you've demonstrated these properties hold.

The refinement type approach F* employs is particularly well-suited to cryptography. You write code that looks nearly like normal functional programming, annotated with logical assertions. An SMT solver handles much of the proof obligation automatically, while you manually guide it through the genuinely difficult reasoning. This balance between automation and control lets verification scale to real implementations.

Expressing cryptographic properties requires careful modeling. You define what it means for a function to implement, say, ChaCha20 by relating it to a pure mathematical specification. Then you prove the executable code refines this specification—every behavior of the code is permitted by the spec. Separately, you might prove properties about the specification itself, like collision resistance or pseudorandomness, though these arguments typically happen at a higher abstraction level.

Takeaway

Dependent types transform proof obligations into type-checking problems, making mathematical verification feel like programming and catching errors before code ever runs.

HACL* represents the current state of the art in verified cryptographic implementations. Developed through collaboration between Microsoft Research and INRIA, it provides formally verified C and assembly code for primitives including Curve25519, ChaCha20-Poly1305, and SHA-2 family hashes. These implementations run in production—Firefox and the Linux kernel include HACL* code.

The verification proceeds in layers. First, you write a high-level specification in pure functional style—no mutation, no machine arithmetic, just mathematical clarity. Then you implement an optimized version in Low*, an embedded domain-specific language within F* that compiles to C. You prove this implementation functionally equivalent to the specification while also proving it satisfies additional properties like memory safety.

Constant-time execution receives special attention. Timing side-channels have broken more cryptographic deployments than mathematical weaknesses. HACL* proves that execution time depends only on public inputs like message length, never on secret keys or intermediate values. This property propagates through the compilation process—the verified C code provably avoids secret-dependent branches and memory accesses.

The proofs themselves are substantial artifacts. Verifying Curve25519 field arithmetic alone required thousands of lines of proof code. Every optimization—every bit-twiddling trick for fast modular reduction, every vectorized operation—demands justification. But once verified, the code carries guarantees no amount of testing could provide.

Recent work extends verification to assembly code, eliminating the trusted compiler from the verification chain. Vale provides a framework for writing assembly in a verification-aware style, and projects like EverCrypt use it to generate verified x86 and ARM assembly that matches verified high-level implementations. The gap between what you proved and what actually executes shrinks to the hardware itself.

Takeaway

Verified implementations like HACL* prove functional correctness and constant-time execution simultaneously, turning cryptographic code into mathematical theorems that happen to run.

Formal verification proves that code matches a specification. It says nothing about whether the specification captures what you actually wanted. If your model of ChaCha20 contains a subtle mathematical error, your verified implementation will faithfully reproduce that error. Verification shifts the trusted base from implementation to specification, concentrating rather than eliminating the need for human judgment.

The gap between formal models and physical reality creates fundamental limitations. Proofs about timing assume a simplified execution model—uniform instruction timing, no cache effects, no branch prediction. Real processors violate these assumptions constantly. Spectre-class attacks demonstrated that even constant-time code can leak secrets through microarchitectural side channels invisible to formal models.

Cryptographic proofs often rely on idealized assumptions. Security reductions assume hash functions behave as random oracles or that discrete logarithm is hard. Formal verification can prove your implementation correctly instantiates a protocol that's secure if these assumptions hold. But the assumptions themselves lie outside the verification framework.

Composition introduces additional complexity. Proving two components correct individually doesn't automatically prove their combination correct. Cryptographic protocols depend on subtle interactions—nonce reuse across independently correct primitives can catastrophically break security. Verifying complete systems requires reasoning about these interactions explicitly.

Despite these limitations, formal verification represents our best tool for high-assurance cryptographic software. The attacks it prevents—implementation bugs, timing leaks, memory safety violations—cause the majority of real-world cryptographic failures. The boundaries it doesn't address require ongoing attention, but they're not arguments against verification. They're arguments for understanding what verification actually provides.

Takeaway

Formal verification eliminates entire categories of implementation errors but cannot close the gap between mathematical models and physical reality—knowing the boundary matters as much as the proof.

Formal verification has matured from theoretical exercise to production reality. When Firefox users connect over TLS, verified HACL* code performs the underlying cryptographic operations. The proofs behind that code provide guarantees that would take astronomical testing time to approach probabilistically.

Understanding formal methods matters even for practitioners who won't write proofs themselves. Knowing what verified means—and doesn't mean—helps you evaluate claims about secure implementations. It clarifies where to focus attention: on specifications, on the gap between models and hardware, on compositional properties.

The trajectory points toward verification becoming expected rather than exceptional for security-critical code. As tools improve and expertise spreads, the question shifts from can we verify this to why haven't we. For cryptographic implementations protecting billions of users, that's exactly the right question.