# Constructing an XChaCha20-Poly1305 Equivalent using FIPS-140 Primitives

I am playing around with the idea of modelling clustered data storage as a series of AEAD messages. XChaCha20-Poly1305 has nice properties for my intended design, as the ability to use random IVs decouples constructing AEAD messages from the state of the storage cluster. However FIPS compliant primitives would be a business requirement in a production implementation.

AES-GCM is the obvious first choice, however its 2^32 invocation limit for random IVs does not lend itself well to data storage. The total write throughput might be 100s of TiBs over the lifetime of a system. Having a global monotonic counter, like the FIPS specification suggests, is difficult to implement in my case. The architecture doesn't have a notion of a "secure global clock" (at least not one that wouldn't be vulnerable to Replay or Sybil attacks).

Is it possible to construct an AEAD Cipher with similar properties to XChaCha20-Poly1305 using only FIPS-140 primitives?

The properties I am interested in are:

• Single pass encryption.
• Hardware/FPGA implementation friendly.
• A nonce can be any random value. (No global state to track)
• A large upper bound on maximum invocations per key. (~2**50)
• The primitives are listed in the FIPS-140-3 standard.

I already have a scheme in mind, detailed below. I'm interested in feedback on how it could be improved, or if there would be a better alternative I've overlooked. I'm aware of AES-GCM-SIV, but who knows when, if ever that will become an approved function. An alternative could be AES-XTS + KMAC, however that would be quite resource intensive.

Scheme

Derive a random <Key, IV> pair for each AES-GCM invocation using a salt, and transmit the salt as part of the associated authenticated data.

State:
Let {M} be a pre-shared master key of at least 256 bits.
Let {S} be a randomly generated salt of at least 256 bits.
Let {I} be associated data relevant for generating the key. May be empty.
Let {P} be the plaintext message to encrypt.
Let {AAD} be associated data to interpret the ciphertext message.
Let {KDF} be a key derivation function listed in NIST SP 800-56C.
Let {ENC} be a FIPS-140 compliant AES-GCM encrypt function.
Let {DEC} be a FIPS-140 compliant AES-GCM decrypt function.
Let {AUTH} be a FIPS-140 compliant AES-GCM authentication check function.
Let {C} be the ciphertext.
Let {T} be the authentication tag.
Let {MSG} be the final AEAD message.

Encrypt Procedure:
Generate a derived Key and IV, let {K, IV} = KDF(M, S, I)