Apropos of my last post, Colin Percival tweets:

I still think encrypt+MAC trumps AEAD because of side channel attacks on block ciphers.

AEAD stands for Authenticated Encryption with Associated Data, and it describes several new modes of operation that perform encryption and authentication all in one go, using a block cipher and a single key, rather than a separate MAC.* In my last post I recommended using one of these things, mostly because it’s simpler.

Colin thinks you’re better off using traditional encryption plus a separate hash-based MAC, e.g., HMAC (using a separate key), rather than one of these fancy new modes. This is because, at least in theory, using a block cipher for authentication could make you more vulnerable to side channel attacks on the block cipher.**

This tweet is followed by some back and forth, which becomes amusing when I fail to read a simple diagram and make a fool of myself. Also, I step on a rake.

My foolishness aside, this point deserves some unpacking. Let’s grant — without comment — the proposition that block-ciphers are vulnerable to side-channel analysis and HMAC-SHAx isn’t. Or at very least, if it is vulnerable, we’re only going to expose the MAC key, and we don’t care about that.***

Let’s also grant that our implementation is free of better vulnerabilities, and that side-channel attacks on block ciphers are actually where our attacker’s going to hit us.

So now we’re talking about three separate questions:

1. Will using Encrypt + MAC (vs an AEAD) protect you from side-channel attacks on encryption? Trivial answer: no. You’re using the block cipher to encrypt, so who cares what authentication you perform afterwards.

But ok, maybe your side-channel attack requires the device to encrypt known, or chosen plaintexts, and it won’t do that for you. So you need something stronger.

• Will using Encrypt + Mac (vs an AEAD) save you from side-channel attacks that work against the decryption of arbitrary ciphertexts? Answer: again, probably not. If you can get your hands on some legit ciphertexts (replays, for example), you can probably exercise the block cipher. At least in theory, this should be enough to implement your attack.
• Will using Encrypt + Mac (vs an AEAD) save you from side-channel attacks that require decryption of known, or chosen ciphertexts? Answer: this may be the case where the means of authentication really matters.

So let’s drill into case (3) a bit. If you’re using Encrypt + MAC with a hash-based MAC (and a separate key), then the block cipher only comes into play for legitimate messages. Your decryption process simply terminates when it encounters an invalid MAC. This should prevent you from submitting chosen or mauled ciphertexts — you’re limited to whatever legit ciphertexts you can get your hands on.

On the other hand, if you’re using an AEAD mode of operation — which typically uses a single key for both authentication and encryption — then technically your block cipher (and key) come into play for every ciphertext received, even the invalid ones.

Alright, let’s dig into the modes a bit to see what kinds of encipherment/decipherment actually happens when you submit a ciphertext (and its IV, associated data) to be decrypted:

Since the IV is typically adversarially-selected (in part), this gives the adversary a chance to exercise the encipherment mode of the cipher on a single partially-chosen block. One block doesn’t sound bad — however, he may be able to submit many such chosen ciphertexts.

• CCM mode: CCM is a combination of CTR-mode encryption with CBC-MAC. Since the MAC is computed over the plaintext, the CCM decryptor can’t verify (and hence reject a bad ciphertext) until after he’s completely decrypted it. Decryption is actually encipherment of a set of known counter values, the first of which is (partly) chosen by the adversary.
• OCB mode: Difficult to say. It’s the same as CCM, as far as decryption before MAC testing. However, this complicated by the fact that the cipher is ‘tweaked’ in a DES-X-type construction. And honestly, nobody uses it anyway.
• EAX mode: the good news is that the MAC is computed on the ciphertext, so the decryptor shouldn’t decrypt the ciphertext unless the MAC is valid. The bad news is that the MAC is a CBC-style MAC (OMAC), using the same key as for decryption, so authentication will encipher at least some chosen values.

So where are we? Pretty far down the rabbit hole.

I’m going to go with the following: if you’re deeply afraid of side-channel attacks on your block cipher, you might feel marginally better about with Encrypt + MAC if your application is definitely not vulnerable to cases (1) and (2) above and you’re positive that HMAC-SHAx isn’t vulnerable to side-channel attacks. Otherwise I’d use an AEAD just to make my life simpler.

But I’m not passing judgement on this. It’s a new perspective to me, and I’m genuinely curious to see what others have to say. Can people recommend any practical attacks, papers, opinions on this subject?

Notes:

* Includes GCM, CWC, OCB, EAX and CCM modes.

** Attacks like the recent attack on the Mifare DESFire, or timing/cache timing attacks on AES.

*** Of course, if you do expose the MAC key through one side-channel attack, then you might be able to do something more sophisticated against the encryption algorithm. But my head is already hurting too much.

**** Technically, checking GHASH also requires you to encipher the 0 message under the cipher key, but that can be done beforehand. It doesn’t need to happen each time you decrypt.