Galois/Counter Mode and random nonces | Hacker News Reader

Galois/Counter Mode and random nonces

neilmadden.blog

66 pointsthunderbong26 comments

XSalsa and XChaCha do something extremely similar. In order to extend the nonce space by 128 bits you basically run a round of ChaCha against 128 bits of your nonce. Those 128 bits represent 96 bits of nonce and 32 bits of counter. Because you know you'll never encode more than 1 full block of data, the counter won't overlap. 256 bits of internal state become the key for the next round of ChaCha plus the remaining 64 bits of nonce and you get to use the full counter space because nonce just became the key.

The paper is also extremely approachable.

https://cr.yp.to/snuffle/xsalsa-20110204.pdf

I wonder if processes like this extend cryptographically in most symmetric ciphers. To add more nonce, encrypt your nonce, output becomes key for next round, add more nonce, repeat. Like all things crypto though, your search space could absolutely collapse if the cipher doesn't have the right properties.

In my experience nonce reuse doesn't happen because of a probabilistic collision. It happens instead because people who don't know the history or context of what they're doing make a change to the code base that results in the nonce being reused, and there were guardrails missing that should have been there to help prevent it.

It stems from hubris I see repeatedly in the software engineering industry. "I know the constraints and am capable of engineering to them, so don't lecture me about the potential dangers. I'll just make sure we do it right, because I'm smart and capable and can do it right."

They think the problem they need to solve is to write code that's correct today, while the actual problem they need to solve is that it remains correct tomorrow, next quarter, next year, and next decade. Based on repeated failures in this category I've personally witnessed, the majority of software engineers with fewer than ~10 years of industry experience lack an intuition about how software changes over time as people come and go.

> "random nonces"

I find it amusing in spite of the various words that have fallen out of favour in recent times for political reasons, "nonce" continues to soldier on.

I would guess that it's because it doesn't have any special meaning in American English primarily, most Americans have never even heard of its meaning in British slang

I in fact only learned the slang meaning five seconds ago when this discussion made me google it.

Agree, most of the Brits I know think it's hilarious that it's ended up as a term of art, and Americans are generally completely oblivious to its meaning.

I am in no great hurry to change the word though. It's not something that comes up much outside of extremely technical contexts, and whilst it's a bad word, its regional character and multiple meanings kinda make it fine. It's not like it is being used for the meaning that's offensive, the meanings have unrelated histories (and the offensive one is much newer).

I don't think it would be right to change an ordinary English word because it sounded similar to an offensive word in a foreign language, and I think that's essentially what's happened here.

There was actually an NFT startup a while back that called itself "Nonce Finance." They wound up rebranding.

Just googled it... yikes not the cryptography joke I was expecting...

Probably because this unfortunate state of affairs is very appealing to the British dark sense of humour. Americans seem much more inclined to want to replace any term that is even obliquely offensive.

See also “Fanny pack” which has made its way into British English despite the crudeness.

I do wish there was some alternative word so that I can discuss cryptography with my countryfolk.

It has not, it remains a term of abuse.

> If it is not 96 bits, then the value is first hashed with GHASH, GCM’s universal hash function, and the full 128-bit output becomes the initial counter value: [---] However, we can’t just assume that the output of GHASH is ideal with respect to collisions

They already special-cased 96 bits, so couldn't they have special-cased 128 bits to be direct addition, without concatenation?

Sure, they could have - but didn't. Probably because they were strongly biased toward nonces being generated by a counter, and separating an external 'message counter' from the internal 'block counter' is a nice scheme to have essentially unlimited, large messages without any concern for nonce reuse.

Except for subsequent experiences showing us that reliably keeping track of a counter can be a lot harder than it first appears, hence the attractiveness of randomized nonces.

At the end it mentions a nonce based approach probably being the more sensible way. Shay Gueron presented at RWC 2024 about a nonce based approach (DNDK-GCM): https://www.youtube.com/watch?v=GsFO4ZQlYS8&list=PLeeS-3Ml-r... -- they mention Meta are using this as their default in their encryption library.

There is also an internet draft on it: https://datatracker.ietf.org/doc/draft-gueron-cfrg-dndkgcm/

See also perhaps:

> AES-GCM-SIV is a mode of operation for the Advanced Encryption Standard which provides similar performance to Galois/Counter Mode as well as misuse resistance in the event of the reuse of a cryptographic nonce. The construction is defined in RFC 8452.[1]

* https://en.wikipedia.org/wiki/AES-GCM-SIV

In my opinion, the author understates how good AES-GCM-SIV is:

> The solution they designed is described in that linked paper: AES-GCM-SIV, which is able to tolerate some number of nonce collisions, but under a weaker notion of security that is only really applicable to that use-case (where the data being encrypted is itself random).

AES-GCM breaks catastrophically if you reuse a nonce; but the only thing that happens if you reuse a nonce with AES-GCM-SIV for two messages is that an attacker can see if the messages are equal (since AES-GCM-SIV is a deterministic algorithm, this is pretty much unavoidable). So yes, "weaker notion of security", but still applicable to a lot more than just that use-case. I wonder why AES-GCM-SIV is not used more, since it's so developer-friendly and misuse resistant.

