How to compose multiple values to MAC authenticate?

Question

If the data I want to authenticate consists of multiple values and I compute a MAC simply concatenating the values, an adversary can "shift" characters within those values without invalidating the MAC. How is this issue commonly and best addressed?

I have found this existing question about MACing multiple messages, but I feel the proposed solutions do not generalize well for more than two messages.

Consider the following contrived example:

Suppose I have a server that stores authentic log entries for clients. The client writes a log entry, authenticates it using a MAC and sends it to the server. Later, when the client retrieves log entries from the server, it should be able to verify their authenticity.

Let's say log entries have the following structure:

{
  createdAt: "1621012345",
  message: "first entry"
}

Naively I could create a MAC for a log entry l as $$ mac = \text{HMAC}(K, l.createdAt \| l.message) $$ where $\|$ denotes concatenation and $K$ is the secret key.

If I were to go ahead to store this log entry and MAC on a server and retrieve it later, the server could return

{
  createdAt: "1621012",
  message: "345first entry",
  mac: "<the MAC computed above>"
}

Since 1621012 || 345first entry is the same as 1621012345 || first entry I would not notice the manipulation when checking the MAC.

Note that in this case I should actually detect the manipulation by validating then length of createdAt. But that only works if the length is fixed and not if I had, say, authorName instead of the timestamp.

I can think of the following ways of dealing with this:

1. Intersperse a delimiter

If I calculated my MAC as $mac = \text{HMAC}(K, l.createdAt \| \text{':'} \| l.message)$ I believe this attack would not be possible anymore. At first glance it seems problematic that the delimiter character can appear in the message. But that only makes it impossible to unambiguously reconstruct the values from the concatenated string, which is irrelevant in this scenario. I cannot think of any way to make the calculation of the MAC ambiguous here. Is this simple solution secure?

2. Hash values before concatenating

I could calculate the MAC, for example, as $mac = \text{HMAC}(K, \text{SHA256}(l.createdAt) \| \text{SHA256}(l.message))$ (or any other cryptographic hash function). This ensures that an adversary cannot meaningfully manipulate the values I concatenate. It also ensures that the concatenated values always have a fixed length. Does the hashing add any value compared to the first idea?

3. Authenticate the whole structured data

I could also calculate the MAC over the complete JSON object of the log entry. Effectively, this means I have more elaborate, meaningful delimiters (the keys and syntax). Basically, like a JWT. Note that this approach also has some downsides, which mostly boil down to loss of API flexibility and the need to canonicalize the JSON. There's a great blog post about this at https://latacora.micro.blog/2019/07/24/how-not-to.html.

---

Am I missing any good solutions for this problem? Is there a recommended way to deal with this?

Answer 1

Luckily, your exact problem has been treated in the paper Deterministic Authenticated-Encryption A Provable-Security Treatment of the Key-Wrap Problem by Rogaway and Shrimpton. In particular, look at section 5.

In short, what you have is a function $f$ that works on strings $X \in \{0,1\}^*$, but what you actually want is a function $f^*$ that works on vectors of strings $\mathbf{X} =(X_1, X_2, \dots, X_n) \in (\{0,1\}^{*})^*$. As you have already noted, one way of building $f^*$ from $f$ is simply by encoding $\mathbf{X}$ into a single string $\langle X \rangle$ in some reversible manner, and then applying $f$ to it. While this works, it's not actually very efficient.

What Rogaway and Shrimpton suggests is a more clever construction, called S2V (string-to-vector), which transforms a string-input function $f$ to a vector-input function $f^*$. The construction is shown in the figure below.

In summary, the S2V construction applies the $f$ function to each element of $\mathbf{X}$, adds one extra call to $f(0^n)$, and does some doublings in the finite field $\mathbf{F}_{2^n}$. Note that there are two versions of the S2V depending on whether the final vector element is longer or shorter than $n$.

Finally, Rogaway and Shrimpton show that the security of $f^*$ reduces to the security of the underlying function $f$.

Answer 2

To partly answer my own question here: idea 1 is in fact not secure.

It does become problematic if the delimiter appears in the value after all. Consider using , as a delimiter for the values Hello, and World. Interspersed with , this gives Hello,,World, where the first comma is part of the message and the second is the delimiter. Unfortunately, the values Hello and ,World yield the same message. So the intuition that the composed message should be parsable seems to hold after all.

As pointed out by @poncho in the comments, this could be fixed by prepending the length of the field to each field, instead of using delimiters.

Personally I'll probably go with the second version (hashing the values before concatenating). But I'd still be interested if anyone else has come accross this and how you've solved it.