# Recommended authenticated stream cipher for minimum overhead?

I'm running my TCP/IP protocol secured by encrypting each packet with AES128/CBC, bundling a SHA256 HMAC over that packet.

This causes quite a bit of space overhead for small packets, so at first I was thinking of running AES in CTR-mode and still use the HMAC, but it would be much better to run some sort of stream cipher with integrated authentication.

What are my best options?

Edit:

I should mention that failing an integrity check will always disconnect a connection.

This means re-negotiating the encryption keys, which gives each new connection a new encryption and signing key.

In other words, make a wrong guess and the keys are reset. Even with a small integrity checksum, guessing right to sustain an exchange appears to be a hard problem.

-
You will still have the same overhead with an authenticated stream cipher. They still have a message fingerprint, the strength of authenticated modes of encryption is in safely coupling encryption and authentication. AES-CTR is a stream cipher, by the way. If your packets are so small, are you sure you need to authenticate them all as they are received? Perhaps you could batch the authentication step if the packets are sent at a high rate, to alleviate the space overhead issue? –  Thomas Jun 14 '13 at 10:12
@Thomas yes, of course AES-CTR is a stream cipher. In order to avoid trivial bit-flipping of the packets, some integrity checking is necessary. As I understand it there are several ways to put that on top a stream cipher without having a separate HMAC or similar as checksum. –  Nuoji Jun 14 '13 at 10:55
Yes, of course. But, no, a MAC always requires extra information. Think about it - if you have X bits of plaintext to encrypt and authenticate, and Y bits of output, at the very least X = Y to ensure correct decryption (pigeonhole principle) which leaves nothing for authentication. So Y > X. So, no, any authentication mechanism will always add a few bytes of overhead to store the fingerprint. So your options are in making the fingerprint smaller (not ideal for obvious reasons) or authenticating more data per fingerprint. –  Thomas Jun 14 '13 at 11:03
If it were possible to have zero authentication overhead, authenticated encryption schemes would already be doing it. You won't find your solution at this low a level, you need to go up a notch and design your system around minimizing overhead. –  Thomas Jun 14 '13 at 11:04
That's a bad idea. Using only parts of the HMAC is a loss of integrity. Assuming the attacker knows the message is only 1 byte long. He still can not test these $2^8$ possibilities and find a correct HMAC , because he does not know $k$. If you use only part of the HMAC, his chance of random guessing went up to non-neglectible probability. –  tylo Jun 14 '13 at 16:04

You asked the same question over on the IT Security site. Please don't cross-post. It is frowned upon, under the rules these sites operate.

Here is what you should be doing:

• Truncate the MAC tag to an acceptable length. You will need to choose a length that provides a suitable tradeoff between packet size vs. security against forgery. I suggest you use an authenticated encryption scheme. See my answer on the other site for details.

• For additional robustness, you could include in the MAC a running hash of all prior packets. This way, if anyone tampers with a single packet, then it will invalidate all subsequent MAC tags. This may or may not add security, depending upon the application. However, it can't hurt: it doesn't increase the length of the packet at all, so it is free, and in some cases it might help stop some attacks (if they require forging a packet in the middle of a stream).

For example, suppose you use a 16-bit MAC tag. This is too short to prevent an attacker from forging a packet by sheer blind luck: if the attacker sends a forged packet with a random 16-bit tag, then it will be accepted with probability $1/2^{16}$. Therefore, an attacker can get a single forged packet accepted, by trying $2^{16}$ times until they succeed. In some applications, that's bad enough that the application is irrecoverably broken. But in others, forging a single packet is not devastating in itself. In the latter case, we can proceed to ask: after the attacker successfully forged a single packet, what happens next? If you don't add a running hash, then the attacker can allow the rest of the packets to flow unimpeded, and the connection will continue. In particular, it's possible that neither endpoint will notice anything has gone awry. But if you use a running hash, then there's no way the attacker can allow the conversation to continue. If the attacker forges one packet then allows all subsequent packets to flow unimpeded, the recipient will reject all subsequent packets, as they don't have a matching running hash. There's no way for the attacker to recover and repair the connection so it can continue at length -- so a successful forgery inevitably leads to denial of service shortly thereafter. This increases the chances that a successful attack will be noticed, and makes it harder to carry out attacks that require multiple successful forgeries. So, in some applications, it may make some attacks harder (no guarantees, but it might just help).

And again, you probably really ought to be looking much more seriously at TLS or DTLS. Writing your own packet format is a recipe for trouble.