(Article author here).

Being able to see if two messages are equal means that it doesn’t even achieve IND-CPA security (when nonces repeat). Although this may seem like a small loss of security, it can have significant consequences. For example, when you are performing encryption of long messages, you generally want to split them into smallish chunks -- otherwise you’ll likely have to release unverified plaintext during decryption unless you buffer the entire message in memory. But now if your AEAD reveals message equality, like AES-GCM-SIV does under nonce reuse, then an attacker can see when chunks are equal if you are not careful. So you can end up vulnerable to the kind of chosen plaintext attacks that are devastating against ECB encryption.

Phillip Rogaway, co-inventor of the original SIV mode and the MRAE security model, discusses BEAST-style chosen plaintext attacks against online encryption modes using MRAE schemes in https://eprint.iacr.org/2015/189.pdf. As he says in that paper: "The paper defining MRAE never suggested that nonce-reuse was OK.” It leads to security weaknesses, and AES-GCM-SIV has increasing likelihood of nonce reuse after 2^32 messages.

So, yes, AES-GCM-SIV is a lovely piece of work, but if you want to encrypt large numbers of messages with a single key, then you need to be very aware of the security definitions. I wouldn’t recommend it for general use.

> AES-GCM-SIV has increasing likelihood of nonce reuse after 2^32 messages.

While I agree on your cautions, this is still an exceptionally large number. Also AFAIK the actual bound depends on the message size, e.g. you can "safely" encrypt 2^64 messages of ~128 KiB each with the identical key but random nonce. So as long as one keep using as random nonce as possible but allowing for a few exceptional reuses, casual developers indeed have a very low chance to actually reach that threshold.

Talking about Rogaway: I implemented OCB3 a long time ago as an exercise (after failing for many weeks to get GCM working. I am neither a programmer nor mathematician). Iirc it could have any nonce length up to 120ish bits. I don't remember much from it.

Could it be extended in a similar way to be more like xchacha with 192 bit nonces where using random nonces are easier?

I don’t remember much about the specifics of OCB. But the xchacha/xsalsa20 approach is completely generic, so can be applied to any cipher: effectively just run a large nonce through a PRF to derive a fresh key for each message.

Sorry, but to my UK friends the phrase "random nonces" holds a different interpretation to the rest of us. Learned that one from sorry experience.

the general problem seems to be when a protocol uses the counter as a diversification component, it becomes another secret value to manage. I can't think of an example where it is and isn't, but only using an authenticated counter (via something like hotp or a ratchet) is a subtle design challenge.

The GCM (or XSalsa, or...) nonce is not secret - in almost all protocols the nonce goes over the wire in plaintext! - but must be a number-used-once. Those are quite distinct requirements.

this is also notably true for pretty much all uses of IV/nonces/salts. They are intended to provide randomization to an otherwise deterministic process (similar to specific types of RSA/DSA padding) to avoid being able to brute force/easily determine the contents from known examples. For ex: known plaintext attacks being one common example.

It’s the same reason salts are used in passwords - there will be people using the equivalent of ‘password’, and without a salt it would be trivial to find them with just a lookup table (often in nearly O(1) time). With a salt it at least requires per-entry hashing of possible values per user, with no re-usability between users. So O(n^p) time (worst case) where n == number of users, p == number of possible values to test. A pretty huge difference.

Without the person on the other end having the value of the IV/nonce/salt, you might as well just stuff random bytes into the cyphertext field instead of the actual cyphertext, as if the algorithms are designed correctly they would be indistinguishable anyway.

The counter starts from an initialization value (IV), which does not need to be secret. What should be ensured (to prevent forgery attacks) is that each possible (key, initialization value) pair is never used twice.

There are two standardized ways (from NIST’s SP 800-38D) of ensuring unique (key,IV) pairs:

1. Use either a random number generator to make a nonce for the entire IV, or 2. Construct an IV by concatenating two fields, one field for the most significant bits set it to zero and increment it every time the key is used, the other is simply a fixed at zero.

With the second option, some new limitations exist to maintain the constructed IV’s uniqueness. The first being how many blocks of data you can encrypt in an operation (2^(size(fixedfield)) because you don’t want to overflow into your key-reuse field. The second is being the number of times you can reuse the key is now limited to 2^size(keyreusefield).

reuse in implementations is common, and most protocols need to handle an asynchronous "offline" mode which means a sliding window of valid counters, and a thread to pull. the difference between a single use key and a limited use key is significant and has been known to get fudged somewhere between approved spec and implementation.

Sure don't reuse the IV and make sure it can't be easily derived or guessed, but if I'm looking for problems in an implementation, my point was that counter usage is one of the low-entropy threads to pull.

Why not just treat the entire IV as a big integer with that many bits? With AES-128 the IV is also 128 bits, which is effectively infinite. It's roughly the same number as the number of sand grains in the visible universe.

It's simple enough to implement as well, it's just two 64-bit additions with a check for wraparound on one of them.

Reply on news.ycombinator.com