Subject: Re: Last Call: <draft-bormann-cbor-04.txt> (Concise Binary Object Representation (CBOR)) to Proposed Standard

From: Yaron Sheffer <[email-masked]>
Date: Fri, 16 Aug 2013 01:11:27 +0300

Hi Paul,

Sorry for the top posting. IMAP ate your mail. Responding to several remaining points:

- A parser that looks for duplicates must be able to detect that {{"a":1, "b":2}:4, {"b":2, "a":1}:5} does in fact have a duplicate key, because the two internal maps (used as keys) are identical. So in general, parsers need to canonicalize maps to any depth in order to detect duplicates. This is "complex" by any definition of the word.

- Even for an unloved diagnostic notation, you want people to read it without resorting to little pieces of paper. So a symbolic representation (TAG_URI) is definitely better than numbers.

- I don't understand your reply re: tags when applied to arrays. Is it up to the application to decide whether the tag applies to all elements, to the first one, to the last 14?

- Regarding error handling and security, I am slightly happier with -05, but not by much. For some reason you avoid using 2119 language in places where I would expect: parsers SHOULD include a "strict mode". A strict mode parser MUST fail when the syntax is broken (sec. 3.3, 3.4, and also 3.5). And so forth.

- Unknown tags: you specifically allow decoders (Sec. 3.5) to not implement any tags they don't like, and then you specify the behavior of the decoder as "do whatever you feel like" (and this is in -05). So a sender cannot rely on *any* tag being implemented by the receiver, and cannot expect deterministic behavior if any are not. This is a security issue IMO, but also an interoperability thing.

Thanks,
Yaron

---

On Aug 13, 2013, at 2:11 PM, Yaron Sheffer <yaronf.ietf at gmail.com> wrote:

> sorry I'm submitting these comments after the end of the LC period. I hope they can still be of use.

No problem, and the are. Some answers below.

> - The "diagnostic notation" can be used very effectively for things like configuration files, e.g. if an application already uses CBOR on the wire. Therefore I would suggest to formalize it a bit more, so that we also have interoperability at this level.

Based on other things we heard, we went sort of in the other direction in the next draft: saying that an implementer might consider a different notation for config files, such as YAML.

> - And since this notation is not meant as a JSON extension, this is a good time to introduce comments (e.g. with an initial '#') into the notation.

Comments are not needed in diagnostics. :-)

> - The positive vs. negative encoding means that the parser actually deals with 9-, 17-, 33- and 65-bit integers. I don't think this makes it easier to write parsers.

If you primarily think about signed integers, that may be one way of viewing it. CBOR is primarily addressing unsigned integers. Negative integers are clearly separated out, and indeed do require watching the sign bit. There is no way to handle this that is painless for all applications.

Multiple people have implemented parsers in multiple languages (JavaScript, Python, Ruby, ...), and we found it was pretty easy, and very little code.

> - Arrays are prefixed by the number of elements but not by their length in bytes. And elements need not be all of the same size. So you cannot skip the array without fully parsing every last element. IIRC this is a major disadvantage compared to ASN.1 encodings.

Correct. Counting items and not bytes is indeed a fundamental design decision in CBOR that has advantages and disadvantages. We believe the advantages outweigh the disadvantages.

In specific here, we are not assuming that "skip over an array/map" is a common desire for a decoder. Forcing an encoder to marshall all the bytes before it could start emitting an array/map causes overhead for the encoder that is avoided if it just knows the number of elements it will emit.

> - A puzzling change from JSON, and one that probably complicates implementations quite a bit, is that a map's index can be of any type, not just a string. And this includes mixed index types for the same map.

We have looked at this, and do not think that it complicates many implementations. It does not complicate encoders at all. It does not complicate decoders, even those that are looking for duplicate keys (which will be an error). It only complicates decoders that are also sorting the keys. We assume that the latter does not need to happen in the parser, but in the application that needs the keys sorted by semantics it knows about.

> - And similarly to arrays, you cannot skip a map element without deep parsing of the element.

Ditto from above.

> - I think many of the tag values are too specific, and are best left to applications. For example, why should the format care if the app encodes a UTF-8 string in base64?

Because a generic parser could then do the Base64 decoding. This will always be an iffy space: CBOR will either force too much knowledge on the application, or it will do too much. We picked somewhere on that continuum, knowing that it will make no one happy. FWIW, Carsten and I disagreed with each other on this to varying degrees during the different drafts, and different people proposed different places on the continuum where CBOR "should" be.

> OTOH, I would reserve a part of the tag space for "private" application-specific allocations.

One of the always-repeating IETF rat-hole. We didn't go there, nor will we say you're wrong for wanting to go there. The first-come-first-served space should enable such allocations. If you just want to play around in the lab, the range up to 18446744073709551615 should allow reliably avoiding collisions.

> - One tag value you may want to consider adding is "critical" in the security sense of the word, i.e., an application is required to fail if it does not understand the value (probably best applied to map keys).

That is a lovely proposal for an extension from a developer who is using CBOR in such an environment so that they can write the three or four paragraphs that would be needed to explain that in detail.

