Can authenticated encryption reduce bandwidth overhead of per-packet encryption?

Question

I know that authenticated encryption modes of operation like GCM offer certain security advantages, as well as increased performance. (On my laptop with AES-NI, the benchmark performance of AES-128-GCM is about 3.7× faster than AES-128-CBC-SHA1.)

What I'm less certain about is whether authenticated encryption modes offer any advantages in terms of bandwidth overhead, in particular for datagram/UDP-based VPNs.

I've been working recently on supporting a commercial ESP-based VPN in an open-source VPN client, and have been struck by the substantial overhead of wrapping IP packets in ESP:

• 20 bytes for SHA1 MAC
• 16 bytes for an AES-128 IV

Including ~17 bytes for padding and a 4-byte SPI), the ESP overhead can be around 5% of the size of an IPv4 packet on a network with a typical MTU around 1500 bytes.

Do authenticated encryption modes offer any possibility to trim the per-packet bandwidth overhead of encryption and authentication, while retaining similar security levels?

My understanding of GCM is that it still uses authentication tags and IVs of similar length to ciphersuites like AES-128-CBC-SHA1, but perhaps there are possibilities that I'm looking here.

Answer 1

GCM supports multiple authentication tag sizes. To the extent that overhead outweighs security in your application, you perhaps could use GCM with reduced tag size. You'd be settling for a lower security level, so that needs to be thought through very carefully.

---

The common requirements on the use of IVs are the following:

1. The sender and recipient must agree on what the IV is for each encryption/decryption pair. Even better, they should authenticate the IV.
2. Other additional requirements that the cipher imposes on IVs. The two typical ones:
   • Some ciphers require the IVs to be a nonce—that two encryptions with the same key never reuse the same IV, or otherwise the cipher may fail catastrophically. CTR and GCM are like this.
   • Other ciphers require the IVs to be random. CBC is like this.

Requirement #1 is often achieved by sending the IV along with the ciphertext, but this is just one way of achieving the goal. The alternative would be to have some protocol where the parties can locally generate the correct IV for each encryption/decryption pair without having to individually transmit them. Many solutions are possible here. One very simple scheme, suitable for nonce-based ciphers, is to treat the IV as a counter. The documentation for the NaCl library has an example trick worth quoting:

Distinct messages between the same {sender, receiver} set are required to have distinct nonces. For example, the lexicographically smaller public key can use nonce 1 for its first message to the other key, nonce 3 for its second message, nonce 5 for its third message, etc., while the lexicographically larger public key uses nonce 2 for its first message to the other key, nonce 4 for its second message, nonce 6 for its third message, etc.

This does require that recipient be able reconstruct the order in which the sender used encrypted the messages. But there are other ideas that can help if that's a problem:

• If your messages carry some plaintext metadata that contains values that offer some uniqueness guarantee, you might be able to use that metadata as an input to compute a unique or pseudorandom nonce.
• You could put a variable-length encoding of the counter into the datagrams along with the ciphertexts, and have the recipient expand the counter values to the full IV size for decryption.

Note that these implicit IV techniques stress the importance of authenticating the IV as well as the ciphertext, otherwise active attackers may be able to fool you by reordering, deleting or adulterating packets. (Authenticated encryption modes like GCM implicitly authenticate the IV already, however.)