What Are Secure Limits to Truncate the Authentication Tag (Mac) for Short Messages? I have messages with the following fixed lengths:


4 byte
8 byte
16 byte


I want to encrypted them and prevent modification by appending an authentication tag using a MAC algorithm of my choosing (e.g. using Encrypt-then-Mac schema). Additionally I want the cipher output message to be as short as possible.

Let's say the normal MAC output size would be 16 byte (e.g CMAC with AES). Can I truncate the MAC with a short message like 4 byte to get similar security assurances?

According to various NIST standards, minimum lengths of MAC from 64 bit (CMAC) to 96 bit (GMAC) are recommended.
Cryptographic strength of an authentication tag strongly depends on the tag size and you shouldn't use a tag less than 64-bits for any application. 64-bits is really the minimum you should use. 

Such a short tag is acceptable for online protocols, where the intent is just to authenticate a packet that has been received. Since 64-bits will not be collusion resistant, previous tags will be reused before ~2^30 messages. To mitigate this, you might need to rotate key frequently. 

You can consider using SipHash function which is optimized for short inputs and has an output of 64-bits. 

https://eprint.iacr.org/2012/351