I want XAES-256-GCM/11

https://words.filippo.io/dispatches/xaes-256-gcm-11/

by harporoeder • 3 years ago

146 98 3 years ago

words.filippo.io

forty4• 3 years ago

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?

wolf550e• 3 years ago

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.

forty4• 3 years ago

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.

conradludgate• 3 years ago

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

forty4• 3 years ago

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

zahllos4• 3 years ago

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.

JoshTriplett• 3 years ago

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.)"

zahllos4• 3 years ago

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.

nmadden7• 3 years ago

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.

tptacek18• 3 years ago

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.

amadvance3• 3 years ago

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.

purple_elephant• 3 years ago

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.

tptacek18• 3 years ago

GCM is an encrypt-then-MAC mode.

some_furry8• 3 years ago

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...

formerly_proven3• 3 years ago

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)

some_furry8• 3 years ago

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.

amadvance3• 3 years ago

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.

some_furry8• 3 years ago

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.

jwilk• 3 years ago

What does 11 mean?

some_furry8• 3 years ago

11 rounds instead of 14 rounds.

zahllos4• 3 years ago

Number of rounds. AES128 uses 10 rounds, 192 uses 12 and 256 14. The proposal being to drop AES256 from 14 to 11 rounds.

kmeisthax• 3 years ago

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.

nemo1618• 3 years ago

You'd probably be interested in the "Too Much Crypto" paper linked in the post: https://eprint.iacr.org/2019/1492

Joker_vD• 3 years ago

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.

dragontamer• 3 years ago

Isn't AES completely broken under 5 rounds and currently is considered completely safe at like 8 rounds?

tedunangst3• 3 years ago

Skipjack is notable for having 32 rounds and being broken for 31 rounds.

sdrapkin2• 3 years ago

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..

tptacek18• 3 years ago

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?

sdrapkin2• 3 years ago

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".

oconnor6632• 3 years ago

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.

vlovich1234• 3 years ago

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.

goalieca• 3 years ago

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.

fargle2• 3 years ago

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-...

barbegal• 3 years ago

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.

mike_hock• 3 years ago

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.

SahAssar• 3 years ago

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.

dcow2• 3 years ago

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?

tptacek18• 3 years ago

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.

dcow2• 3 years ago

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.

mananaysiempre• 3 years ago

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...

tptacek18• 3 years ago

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.

exabrial• 3 years ago

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?

tptacek18• 3 years ago

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.

vlovich1234• 3 years ago

Is AES256 meaningfully slower than AES128 when you have AES-NI extensions?

formerly_proven3• 3 years ago

Nah

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.

Scarjit• 3 years ago

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.

NohatCoder• 3 years ago

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.

cosmojg• 3 years ago

If FIPS compliance is one of your primary motivations for using AES, why not use Ed25519 or Ed448 instead?

pingiun• 3 years ago

those are signature algorithms. aes/chacha are symmetric ciphers

jedisct1• 3 years ago

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...

I want XAES-256-GCM/11

Related Stories