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

From: Yaron Sheffer <[email-masked]>
Date: Wed, 14 Aug 2013 00:11:45 +0300

Dear authors,

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

- The document is well written and very clearly explained.
- I am still of the opinion that this document should better be 
published as Experimental RFC. Unlike TCP and UDP. But the comments 
below are unrelated to this discussion.
- 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.
- 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.
- 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.
- 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.
- 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.
- And similarly to arrays, you cannot skip a map element without deep 
parsing of the element.
- 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? OTOH, I would reserve a part of the tag space 
for "private" application-specific allocations.
- 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).
- In the "diagnostic notation", I suggest to use symbolic values rather 
than integers for tags, e.g. TAG_URI.
- 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.
- 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. IMHO this just adds complexity and it's best to only tag 
the atomic item.
- 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.
- 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.
- 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.
- 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.

Thanks,
     Yaron

---

From: Joe Hildebrand <[email-masked]>
Date: Tue, 13 Aug 2013 16:20:45 -0600

(leaving a full response to the authors, and responding to a couple of
points I found interesting)

>- And similarly to arrays, you cannot skip a map element without deep

One of the reasons why I like the CBOR tag applied to a byte stream is
that 
it can be used to skip parsing on entire sections (no matter their
underlying types) in processors that don't need to understand that section.

>I would reserve a part of the tag space

I like that.

>it does not understand the value (probably best applied to map keys).

That's also an interesting idea.  If included, it would be best to add
this as soon as possible, and ensure that it gets added to the test
vectors, to avoid problems we've had in the past with inadequate
implementations of criticality.

>than integers for tags, e.g. TAG_URI.

How would you deal with tags that your implementation doesn't understand,
then?

-- 
Joe Hildebrand

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 13 Aug 2013 16:12:29 -0700

On Aug 13, 2013, at 2:11 PM, Yaron Sheffer <[email-masked]> 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: Dave Crocker <[email-masked]>
Date: Wed, 14 Aug 2013 08:23:38 -0700

> underlying types) in processors that don't need to understand that section.

This is an example of the core reason that having a "one true standard" 
is not appropriate for many topics:  design choices optimize along 
particular axes, giving particular optimizations, typically at the 
expense of others.  Different operating context benefit from different 
optimizations.

It makes sense for a specification to document its tradeoffs; it often 
does not make sense to choose only one such specification for use in all 
scenarios.

d/

-- 
Dave Crocker
Brandenburg InternetWorking
bbiw.net

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 14 Aug 2013 21:15:14 +0100

On Wed, Aug 14, 2013 at 4:23 PM, Dave Crocker <[email-masked]> wrote:

> This is an example of the core reason that having a "one true standard" is
> not appropriate for many topics:  design choices optimize along particular
> axes, giving particular optimizations, typically at the expense of others.
>  Different operating context benefit from different optimizations.
>

Maybe, but should the standards process at least uncover what the potential
design axes might be?

I think that we could actually dispense with design options for application
protocols entirely Remember that standards are all about making design
choices that don't matter.

It does not matter how the bits are encoded on the wire, all that actually
matters is the complexity of decoding them. And CBOR is not a good encoding
by that measure. It has a lot of options and is designed to offer even
more. CBOR is retrograde to MessagePack, a step backwards.

90% of Application protocols are simple API function calls. The other 10%
are API function callbacks. Thats it.

We have a complete set of intrinsic types that are recognized by modern
programming languages. There are some programming languages that don't
recognize all the intrinsic types of C/C#/Java but at this point the
intrinsic types that are not supported those languages are pretty few and
tending to decrease rather than increase over time.

The approach I took in JSON-BCD was to start with the assumption that the
JSON data model was sufficiently complete to be considered definitive
(after adding binary arrays) and then propose three extensions to the JSON
encoding model to provide what I believe to be 100% coverage of all
reasonable use cases.

It is possible that I did not succeed but there are two ways that I might
have slipped up. Dave does not distinguish between these.

1) An application might need a richer data model than JSON affords.
2) An application might need a more efficient bit packing than JSON-BCD
provides or a canonical encoding.

I can't address the first since the starting point for my design is to not
change the JSON data model. If someone did find JSON insufficient then they
should probably be looking at XML or ASN.1 anyway.

The second is easy enough to address, just add another encoding like I did.

