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.

  • $\begingroup$ 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... $\endgroup$
    – Maarten Bodewes
    Dec 4, 2023 at 13:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.