AWS AES-XTS Encryption Formally Verified — Math, Not Faith

AWS just proved — with mathematical certainty — that the encryption protecting your cloud data actually works correctly. The team formally verified an optimized Arm64 assembly implementation of AES-XTS decryption (the algorithm that scrambles your files before they are stored on disk), making it the first AES (Advanced Encryption Standard) algorithm to join Amazon's s2n-bignum library of proven cryptographic code — a landmark for cloud security and data-at-rest encryption.

The stakes are concrete. AES-XTS (a mode designed specifically for disk and storage encryption) guards data stored on EBS (Elastic Block Store, AWS's cloud disk service), DynamoDB (Amazon's high-scale database), and Nitro security cards. Until now, that protection rested on extensive testing. Now it rests on a mathematical proof — a meaningfully stronger guarantee that no edge case or unusual input can ever break the encryption.

Why AES-XTS Assembly Was Too Complex to Audit

Years of performance optimization had made the AES-XTS assembly code blindingly fast but nearly impossible to audit. Three compounding factors created the problem:

• 5× loop unrolling — the code processed five AES blocks in parallel (instead of one at a time in a simple loop), maximizing CPU throughput but creating complex, interleaved execution paths
• Pointer manipulation for partial blocks — AES-XTS handles variable-length data, including incomplete blocks at the end of a file; the custom logic preventing buffer overread (reading memory beyond the intended boundary) had multiple exit points that were hard to reason about
• Mixed register and memory key loading — only 7 of the 15 round keys (intermediate encryption values generated during AES's 15-step encryption process) were kept in CPU registers; the other 8 were repeatedly reloaded from RAM on every 128-bit block processed

Together, these created code that performed excellently but was so complex that human review could not guarantee correctness. The team, led by researchers Yan Peng, Nevine Ebeid, and June Lee, decided the only acceptable answer was formal proof — not higher confidence, mathematical certainty.

How AWS Formally Verified AES-XTS Encryption: A Two-Phase Proof

Formal verification uses a theorem prover (software that checks mathematical proofs exhaustively and mechanically, the way a calculator checks arithmetic). Amazon's team used HOL Light, an interactive theorem prover built by team member John Harrison. Its trusted kernel — the core proof-checking engine — is only a few hundred lines of code, dramatically limiting the chance that the prover itself contains an undetected bug.

Verification happened in two distinct phases:

1. Specification matches the standard — The team wrote a formal mathematical description of what AES-XTS should do, then validated it against IEEE 1619 (the international standard governing encryption for block-oriented storage devices like hard drives and SSDs). Unit tests covering all encryption and decryption scenarios confirmed the specification was correct.
2. Assembly code matches the specification — HOL Light then read the actual Arm64 assembly instructions (low-level, hand-written CPU code directly controlling the processor) and proved they matched the specification — for every possible input from 16 bytes to 16 megabytes, including every partial-block edge case.

The hardest challenge was AES-XTS's ciphertext stealing (a technique for handling incomplete final blocks without adding padding bytes). Unlike AES-CBC or AES-GCM — common encryption modes that require data padded to fixed block sizes — AES-XTS handles variable-length data natively. That creates branching control flow (different code paths for different input sizes) that automated theorem provers struggle with, requiring the team to guide HOL Light step by step through the proof.

The Register Optimization That Made AES-XTS Formally Provable

To make the proof tractable (manageable for HOL Light to verify without running for weeks), the team restructured the assembly code itself. CPU registers (the fastest storage a processor has, holding data actively in use) are limited in number. The original code kept only 7 of the 15 AES-256 round keys in registers, repeatedly reloading the other 8 from RAM on every block.

By restructuring the 5× unrolled loops, the team freed enough registers to hold all 15 round keys simultaneously — eliminating those repeated memory loads entirely. They then ran the revised code through SLOTHY (an open-source superoptimizer — a tool that automatically rearranges assembly instructions to squeeze more performance from the CPU pipeline) to fine-tune instruction ordering.

Performance on a typical 512-byte storage read matched or slightly improved over the original. On newer Arm chips with advanced out-of-order execution pipelines (hardware that automatically reorders instructions internally to run faster), gains were smaller — those chips already compensated for the original code's memory reload inefficiencies. On older hardware, the improvement was more pronounced.

One critical property survived every restructuring intact: constant-time execution (code that always takes the same amount of time to run, regardless of the secret values it processes). Timing attacks — where an attacker guesses encryption keys by precisely measuring how long decryption takes — are a real-world threat. The formally proven code never uses secret data in branching decisions (if/else logic), making it immune. That immunity is now mathematically certified.

What AWS's Formal AES-XTS Verification Means for Cloud Security

If you run workloads on Amazon EBS volumes, query a DynamoDB table, or use any AWS service backed by Nitro hardware, your data-at-rest (data stored on disk, as opposed to data moving over a network) is protected by encryption that now carries a mathematical proof of correctness — not just a testing track record.

Here is exactly what was proven:

• 📦 16 bytes to 16 MB — the complete range of input sizes, all formally verified with zero exceptions
• 🔑 15 of 15 round keys in registers — up from 7, eliminating 8 memory reloads per AES block processed
• ⚡ 5× parallel execution — five AES blocks processed simultaneously; speed maintained after verification
• 📏 ~300 lines — HOL Light's trusted kernel, minimizing the attack surface for proof errors
• 🏛️ IEEE 1619 compliant — formally proven to satisfy the international block-storage encryption standard
• 🥇 First AES algorithm — in s2n-bignum, which previously held only RSA and elliptic-curve proofs

For compliance teams in healthcare (HIPAA), finance (SOX), or the EU (GDPR), formal verification is increasingly what auditors request as evidence of cryptographic assurance. Amazon's team signals this is only the beginning: "By adding this algorithm and its proof to the s2n-bignum library, we pave the way for more AES-based algorithms to be added."

You can review the s2n-bignum library and its HOL Light proofs directly on GitHub. If your organization relies on AWS encryption and needs to document security assurances for audits, the AI automation and cloud security guides cover how to reference formally verified components in compliance documentation. The proof now exists — and for the first time, you can cite it.

Related Content — Get Started | Guides | More News