1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I don't understand the question. If your data is in JSON format, why aren't you sending that JSON data? Why are you looking for a binary format? $\endgroup$ Nov 25, 2019 at 19:30
  • $\begingroup$ I used JSON as an example, but in reality I'm using a binary format. It's the same thing though, either I have strict schema used to re-encode the elements on both sides, or probably more likely the case I serialize/encode then the receiving side doesn't parse at all - but rather uses the binary as AD, confirms, then parses. $\endgroup$ Nov 26, 2019 at 0:33

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Pretty close indeed! I'm trying to avoid it for technical reasons, but it appears without a strict schema and encoding rules for both sides, that my option is really limited to encoding on the transmitting side, and on the receiving side using the actual binary (being JSON or some actual binary format) as the AD, only parsing it after it's confirmed. However technically this is an issue because you're right, it's header data. So parse, use as needed, AND keep a copy of the bytes that it came as on to feed into the AD exactly the way I received it. Wasn't sure that was a legit option. $\endgroup$ Nov 26, 2019 at 0:38
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer here. I checked out TupleHash, but honestly I can't see where "the magic is" other that it appears to be concatenating strings. I probably just need to read it again, I don't see any mention of how or why any one string would concatenate before another. $\endgroup$ Nov 26, 2019 at 0:39
  • $\begingroup$ @jumpifnot0 The magic is that the tuple elements are length-encoded, so, e.g., the tuple $(\mathtt{ab}, \mathtt{c})$ is encoded as 2ab1c while the tuple $(\mathtt{a}, \mathtt{bc})$ is encoded as 1a2bc, roughly. (The length, in turn, is encoded slightly more elaborately than I have represented, in order to allow lengths larger than 9, up to $2^{2040} - 1$, as detailed in §2.3.1.) $\endgroup$ Nov 26, 2019 at 1:05

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.