If you’ve hung around this blog for a while, you probably know how much I like to complain. (Really, quite a lot.) You might even be familiar with one of my favorite complaints: dumb crypto standards. More specifically: dumb standards promulgated by smart people.

The people in question almost always have justifications for whatever earth-shakingly stupid decision they’re about to take. Usually it’s something like ‘doing it right would be hard‘, or ‘implementers wouldn’t be happy if we did it right‘. Sometimes it’s ‘well, we give the option to do it right‘. In the worst case they’ll tell you: ‘if it bothers you so much, why don’t you join the committee and suggest that idea yourself, Mr. Smartypants‘.

Well, first of all, it’s Dr. Smartypants. And moreover, I’ve tried. It doesn’t work.

Case in point: I happen to be lurking on the mailing list of a standards committee that recently decided to allow unauthenticated CBC mode encryption as an option in their new web encryption standard. When I pointed out that the exact same decision led to the failure of a previous standard — ironically, one that this new standard will probably replace — I was told, politely, that:

1. Mandating authenticated encryption would be hard.
2. Real implementers don’t know how to implement it.
3. We already offer the option to use authenticated encryption.
4. Stop telling us things we already know.

What’s Authenticated Encryption and why should I care?

For those of you who don’t know what AE is, I first need to explain one basic fact that isn’t well explained elsewhere:

Nearly all of the symmetric encryption modes you learned about in school, textbooks, and Wikipedia are (potentially) insecure.

This covers things like AES when used in standard modes of operation like CBC and CTR. It also applies to stream ciphers like RC4. Unfortunately, the list of potentially insecure primitives includes many of the common symmetric encryption schemes that we use in practice.

Now, I want to be clear. These schemes are not insecure because they leak plaintext information to someone who just intercepts a ciphertext. In fact, most modern schemes hold up amazingly well under that scenario, assuming you choose your keys properly and aren’t an idiot.

The problem occurs when you use encryption in online applications, where an an adversary can intercept, tamper with, and submit ciphertexts to the receiver. If the attacker can launch such attacks, many implementations can fail catastrophically, allowing the attacker to completely decrypt messages.

Sometimes these attacks requires the attacker to see only an error message from the receiver. In other cases all he needs to do is measure time it takes for the receiver to acknowledge the submission. This type of attack is known as a chosen ciphertext attack, and by far the most common embodiment is the ‘padding oracle attack‘ discovered in 2002 by Serge Vaudenay. But there are others.

The simplest way to protect yourself against these attacks is to simply MAC your ciphertexts with a secure Message Authentication Code such as HMAC-SHA. If you prefer this route, there are two essential rules:

1.  Always compute the MACs on the ciphertext, never on the plaintext.
2.  Use two different keys, one for encryption and one for the MAC.

Rule (1) prevents chosen-ciphertext attacks on block cipher modes such as CBC, since your decryption process can reject those attacker-tampered ciphertexts before they’re even decrypted. Rule (2) deals with the possibility that your MAC and cipher will interact in some unpleasant way. It can also help protect you against side-channel attacks.

This approach — encrypting something, then MACing it — is not only secure, it’s provably secure as long as your encryption scheme and MAC have certain properties. Properties that most common schemes do seem to possess.*

Dedicated AE(AD) modes

Unfortunately, the ‘generic composition’ approach above is not the right answer for everyone. For one thing, it can be a little bit complicated. Moreover, it requires you to implement two different primitives (say, a block cipher and a hash function for HMAC), which can be a hassle. Last, but not least, it isn’t necessarily the fastest way to get your messages encrypted.

The efficiency issue is particularly important if you’re either (a) working on a constrained device like an embedded system, or (b) you’re working on a fast device, but you just need to encrypt lots of data. This is the case for network encryptors, which have to process data at line speeds — typically many gigabytes per second!

For all of these reasons, we have specialized block cipher modes of operation called Authenticated Encryption (AE) modes, or sometimes Authenticated Encryption with Associated Data (AEAD). These modes handle both the encryption and the authentication in one go, usually with a single key.

AE(AD) modes were developed as a way to make the problem of authentication ‘easy’ for implementers. Moreover, some of these modes are lightning fast, or at least allow you to take advantage of parallelization to speed things up.

Unfortunately, adoption of AE modes has been a lot slower than one would have hoped for, for a variety of reasons. One of which is: it’s hard to find good implementations, and another is that there are tons and tons of AE(AD) schemes.

So, which AE mode should I choose?

And now we get down to brass tacks. There are a plethora of wonderful AE(AD) modes out there, but which one should you use? There are many things to consider. For example:

• How fast is encryption and decryption?
• How complicated is the implementation?
• Are there free implementations out there?
• Is it widely used?
• Can I parallelize it?
• Is it ‘on-line’, i.e., do I need to know the message length before I start encrypting?
• Is it patented?
• Does it allow me to include Associated Data (like a cleartext header)?
• What does Matt Green think about it?

