What are the actual merits of Galois/Counter Mode?

Question

GCM (Galois/Counter Mode), in particular in combination with AES, has been a de-facto gold standard for years. Encrypt and authenticate in one step, that's just too awesome, and terms like AEAD work well for impressing a girl, so that would be win-win. But, joke aside...

I've always wondered what makes it so special, and the longer I think about it, the less I understand. If you look at it, then the overall magic isn't so awesome at all. Or maybe, maybe I'm just too stupid to grok it (hence my question).

My thoughts:

First of all, GCM is a form of counter mode. Which means that unlike with e.g. cipher block chaining, the output of one block depends on exactly one block of input. Worse, yet: You can modify a single bit and the decrypted result will differ in exactly that bit. Because if you are honest, a block cipher in counter mode is not a "block cipher" at all, but a (keyed) PRNG followed by a XOR operation. Basically a "blocky" stream cipher. It doesn't take much to imagine a scenario where someone could abuse this to change messages in a harmful way (e.g. change "transaction: +5,000\$" to "transaction: -5,000\$"). Block ciphers normally have the innate property of turning into complete gibberish as you flip a single bit (plus, with chaining, the entire remainder of the message). That's actually a quite nice, desirable property, which we just threw overboard for no good reason.
Sure, with the authenticator, the above attack is difficult to achieve since the tampering will be discovered. But basically, the authenticator only fixes the problem that the choice of mode of operation introduced.

