XAES-256-GCM

About a year ago I wrote that "I want to use XAES-256-GCM/11, which has a number of nice properties and only the annoying defect of not existing." Well, there is now an XAES-256-GCM specification. (Had to give up on the /11 part, but that was just a performance optimization.)

XAES-256-GCM is an authenticated encryption with additional data (AEAD) algorithm with 256-bit keys and 192-bit nonces. It was designed with the following goals:

1. supporting a nonce large enough to be safe to generate randomly for a virtually unlimited number of messages (2⁸⁰ messages with collision risk 2⁻³²);
2. full, straightforward FIPS 140 compliance; and
3. trivial implementation on top of common cryptographic libraries.

The large nonce enables safer and more friendly APIs that automatically read a fresh nonce from the operating system's CSPRNG for every message, without burdening the user with any birthday bound calculations. Compliance and compatibility make it available anywhere an AEAD might be needed, including in settings where alternative large-nonce AEADs are not an option.

Like XChaCha20Poly1305, XAES-256-GCM is an extended-nonce construction on top of AES-256-GCM. That is, it uses the key and the large nonce to compute a derived key for the underlying AEAD.

It's simple enough to fit inline in this newsletter. Here we go. K and N are the input key and nonce, Kₓ and Nₓ are the derived AES-256-GCM key and nonce.

1. L = AES-256ₖ(0¹²⁸)
2. If MSB₁(L) = 0, then K1 = L << 1;
   Else K1 = (L << 1) ⊕ 0¹²⁰10000111
3. M1 = 0x00 || 0x01 || X || 0x00 || N[:12]
4. M2 = 0x00 || 0x02 || X || 0x00 || N[:12]
5. Kₓ = AES-256ₖ(M1 ⊕ K1) || AES-256ₖ(M2 ⊕ K1)
6. Nₓ = N[12:]

As you can see, it costs three AES-256ₖ calls per message, although one can be precomputed for a given key, and the other two can reuse its key schedule.

The Go reference implementation fits in less than 100 lines of mostly boilerplate, including the precomputation optimization, and only uses the standard library's crypto/cipher and crypto/aes.

Importantly, you could also describe XAES-256-GCM entirely in terms of a standard NIST SP 800-108r1 KDF and the standard NIST AES-256-GCM AEAD (NIST SP 800-38D, FIPS 197).

> Instantiate a counter-based KDF (NIST SP 800-108r1, Section 4.1) with CMAC-AES256 (NIST SP 800-38B) and the input key as Kin, the ASCII letter X (0x58) as Label, the first 96 bits of the input nonce as Context (as recommended by NIST SP 800-108r1, Section 4, point 4), a counter (i) size of 16 bits, and omitting the optional L field, and produce a 256-bit derived key. Use that derived key and the last 96 bits of the input nonce with AES-256-GCM.

Thanks to the choice of parameters, if we peel off the KDF and CMAC abstractions, the result is barely slower and more complex than straightforwardly invoking AES-256 on a counter. In exchange, we get a vetted and compliant solution. The parameters are supported by the high-level OpenSSL API, too.

Why no more "/11"? Well, half the point of using AES-GCM is FIPS 140 compliance. (The other half being hardware acceleration.) If we mucked with the rounds number the design wouldn't be compliant.

Indeed, if compliance is not a goal there are a number of alternatives, from AES-GCM-SIV to modern AEAD constructions based on the AES core. The specification has an extensive Alternatives section that compares each of them to XAES-256-GCM.

Also included in the specification are test vectors for the two main code paths (MSB₁(L) = 0 and 1), and accumulated test vectors that compress 10 000 or 1 000 000 random iterations.

To sum up, XAES-256-GCM is designed to be a safe, boring, compliant, and interoperable AEAD that can fit high-level APIs, the kind we'd like to add to Go. It's designed to complement XChaCha20Poly1305 and AES-GCM-SIV as implementations of a hypothetical nonce-less AEAD API. If other cryptography library maintainers like it (or don't), I would love to hear about it, because we are not big fans of adding Go-specific constructions to the standard library.

By the way, I have an exciting update about my professional open source maintainer effort coming in less than two weeks! Make sure to subscribe to Maintainer Dispatches or to follow me on Bluesky at @filippo.abyssdomain.expert or on Mastodon at @[email protected]. (Or, see you at GopherCon in Chicago!)

The picture

Earlier this year I ran in the Centopassi motorcycle competition. It involves driving more than 1600km on mountain roads, through one hundred GPS coordinates you select in advance from a long list, in three days and a half. It's been fantastic. It took me to corners of Italy I would have never seen, and I had a lot of fun. This picture is taken at our 100th location, after a couple kilometers of unpaved hairpins on the side of the hill. The finish line was at the lake you can see in the distance. I was ecstatic.

That's my 2014 KTM Duke 690, a single-cylinder "naked" from before KTM knew how to make larger street bikes. It's weird and I love it.

My awesome clients–Sigsum, Latacora, Interchain, Smallstep, Ava Labs, Teleport, SandboxAQ, Charm, and Tailscale–are funding all my work for the community and through our retainer contracts they get face time and unlimited access to advice on Go and cryptography.

Here are a few words from some of them!

Latacora – Latacora bootstraps security practices for startups. Instead of wasting your time trying to hire a security person who is good at everything from Android security to AWS IAM strategies to SOC2 and apparently has the time to answer all your security questionnaires plus never gets sick or takes a day off, you hire us. We provide a crack team of professionals prepped with processes and power tools, coupling individual security capabilities with strategic program management and tactical project management.

Teleport – For the past five years, attacks and compromises have been shifting from traditional malware and security breaches to identifying and compromising valid user accounts and credentials with social engineering, credential theft, or phishing. Teleport Identity Governance & Security is designed to eliminate weak access patterns through access monitoring, minimize attack surface with access requests, and purge unused permissions via mandatory access reviews.

Ava Labs – We at Ava Labs, maintainer of AvalancheGo (the most widely used client for interacting with the Avalanche Network), believe the sustainable maintenance and development of open source cryptographic protocols is critical to the broad adoption of blockchain technology. We are proud to support this necessary and impactful work through our ongoing sponsorship of Filippo and his team.

SandboxAQ – SandboxAQ's AQtive Guard is a unified cryptographic management software platform that helps protect sensitive data and ensures compliance with authorities and customers. It provides a full range of capabilities to achieve cryptographic agility, acting as an essential cryptography inventory and data aggregation platform that applies current and future standardization organizations mandates. AQtive Guard automatically analyzes and reports on your cryptographic security posture and policy management, enabling your team to deploy and enforce new protocols, including quantum-resistant cryptography, without re-writing code or modifying your IT infrastructure.