To answer these questions (and particularly the most important final one), let’s take a look at a few of the common AE modes that are out there. All of these modes support Associated Data, which means that you can pre-pend an unencrypted header to your encrypted message if you want. They all take a single key and some form of Initialization Vector (nonce). Beyond that, they’re quite different inside.

GCM. Galois Counter Mode has quietly become the most popular AE(AD) mode in the field today, despite the fact that everyone hates it. The popularity is due in part to the fact that GCM is extremely fast, but mostly it’s because the mode is patent-free. GCM is ‘on-line’ and can be parallelized, and (best): recent versions of OpenSSL and Crypto++ provide good implementations, mostly because it’s now supported as a TLS ciphersuite. As a side benefit, GCM will occasionally visit your house and fix broken appliances.

Given all these great features, you might ask: why does everyone hate GCM? In truth, the only people who hate GCM are those who’ve had to implement it. You see, GCM is CTR mode encryption with the addition of a Carter-Wegman MAC set in a Galois field. If you just went ‘sfjshhuh?’, you now understand what I’m talking about. Implementing GCM is a hassle in a way that most other AEADs are not. But if you have someone else’s implementation — say OpenSSL’s — it’s a perfectly lovely mode.

OCB. In performance terms Offset Codebook Mode blows the pants off of all the other modes I mention in this post. It’s ‘on-line’ and doesn’t require any real understanding of Galois fields to implement** — you can implement the whole thing with a block cipher, some bit manipulation and XOR. If OCB was your kid, he’d play three sports and be on his way to Harvard. You’d brag about him to all your friends.

Unfortunately OCB is not your kid. It belongs to Philip Rogaway, who also happens to hold a patent on it. This is no problem if you’re developing GPL software (it’s free for you), but if you want to use it in a commercial product — or even license under Apache — you’ll probably have to pay up. As a consequence OCB is used in approximately no industry standards, though you might find it in some commercial products.

EAX. Unlike the other modes in this section, EAX mode doesn’t even bother to stand for anything. We can guess that E is Encryption and A is Authentication, but X? I’m absolutely convinced that EAX is secure, but I cannot possibly get behind a mode of operation that doesn’t have a meaningful acronym.

EAX is a two-pass scheme, which means that encryption and authentication are done in separate operations. This makes it much slower than GCM or OCB, though (unlike CCM) it is ‘on-line’. Still, EAX has three things going for it: first, it’s patent-free. Second, it’s pretty easy to implement. Third, it uses only the Encipher direction of the block cipher, meaning that you could technically fit it into an implementation with a very constrained code size, if that sort of thing floats your boat. I’m sure there are EAX implementations out there; I just don’t know of any to recommend.

Whatever you do, be sure not to confuse EAX mode with its dull cousin EAX(prime), which ANSI developed only so it could later be embarrassingly broken.

CCM. Counter Mode with CBC MAC is the 1989 Volvo station wagon of AEAD modes. It’ll get you to your destination reliably, just not in a hurry. Like EAX, CCM is also a two-pass scheme. Unfortunately, CCM is not ‘on-line’, which means you have to know the size of your message before you start encrypting it. The redeeming feature of CCM is that it’s patent-free. In fact, it was developed and implemented in the 802.11i standard (instead of OCB) solely because of IP concerns. You can find an implementation in Crypto++.

The rest. There are a few more modes that almost nobody uses. These include XCBC, IAPM and CWC. I have no idea why the first two haven’t taken off, or if they’re even secure. CWC is basically a much slower version of GCM mode, so there’s no real reason to use it. And of course, there are probably plenty more that I haven’t listed. In general: you should use those at your own risk.

Summing up

So where are we?

In general, the decision of which cipher mode to use is not something most people make every day, but when you do make that decision, you need to make the right one. Having read back through the post, I’m pretty sure that the ‘right’ answer for most people is to use GCM mode and rely on a trusted free implementation, like the one you can get from OpenSSL.

But there are subcases. If you’re developing a commercial product, don’t care about cross-compatibility, and don’t mind paying ‘a small one-time fee‘, OCB is also a pretty good option. Remember: even cryptographers need to eat.

Finally, if you’re in the position of developing your own implementation from scratch (not recommended!) and you really don’t feel confident with the more complicated schemes, you should serious consider EAX or CCM. Alternatively, just use HMAC on your ciphertexts. All of these things are relatively simple to deal with, though they certainly don’t set the world on fire in terms of performance.

The one thing you should not do is say ‘gosh this is complicated, I’ll just use CBC mode and hope nobody attacks it’, at least not if you’re building something that will potentially (someday) be online and subject to active attacks like the ones I described above. There’s already enough stupid on the Internet, please don’t add more.

Notes:

* Specifically, your encryption scheme must be IND-CPA secure, which would apply to CBC, CTR, CFB and OFB modes implemented with a secure block cipher. Your MAC must be existentially unforgeable under chosen message attack (EU-CMA), a property that’s (believed) to be satisfied by most reasonable instantiations of HMAC.

** An earlier version of this post claimed that OCB didn’t use Galois field arithmetic. This commenter on Reddit correctly points out that I’m an idiot. It does indeed do so. I stand by my point that the implementation is dramatically simpler than GCM.