GCM cannot be used with random nonces

[wbl]

A nonce collision with GCM is devastating, and there is a 2^{-43} probability of such a collision every single time a message is generated.

[GUIpsp]

What is your suggestion? I think the odds are low enough that this isn't a good attack vector.

[wbl]

I misquoted, it's the birthday bound. Use a mode designed to take random IVs instead of nonces. There are some out there, like AES+CBC followed by HMAC of the ciphertext, but you probably want counter for efficiency. Let me work on it.

[gtank]

Since this keeps coming up (#10, #17), I should probably document my rationale for random-nonce GCM.

In most applications of authenticated encryption, bookkeeping related to nonces is THE point of failure for developers. The NIST recommendations for GCM discuss the design issues of deterministic nonces in section 8.2.1 and lean heavily on the protocol designer to ensure that it's difficult to repeat a nonce. By contrast, it's fine with 96-bit random nonces (as long as the entire field is random) without as many assumptions about the application.

Even in a full protocol like TLS, which is arguably the ideal use case for counter-nonce GCM (it has ephemeral keys bound to a natural counter and doesn't even expose GCM directly) we see widespread problems with nonce management.

I haven't provided a full protocol of any kind here. Instead, I tried to build something that will serve well when you need to encrypt some stuff without adding complex and brittle new state to an application. So I make the birthday-bound tradeoff because it

1. avoids an extremely high risk of a worse problem
2. makes integration with existing code easier
3. is less of a concern in encryption tasks app developers encounter than it is in the design of internet-scale protocols like TLS

I'll elaborate on point 3 here: GCM has inherent limitations on the number of encryption operations you can safely do with a single key, regardless of how you manage nonces. It's a very large number, and if you're getting close to that scale (as you might using TLS on a popular website) then birthday collisions won't be the first thing you hate about this code.

@wbl You are totally right that the failure mode for AES-CBC+HMAC is gentler, but that introduces the questions of padding, composition, and choice of hash algorithm. I prefer to tell people about GCM, which should be good enough in most direct use cases and is definitely the option non-specialists should choose when looking at protocol settings today.

[njaremko]

But the problem is that random nonces are much worse than a counter...as an example, the paper that you linked above found 184 https servers not properly incrementing their counter, but they also found 70,000 servers using random nonces (which they also say is bad).

Telling people that a random nonce is okay could very well lead to faulty encryption implementations (which we're supposed to be avoiding). Furthermore, examples like the paper you linked refer to GCM in the context of TLS, but most people using this code won't be implementing their own TLS server, they'll be encrypting files, etc...

Implementing a proper counter isn't very difficult (the vast majority of the webs TLS sessions are fine), and it doesn't suffer from the same birthday problem collision issues.

[FiloSottile]

We are all on the same page about the birthday bound of random nonces.

However what I think you are overlooking is the 2^{-5} to 2^{-10} probability (to be insanely optimistic) that whoever copy pasted this code would:

• neglect to save the counter at all
• fail to save the counter correctly
• end up losing state somehow

The probability figure is clearly tongue-in-cheek, but I hope you see what I mean.

[FiloSottile]

Also consider that TLS is a very best case for keeping counter nonces, with its sequential packets and session-bound keys. But as you say people will use this code to encrypt files always with the same key across restarts, across different machines, ...

[elithrar]

To necro this thread, and although I think the chances of a nonce collision for longer-term storage (as opposed to a high rate of individual datagrams) is being overstated, why not ChaCha20+Poly1305 as the AEAD in this "library" ala libsodium?

@gtank

[gtank]

@elithrar I wanted to limit myself to the standard library and x/crypto/secretbox (which is XSalsa20 anyway) is notably slower than AES on common platforms. ChaCha-Poly is one of the things (like ECDSA vs EdDSA) that's on my list of recommendations to update when they're ready.

[Yawning]

I question the wisdom of recommending something that is not guaranteed to be timing side-channel free.

golang/go@850e55b