# Short-input (<= 128 bit), short-output (<= 10 bit) MAC

I am faced with a problem of selecting an appropriate message authentication code (MAC) for a particular application. These are the constraints:

I have two 64-bit integers $$r_a$$ and $$r_s$$ as input, where:

1. $$r_a < 2^{52}$$ and $$r_s < 2^{52}$$
2. $$r_a$$ is a multiple of 4, i.e. $$r_a = 0 \pmod{4}$$
3. $$r_s$$ is a multiple of 16, i.e. $$r_s = 0 \pmod{16}$$

This makes for an effective 98 bits of input.

My goal is to get a message authentication code for those 98 bits of input. The message authentication code $$M$$ must be between 2 and 10 bits in length, i.e. $$2 \le |M| \le 10$$. However, more is better, so the ideal goal is a 10-bit MAC.

The security goal to be achieved is the following:

The general flow of the protocol goes like this: Alice submits $$(r_a, r_s)$$ to Steve. Steve returns the concatenation of $$r_a$$ and the message authentication code $$M = F(K, r_a || r_s)$$ for a key $$K$$ only known to Steve, i.e. $$r_{auth} = r_a || M$$. At a later point, Alice submits $$r_{auth}$$ to Steve again. Alice can have as many $$(r_a, r_s)$$ tuples as the limits of the respective input integers allow. If $$M$$ is correct, Alice is permitted to use $$r_a$$ as a resource.

I want to prevent that an attacker can forge a value of $$r_{auth}$$ for any pair of $$(r_a, r_s)$$. If $$M$$ is incorrect, Steve changes the key used to generate $$M$$ and reissues all $$r_{auth}$$ in existence.

My goal is to minimize the likelihood that a valid $$r_{auth}$$ is discovered by an attacker. Of course, an attacker should also not learn $$K$$ as that would imply the ability to forge any $$r_{auth}$$.

The performance constraints are the following:

The generation of $$M$$ must not take more than 50 cycles on the target platform. The target platform is a RISC CPU:

1. with 64-bit integers
2. no rotate instructions
3. no constant-time multiplication
4. no native 64x64->128 multiplication, only 64x64->64
5. no hardware support for AES, GHASH or Keccak

I have looked at SipHash in particular. SipHash-2-4 takes about 64 cycles (at 8 cycles per round with 2 rounds for $$r_a$$ and another 2 rounds for $$r_s$$ and 4 rounds of finalization). The SipHash paper notes that SipHash-2-4 is expected to provide the maximum PRF security possible. There is a distinguisher for four rounds. However, considering the very limited output size of at most 10 bits and the ability to change $$K$$ on a detected forgery, I wonder if lower round counts would be reasonable. If so, however, it is unclear how to best choose them.

Poly1305 is both held back by either having to use 32-bit limbs (or really awkward 64-bit multiplication implementation) and the lack of an obvious way to generate the one-time keys.

What would be the optimal (existing) MAC function given these constraints? There seems to be a lot of choice for long-input MACs, but short-input MACs seem to be a rare issue.

• So 1024 refreshes of the key later the adversary has a 0.5 chance of getting authorized to the resource? Sure it is better than 512 tries without refresh but... Dec 4, 2023 at 13:02