The XAES-256-GCM extended-nonce AEAD

The design is very clever: since it's based on CMAC, we can use AES-CBC to derive keys where lower level primitives are not available.

In AES-CBC terms, the algorithm can be described as:

    1. L = AES-CBC-256ₖ(iv = 0¹²⁸, plaintext = 0¹²⁸)[:16]
    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-CBC-256ₖ(iv = K1, plaintext = M1)[:16] || AES-CBC-256ₖ(iv = K1, plaintext = M2)[:16]
    6. Nₓ = N[12:]

Where AES-CBC-256 returns the first 128-bit block of the ciphertext, discarding the padded block. (Thus, if you can't turn off padding, it costs three additional AES calls with the same key compared to a lower level implementation — not bad). After deriving a key, use it with the standard AES-GCM.

Here's my JS implementation based on WebCrypto API, which uses this fact: https://github.com/dchest/xaes

It accepts a proper CryptoKey intended for AES-CBC, supporting all CryptoKey features, e.g. storing it in IndexedDB with "extractable" bit set to false.

Great job, Filippo!

It seems like this removes the footgun in vanilla AES-GCM where you really need to rotate keys every ~2^32 messages if you are using a random nonce. Nonce collision in AES-GCM is catastrophic (it allows attackers to at least sign arbitrary messages). You don't need to use a random nonce, but it's usually recommended. Fairly clever to use two primitives (counter-based KDF and vanilla GCM) to make this FIPS compliant.

This is freaking fantastic- I only wish it existed when I wrote my last encrypted filesystem a few years back.

Nonce collision is a huge concern on large file system deployments. 2^32 seems huge but when you’re writing 100k iops a second on a PB array the chance of collision is almost guaranteed if you’re betting on PRNG randomness.

I would love to see this used in a FIPS-compliant variant of age[1] for archival file encryption use cases. We had banking industry auditors veto age for this use case due to the use of ChaCha instead of AES (they were fine with the X25519 public key part of age which I think was somewhat recently approved by NIST).

I’ve no experience with golang but it seems like it should drop right in based on the age spec. I might give it a shot if time ever permits. I guess I should call it “cage” as in “compliant actually good encryption”

1: https://github.com/FiloSottile/age

Question from a non-cryptographer: why use 192bit nonces instead of 256? I can’t imagine those extra bits would be considered costly in any practical application.

>(2⁸⁰ messages with collision risk 2⁻³²)

Would there be an issue before that due to the fact that the AES block size is only 128 bits?

> safe, boring, compliant, and interoperable

My favorite kind of technology.

I like it, because it is indeed nice to have a NIST-backed construction.

But at the same time, it is disappointing that you get locked out of several niceties of NIST KDFs, such as label and context. I get that they are sacrificed to minimize the number of AES calls, but still I would prioritize strong cryptographic separation over just a few saved AES calls, especially for messages longer than a few hundred bytes.

Finally, *random* GCM nonces longer than 96 bits are definitely misunderstood and bring better guarantees than 96 bits nonces [1]. But of course, if you can derive a fresh key for every message, that's definitely to prefer.

[1] https://neilmadden.blog/2024/05/23/galois-counter-mode-and-r...