6
$\begingroup$

There are several well-regarded block cipher modes for authenticated encryption which have made their way into standards and protocols: CCM, EAX, GCM, OCB, …

If I am designing a new messaging or storage protocol which requires both confidentiality and authenticity of the data, how do I choose between these modes? I am specifically interested in the case of whole-message encryption and integrity verification (as opposed to block storage).

I'm after answers like “pick whichever of X or Y is easily available in your programming environment”, or “padding for this mode is delicate to implement, but it is more robust to a broken RNG”.

(This is in the spirit of AES CBC mode or AES CTR mode recommended? for modes that provide confidentiality only.)

$\endgroup$
  • 3
    $\begingroup$ @Gilles - be sure to check out this article $\endgroup$ – hunter Aug 28 '14 at 12:29
  • $\begingroup$ @Gilles Added an little edit to my answer to mention a paper that might just be the thing that can help you make up your mind: “Basic comparison of Modes for Authenticated-Encryption (IAPM, XCBC, OCB, CCM, EAX, CWC, GCM, PCFB, CS)” (PDF). It compares a big chunk of AE modes in terms of attributes, implementation, speed, memory usage, tables showing things like the number of the underlying block cipher invocations for each mode, etc. $\endgroup$ – e-sushi Aug 28 '14 at 21:12
  • $\begingroup$ You should state details of a "message". For some distros, a full ISO download is over 5 GB. That's a big message. One US Army project I worked on had a similar requirement. When I asked about the details of a message (i.e., size, frequency, and how its sent/received/handled), they provided workflows and statistics, including Mean, Mode, Median and Standard Deviations. It was very helpful in designing the solution. BTW, Bernstein would argue a big message should be broken into smaller messages and reassembled. The authenticated encryption would be applied to the smaller messages. $\endgroup$ – user10496 Jun 11 '17 at 8:23
  • $\begingroup$ @jww I don't think the answer depends on the size of the message. If it does, that's something you should argue in an answer. Breaking down a message into parts requires an additional level of complexity to assemble the message, which should be avoided if you don't need it because there are many ways to get it wrong (putting the pieces in the wrong order, missing some pieces, assembling parts of different messages, etc.). $\endgroup$ – Gilles 'SO- stop being evil' Jun 11 '17 at 21:32
6
$\begingroup$

GCM

Personally, I would go for GCM (Galois Counter Mode) since it is efficient – meaning: it handles pretty much everything you’ld expect from it, while other modes sometimes tend to lack a specific feature here and there (see image below for a comparison that shows what I’m hinting at). Also, GCM has a pretty good performance (assuming non-flawed implementation). As you most probably already know, it provides Galois mode of authentication with the well-known CTR mode encryption. The CTR aspect practically means that it doesn’t need any padding (which avoids related attack potential) and it means that you keep a bit of flexibility when it comes to message/package lengths (something CCM for example doesn’t offer, since it uses a fixed block length). Also, the Galois field multiplication used for authentication can be computed in parallel, which enables higher speed/throughput than those authentication algorithms that use chaining modes (like CBC etc). Btw: in case you decide to check on GCM, you might find it handy to know that NIST Special Publication 800-38D includes recommendations for IV selection etc.

The rest…

An alternative at the top of my list would have been EAX mode, which also provides several desirable attributes. But: EAX is a “two-pass scheme”… making it slower than well designed one-pass schemes that are based on the same primitives. Since your designing a messaging/storage protocol, you probably will want to get your hands on all the speed you can get. Two-pass seems not to be an option in that case, pushing EAX down on the list.

Now, you also mentioned CCM. That mode is only defined for block ciphers with a block length of 128 bits, which might be a bit restrictive in size for messaging et al. Which is why I would like to remind you of GCM’s counter mode again…

Last on the list of things you’ve mentioned is OCB. I’m a bit uncomfortable when thinking about OCB, because Ferguson found collision attacks on OCB. The attack limits the data that can safely be encrypted with OCB to around and about 64GB per key. That’s about the same 64 GB limit that GCM has (GCM limits plaintext size to $2^{39} − 256$ bits for any given key and IV combination), but we have to remember that GCM’s limit is “by design”… in the case of OCB, it’s “the result of a collision attack”. From a security perspective, I would therefore tend to avoid OCB. We all know attacks can only get better.

There are a few other things that might or might not make a bit of sense, depending on the individual setting… but in the end, I personally would advise to use GCM for a messaging and storage protocol.


Comparing some of the options…

