crypto/cipher: add NewGCMWithRandomNonce

[FiloSottile]

NIST SP 800-38D and in particular FIPS 140-3 IG C.H essentially require that AES-GCM nonces be either generated according to an industry protocol (TLS, SSH) or internally at random by the cryptographic module.

This makes somewhat sense, because AES-GCM nonce reuse is catastrophic and common enough. It makes somewhat less sense because AES-GCM nonces are 96 bits, making the birthday bound of messages that can be encrypted with random nonces with low enough (2⁻³²) chance of collisions a mere 2³² (~4.3 billions).

Anyway, we should offer applications a way to comply with the requirement, and wire it up to the appropriate #69536 API.

The simplest proposal I can think of is to copy NewGCM, folding the NonceSize into the Overhead, like #54364.

// NewGCMWithRandomNonce returns the given cipher wrapped in Galois Counter
// Mode, with randomly-generated nonces. The cipher must have been created by
// [aes.NewCipher].
//
// A 96-bit nonce is randomly generated and prepended to the ciphertext by Seal,
// and is extracted from the ciphertext by Open. The NonceSize of the AEAD is zero,
// while the Overhead is 28 bytes (the combination of nonce size and tag size).
//
// A given key MUST NOT be used to encrypt more than 2^32 messages, to limit the
// risk of a random nonce collision to negligible levels.
func NewGCMWithRandomNonce(cipher Block) (AEAD, error)

Do we want to take the opportunity to make the API return a concrete type? #54364 doesn't and to me it feels like it's not worth breaking the pattern yet (or having it not sort next to the other NewGCMs).

This will have the same implementation challenge described in #54364 (comment): since plaintext and ciphertext don't overlap perfectly when the buffer is reused, Seal will need to avoid stepping over itself.

I regret we are growing a bit of a zoo of AEADs with different properties, but I can't see a way around it (and it's in good part due to the fact that we have only had a bunch of imperfect options for decades, each sub-optimal in different ways): we'll have NewGCMSIV, NewGCMWithRandomNonce, and maybe XAES and XChaCha20Poly1305 with automatic nonces, of which NewGCMWithRandomNonce and NewGCMSIV have a low birthday bound, but NewGCMSIV is collision resistant (as in, it degrades to safe deterministic encryption); and then NewGCM (and the WithNonceSize and WithTagSize variants), NewGCMSIVWithNonce, chacha20poly1305.New, and chacha20poly1305.NewX with manual nonces, of which only NewGCMSIVWithNonce is nonce-misuse resistance. We should eventually clean this all up with a v2 API that only provides the safe ones with automatic nonces, probably with a different interface, but not in Go 1.24.

[gabyhelp]

Related Issues and Documentation

• x/crypto: add AES-GCM-SIV #54364
• crypto/cipher: NewGCMWithNonceSize allows zero-length nonce #37118 (closed)
• Package cipher > type AEAD ¶ 1.2 > func NewGCMWithNonceSize ¶ 1.5
• Package cipher > type AEAD ¶ 1.2 > func NewGCM ¶ 1.2
• crypto/cipher: Support unusual GCM nonce lengths

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[aclements]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.

[aclements]

It's unfortunate that we need yet another NewGCM function, but this is at least consistent with the existing API.

[aclements]

and is expected to be prepended to the plaintext by Open.

I'm not sure I understand this. Expected by whom? NewGCMWithRandomNonce is returning an AEAD, which implements Open. Doesn't that mean it has full control over what Open does with the nonce?

Do we want to take the opportunity to make the API return a concrete type?

I agree with you that consistency with the existing API is better. Another thing for crypto/v2 perhaps. 😄

[FiloSottile]

I'm not sure I understand this. Expected by whom? NewGCMWithRandomNonce is returning an AEAD, which implements Open. Doesn't that mean it has full control over what Open does with the nonce?

Poor wording on my side, reworded to read

// A 96-bit nonce is randomly generated and prepended to the ciphertext by Seal,
// and is extracted from the ciphertext by Open. The NonceSize of the AEAD is zero,
// while the Overhead is 28 bytes (the combination of nonce size and tag size).

What I am trying to convey is that you don't need to think about the nonce, it's just a ciphertext prefix that Seal and Open know about.

[aclements]

Based on the discussion above, this proposal seems like a likely accept.

The proposal is to add the following to crypto/cipher:

