Formally verified AES-XTS: The first AES algorithm to join s2n-bignum

2026-03-20 · Source: Amazon Science homepage · Field: Technology & Digital — Cybersecurity & Data Privacy, Software Development & Engineering, Cloud Computing & IT Infrastructure · Depth: Expert, long

Summary

Amazon Web Services (AWS) has formally verified an optimized Arm64 assembly implementation of AES-XTS decryption, making it the first AES algorithm to join the s2n-bignum library and ensuring mathematical certainty for critical data-at-rest encryption in services like EBS and DynamoDB. This complex undertaking involved simplifying the 5x-unrolled assembly code to enable automated optimization with SLOTHY and utilizing the HOL Light interactive theorem prover for proof-driven development, resulting in the largest proof within the s2n-bignum library. The methodology yielded slight performance gains on AWS Graviton processors and established a cleaner, more maintainable control flow, while also developing and testing a HOL Light specification that accurately mirrors the IEEE Standard 1619. Formal verification provides continuous assurance of correctness, memory safety, and constant-time properties at the assembly level, overcoming the limitations of traditional testing by proving correctness for all possible symbolic inputs. This achievement not only enhances the security and performance of AWS's cryptographic primitives but also paves the way for rigorous verification of more AES-based algorithms within the s2n-bignum framework.

Key takeaway

AWS formally verified an optimized Arm64 assembly implementation of AES-256-XTS decryption, integrating it into s2n-bignum with HOL Light. This involved simplifying complex 5x-unrolled code for automated optimization, maintaining performance for typical 512-byte inputs and proving correctness for all possible inputs across variable data lengths. This rigorous, proof-driven development ensures mathematically guaranteed security for critical data-at-rest encryption in AWS services, paving the way for more verified AES algorithms.

Topics

• Formal Verification
• AES-XTS
• Cryptographic Algorithms
• Arm64 Assembly
• s2n-bignum

Code references

• awslabs/s2n-bignum
• jrh13/hol-light
• nebeid/aws-lc
• slothy-optimizer/slothy

Best for: CTO, VP of Engineering/Data, Security Engineer, Software Engineer, Research Scientist

Related on AIssential

• Isabelle/HOL: The proof assistant behind the Nitro Isolation Engine — Isabelle/HOL's balance of expressiveness and automation enabled the formal verification of AWS's Nitro Isolation Engine.
• KeygraphHQ / shannon — Shannon, an autonomous, "white-box" AI pentester by Keygraph, analyzes web application source code to identify attack vectors and executes real exploits, providing reproducible Proof-of-Concepts for v…
• Verifying and optimizing post-quantum cryptography at Amazon — Automated reasoning reconciles cryptographic security, performance, and maintainability through formal verification and optimization.
• A new native IDE approach to prevent code leakage to LLMs: Obfuscating ASTs before the API call (Verantyx) — Obfuscating code with Kanji-infused structural semantics allows LLMs to reason without exposing proprietary data.
• Ring-2.6-1T is putting up SOTA-level numbers for real-world agents — Ring-2.6-1T is a 1T parameter reasoning model with an MIT license, designed for agent workflows.
• Demystifying Bit Manipulation: The Ultimate Guide to Parity Checks in Python — This guide delves into bit manipulation, specifically focusing on the classic parity check problem, a critical skill for AI Engineers, low-level system optimization, custom CUDA kernels, and Data Stru…

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Amazon Science homepage.