To compare, you might also want to check out the nice comparison table on slide 7 of this PPT file by David Wagner. I’ll quote it as a graphic here for reading convenience (as you’ll notice GCM is a winner):

comparison table


EDIT

Sometimes, my brain seems to be a bit slow when it comes to remembering papers I’ve once been reading.

Anyway, I’m pretty confident you’ll enjoy reading “Basic comparison of Modes for Authenticated-Encryption (IAPM, XCBC, OCB, CCM, EAX, CWC, GCM, PCFB, CS)” (PDF) which compares a truckload of modes in terms of attributes, speed, implementation, memory usage, tables showing things like the number of the underlying block cipher invocations for each mode, etc.

After reading that, you’ll have ample info at hand to decide for yourself what makes most sense.

$\endgroup$
  • $\begingroup$ "... CCM. That mode is only defined for block ciphers with a block length of 128 bits" - I don't understand this as a critique of CCM, since this statement is true of GCM and OCB as well (EAX can be used with arbitrary block sizes). The major critiques of CCM are usually speed (2-pass) and that it's packet mode. $\endgroup$ – archie Aug 28 '14 at 19:56
  • $\begingroup$ "Also, GCM has a pretty good performance" - this should really be can have pretty good performance. As @SquareRootOfTwentyThree's answer notes, non hardware/SIMD-accelerated table based GCM (e.g. pure Java impls) is either memory intensive (typically 8k of key dependant tables for decent speed) or unbearably slow. On many platforms, GCM can be unusable, while CCM/EAX will still perform reasonably. $\endgroup$ – archie Aug 28 '14 at 20:07
  • 3
    $\begingroup$ @archie What makes you think OCB is limited to 128 bits? Quoting Rogaway: You can use OCB with any block cipher that you like. … If you use OCB with a block cipher having a 64-bit block length instead… etc. and in case of doubt, I invite you to have a good look at the OCB-AES128, OCB-AES192, and OCB-AES256 test vectors. ;) $\endgroup$ – e-sushi Aug 28 '14 at 20:19
  • $\begingroup$ @e-sushi "And in case of doubt, have a look at the OCB-AES128, OCB-AES192, and OCB-AES256 test vectors" - last I looked those were all 128 bit block size ;). I was referencing RFC 7253 which explicitly limits the standardised OCB to 128 bits, but I take your point that OCB in general can use different block sizes. My question about the critique of CCM stands though... $\endgroup$ – archie Aug 28 '14 at 20:27
  • 1
    $\begingroup$ @archie Well, one of the issues I see with CCM is that (to retain security) IV must be carefully chosen and never used more than once for a given key. That “choice” makes me feel a bit uncomfortable. Besides that, I’m probably not feeling love for CCM since it performs worse than OCB (and the fact that its development was merely sparked due to patent discussions when OCB mode was submitted). And let’s not forget EAX mode was proposed as a replacement for CCM (for good reasons). As comments are limited, check “the 2 attributes CCM lacks”. $\endgroup$ – e-sushi Aug 28 '14 at 20:47
4
$\begingroup$

I would pick EAX as it is by far the simplest to implement and therefore to understand and audit. It is reasonably fast if based on AES.

GCM seems quite popular, but I personally see a number of issues with it:

  • it is very difficult to implement in software (which is not surprising, since it was developed with hardware in mind).
  • it is slower than it seems (because of the Galois multiplication) both in terms of throughput and key agility, unless you make use of the PCLMULQDQ instruction available on the most recent Intel CPUs or the VMULL instruction on high-end ARM CPUs (with older CPUs or other architectures you are out of luck though).
  • it is very sensitive to cache-based side-channels attacks because of the large tables one has to employ in order to speed it up to a reasonable level. Again, using the low-level instruction mentioned above solves this problem.
  • using the PCLMULQDQ instruction is not straightforward and it was attacked at least once

In other words, GCM can be fast, secure against side-channel attacks or independent of the CPU architecture. Pick two. Or, as As Adam Langley puts it "GCM is fundamentally unsuitable for software implementation".

Special mention should go to SIV. It is a cute mode based on AES and primarily meant for key wrapping (or Deterministic Authenticated Encryption). Unlike EAX, GCM and most AEAD modes it does not fail catastrophically if the nonce or the counter happen to be reused. That is easy to ensure only in theory: in practice, bad RNGs or virtualized environment may make it very hard. The drawback of SIV is that it is not an online mode (you must see the whole message before starting the encryption) and it requires two independent AES keys.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.