-
I know I shouldn't cross-post, but the type of answers differ widely, so I couldn't resist it. As for the running MAC, I already bundle a counter with the packet (in the encrypted data) to avoid replay attacks. I'm guessing that either: a) putting the counter in the encrypted data or b) adding the counter to the HMAC of c) keep a running hash would be fairly equivalent, or? –  Nuoji Jun 17 '13 at 7:25
But a counter would be unnecessary if I instead run in a streaming mode like CTR, right? –  Nuoji Jun 20 '13 at 8:11
[@Nuoji, Oops, I just realized my last comment had a massive typo. I'll re-print it, but this time with a correction. See also my edited answer.] No, a counter is not equivalent to a running hash. I'm suggesting a running hash as a hardening measure, so that it's hard to forge a single packet and then allow the other packets through unchanged. A counter doesn't provide that same benefit. –  D.W. Jun 20 '13 at 23:28

There aren't any known attacks on the PRFness of HMAC-SHA256 better than brute force.
(So you can truncate that MAC to length L where $\:\:\frac1{2^L}+\epsilon\:\:$ is an acceptable risk of forgery.)

To reduce the impact of a forgery without making the ciphertext any longer, one should use a
format-preserving encryption (FPE) scheme that is secure against one query to the encryption
oracle and one query to the decryption oracle, which are not necessarily made in that order. $\;\;\;$
Choose either $\; [b_{client} = 0 \: \text{ and } \: b_{server} = 1] \:$ or $\: [b_{client} = 1 \: \text{ and } \: b_{server} = 0] \;$.
Let $\;\; \operatorname{pL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be an injective function that can be inverted
efficiently enough. $\;\;\;\;$ For the sentence two after this one to be possible, you will also need that
for all $m$, $\: m\leq \operatorname{pL}(m) \:\:$. $\;\;\;\;$ Let $\;\; \operatorname{rL} \: : \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \: \to \: \{0,\hspace{-0.03 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\} \;\;$ be a function that
can be computed efficiently enough. $\;\;\;\;$ Let $\;\; \operatorname{pad}_{\hspace{.01 in}m}\hspace{-0.01 in} \: : \: \{0,\hspace{-0.03 in}1\}^m \hspace{-0.01 in} \times \{0,\hspace{-0.03 in}1\}^{\operatorname{rL}(m)} \: \to \: \{0,\hspace{-0.03 in}1\}^{\operatorname{pL}(m)}$
be a sequence of injective functions that can be computed efficiently enough and satisfies
$[message$ can be efficiently computed from $\:\operatorname{pad}_{\operatorname{length}(message)}\hspace{-0.02 in}(message,\hspace{-0.02 in}randomness)]$.

$\operatorname{unpad}_{\operatorname{length}(message)}\hspace{-0.02 in}(\operatorname{pad}(message,\hspace{-0.02 in}randomness)) \: = \: message$
For all other values of $x$, $\;\; \operatorname{unpad}(x) \: = \hspace{.08 in} \perp \;\;\;$.

$\operatorname{Enc}(key,party,packetnumber,plaintext,randomness)$
$=$
$\operatorname{FPEencrypt}(\operatorname{HMAC}(key,b_{party}||\hspace{.02 in}packetnumber),\operatorname{pad}(plaintext,randomness))$

$\operatorname{Dec}(key,party,packetnumber,ciphertext)$
$=$
$\operatorname{unpad}(\operatorname{FPEdecrypt}(\operatorname{HMAC}(key,(1-b_{party})||\hspace{.02 in}packetnumber),ciphertext))$

As long as each party only encrypts and decrypts once each for each $packetnumber$, a feasible adversary will have probability $\:\: \frac1{2^{\operatorname{pL}(m)-(m+\operatorname{rL}(m))}}+\epsilon\:\:$ of violating integrity for each submitted ciphertext
of length $\operatorname{pL}(m) \:$ (and a ciphertext whose length is not in $\:\operatorname{range}(\operatorname{pL})\;$ will always decrypt to $\perp$).

Furthermore, if the parameters are such that that probability is noticeable, then the decryptions
of ciphertexts with length $\operatorname{pL}(m)$ that violate integrity will be computationally indistinguishable
from independent samples from the following distributions for each such ciphertext:

if the indicated $party$ did not output a ciphertext for that $packetnumber$, then uniform on $\{0,\hspace{-0.03 in}1\}^m$
else, the plaintext used by $party$ for that $packetnum$ with probability $\frac{2^{\operatorname{rL}(m)}-1}{2^{m+\operatorname{rL}(m)}-1}$,
and each other member of $\{0,\hspace{-0.03 in}1\}^m$ with probability $\; \frac{2^{\operatorname{rL}(m)}}{2^{m+\operatorname{rL}(m)}-1} \:\:$.

-
What way would that be? –  Nuoji Jun 14 '13 at 22:52
Ergh. No offense, but I find multi-character variables to be incredibly ugly. Isn't $\operatorname{length}(message)$ so much less appealing than $\ell(m)$? Also, $\{0,1,2,3,\dots\}$ could be specified as $\mathbb{N}_0$. –  Reid Jun 20 '13 at 1:10