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:
- The sender and recipient must agree on what the IV is for each encryption/decryption pair. Even better, they should authenticate the IV.
- 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.)
