AES-CTR-MAC alternative

Question

I have to send small (~10 bytes) authenticated messages over an insecure channel. I was thinking of an alternative to the "conventional" AES128-CTR-MAC, which will take 16 bytes for the CT and additional 2 or 4 bytes for the MAC. The motivation is that I'd like to reduce the message size as much as possible.

---

My alternative is to use a nonce and a counter, pass it to a HASH function, xor with the PT, and then AES encrypt. This would produce the CT.

Since PT is small, I was thinking off zero padding it (with two or 4 bytes). Then on decryption, I can compare the zero padding and use it as an authentication.

As I see it, this method is not prone to "bit switch" attack (as changing the CT will totally ruin the PT).

Do you think it's a reasonable way to do authentication? Is it enough to use a plain HASH function, or is it better to add a key to the HASH?

If, in addition, I also want to authenticate a non encrypted part of the message, It is OK to concatenate this message to the HASH input?

---

In addition: The transmitter and the receiver are time synchronized. and keep their internal (and equal) counter value. on each transmission, the transmitter and receiver increment their counter. The message is sent once every 10 seconds, and the receiver will accept only one packet on scheduled time. That way, the attacker can't brute force the MAC.

Answer 1

I can see at least one big issue with your own scheme: the attacker could cycle through as many counters until one is found that produces the same bits in the hash at the location of the padding bits used for authentication. In that case the authentication would succeed with a different nonce / counter. This problem also disallows additional authenticated data to be added to the scheme. This would be fixed by using HMAC instead of a hash. When validating the padding bits I would use a constant time compare to be on the safe side (I don't see a direct issue, but better safe than sorry).

---

You need to pad to the end of the block anyway otherwise you cannot XOR with the hashed IV. So you should at least use as many zero bits as possible. For two bytes you have a chance of one in $2^{16}$ that a random message is accepted. That's too large for most cryptographic systems.

So for a fixed sized message you could use 4 bytes minimum, giving you a chance of one in $2^{32}$ - somewhat over 4 billion in the short scale - to accept a random message. Even then it would be a good idea to implement additional ciphertext messages. Your messages would 12 bytes of course, as the AES block size is 16 bytes in size. The larger the padding the better.

---

Truncating a MAC (over the ciphertext) is common. It has the same problem as validating the padding in your scheme: if you check too few bits then the message may be accepted with a probability that is considered too high. It has the advantage of being secure for variable size messages, at the obvious cost of bits compared to your scheme.

Older triple DES schemes usually use 4 bytes / 32 bits. This could be OK if an authenticated session is broken if a bad packet is received, but remember that sending $2^{32}$ random messages is commonly not out of reach to an attacker.

I'd say that having a 10 byte cipher text (for a 10 byte message, there is no need to use 16 bytes for a 10 byte message) for AES-CTR and a 4 byte MAC is more secure than your proprietary scheme. CCM and EAX are ready made AEAD schemes that could be useful in your situation. They rely just on AES and allow shorter tag sizes without losing too much security, and they allow additional authenticated data as well.

---

The addition (having the counter and time synced) does make it harder for an attacker to have an invalid message accepted. However, it still doesn't disallow attacks on additional authenticated data that gets hashed. It should be noted that keeping a nonce and the time synchronized can be a deceptively hard problem. An attacker is often capable of power cycling devices, slowing down clocks etc.

Answer 2

CTR mode ciphertext size is identical to its plaintext size. If you're seeing extra bytes (excluding the MAC) then that's probably because you're using an implementation that writes the IV first followed by ciphertext.

If you somehow can ensure IVs are synchronized between clients and not reused with the same key then you don't need to actually send the IV. In modes (like CTR) that aren't weakened by predictable IVs you can just set the nonce for the first message^* to zero and increment it by one each time you send a message. If you reboot and "forget" what the old IV was then you need to establish a new symmetric key.

CTR mode message length has zero overhead excluding the IV. However it is unsafe to use CTR without authentication. You can use the smallest MAC length that is both (A) Allowed by the MAC algorithm and (B) Is large enough to make the probability of forgery with a random MAC sufficiently small.^**

If a MAC can be truncated or if its output is already the desired tag length and you don't need to send the IV then CTR plus that MAC algorithm already produces the smallest possible message size.

_{* This is confusing because here by "message" I mean one byte stream that can be multiple blocks long. Not a single packet. It's not necessary to set the nonce part of the IV equal to the counter part of the IV. In this context it doesn't matter how you form the IV as long as it's not reused.}

_{** The probability is $2^{-n}$ if the MAC algorithm's output is unbiased. For some algorithms it may be safe to use only the first $n$ bits. If you can limit the number of tags that can be tried then $n \geq 64$ is probably fairly safe.}

Answer 3

Truncating the MAC tag is done not so rarely. The IANA has a registery of AEAD algorithms with truncated MAC tags, but usually they're not shorter than 64 bits.

What your diagram describes is not so different from that used in the key wrapping mode as specified in NIST SP 800-38F. They append short constant values to the plaintext, then use a key wrapping transformation (built from block ciphers such as AES) to generate the ciphertext.