Order of operations and MAC security

| Comments (1) |
Recent work on attacking HMAC highlights a point about secure protocol design. As I mentioned, the attack requires having a lot of (m,X) pairs. Now, some protocols, like SSL, use what's called authenticate-then-encrypt (AtE) in which you apply the MAC and then encrypt the message (and usually the MAC). Other protocols, like IPsec, use what's called encrypt-then-authenticate (EtA) in which you encrypt the message and then compute the MAC over the ciphertext. A well-known paper by Hugo Krawczyk showed that there were (contrived) ways of using AtE with otherwise secure algorithms which were themselves insecure. As a result, the crypto community generally recommends EtA.

What's interesting to note, however, is that encrypting the traffic (and MAC) as is done in AtE, hides the plaintext (and the MAC) from the attacker. This would seem to preclude mounting a Contini-Wang style attack on the underlying hash function. By contrast, if you use EtA, then the attacker gets a chance to attack the MAC first and then move on to the encryption.


Another case where I saw this effect is GCM. It computes a MAC over the ciphertext. However it uses a Carter-Wegman construction based on a universal hash GHASH. These require a nonce, which is basically E(K,IV). CW MACs are insecure if you ever reuse the nonce, and can even reveal the MAC key. So with GCM if you reuse the IV accidentally, not only is your plaintext likely revealed (it uses counter mode) but you also reveal your MAC key. Since the MAC is over the ciphertext, the whole MAC calculation is in the open so given the nonce collision it is easy to reverse it and derive the key.

If the MAC had been done before the encryption, and if something besides counter mode were used, it would have much more immunity to this mistake. Doing encrypt-then-authenticate and using a universal hash based MAC like this one, or UMAC, or Dan Bernstein's Poly1305-AES, means that you have to be very, very, very careful never to reuse a nonce. Just another source of brittleness.

Leave a comment