Any standards for canonical ordering of HMAC or additional data in AEAD ciphers?

Question

According to RFC 5116... If the AD input is constructed out of multiple data elements, then it is essential that it be unambiguously parseable into its constituent elements, without the use of any unauthenticated data in the parsing process. (In mathematical terms, the AD input must be an injective function of the data elements.) If an application constructs its AD input in such a way that there are two distinct sets of data elements that result in the same AD value, then an attacker could cause a receiver to accept a bogus set by substituting one set for the other. The requirement that the AD be uniquely parseable ensures that this attack is not possible. This requirement is trivially met if the AD is composed of fixed-width elements. If the AD contains a variable-length string, for example, this requirement can be met by also including the length of the string in the AD.

I’m using an AEAD to confirm integrity on a message and occasionally decrypt a payload if it exists, but my issue should apply to any arbitrary data in CRC to HMAC. How do you take arbitrary data and unambiguously order it

Imagine I have some serialization (example JSON) that can have 1-100 fields I’ll assemble into data to be get a MAC (my AD in AEAD). The receiving end has no idea which ones are coming, and the ordering of decode is not guaranteed.

It seems my options are to order the object data in some predetermined way like apple’s value is placed into a byte array before bannana’s value is. But then there is an issue of types, in my system apples will only ever be 0-12 so one byte works great, but bananas can get to 65000, so two bytes, carrots need a 32bit, and I am owe dates so I need signed there. Or I have the option of using the serialized container without parsing it at all but there are other problems with that.

Without getting too over the top in examples, I see the issue even if I gave everything a 64bit space and put its length in front, I quickly end up with a confining system - or I end up with a schema that needs to be shared on both sides.

So are there any standards or even formally recommended practices for this?

Answer 1

Imagine I have some serialization (example JSON) that can have 1-100 fields I’ll assemble into data to be get a MAC (my AD in AEAD). The receiving end has no idea which ones are coming, and the ordering of decode is not guaranteed.

If the receiving end really has no idea which fields are coming as you say, then the only way it can possibly determine the authentic AD for a message has to be from information that's transmitted alongside that message. There's a bit of a subtle point here: the AD for a message in practice can be either (or a mix of):

1. Unencrypted data that is stored or transmitted along with the encrypted data proper. Often people will call this a "header." In this case the receiving end knows the AD because it's right there next to the ciphertext so to speak.
2. An encoding of information that isn't stored or transmitted along with the ciphertexts, but which the sender and receiver can correctly infer from the context in which each message occurs. For example, if messages are part of some protocol where the participants' interaction is governed by some state machine, an encoding of the current mutually known state can be used as AD.

If your statement that "the receiving end has no idea which [fields] are coming" is true, then, it sounds like you're in a pure example of #1—you have to send the JSON-encoded AD along with the ciphertext for the recipient to know it at all. In that case the JSON text sounds like it would serve you just fine as AD or an element thereof, as the JSON encoder call that produced that text embodies some injective function of the data elements into a textual representation that can then be uniquely parsed.

JSON-encoded data however can be problematic for case #2 (implicit AD), because although JSON is uniquely parsable, there is more than one textual encoding for any given datum, e.g., whether you use optional whitespace or not, and ordering of named fields as you remark. The problem is that even if both ends mutually know the correct set of key/value mappings, they might encode it to different textual AD strings that would then fail the authenticity checks. In that case either the two ends would have to agree on how to do the JSON encoding in an identical manner, or use some other encoding that's not prone to this problem. Encoding the fields alphabetically by field name as suggested is one possible tool for this, indeed.

Answer 2

You need to make sure that individual properties are length-prefixed (to avoid the same output for a || bb and ab || b), and that the ordering of the properties is well defined, for example by ordering the keys.

There is a standard for this: TupleHash, one of the SHA-3 derived constructions. It was designed for cSHAKE, but the input encoding can be used with any hash functions.

Still, the data has to be in a predictable order. If your inputs are key/value pairs, sort the keys.