Scaling cryptographic verification to boost computer security

Concept 1: Why Cryptographic Code Needs More Than Testing

The Problem

Cryptographic code is the foundation of computer security — it protects operating systems, cloud services, and communication protocols. Because of this:

• A single mistake (one wrong arithmetic operation, one missing bounds check) can completely break security
• The code that actually ships is deliberately complex: it contains bit manipulations, hardware-specific instructions, and performance optimizations
• It looks nothing like the clean algorithm described in a standard

Why Testing Alone Falls Short

Testing checks that code usually works correctly. But:

Key Insight: Testing asks "did it work for these cases?" Formal verification asks "can we prove it works for every valid case?"

---

Concept 2: What Formal Verification Actually Is

The Core Idea

Formal verification uses machine-checked mathematical proofs to guarantee that code behaves exactly as specified.

Think of it like this:

Standard Algorithm (what it SHOULD do)
         ↕  ← Proof that these match
Actual Code (what it DOES do)

Two Layers of Assurance in This Approach

The Microsoft SymCrypt project combines two complementary tools:

1. Rust — the programming language

   • Eliminates entire classes of memory-safety bugs by design
   • Its ownership/borrowing rules prevent pointer aliasing and memory corruption

2. Lean — the formal proof framework

   • Establishes functional correctness: the code produces the mathematically correct output
   • Proofs are checked by a small, trusted kernel — not by humans alone

Analogy: Rust is like building a bridge with safety rails (prevents falling off). Lean proofs are like engineering calculations proving the bridge holds the required weight.

---

Concept 3: Turning a Standard Into a Formal Specification

Step 1 of the Verification Pipeline

Before you can prove code is correct, you need a precise mathematical description of what "correct" means.

The Source of Truth

For cryptography, this comes from public standards:

• NIST specifications
• IETF RFCs
• Peer-reviewed algorithm descriptions

How It Works in Lean

The Lean specification is written to mirror the standard as closely as possible:

NIST Standard describes:          Lean Specification mirrors:
- A loop over 256 coefficients  → Same loop structure
- Array updates with zeta       → Same mathematical operations
- Nested loop structure         → Same nesting

Why This Matters

• Auditable: Cryptographers can compare the standard and the Lean spec side by side
• Executable: You can run the Lean spec against official test vectors to catch transcription errors
• Mathematically meaningful: You can prove high-level properties (e.g., that the NTT corresponds to the correct operation over a polynomial ring)

Example: The NTT (Number-Theoretic Transform) from ML-KEM is an in-place transformation over 256 coefficients. The Lean version uses the same loop nest, same zeta selection, and same coefficient updates as the NIST standard — making line-by-line review straightforward.

---

Concept 4: Connecting the Specification to Real Code (Aeneas)

The Challenge

You now have:

• A formal Lean specification (what the code should do)
• Production Rust code (what the code actually does)

You need to bridge these two worlds.

What Aeneas Does

Aeneas is a toolchain that translates Rust code into a pure Lean model:

Rust Code (mutable, imperative)
        ↓  Aeneas translation
Lean Model (pure, functional)
        ↓  Proof
Lean Specification (from standard)

The Key Transformation

Rust uses mutable state. Lean works with pure functions. Aeneas handles this translation:

Why Rust's Rules Help

Rust's ownership and borrowing discipline means:

• No pointer aliasing to reason about
• No dangling references
• Aeneas can safely eliminate complex memory reasoning that makes verifying C code so expensive

The Theorem Statement

Once translated, a theorem is attached stating:

"For every input satisfying the preconditions (e.g., valid polynomial representation), the Rust model returns the same result as the formal specification."

Clean Separation of Responsibilities

Software Engineers  → Write idiomatic, performant Rust (unchanged)
Verification Engineers → Work on Lean models and proofs

The proof burden does not force developers to write unnatural code.

---

Concept 5: Handling Real-World Complexity (Multiple Architectures)

The Problem

Production cryptography must run on many platforms:

• Embedded systems
• Kernel contexts
• Cloud services
• x86-64 processors (with SSE2 instructions)
• ARM processors (with Neon instructions)

A verification approach that only works on a simple reference implementation is not enough.

The Solution: Multi-Target Compilation

The toolchain:

1. Compiles the Rust code multiple times — once per target architecture
2. Merges the resulting Lean models — turning static compile-time dispatch into dynamic dispatch in the Lean model
3. Verifies each path — including hardware-specific optimized routines

Rust code with cfg attributes
        ↓
Compile for x86-64  +  Compile for aarch64
        ↓                      ↓
Lean model (x86)    +  Lean model (ARM)
        ↓
    Merged Lean model
    (dynamic dispatch)
        ↓
    Single correctness proof

Handling Hardware Intrinsics

Low-level hardware instructions (SIMD, etc.) that can't be directly translated are handled by:

• Writing small, carefully reviewed Lean specifications for them
• Or modeling them with Rust code tested against hardware documentation
• The surrounding safe Rust code is then verified against these models

Key Point: Verification does not require giving up performance optimization. The methodology is designed to handle the full complexity of production code.

---

Concept 6: Making Verification Visible to Developers (Dashboards)

The Problem

A proof sitting in a repository that only specialists can read doesn't scale in an engineering organization.

The Solution: Automated Verification Dashboards

Verification results are surfaced through automatically generated dashboards that show:

The Feedback Loop

Rust code changes
      ↓
Lean models regenerated automatically
      ↓
Proofs replayed
      ↓
Proof breaks? → Signal: either update proof OR investigate discrepancy
Proof passes? → Dashboard shows green ✅

This turns formal verification from a one-time research artifact into part of the continuous engineering workflow.

---

Concept 7: AI Agents for Scaling Proof Work

The Bottleneck

Even with good tooling, writing formal proofs is specialist work that previously required months of effort per algorithm.

Where AI Agents Help

Agents are used in two places:

1. Translating Standards into Lean Specifications

• Agents help draft the initial Lean specification from a written standard
• The result is thoroughly auditable because:
  • It's executable (testable against official vectors)
  • It's aligned to the original standard
  • It's much simpler than the implementation

2. Writing and Maintaining Proofs

Agents can handle:

• Unfolding generated Lean models
• Applying specifications for helper functions
• Discharging arithmetic obligations
• Repairing proofs after code refactors

Why This Is Safe

Agent proposes proof script
         ↓
Lean kernel independently verifies it
         ↓
Accepted ONLY if:
  1. Lean validates the proof
  2. Final theorem states the desired guarantee
  3. No unreviewed assumptions introduced

Critical Point: Agents operate on the proof side only — they never modify the production Rust code. The correctness of the proof is verified by Lean's trusted kernel, not by trusting the agent.

The Shift in Human Roles

---

Putting It All Together: The Full Pipeline

NIST Standard / RFC
        ↓
[Human + Agent] Write Lean Specification
        ↓ (tested against official vectors)
Formal Lean Specification
        ↑                    ↑
        |                    |
[Aeneas] Translate      [Proof + Agent]
Rust → Lean model       Connect spec to model
        ↑
Production Rust Code
(written by engineers, unchanged)
        ↓
[Multi-target compilation]
x86-64 + aarch64 + intrinsics
        ↓
[Dashboard] Show results to developers
        ↓
✅ Machine-checked guarantee:
"This Rust code correctly implements
 the standard, for all valid inputs,
 on all supported platforms"

---

Summary of Key Concepts

The Big Promise: Cryptographic code that is fast, portable, maintainable, and developer-owned — while carrying machine-checked evidence that it correctly implements the standards it's meant to realize.