-- 
Website: http://hallambaker.com/

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 15 Aug 2013 22:26:24 +0300

Hi Joe,

please see below.

Thanks,
	Yaron

> underlying types) in processors that don't need to understand that section.

I suppose you mean you don't understand the section at a semantic level 
(e.g. you don't understand the map "section-7") but you do need to parse 
every last data item in the section before you know its byte length. So 
at a syntactic level you don't skip anything.

> implementations of criticality.

I agree this needs to go into the base spec ASAP, so that it really is 
treated correctly. And it certainly cannot be a later extension, as Paul 
suggested in another message.

Also note that "critical" can be applied to all sorts of data, including 
data items that are already tagged! I think this is not allowed for 
according to the spec. But the new "self-describing" tag that appeared 
in -05 suffers from the very same problem. It can be applied to things 
that need other tags. So supporting multiple tags may be a good idea 
after all.

> How would you deal with tags that your implementation doesn't understand,

That's simple, especially if the diagnostic notation is really "write 
only" as Paul suggests. Just use the integer in this case.

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 15 Aug 2013 12:57:13 -0700

On Aug 15, 2013, at 12:26 PM, Yaron Sheffer <[email-masked]> wrote:

> I agree this needs to go into the base spec ASAP, so that it really is treated correctly. And it certainly cannot be a later extension, as Paul suggested in another message.

You and I have been in IETF security WGs together for over a decade, and we have seen how often implementers have gotten "critical" wrong regardless of the wording in the various specs. They disagree about what it means to "understand" an extension, to "be able to process" an extension, and so on. They are completely sure that people who disagree with them are obviously wrong, even in the face of multiple examples by seasoned programmers.

Someone joked at the mic in some WG years ago that the critical bit was called that because we should be criticized for how poorly it is understood.

Instead of thinking "this time I'm sure we'll get everyone to understand this", it might be better to have an extended discussion which possibly ends in multiple tags with varying descriptions.

> Also note that "critical" can be applied to all sorts of data, including data items that are already tagged! I think this is not allowed for according to the spec.

That is incorrect. Please point to the area where you think it says that so we can make it clearer.

--Paul Hoffman

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 15 Aug 2013 23:19:23 +0300

Hi Paul,

I am quite sure that I fully understand the semantics of "critical" 
(probably erroneously), so I'm not the right person to clarify the 
various meanings of the word. I would appreciate a proposal.

Just for the record, my "critical" means: the reader must be able to 
process the data item according to its specification, not just 
syntactically but also semantically, and must fail otherwise. There may 
still be contained non-critical data items that are NOT understood by 
the reader.

Sec. 2.4 consistently mentions "tag" in the singular. For example, the 
first sentence could be "a data item can optionally be preceded by one 
or more tags" - but it isn't.

Thanks,
	Yaron

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 15 Aug 2013 13:35:55 -0700

On Aug 15, 2013, at 1:19 PM, Yaron Sheffer <[email-masked]> wrote:

> I am quite sure that I fully understand the semantics of "critical" (probably erroneously), so I'm not the right person to clarify the various meanings of the word. I would appreciate a proposal.
> 
> Just for the record, my "critical" means: the reader must be able to process the data item according to its specification, not just syntactically but also semantically, and must fail otherwise. There may still be contained non-critical data items that are NOT understood by the reader.

And what you say should happen if a decoder saw the One True Critical tag before an array item, and then the decoder soon thereafter finds a tag it does not know about? The "critical" tag was on the array, not on the unknown item.

And so on. We've been there, and we haven't done that so well.

> Sec. 2.4 consistently mentions "tag" in the singular. For example, the first sentence could be "a data item can optionally be preceded by one or more tags" - but it isn't.

A tag is also a data item. A tag refers to the next data item, even if that next data item is also a tag. We'll try to clarify this in the -06.

--Paul Hoffman

---

From: Yaron Sheffer <[email-masked]>
Date: Thu, 15 Aug 2013 23:44:03 +0300

In fact I answered your question precisely when I mentioned "contained" 
data items (i.e., contained in the critical one). So I may be wrong but 
at least I'm consistent...

I think the concept of criticality is powerful, even if in the past we 
messed it up.

Thanks,
	Yaron

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 15 Aug 2013 21:48:56 +0100

On Thu, Aug 15, 2013 at 9:19 PM, Yaron Sheffer <[email-masked]>wrote:

> (probably erroneously), so I'm not the right person to clarify the various
> meanings of the word. I would appreciate a proposal.
>
> still be contained non-critical data items that are NOT understood by the
> reader.
>
> first sentence could be "a data item can optionally be preceded by one or
> more tags" - but it isn't
>

+1

The semantics of critical have never been ambiguous. The problem has been
that some people have been misled into thinking 'critical' means
'important'. So we have certain PKIX extensions where the specification
says that they MUST be marked critical even though marking them critical is
stupid.

Marking an extension critical in a PKIX certificate means 'if you do not
understand this extension you cannot understand the semantics of the
certificate and so you MUST NOT rely on it'.

As such, this is an essential feature to have available if you have a
certificate that depends on some novel revocation mechanism. But it is
something that should only be used if the semantics are so important that
breaking backwards compatibility is desirable.

It is an essential semantic but I don't believe that semantics belong in
the encoding layer. The bit can only be processed at the application layer
so the encoding layer should not be dealing with it. Consider the situation
where you have one application moving bits for another. I might send along
a piece of data that has a critical bit set but it is presented in a
context where the piece of data is optional.

And it need not be a bit. The Critical bit in SAML is actually the
<Conditions/> element. It was necessary to disguise it as I knew that
having a criticality bit would lead to a lot of unproductive arguing and
possibly the same sort of misuse as in PKIX. Calling it Conditions was a
twofer.

---

From: Joe Hildebrand <[email-masked]>
Date: Fri, 16 Aug 2013 15:58:32 -0600

>at a syntactic level you don't skip anything.

Example:

{"to": "you", "from": "me", "content": 24(h'a26161016162820203')}

If I'm just routing this based on the "to" address, I don't need to parse
the
"content" value.  If I'm the end recipient, I can either put my parser
into a 
mode that parses into CBOR (tag 24) blocks, or I can feed the byte string
I 
get for "content" from a generic parser back into that same parser.
Either 
way, I find out that the "content" is:

{"a": 1, "b": [2, 3]}

-- 
Joe Hildebrand

---

From: Yaron Sheffer <[email-masked]>
Date: Sat, 17 Aug 2013 13:58:37 +0300

Got it, thanks for the example.

But tag 24 makes it harder for pedantic security devices to validate 
CBOR, somewhat like an "eval" statement.

Is a "strict mode" decoder required to decode/validate the contents of 
this tag?

And security aside, this usage means that endpoints (sender and 
receiver) work a bit harder, in order to make the life of middleboxes 
easier. This may or may not be the right trade-off, depending on your 
architecture.

Thanks,
	Yaron

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 17 Aug 2013 15:02:17 +0200

> But tag 24 makes it harder for pedantic security devices to validate CBOR, somewhat like an "eval" statement.

Well, eval is Turing-equivalent, while tag 24 has quite narrow semantics.
So the added onus should be much more limited.

> Is a "strict mode" decoder required to decode/validate the contents of this tag?

Good question.
In my mental model, the "CBOR data"-tagged byte string is handed to the application, and this would then have to explicitly call the decoder again if needed (usually in strict mode again).
If the application does task the decoder to decode it as well, the strict mode should transfer to that (unless the application has explicitly said otherwise).

> And security aside, this usage means that endpoints (sender and receiver) work a bit harder, in order to make the life of middleboxes easier. This may or may not be the right trade-off, depending on your architecture.

There may be other reasons for a sending application to facilitate deferring decoding a part of the structure.

I'm not as sure about the continued importance of the premise here.
The premise seems to be "you are only middlebox-friendly if you provide a highly efficient way to skip large swaths of coded data the middlebox happens not to be interested in".
Unless the application knows precisely what the middlebox is trying to do (like in Joe's routing example), this may be hard to achieve.
With the move to architectures where every byte needs to be touched anyway (say, for encryption, or with transports like Minion), this also becomes less relevant.

I'm pretty sure the encoder-friendliness of item-counting (as opposed to byte-counting) approach trumps any middlebox-friendliness aspect here.

... switching messages here:

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

This is not a property of tags in general.  A tag tags just the one item it contains.
(This sentence could be used to describe a specific property of the "expected conversion" tags, but saying it this way might be confusing.  For these three tags, the additional onus of inheriting the "expected conversion" to byte strings embedded in the tagged data item is only paid by JSON converters.)

Grüße, Carsten