> - In the "diagnostic notation", I suggest to use symbolic values rather than integers for tags, e.g. TAG_URI.

You seem to like the diagnostic notation more than we do. :-) If CBOR becomes at all popular, having a second, more thought-out diagnostic notation seems like a reasonable project.

> - Sec. 3: because of the need for deep parsing mentioned above, a wire protocol cannot be extended by adding an element that uses a new data type (e.g. double precision FP) unless all potential recipients understand the type, even though they might not need to use the data element.

Correct. We are adding more text to make that clear.

> - Type restrictions for tags should be spelled out more clearly. E.g. in 2.4.4.2, please clarify that when this tag applies to an array or map, *all* the items (and potentially items of nested arrays/maps?) MUST be byte strings.

A CBOR protocol can choose to do just that.

> IMHO this just adds complexity and it's best to only tag the atomic item.

Noted. Some of the tags imply more restrictions that we would have hoped, but if it isn't specified in the tag, the complexity just gets pushed to all the applications.

> - Text such as this (for unknown simple types): "might issue a warning, might stop processing altogether, might handle the error by making the unknown value available to the application as such, or take some other type of action." is a security disaster waiting to happen. Also, it does not allow extensibility. Even though the encoding format is nominally extensible, in reality you cannot add stuff because the behavior of existing implementations when faced with it is unpredictable.

You (and the other folks who made similar comments about the looseness in this section) should be much happier with the next draft.

> - Similarly for unknown tags (which IMHO should be ignored). Note that "unknown" includes currently specified tags, because implementations are not required to implement all current tags.

Not sure what you mean here.

> - Another security issue, for incomplete arrays: "a parser may completely fail the decoding, or substitute the missing data and data items using an decoder-specific convention. " This is a buffer overflow vulnerability by a different name.

How is that different than, say JSON, where the decoder might never see the final "}" or "]"?

> - And by the way the entire Sec. 3 is non-normative. I suggest to use normative language for parser behavior, to ensure it is deterministic.

We think we have done so in the next version.

--Paul Hoffman

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 16 Aug 2013 18:48:30 -0700

> - A parser that looks for duplicates must be able to detect that {{"a":1, "b":2}:4, {"b":2, "a":1}:5} does in fact have a duplicate key, because the two internal maps (used as keys) are identical.…

It does not need to canonicalize, but it does need to reify (or some word that means "know what each name means"). This is not additional code: the decoder already has that in the semantic processor. It is only additional runtime during decoding, and only in protocols/applications that use maps as keys.

We could say "you cannot use maps as keys in maps because it is too hard", but then the question is where do we draw the line on "too hard". Is it "too hard" to use arrays? They might be arrays with arrays in them; is that too hard? Instead of the CBOR spec saying "this is too hard for you to do", we at some point have to trust the protocol/application developer to understand the tradeoffs.

> - Even for an unloved diagnostic notation, you want people to read it without resorting to little pieces of paper. So a symbolic representation (TAG_URI) is definitely better than numbers.

You keep trying to elevate the diagnostic notation; we keep resisting.

> - I don't understand your reply re: tags when applied to arrays. Is it up to the application to decide whether the tag applies to all elements, to the first one, to the last 14?

My reply may have been unclear, but the text in -05 should be clearer:

A tag always applies to the item that is directly followed by it. Thus, if tag A is followed by tag B which is followed by data item C, tag A applies to the result of applying tag B on data item C. That is, a tagged item is a data item consisting of a tag and a value. The content of the tagged item is the data item (the value) that is being tagged.

> - Regarding error handling and security, I am slightly happier with -05, but not by much. For some reason you avoid using 2119 language in places where I would expect: parsers SHOULD include a "str…

This feels like creep to me, but Carsten wants to add more about strict mode in the -06.

> - Unknown tags: you specifically allow decoders (Sec. 3.5) to not implement any tags they don't like, and then you specify the behavior of the decoder as "do whatever you feel like" (and this is in…

In his new wording for strict mode, the decoder will not be able to ignore any tag.

--Paul Hoffman

---

From: Yaron Sheffer <[email-masked]>
Date: Sat, 17 Aug 2013 11:19:35 +0300

Hi Paul,

please see below.

Thanks,
	Yaron

On 2013-08-17 04:48, Paul Hoffman wrote:
>> - A parser that looks for duplicates must be able to detect that
>> {{"a":1, "b":2}:4, {"b":2, "a":1}:5} does in fact have a duplicate
>> key, because the two internal maps (used as keys) are identical. So
>> in general, parsers need to canonicalize maps to any depth in order
>> to detect duplicates. This is "complex" by any definition of the
>> word.
>
> It does not need to canonicalize, but it does need to reify (or some
> word that means "know what each name means"). This is not additional
> code: the decoder already has that in the semantic processor. It is
> only additional runtime during decoding, and only in
> protocols/applications that use maps as keys.
>
> We could say "you cannot use maps as keys in maps because it is too
> hard", but then the question is where do we draw the line on "too
> hard". Is it "too hard" to use arrays? They might be arrays with
> arrays in them; is that too hard? Instead of the CBOR spec saying
> "this is too hard for you to do", we at some point have to trust the
> protocol/application developer to understand the tradeoffs.