GHASH is a MAC which supports extra authenticated data. From what I can tell, that's an outright lie. Or call it "optimistic exaggeration" if you will. It's just a compression function with non-intuitive math (to non-mathematicians) behind, but in the end it does nothing but a simple multiplication and throwing away half of the input bits with the equivalent of "overflow". Which is just what, with more mundane math, can be done in two lines of C code per block within a dozen cycles (or if you are OK with using 32-bit multiplications rather than 64, can be done in parallel e.g. with AVX2's vpmulld for two complete blocks in ~4 cycles).
Those who still remember IDEA will recall that they used addition mod 2¹⁶ and multiplication mod 2¹⁶+1 as S-boxes which had the nice property of being reversible (kinda necessary if you wish to decrypt). Unluckily, this couldn't be extended to 32-bits because 2³²+1 isn't a prime number, so not all inputs are guaranteed to be relatively prime to it, and thus you have trouble inverting the operation. But... that's mighty fine in our case, we don't want our compression function to be invertible! So really, "simple", ordinary multiplication should just do the trick as well?

So, that simple, no-special, no-magic compression function happens to be initialized with the key and IV, which incidentially makes the final output key-dependent one way or another, so that ordinary function effectively becomes a MAC. If you have "extra data", you just feed it into the hash prior to encrypting your data, done. Again, that's not something super special.
Overall, it's nothing that you couldn't achieve with pretty much every other hash function, too.

Now, Galois/counter presumes that counter mode be used. Counter mode (and its derivatives) as well as GHASH have the advantage that you can encrypt/decrypt blocks in parallel. Also, GHASH is trivially parallelizable.
Yay, performance! But let's be honest, is this really an advantage, or rather an huge disadvantage?

Does it matter how long it takes to decrypt a gigabyte- or terabyte-sized message, and how well you can parallelize that work? Or applications where you absolutely want to be able to "seek" to random positions? Well, there are applications where that may matter, sure. Full disk encryption comes to mind. But you wouldn't want to use GCM in that case since you want input size and output size to be identical.

For a busy server (or VPN) it will matter, or so it seems, but these can process anything in parallel anyway since they have many concurrent connections. So, whether or not you can parallelize one stream makes really no difference overall. What about applications where there are only few connections? Well, you don't normally transmit terabytes of data over a login terminal, and if you do, your internet connection is still probably the limiting factor anyway, as single-core performance easily outruns GbE bandwidth even on 7-8 year old desktop processors.
Alright, you might possibly have to wait 2-3 seconds longer when extracting an encrypted 2TB 7z-file on your hard disk (if creating thousands of directory entries isn't really the bottleneck, which I'm inclined to believe will be the case). How often have you done that during the last year? Me: zero times.

The only ones to whom it really makes a difference is the "bad guys", i.e. exactly those whom you don't want to have an easy life. Sure enough, if you can trivially parallelize, attacks get much easier. Throw a room full of dedicated hardware (GPUs, FPGAs, whatever) at the problem and let it grind away. No communication between nodes needed? Well, perfect, it can't get any better.
Is this really an advantage? I don't know, to me it looks like a huge disadvantage. If anything, I'd want to make parallelizing as hard as possible, not as easy as possible.

So... enough pondering, and to the question:

What is the fundamental thing that I'm missing about GCM that makes it so awesome that you should absolutely use it?

Answer 1

TL;DR: GCM provides excellent performance with the best security properties we expect from ciphers today (AEAD).

GCM use CTR to build a stream cipher. This a well studied method, which has only one drawback: it absolutely needs some authentication to prevent bit flipping. Before GCM, CTR-then-MAC was the solution. One main advantage of stream ciphers is the absence of padding attacks (because there is no need for padding). Another advantage is that AES-CTR can benefit from the AES-NI instructions.

GCM is CTR-then-MAC with better performance. One key improvement over CRT-then-MAC is the ability to overlap the execution of encryption and authentication. Moreover, it has been proven secure in the concrete security model and it is not encumbered by patents, so it's a no-brainer to use it.

It has some drawbacks: it is not efficient in embedded hardware and it is hard to implement efficiently. The last point is countered by using libraries written by others. However, those are reasons why xchacha20-poly1305 became popular over GCM.

Answer 2

First of all, GCM is a form of counter mode. Which means that unlike with e.g. cipher block chaining, the output of one block depends on exactly one block of input. Worse, yet: You can modify a single bit and the decrypted result will differ in exactly that bit. Because if you are honest, a block cipher in counter mode is not a "block cipher" at all, but a (keyed) PRNG followed by a XOR operation. Basically a "blocky" stream cipher. It doesn't take much to imagine a scenario where someone could abuse this to change messages in a harmful way (e.g. change "transaction: +5,000\$" to "transaction: -5,000\$").

The message authentication that GCM layers on top of CTR makes its malleability inconsequential.

Block ciphers normally have the innate property of turning into complete gibberish as you flip a single bit (plus, with chaining, the entire remainder of the message). That's actually a quite nice, desirable property, which we just threw overboard for no good reason.

This is very, very wrong. First of all, CBC mode also suffers from a kind of malleability weakness; if you flip one bit of the ciphertext, you scramble only one block and flip the corresponding bit of the net block. And there are other malleability attacks against CBC; see, for example, the EFail attack.

More generally, your informal idea of messages "turning into complete gibberish" isn't good enough. We absolutely need computers to mechanically detect, with a definite "yes/no" answer, when an encrypted message has been forged. Trusting that a human will be in the loop early enough to spot "gibberish" isn't enough.

GHASH is a MAC which supports extra authenticated data. From what I can tell, that's an outright lie. Or call it "optimistic exaggeration" if you will. It's just a compression function with non-intuitive math (to non-mathematicians) behind, but in the end it does nothing but a simple multiplication and throwing away half of the input bits with the equivalent of "overflow".

The MAC doesn't fail to work because the users don't understand the math. That's like saying that people can't watch satellite TV because they don't know calculus. Finite field MACs are a standard construction, known for decades now.

Which is just what, with more mundane math, can be done in two lines of C code per block within a dozen cycles (or if you are OK with using 32-bit multiplications rather than 64, can be done in parallel e.g. with AVX2's vpmulld for two complete blocks in ~4 cycles).

There is actual debate on whether MACs based on Galois fields like GHASH, or MACs based on prime fields like Poly1305, are a more practical choice. A lot of it hinges on the tradeoffs between designing MACs to emphasize software vs. hardware implementations; e.g., Galois field multiplications are nightmarish in software, but much simpler than arithmetical multiplications in hardware. A good chunk of the tradeoffs also hinges on vulnerability to side-channel attacks, e.g., power analysis.

But there isn't a debate whether either Galois fields or prime fields are fundamentally unsound. The math checks out on both.

Yay, performance! But let's be honest, is this really an advantage, or rather an huge disadvantage?

Tell that to the endless parades of engineers through the decades who have resisted adding encryption to products because of performance. And don't just think of powerful PCs; think of embedded devices, and be very scared of the Internet of Things.

I mean, this is not a dead issue at all. Over the past couple of years there was a vigorous debate and the development of a novel cryptographic construction to support full-disk encryption on low-end Android devices that were judged not powerful enough for the AES-based algorithms Android offered before.

The only ones to whom [performance] really makes a difference is the "bad guys", i.e. exactly those whom you don't want to have an easy life. Sure enough, if you can trivially parallelize, attacks get much easier. Throw a room full of dedicated hardware (GPUs, FPGAs, whatever) at the problem and let it grind away.

Ciphers solve this by using sufficiently large key sizes, not by making the ciphers slow down. The concern you're bringing up arises in password-based cryptography where you don't have sufficiently entropic secret keys. 256 bit symmetric keys will forever be more than big enough to defeat any brute force attack in our universe.

What is the fundamental thing that I'm missing about GCM that makes it so awesome that you should absolutely use it?

You don't absolutely have to use GCM. It is at the same time:

• Fundamentally sound and very widely supported in hardware;
• Encumbered by a number of drawbacks that you didn't bring up, like poor software performance and catastrophic authenticity failure on nonce reuse, that often disqualify it in some practical contexts.

If you have hardware that has native AES-GCM support and well-audited software that leverages it, it'd be unwise not to have it among your top candidates.