GCM (ie. AES-GCM) has the following problems, which extended variants - those that deterministically randomize (key,nonce) pair - do not solve:
Inability to encrypt more than 64Gb with the same (key,nonce) pair.
Lack of commitment (whether key-commitment, or key+nonce+ad commitment).
If one is seriously considering breaking away from existing GCM standards to create yet-another-standard, such proposal would need to offer improvements in all areas (ex. a proposed standard for converting any AEAD into streaming chunk-based AEAD with practically unlimited message sizes under the same (key,nonce) and unlimited message counts.
GCM-256 is ubiquitous and is often the preferred choice for all the reasons mentioned by the author, but that very argument is what makes non-standard GCM with 11 AES-rounds silly.
In 2023 we should be working on new standards that "wrap" existing crypto-primitives (which are already implemented/available in countless hardware-accelerated libraries/APIs) to get additional features/benefits/capabilities - not musing about AES with 10+1 rounds or SHA-512-really-fast with 80-1 rounds..
> Inability to encrypt more than 64Gb with the same (key,nonce) pair.
I think a better way is to derive the content per file part and then use a ratcheting nonce to encrypt the subparts. That also gives you random access into the entire file in ~O(1) (i.e. no need to decrypt the entire file) and the ability to interrupt and resume decryption. Unfortunately, there's no standard that describes how the output should be serialized, so tool interop becomes a problem. Although, to be fair, there's no serialization standard for AES either (i.e. what do you do with the nonce?) so it's probably not a big deal.
The issue with 64GB is one thing. Not many people encrypt single 64GB files. But people do use aes-gcm for tunnels and encrypting billions of messages and you can only use the key so many times before you have to rotate. Many people screw this part up.
I think it's easier than that. When using the IV using a 96 bit fixed field and 32 bit counter, FIPS SP800-38d says you are limited to 2**32 "invocations of the authenticated encryption function with any given fixed field and key". What they call the fixed field is the common 96 bit IV or nonce.
So you can do 512Gb or 64GB under one nonce. Then simply increment the fixed field and run the next 64GB under the same key and new nonce (nonce+1) and so on. In essence, it's the same thing is just making the fixed field smaller and the counter bigger, but meets the letter and intent of the law. The "fixed field" can be anything the user wants, including being "constructed from two or more smaller fields". And it is not constrained to remain the same under multiple invocations. Still compatible with FIPS and common implementations. It doesn't have to be some fancy ratcheting scheme.
The initial "fixed field" or nonce could even always just be all zeros [1]. It doesn't matter, it's not secret.
If for some reason you want to encrypt that much under one key, which I think you really don't.
The problem with this is that if the nonce ever collides under the same key, GCM's security falls to pieces, and so if you're using the nonce as an extended counter --- a thing people do, in part because they're worried 96 bits is too short to safely choose randomly --- you have to design a system that can't use the nonce "0" (or "1" or "2") twice.
If all your keys are ephemeral this isn't a big worry, but if they aren't, you can end up talking about reliably keeping state between invocations of your whole program.
> you have to design a system that can't use the nonce "0" (or "1" or "2") twice.
just like any counter mode. it's vitally important, but not difficult to understand or implement.
the other point is, WHY NOT JUST ROLL THE KEY MORE OFTEN. nobody should be encrypting 64GB under the same key. and 96+256 is enough bits that can be chosen randomly to never worry about collisions.
This bit about it not being difficult to implement is false. The single most damaging vulnerability class of the last 25 years came from the inability of programmers to reliably count bytes. It's simple to come up with something that works reliably without the presence of an adversary. But as soon as you add an adversary who will manipulate inputs and environments to put you into corner cases, counting becomes quite difficult indeed, no matter how simple you think it is to understand counting.
If you create the opportunity to make a mistake remembering to freshen a nonce, even if that opportunity is remote, such that you'd never trip over it accidentally, you've given attackers a window to elaborately synthesize that accident for you. That's what a vulnerability is.
There is a whole subfield of cryptography right now dedicated to "nonce misuse resistance", motivated entirely by this one problem. This is what I love about cryptography. You could go your entire career in the rest of software security and not come up with a single new bug class (just instances of bug patterns that people have been finding for years). But cryptography has them growing on trees, and it is early days for figuring out how to weaponize them.
That's why people pay so much attention to stuff like nonce widths.
Say what now? GCM is itself vulnerable to CCA in a nonce reuse scenario - exactly the subject of this thread. Not to mention padding oracle attacks against CBC mode etc. Almost all modern symmetric ciphers achieve CCA security by combining the cipher with a MAC to create an AEAD mode. So if your AEAD mode gives up the MAC subkey, as GCM does under nonce reuse, then you lose all CCA security, and usually starting leaking details about plaintexts not long after.
Sigh. If you're talking about crypto, then terms actually matter. GCM is not a symmetric cipher.
It's a cipher mode. You can use GCM with any block cipher. OK, I assume that you meant AES-GCM.
But GCM as a construction in itself is not vulnerable to chosen ciphertext attacks, as long as the underlying symmetric cipher is secure.
GCM will lose the authentication property, if you know the authentication key, which you _might_ be able to get if you can mount a chosen _plaintext_ attack under conditions of nonce reuse. Simply getting a couple of random messages with the same nonce is NOT enough.
AES-GCM as specified has a nonce that is large enough to not care about it in practical cases (e.g. TLS), and it can become a problem only in very unrealistic cases (attacker-controlled likely exabyte-sized plaintexts).
These cases are maybe _juuuust_ in the realm of possibility, if you have access to a supercomputer, and you want to specifically design an application that is vulnerable to an attack, and then allow your adversary to covertly connect to your supercomputer cluster. To be clear, we're talking here about repurposing the entire NSA computing and storage power to host this single application, and allowing the attacker (e.g. Russian troll farms) to completely control the plaintexts that it transmits.
Extending the nonce to 256 bits would move that from outside the realm of possibility even for a contrived scenario. It's not a bad idea, but it's also not at all an urgent one.
> Simply getting a couple of random messages with the same nonce is NOT enough.
Yes it is. You simply XOR the two auth tags and then compute the roots of the resulting polynomial (with known coefficients). There typically aren’t that many candidate roots to test. This has been known since GCM was first specified, see eg Joux’s comments: https://csrc.nist.gov/csrc/media/projects/block-cipher-techn...
It’s clear from your comments here and elsewhere that you don’t know what you are talking about, so I’ll take tptacek’s advice and bow out here.
I don't think you can walk back your previous comment, which was pretty categorical. Either way, we're clear about the brittleness of GCM at this point, and there's little else for us to talk about.
Brittleness? Not really. It's not completely future-proof, and it would be easier if a larger nonce is standardized, but all realistic attacks require rather unlikely sets of circumstances.
And no, you can't recover the encryption key (i.e. the thing that allows you to decrypt messages) from any weakness in the nonce choice.
Presumably, if you're going to do an extended-nonce GCM, you could reformat the counter block (since the nonce is encoded in the key anyways) to get rid of the 64Gb limit --- but that complicates the FIPS story, I guess?
Indeed. But FIPS is not the only problem. Both the McGrew/Viega spec and subsequent NIST spec of GCM mandate a 4-byte counter - any departure from that would be "no longer GCM".
Is the argument for a small counter that nobody serious will treat it as a significant diversification component or reliable source of entropy, especially in a streaming mode? It's a counter whose function is necesesarily finite and predictable (and reversible?), if not explicitly linear. Intuitively, any substitutions or convolutions derived from it would weaken subsequent operations, no?
I think the message size limit is a bit of a red herring. Anyone using AES-GCM with messages that large is probably doing sketchy things with unauthenticated plaintext on the decryption side. A non-hazmat/not-just-for-experts cipher really needs to be chunked.
I've seen operating on unauthenticated plaintext enough times to list it as my own pet peeve with AES-GCM. But it's a problem for chunked messages too. A few years ago we released a SCRAM mode that makes very minimal changes to AES-GCM so that it mathematically can't operate on unauthenticated plaintext. https://github.com/aws/s2n-tls/tree/main/scram
I'm curious to hear more about what you've seen. My naive hope was that a proper streaming decrypt API would be enough of a pit of success that developers wouldn't be tempted to sabotage themselves.
A great amount of modern systems is copying data from A to B to C. The construct of frontends and backends implies it, or middleware, or proxies, or distributed storage, or blockchains. Even in the most complex systems, latency is one of the easiest core metrics to measure, and is always a priority. It is always lower latency to prefetch the inter-system pipelines, or to use optimistic concurrency and to preprocess data before it has been authenticated.
Chunked streaming can make the difference smaller, but even that "small" difference is beyond what is relevant to say ... filling an L1 cache, or waiting a round-trip. Some of the cases of "read before auth" I've seen have been on very small messages, but in contexts where the incentives are even further driven up, like trading or bidding protocols. It just left me thinking that we should enforce AEAD mathematically. Many practitioners often assume it already is enforced!
Has there been any situation in which 10 rounds would be utterly broken but 14 would give you "enough" of a security margin? My impression is that once you've managed to break a cipher enough to get that many rounds, you've also discovered a linear-time attack on that cipher[0]. Adding a mere 28% slowdown on that attack won't help.
[0] "Linear time" means O(n), which is computer science speak for "f(n) = an, but we ignore the a because we're only interested in the fastest growing component of the function". In some cases the a is so large as to make the algorithm in question not feasible for ANY size. Let's just pretend the attacker doesn't have that problem.
> To support this claim, we review the cryptanalysis progress in the last 20 years,
...and rationally and scientifically assuming that the rate of the progress won't increase and that there will be no major breakthroughs in the future, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3.
The crypto is already fast enough, thank you very much; many attacks work only precisely it's quite fast to brute force huge subspaces of key material.
Rogaway says he has released all his OCB patents into the public domain[1], so it sounds like OCB might be an option for greenfield projects? OTOH, I don’t see why you’d use any kind of AES in a greenfield project outside the surreal FIPS world, given how absolutely miserable constant-time software for it is. (ChaCha is kind of miserable when you don’t have at least a 32-bit ALU with a barrel shifter—that is on exactly the kind of platforms where table-based AES might actually be constant-time—but I’m not sure that’s a good enough reason.)
It is now, but when all this stuff was getting nailed down and all the standards were being written and all the AEAD libraries were being implemented it was off the table, so a lot of people feel like rehabilitating OCB isn't a great hill to die on.
There are also other minor GCM-specific issues (weak keys etc.). None of the issues are cypher-breaking, but I wouldn't say that AES-GCM is automatically the best choice for everything.
Etam absolutely allows you to authenticate an unencrypted context. In fact, you must ensure that the nonce, a piece of unencrypted context, is authenticated. Nothing stops you from throwing more stuff in there.
The only thing you can do with an integrated AEAD that you can't do with a constructed one (with standard interface and security) is include authenticated and unencrypted context halfway through an encryption.
> Etam absolutely allows you to authenticate an unencrypted context.
You can specify an EtM construction that accepts additional authenticated data. However, you can also do it insecurely (as the post I linked above describes) without realizing you did it insecurely. This is why most people prefer to use cryptographer-approved AEAD modes.
> In fact, you must ensure that the nonce, a piece of unencrypted context, is authenticated.
For CBC mode, sure. For CTR mode? Not really.
> Nothing stops you from throwing more stuff in there.
What prevents an attacker from shifting bits from the ciphertext field into the AAD field in the decrypt path and yield the same HMAC tag? Unless you have an answer to this question, vanilla "encrypt then MAC" is not sufficient. You need a better-engineered construction than that.
I'm pretty sure the linked post covered all of this nuance. Please let me know if something wasn't clear, or you feel it was missing.
> You can specify an EtM construction that accepts additional authenticated data. However, you can also do it insecurely (as the post I linked above describes) without realizing you did it insecurely. This is why most people prefer to use cryptographer-approved AEAD modes.
Sure, I agree with this. But then the advantage of AEAD over a bespoke EtM is not that AEAD allows the authentication of unencrypted context.
>> In fact, you must ensure that the nonce, a piece of unencrypted context, is authenticated.
> For CBC mode, sure. For CTR mode? Not really.
If you don't, you do not get ciphertext integrity: decryption will succeed, but mostly yield gibberish, if the adversary changes the nonce in a decryption query. This may expose a padding oracle, with all the nice attacks those things allow, depending on details of the application.
>> Nothing stops you from throwing more stuff in there.
> What prevents an attacker from shifting bits from the ciphertext field into the AAD field in the decrypt path and yield the same HMAC tag? Unless you have an answer to this question, vanilla "encrypt then MAC" is not sufficient. You need a better-engineered construction than that.
Yes, you need a well-engineered construction.
> Please let me know if something wasn't clear, or you feel it was missing.
And yes, your linked post covers all this, but that is not the point: your summary of the linked post just claims superiority of AEAD (which I took as integrated AEAD modes) over EtM because of a functionality you claim is missing from the latter. But in the same way you need a well-engineered integrated AEAD to get any kind of security, you will need a well-engineered Encrypt-then-MAC-with-AD construction to get a secure construction. And here "well-engineered" means "ensure unambiguous parsing of decryption inputs," we're not talking about high-flying stuff that doesn't have standard solutions.
In short: I accept the point of your linked post, and I agree with it. But I reject the claim that a functionality mismatch is what makes integrated AEAD better than a constructed EtM.
> This may expose a padding oracle, with all the nice attacks those things allow, depending on details of the application.
Please describe the padding oracle attack against AES-CTR you're envisioning.
> In short: I accept the point of your linked post, and I agree with it. But I reject the claim that a functionality mismatch is what makes integrated AEAD better than a constructed EtM.
Okay, I don't think we disagree then. We're just debating semantics at this point. :)
Maybe I'm missing something here or I'm just being dense but what exactly is the problem with EtM and AAD? Just use a suitable encoding like MAC(len(aad) || aad || E(plain))
Well, when that happens, I feel the need to pipe in :)
If you're careful enough to not implement a naive protocol that stitches AES+CBC and HMAC-SHA2 together (or, as tptacek put it in a podcast episode, throw some crypto potions into a cauldron and see what happens), you're probably the minority of crypto-savvy people.
They feed an IV and ciphertext into HMAC. They don't feed additional authenticated data.
If someone followed Signal's example, they either wouldn't have AEAD, or they're likely to make the exact mistake described in the post I linked above.
I don't know how to be more helpful here. I've been only repeating myself.
The IV can be any length up to 2^64-1. The reason for picking 96-bit IVs is that other values require an extra invocation of GHASH (page 15). The document recommends 96-bit for interoperability but that's by no means a requirement.
I may be misunderstanding, but this might be the thing already discussed in footnote 2 of the article: "Technically, GCM accepts longer nonces. However, nonces longer than 96 bits are hashed into a starting 128-bit counter value, leaving no dedicated counter space. (96-bit nonces are instead concatenated with a 32-bit counter.)"
That said, I find the wording of dedicated counter space a bit bizarre. There are only 128 bits per block in AES - in fact I'm not aware of a widely deployed cipher which a larger block size. Whatever goes through ghash becomes the initial plaintext passed to aes under the key (this is the counter) part and then you just increment. This is just a limitation of counter mode in general: the whole IV is technically counter space and is treated as whole when evaluating the birthday bound issue.
The critical part mentioned in the post is that XChaCha "hashes the key+nonce into a fresh key". A very similar technique is used un: AES-GCM-SIV (https://datatracker.ietf.org/doc/html/rfc8452#section-9). The improved security here comes not from any "counter space" or nonce extension per se but the fact that changing the IV changes the effective key used in the block primitive (i.e. the raw aes-encrypt function) as well as the first block of plaintext fed to AES by deriving these from nonce+key.
So I guess this is asking for a somewhat different construction. Personally aside from the fact it is already widely deployed I'm not sure I'd keep GHASH.
The SIVs have somewhat different security properties than straight AEAD; they're usually a win, but not always. Moreover: the whole point of doing an extended-nonce AEAD is to avoid the extra mechanism of a nonce-misuse-resistant AEAD by giving yourself enough headroom to just pick huge random nonces.
If you are using random nonces, segregating the nonce space to have a dedicated 32-bit block counter yields worse security bounds anyway. The whole point of that segregation is to avoid collisions when using a deterministic nonce like a counter. Unless your messages approach the size limit then randomizing the whole 128-bit nonce provides much better bounds than current GCM - effectively the same as randomized CTR mode. (ie nearer to 2^48 messages limit).
So yes, using GCM with a 128-bit random nonce is already good enough for most of these cases.
However IMO all of this is a distraction anyway. One of the most devastating real-world attacks involving nonce reuse was the KRACK attacks, and that involved a protocol error allowing the attacker to force nonce reuse. No amount of extra large random nonces would have saved from that. (And using random nonces in such a protocol significantly bloats the wire format).
What we really need to do is move away from hugely fragile polynomial MACs. For 90%+ of usecases a more robust PRF is perfectly performant enough - eg note that the impact of KRACK was less severe against CCM than GCM. Heck, even CTR/CBC+HMAC is perfectly fast enough for many use-cases. Stop with the premature optimisation already.
As I understand it, the limitation people are concerned about is that of the IV/counter block. It's not that you can't hash an arbitrarily large nonce down to 96 bits; you obviously can. It's that ultimately you've only got 96 bits on the wire to express your nonce, and if they collide GCM falls apart. That's the X trick in XSalsa: the wider nonce gets laundered into the key.
Looking at the implementation, the longer nonce is hashed to 128 bits, with the last 32 used as a starting counter. So, if you don't use the whole 32 bits space of the counter, you are effectively using more than 96 bits nonce.
Sure, no more than 128 bits, but indeed better than 96.
The only thing to potentially be aware of is that the randomized block counter may end up overflowing if it happens to end up with a large initial value (or you encrypt large messages). That should be fine, but it's quite likely that some GCM implementations are not expecting that and either blow up when the counter resets to 0 or do something else unexpected. So although I think this is theoretically a fine thing to do, I absolutely wouldn’t trust my sensitive data to it.
How does it compare to XChachaPoly? I guess it's only useful when you are sure to have CPU support for AES and not having to deal with the annoyance of non constant time software implementations. I feel like XChachaPoly has the benefit of being annoyance free (constant time by design even in software implementation), fairly fast even without hardware support and to exists, so it's probably a good choice for most use cases.
EDIT: my question is probably more clearly asked as: what's wrong with XChachaPoly that is solved by this new construct?
Because AESNI and CLMUL, AES-GCM is faster than a SIMD implementation of ChaCha20Poly1305. In theory, ChaCha20 is overkill, 8 rounds would have been enough and people do use 12 rounds for disk encryption.
Yes that was my thoughts as well, if you are concerned about speed and dropping AES rounds, you might as well do the same with Chacha and use Chacha20/8 (which I don't know if it "exists" but Salsa20/8 is a thing, used in scrypt and available in libsodium for example). At least it's also fast when you don't have AESNI.
Really pedantic nit here, but the cipher Salsa20 is called “Salsa20” and so reduced round versions are called e.g. “Salsa20/8”. However the ChaCha cipher is just called “ChaCha” so the specific-round versions are just “ChaCha20” or “ChaCha8”.
I feel like I just “actually it’s GNU/Linux”ed you there though... I feel bad, I’m sorry.
I've unfortunately seen many situations where only NIST approved constructions are allowed. ChaCha is not an approved NIST algorithm but AES-256-GCM is
Cool. If I can propose a little improvement, it would be nice to allow an arbitrary long nonce. Like, feeding the first 96 bits of the nonce into GCM, and the rest in CBC-MAC.
What benefit do you hope to gain from an arbitrarily long nonce?
The design I sketched out extended the 96-bit GCM nonce to 224 bits, which is longer than the 192 bits of XSalsa and XChaCha. That's also the maximum that's supported by the algorithms as used.
If we supported arbitrarily longer inputs to AES-CBC-MAC, it's going to get mixed down into an AES block (128 bits long) anyway, so the benefit of arbitrary-length extensions over a 128-bit extension is unclear to me.
AES-256-GCM runs at well above 10 GB/s per core on semi-modern desktop/server CPUs and the 128 variant isn’t actually 40% faster iirc. I think it was like 11 vs 13 GB/s on the same hardware, not what 10-vs-14 rounds would seem to imply. Even chapoly is only around 3-4x slower.
Because it predates awareness of how nonce-based AEADs are misused by developers. Which, in fairness, is true of most of the first generation of AEADs, including Chapoly --- XSalsa was a clever hack, not the original design.
AES has a key length and a round count. The speed of the cipher depend only on the round count. This suggestion takes a large key, but a moderate round count, making it only slightly slower than AES128-GCM.
Specifically, "nah with OpenSSL on AMD or Intel boxes from the last decade":
AES-128 (ctr mode) 9.7 GB/s
AES-256 (ctr mode) 8.6 GB/s (90 % as fast,
not ~70 % as 10-vs-14 rounds would naively suggest)
AES-128 (gcm mode) 12.4 GB/s
AES-256 (gcm mode) 10.8 GB/s
(plain CTR is slower than GCM because the GCM implementation in OpenSSL has received more attention than the counter mode implementation, simply because standalone counter mode is used a lot less)
And this is just one core anyway. How many 100 GbE ports are you running per core?
I keep reiterating this because crypto=slow is still a very common idea from the days when AES-128 would peg a core running at 40 MB/s, rcp actually was 3x faster than scp, http:// instead of https:// would actually meaningfully reduce load, SMB/NFS encryption would actually slow things down and it was a bog to actually use a system running with LUKS-encrypted drives. But that's not the case any more. Encryption is really really fast and has been for about ten years, depending on what you're looking at exactly. Nowadays even many microcontrollers have AES acceleration because - internet of things mainly.
It's an AES-based mode, so it only has the AES message block (and, implicitly, the key) to work with, and some of the bits in the message block need to hold the CTR counter. The problem is that leaves an uncomfortably low margin of random bits.
I guess I never conceptually got onboard with the idea that hashing down more entropy is better than pulling the exact amount of good entropy. But I lack the formal qualifications to argue as much (or knowledge of a proof to the contrary). I know we like to be paranoid when things make us uncomfortable.
It's not an entropy question at all; it's that the algorithm only gives you a fixed amount of bits (the key size plus the AES message block) to divide up, and if you only use the message block itself (as NIST GCM does) that's not enough space to feel comfortable picking nonces at random due to e.g. the birthday problem.
> If for example an application encrypts 2^48 messages under different 128-bit keys, and all messages start with the same few bytes, an attacker can build a lookup table, try and lookup the ciphertext of 2^64 keys, and have a 2^-16 chance to decrypt one message. Not good.
This is satire right? The computational and storage requirements to preform such an attack to just get a small probability of decrypting one message seem ludicrous.
Millions of terabyte disks of storage. Then repeat the attack a couple thousand times.
In cryptography, you don't want "ludicrously" infeasible, as in the NSA can just about afford the hardware and do it, you want astronomically infeasible.
Inability to encrypt more than 64Gb with the same (key,nonce) pair.
Lack of commitment (whether key-commitment, or key+nonce+ad commitment).
If one is seriously considering breaking away from existing GCM standards to create yet-another-standard, such proposal would need to offer improvements in all areas (ex. a proposed standard for converting any AEAD into streaming chunk-based AEAD with practically unlimited message sizes under the same (key,nonce) and unlimited message counts.
GCM-256 is ubiquitous and is often the preferred choice for all the reasons mentioned by the author, but that very argument is what makes non-standard GCM with 11 AES-rounds silly.
In 2023 we should be working on new standards that "wrap" existing crypto-primitives (which are already implemented/available in countless hardware-accelerated libraries/APIs) to get additional features/benefits/capabilities - not musing about AES with 10+1 rounds or SHA-512-really-fast with 80-1 rounds..