2
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ One alternative solution would be to prepend each entry with its length; e.g. $HMAC_k( len(createdAT) | createdAT | len(message) | message )$. Of course, you need some canonical way of converting length into a byte string; e.g. always convert it into a 4 byte little-endian value... $\endgroup$
    – poncho
    Jul 12, 2021 at 15:05
  • $\begingroup$ Good point! I forgot this one. I read that ethereum used to do that and then changed to 32 || Keccak256(message) (since the hash is always 32 bytes). Unfortunately the motivation of this change is not clear to me from the article. $\endgroup$
    – leftfold
    Jul 12, 2021 at 15:11
  • 1
    $\begingroup$ The other thing you need to include in your MAC are the field labels; if the attacker is able to convert "createdAT: time" to "deleteBY : time", well, that's something we'd want to detect... $\endgroup$
    – poncho
    Jul 12, 2021 at 15:33
  • $\begingroup$ True, although depends on the use case and how the client does the validation. I imagine when the client computes the MAC for validation, it looks for l.createdAt and uses the that value for the MAC. If there's no field createdAt then the object it got from the server is already invalid. (deletedBy is potentially ignored then.) That said, if we want to consider the whole JSON as one "document", then we should include the labels. I believe this is very close to canonicalizing and authenticating the whole JSON as outlined in the 3rd idea. $\endgroup$
    – leftfold
    Jul 12, 2021 at 16:40
  • $\begingroup$ For log entries I would MAC the canonicalized messages separately, but I would include a counter. You'll want to have centralized logging anyway, and I would not want to include a sub-nanosecond counter or performing tricks such as waiting at least a nanosecond before continuing. If synchronization is an issue you could include a service ID or something similar. Databases are good at this kind of stuff. $\endgroup$
    – Maarten Bodewes
    Aug 14, 2021 at 17:52

2 Answers 2

2
$\begingroup$

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.

enter image description here

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.