I want XAES-256-GCM/11(words.filippo.io)
words.filippo.io
I want XAES-256-GCM/11
https://words.filippo.io/dispatches/xaes-256-gcm-11/
104 comments
> 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.
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.
1: well, in most cases especially AES-256: https://crypto.stackexchange.com/questions/68774/can-a-zero-...
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.
1: well, in most cases especially AES-256: https://crypto.stackexchange.com/questions/68774/can-a-zero-...
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.
(Apologies if this is obvious!)
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.
(Apologies if this is obvious!)
> 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.
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.
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.
> GCM's security falls to pieces
That's an exaggeration. Reusing the nonce in GCM allows decryption of messages with the same nonce. It does NOT compromise the key.
That's an exaggeration. Reusing the nonce in GCM allows decryption of messages with the same nonce. It does NOT compromise the key.
Allowing decryption of the messages sounds like falling to pieces to me...
Messages with duplicate nonces. Recovery of the authentication key may also allow message forgery (although it won't allow decryption).
Message forgery does quite often lead to decryption actually - google “chosen ciphertext attack”.
None of the modern symmetric ciphers are susceptible to chosen ciphertext attacks.
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.
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.
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.
[deleted]
Yes, and? It allows recovery of the authentication key, but not the source AES key.
The authentication key is _derived_ from the AES key, but they're not the same.
The authentication key is _derived_ from the AES key, but they're not the same.
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.
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.
https://www.usenix.org/conference/woot16/workshop-program/pr...
I think you should stop digging. Sean and Hanno gave a Black Hat talk whose slides were unwillingly hosted on a GCHQ website because of this problem.
I think you should stop digging. Sean and Hanno gave a Black Hat talk whose slides were unwillingly hosted on a GCHQ website because of this problem.
cyberax(1)
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?
Yep. Gross.
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
> But it's a problem for chunked messages too.
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.
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!
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.
[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.
Skipjack is notable for having 32 rounds and being broken for 31 rounds.
Isn't AES completely broken under 5 rounds and currently is considered completely safe at like 8 rounds?
You'd probably be interested in the "Too Much Crypto" paper linked in the post: https://eprint.iacr.org/2019/1492
> 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.
...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.
Which attacks would those be? Are you thinking about password cracking? What are the other ones?
SHA-1 collisions are (almost) as much brute force as anything.
But that's not because SHA-1 doesn't have enough rounds; there's a more fundamental flaw in SHA-1.
Okay, fair, I hallucinated bits into the statement.
> we might wish OCB hadn’t been patented
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.)
[1] https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3...
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.)
[1] https://mailarchive.ietf.org/arch/msg/cfrg/qLTveWOdTJcLn4HP3...
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.
>In 2023, the way to use AES is AES-GCM. Anything else is very unlikely to make sense.
Encrypt-then-MAC remains the most conservative and theoretically secure option.
Leaving aside the (very serious) nonce reuse issue, the cracks on non-committing AEADs in general (such as AES-GCM) are already showing. Partitioning oracle attacks affect all of them: https://crypto.stackexchange.com/questions/88716/understandi...
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.
Encrypt-then-MAC remains the most conservative and theoretically secure option.
Leaving aside the (very serious) nonce reuse issue, the cracks on non-committing AEADs in general (such as AES-GCM) are already showing. Partitioning oracle attacks affect all of them: https://crypto.stackexchange.com/questions/88716/understandi...
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.
GCM is an encrypt-then-MAC mode.
And AES-GCM-SIV is MAC-then-Encrypt but is still secure (albeit not committing), so people cry foul when it's pointed out.
AEADs are obviously better than EtM, because EtM doesn't allow for authenticating the unencrypted context.
I wrote about turning CTR+HMAC into a committing AEAD and promptly screwing it up badly: https://soatok.blog/2021/07/30/canonicalization-attacks-agai...
AEADs are obviously better than EtM, because EtM doesn't allow for authenticating the unencrypted context.
I wrote about turning CTR+HMAC into a committing AEAD and promptly screwing it up badly: https://soatok.blog/2021/07/30/canonicalization-attacks-agai...
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))
It's easy to say "just use a suitable encoding".
But when people say "use AES-CBC + HMAC" and cite Signal as an example, and Signal's implementation does this: https://github.com/signalapp/Signal-Android/blob/main/app/sr...
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.
But when people say "use AES-CBC + HMAC" and cite Signal as an example, and Signal's implementation does this: https://github.com/signalapp/Signal-Android/blob/main/app/sr...
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.
> But when people say "use AES-CBC + HMAC" and cite Signal as an example, and Signal's implementation does this: https://github.com/signalapp/Signal-Android/blob/main/app/sr...
That's very vague and therefore not very helpful. Could you say what exactly is wrong with the code you linked?
That's very vague and therefore not very helpful. Could you say what exactly is wrong with the code you linked?
It does exactly what I've been describing!
They provide AE, not AEAD.
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.
AEAD modes let you bind a ciphertext to a context without increasing bandwidth. This is super important for database cryptography. Read more: https://soatok.blog/2023/03/01/database-cryptography-fur-the...
Whether "it's not AEAD" matters for an application depends on many factors. Signal doesn't need it.
They provide AE, not AEAD.
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.
AEAD modes let you bind a ciphertext to a context without increasing bandwidth. This is super important for database cryptography. Read more: https://soatok.blog/2023/03/01/database-cryptography-fur-the...
Whether "it's not AEAD" matters for an application depends on many factors. Signal doesn't need it.
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.
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.
> 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.
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. :)
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. :)
From the NIST doc for GCM: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpubli...
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.
The X part is thus in theory already allowed.
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.
The X part is thus in theory already allowed.
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.)"
I missed that, good catch.
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.
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.
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.
Sure, no more than 128 bits, but indeed better than 96.
Right, and 128 bits is way 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.
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?
EDIT: my question is probably more clearly asked as: what's wrong with XChachaPoly that is solved by this new construct?
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
I totally get that, but XAES-256-GCM/11 is in an even worse situation than XChachaPoly since none are NIST but XChachaPoly has at least a RFC ^^
EDIT: I'm wrong, ChachaPoly has an rfc, but not the X variant
EDIT: I'm wrong, ChachaPoly has an rfc, but not the X variant
XChaCha20Poly1305 does have an RFC authored by Scott Arciszewski: https://datatracker.ietf.org/doc/html/draft-arciszewski-xcha...
Yes but it has been expired for a while
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 feel like I just “actually it’s GNU/Linux”ed you there though... I feel bad, I’m sorry.
I sketched out an extended nonce construction using AES-GCM with CBC-MAC last year (both of which are permitted by FIPS).
https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-w...
I never considered only using 11 rounds, though. That'd have a significant performance impact if we could.
https://soatok.blog/2022/12/21/extending-the-aes-gcm-nonce-w...
I never considered only using 11 rounds, though. That'd have a significant performance impact if we could.
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.
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.
That would make AES-XGCM an immediate replacement of AES-GCM that already supports an arbitrary long nonce.
The "arbitrary long nonce" gets hashed down (using GHASH) to 96 bits.
I mean, sure, if you really want to, you can already do that with the GCM part. I would hesitate to do that to the AES-CBC-MAC part.
Your proposal would then be to dedicate the first 16 bytes (128 bits) to the extension, and the rest to GCM.
I mean, sure, if you really want to, you can already do that with the GCM part. I would hesitate to do that to the AES-CBC-MAC part.
Your proposal would then be to dedicate the first 16 bytes (128 bits) to the extension, and the rest to GCM.
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.
(That’s gigabytes per second, not gigabits)
(That’s gigabytes per second, not gigabits)
AEGIS is being standardized, and solves many of the AES-GCM issues while being significantly faster.
https://datatracker.ietf.org/doc/draft-irtf-cfrg-aegis-aead/
https://github.com/jedisct1/aegis-128X
Many implementations are available, including for Go: https://github.com/jedisct1/draft-aegis-aead#known-implement...
https://datatracker.ietf.org/doc/draft-irtf-cfrg-aegis-aead/
https://github.com/jedisct1/aegis-128X
Many implementations are available, including for Go: https://github.com/jedisct1/draft-aegis-aead#known-implement...
Do you _really_ need AES256 though? Just a large computation overhead while AES128 is extraordinarily secure already.
The conversation about nonce sizes is 100% on point however. Why isn’t it at least the size of the key?
The conversation about nonce sizes is 100% on point however. Why isn’t it at least the size of the key?
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.
Is AES256 meaningfully slower than AES128 when you have AES-NI extensions?
Nah
Specifically, "nah with OpenSSL on AMD or Intel boxes from the last decade":
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.
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
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 was a trick on my part to ask a leading question I already knew the answer to for others to provide the details as I didn’t have it handy :)
Asymmetric encryption remains “slow” but symmetric is within an order of magnitude of a memcpy.
Asymmetric encryption remains “slow” but symmetric is within an order of magnitude of a memcpy.
Just doing some very quick benchmarks:
https://scarjit.github.io/cryptoBench/target/criterion/repor...
It's measureable, but in most applications i wouldn't optimize this part.
It's measureable, but in most applications i wouldn't optimize this part.
<5% at 1 MiB (~50 us per MiB). Measurable but unlikely to be really noticeable.
Why are we even hashing the nonce in the first place? Don’t we have enough entropy these days to just pull what we need?
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.
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.
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.
And you want it to be so infeasible that even attacking a single message with perfect knowledge of all non-secrets is "astronomically infeasible".
Its not enough to just make it astronomically infeasible to attack everyone.
Its not enough to just make it astronomically infeasible to attack everyone.
What does 11 mean?
11 rounds instead of 14 rounds.
Number of rounds. AES128 uses 10 rounds, 192 uses 12 and 256 14. The proposal being to drop AES256 from 14 to 11 rounds.
jeron(1)
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..