I don't understand why you think you are shifting the complexity to the
application/protocol. Detecting duplicates is the responsibility of a 
generic decoder (parser?), and any complexity will fall there. As will 
any resultant security vulnerabilities.

In fact you do NOT need to understand "what each name means", you need
precisely a canonical order. Even if we don't like the C word for
historical reasons.

Since it's trivial to emulate complex keys with arrays, I would 
recommend to avoid this whole thing and only allow keys that are simple 
values. And even then you need to define how data items are compared, 
i.e. whether there are duplicates in {1:"a", 1.0:"a", "1":"a"}.

>
>> - Even for an unloved diagnostic notation, you want people to read
>> it without resorting to little pieces of paper. So a symbolic
>> representation (TAG_URI) is definitely better than numbers.
>

If it's a diagnostic notation, we want people (not machines) to read it.
People can read symbolic values ("TAG_MIME") much better than numbers
("36").

>
>> - I don't understand your reply re: tags when applied to arrays. Is
>> it up to the application to decide whether the tag applies to all
>> elements, to the first one, to the last 14?
>
> A tag always applies to the item that is directly followed by it.
> Thus, if tag A is followed by tag B which is followed by data item C,
> tag A applies to the result of applying tag B on data item C. That
> is, a tagged item is a data item consisting of a tag and a value. The
> content of the tagged item is the data item (the value) that is being
> tagged.

This is indeed good text. I suggest to also add: "A tag followed by an
aggregate data item (map or array) applies to all members of the data item."

[snip]

---

From: Tony Finch <[email-masked]>
Date: Mon, 19 Aug 2013 10:08:19 +0100

Paul Hoffman <[email-masked]> wrote:
> > key, because the two internal maps (used as keys) are identical. So in
> > general, parsers need to canonicalize maps to any depth in order to
> > detect duplicates. This is "complex" by any definition of the word.
>
> code: the decoder already has that in the semantic processor. It is only
> additional runtime during decoding, and only in protocols/applications
> that use maps as keys.
>
> hard", but then the question is where do we draw the line on "too hard".
> Is it "too hard" to use arrays? They might be arrays with arrays in
> them; is that too hard? Instead of the CBOR spec saying "this is too
> hard for you to do", we at some point have to trust the

YAML allows map keys to be arbitrary data structures. It requires keys to
be unique and uses structural equality to determine uniqueness, which
leads to the interesting difficulty that Yaron Sheffer pointed out.

Lua allows table keys to be arbitrary data structures. It requires keys to
be unique, but keys that are composite data structures are compared by
reference: each table literal is a new table.

You can express Lua-style data structures in YAML by giving unique tags to
each part of the data structure. You can express sharing in Lua by
assigning a part of the structure to a variable which is later used to
refer to that part.

I think CBOR should be clear about how it handles sharing and equality.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Forties, Cromarty: East, veering southeast, 4 or 5, occasionally 6 at first.
Rough, becoming slight or moderate. Showers, rain at first. Moderate or good,
occasionally poor at first.

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 19 Aug 2013 12:37:42 +0200

On Aug 19, 2013, at 11:08, Tony Finch <[email-masked]> wrote:

> sharing

CBOR and JSON have in common that their data model is based on trees.

A number of other data representation formats generalize this model to (directed, usually connected) graphs.
E.g., as you say YAML has ways to explicitly reference a part of the structure (which previously has to have been assigned a label).
(With other formats such as Python's pickle, I'm not even sure the resulting graph is always connected...)

With the data formats that provide sharing, there almost always is a semantic ambiguity:
Is the sharing just being used for more efficient transport of what semantically is a tree, or is the sharing actually part of the semantics (i.e., the format does express a graph for use by the application)?

An earlier version of what has become CBOR actually had both versions of sharing (it's easy to write them up in the spec, no? :-).
We decided to go back to a plain tree based on implementer feedback*).
We also weren't too happy about the security implications of implementation bugs in this space.

> equality.

The tree model should make it clear that the model of equality is what is called structural comparison in programming languages; reference comparison would be vacuous (always unequal).

Yes, both (tree model, structural comparison) should be said explicitly.

Grüße, Carsten

*) CBOR is extensible, though.  If an application really needs (semantic) sharing, it can still use CBOR after defining two tags: def and ref.

def([5, {"foo": "bar"}]) defines a label 5 for the data item given as the second element of the array, which is also included in the graph at the point where it occurs.
ref(5) adds an edge to that data item at the point where it occurs.
(Yes, you could even allow def([5, {"foo": "bar", "cycle": ref(5)}]) -- depending on where in the sequence of decoding the effect of the "def" occurs.  No, you don't actually have to include the label in the def — that could be assigned in sequence, and you could use relative references to enable painless nesting.  Etc., etc.)

We don't think we can generalize tags like these enough so they belong in the CBOR spec.
There are several ways to do them and an application that needs them, if any, should decide on the details based on its needs.