# Authenticated Encryption with smallest Overhead (Input and Output)

I'm searching for the authenticated encryption algorithm that produces/requires the least overhead in total. This includes the authentication tag that it produces and the additional input that has to be sent along the message for a secure use of the algorithm in a communication protocol.

Let's take for instance GCM:
It requires a 96-bit IV which is usually split into a 32-bit explicit nonce and a 64-bit counter. The authentication tag has to be 128 bits long (according to Ferguson). Thus, the total overhead is 196 bits.

But what about other algorithms such as CCM or EAX, etc.? Can they use shorter IVs or are they also secure with 64-bit authentication tags? Do they have other vulnerabilities that affect the overhead? What about an even smaller 32-bit tag?

If there are more authentication encryption algorithms that require the some amount of overhead which is the one with the least computational effort?

I know this question might be related to this post. However, he wants to use AES-CTR and then do his own MAC computation with HMAC instead of using a single authenticated encryption algorithm. I'd just like to use one algorithm like GCM, CCM or EAX.

• You can omit an explicit nonce if you can guarantee synchronization between machines, alternatively the IV only needs to be unique meaning smaller (padded) sizes are also OK. – SEJPM Sep 23 '16 at 20:24

It (GCM) requires a 96-bit IV which is usually split into a 32-bit explicit nonce and a 64-bit counter.

GCM uses a 96 bit IV internally, but the size of the IV is actually configurable (implementations may vary, of course).

From the specification:

$1 ≤ \operatorname{len}(IV) ≤ 2^{64}-1$.

however, the same specification also indicates:

For IVs, it is recommended that implementations restrict support to the length of 96 bits, to promote interoperability, efficiency, and simplicity of design.

Q: The authentication tag has to be 128 bits long (according to Ferguson). Thus, the total overhead is 196 bits.

The size of the authentication tag is also configurable, ranging from 64 bit to 128 bit in 8 bit increments. The shorter tag is just the leftmost bytes of the full 16 tag, so you can basically allow any size tag. The problem with GCM is that the security of the algorithm quickly diminishes for shorter authentication tags. Other algorithms will fare better.

The bit length of the tag, denoted $t$, is a security parameter, as discussed in Appendix B. In general, $t$ may be any one of the following five values: 128, 120, 112, 104, or 96. For certain applications, $t$ may be 64 or 32; guidance for the use of these two tag lengths, including requirements on the length of the input data and the lifetime of the key in these cases, is given in Appendix C

But what about other algorithms such as CCM or EAX, etc.? Can they use shorter IVs or are they also secure with 64-bit authentication tags? Do they have other vulnerabilities that affect the overhead?

Most authenticated ciphers - including CCM and EAX - are based upon CTR. They just require a nonce, which you can even send in a single byte or even bit, depending on the number of messages. You should study the specific API's how the IV is interpreted. CCM is a bit special in the sense that it also specifies the packet format, although that format is configurable with regard to various sizes.

CCM and EAX depend on (AES-)CBC-MAC and (AES-)CMAC respectively. These constructions are less vulnerable to smaller authentication tag sizes. Both are considered secure when used correctly.

If there are more authentication encryption algorithms that require the some amount of overhead which is the one with the least computational effort?

There is always OCB mode. It has one block cipher operation per plaintext block and configurable output size. It is also patented and not available for military use (which means you get into a IP rights minefield if you use it).

Currently there are efforts on the way to use the the Keccak sponge for single pass authenticated encryption. That's still under construction though.

Finally there is SIV mode. SIV mode uses a synthetic IV calculated from the plaintext, which doubles as authentication tag. This means that, as long as your plaintext is unique, the calculated IV is unique and the mode is CPA secure and authenticated. SIV is however two pass, two full passes over the plaintext are needed during encryption. This means it is not online as many other modes.

• The mentioned bit lengths were based on a higher security level not the specifications (that allow many other lengths). Ferguson describes CTR mode collisions if the IV is not 96 bits. However, my question was which algorithm achieves the highest security level with the lowest overhead. You said the nonce could be one byte. How many messages could I send if the nonce is just one byte (in CCM)? How many message could I send if my nonce is 32 bits and the authentication tag is also 32 bits (in CCM)? In this case, how big is the computational effort to break the encryption and/or authentication? – budderick Sep 23 '16 at 11:46
• A nonce is a nonce. A byte has 256 distinct values. If your nonce is 32 bits then you can send 4Gi worth of messages. As for the size of the MAC, you cannot give a overly broad statement other than "without careful analysis" you should use a tag length of 64 bits or higher. In general the nonce size (and thus the number of messages) should be at least $2^{20}$ lower than the tag size. Please take a look at appendix B.2 of CCM, as far as I know there are no results that would invalidate the calculations there. – Maarten Bodewes Sep 23 '16 at 13:16
• By the way, if you want to use CCM and don't want their packet format, I'd strongly recommend EAX instead which explicitly has been designed as a more flexible CCM. – Maarten Bodewes Sep 23 '16 at 13:23
• About the tag: Rogaway[p.120/121] describes that if an authentication tag with 32 bits and rekeying after 10,000 invalid messages is used, the probability to forge a message is still $2^{32}$. Doesn't this disagree with the difference of $2^{20}$ between nonce and tag that you mentioned? Or am I misunderstanding his statement? The appendix B.2 of CCM says $Tlen \geq lg(MaxErr/Risk)$. However, with $MaxErr=2^{32}$ and $Risk=2^{-32}$ I receive $Tlen \geq 19.26$? Yet they follow that $Tlen \geq 64$. – budderick Sep 23 '16 at 14:12
• Before and after comments are always dangerous. If I didn't win the lottery 10 times then the chance of winning it next time hasn't increased. This is however already a broad question and extensive answer. If you want to ask additional question then please ask submit new ones. – Maarten Bodewes Sep 23 '16 at 14:16