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.


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.

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)
Construct the AEAD header, let {HEADER} = {AAD || S}
Generate the ciphertext and tag, let {C, T} = ENC(HEADER, P, K, IV)
Output the final message, let {MSG} = {HEADER || C || T}

Decrypt Procedure
Extract the salt from the AEAD header, let {S} = MSG.HEADER.S 
Generate a derived Key and IV, let {K, IV} = KDF(M, S, I)
Validate the AEAD message, let {res} = AUTH(MSG, K, IV)
if res is FAILED, output error. 
else Extract the ciphertext, let {C} = MSG.C
Output the plaintext, let {P} = DEC(C, K, IV)
  • 1
    $\begingroup$ Be aware that FIPS 140 has specific ways to generate keys so your KDF is limited to what's there. You can't create keys in any way you want. $\endgroup$ Apr 16 at 15:00
  • $\begingroup$ @Swashbuckler, definitely. I'm more concerned if using AES-GCM in this way is valid, as it determines the design of the architecture. Pouring over the details of FIPS-140 and designing KDF is future me's problem. $\endgroup$
    – BlamKiwi
    Apr 16 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.