// NewGCMWithRandomNonce returns the given cipher wrapped in Galois Counter
// Mode, with randomly-generated nonces. The cipher must have been created by
// [aes.NewCipher].
//
// It generates a random 96-bit nonce, which is prepended to the ciphertext by Seal,
// and is extracted from the ciphertext by Open. The NonceSize of the AEAD is zero,
// while the Overhead is 28 bytes (the combination of nonce size and tag size).
//
// A given key MUST NOT be used to encrypt more than 2^32 messages, to limit the
// risk of a random nonce collision to negligible levels.
func NewGCMWithRandomNonce(cipher Block) (AEAD, error)

[gopherbot]

Change https://go.dev/cl/624916 mentions this issue: crypto/internal/fips/aes/gcm: add SealWithRandomNonce

[glycerine]

With such a low birthday bound for these short random nonces, it seems like it would be worth keeping a use count and defining a distinguished error message that is returned if the same key is used, say, 2^32 - 4096 times, to let the user know that re-keying will be needed "real soon now", as your security is "on the edge" of collapsing.

[ericlagergren]

It should probably just return an error once it's hit the upper limit. That doesn't really help if you're using two copies of the key, though.

[wadey]

Could we also support this new SealWithRandomNonce with the current boringcrypto experiment so that we can use it until Go gets its own FIPS approval?

boringcrypto has the method:

// EVP_aead_aes_256_gcm_randnonce is AES-256 in Galois Counter Mode with
// internal nonce generation. The 12-byte nonce is appended to the tag
// and is generated internally. The "tag", for the purpurses of the API, is thus
// 12 bytes larger. The nonce parameter when using this AEAD must be
// zero-length. Since the nonce is random, a single key should not be used for
// more than 2^32 seal operations.
//
// Warning: this is for use for FIPS compliance only. It is probably not
// suitable for other uses. Using standard AES-GCM AEADs allows one to achieve
// the same effect, but gives more control over nonce storage.
OPENSSL_EXPORT const EVP_AEAD *EVP_aead_aes_256_gcm_randnonce(void);

[aclements]

@wadey , please file a separate proposal for that. Thanks!

With such a low birthday bound for these short random nonces, it seems like it would be worth keeping a use count and defining a distinguished error message that is returned if the same key is used, say, 2^32 - 4096 times

I don't see how to do this practically... NewGCMWithRandomNonce can't see through the Block interface to know what key is being used. And if it could (which is not a backdoor I'd want to open up), it would have to somehow keep a running count of how many times each key has been used, which would be a global and growing data structure, and would mean keeping either the key or at least some fingerprint of the key in memory. And if multiple processes are using the same key (say, loaded from the file system), none of this would help anyway.

[aclements]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.

The proposal is to add the following to crypto/cipher:

// NewGCMWithRandomNonce returns the given cipher wrapped in Galois Counter
// Mode, with randomly-generated nonces. The cipher must have been created by
// [aes.NewCipher].
//
// It generates a random 96-bit nonce, which is prepended to the ciphertext by Seal,
// and is extracted from the ciphertext by Open. The NonceSize of the AEAD is zero,
// while the Overhead is 28 bytes (the combination of nonce size and tag size).
//
// A given key MUST NOT be used to encrypt more than 2^32 messages, to limit the
// risk of a random nonce collision to negligible levels.
func NewGCMWithRandomNonce(cipher Block) (AEAD, error)

[wadey]

Can we make this method compatible with the equivalent BoringCrypto one? BoringCrypto appends the generated nonce to the tag, where as this proposal says it will be prepended to the cipher text instead.

[gopherbot]

Change https://go.dev/cl/629175 mentions this issue: crypto/cipher: add NewGCMWithRandomNonce

[aclements]

Can we make this method compatible with the equivalent BoringCrypto one? BoringCrypto appends the generated nonce to the tag, where as this proposal says it will be prepended to the cipher text instead.

@FiloSottile , mind weighing in on this?

[FiloSottile]

The convention is pretty universally to prepend the nonce to the ciphertext.

The BoringSSL equivalent, EVP_aead_aes_256_gcm_randnonce, is purely a compliance API, so I understand their choice of appending the nonce to the tag, as it makes implementing this way way easier, but unless we also plan to mark ours as effectively deprecated, I think we should do the extra work to make it generally useful.