Subject: Re: [Cbor] [Technical Errata Reported] RFC7049 (6221)

From: Carsten Bormann <[email-masked]>
Date: Sun, 5 Jul 2020 01:43:44 +0200

Hi Stuart,

thank you for this errata report.

Are you aware of the 7049bis effort?
That document was submitted to the IESG a couple of weeks ago.

We had exactly that same discussion in https://github.com/cbor-wg/CBORbis/issues/96, and added https://github.com/cbor-wg/CBORbis/pull/101/files as a fix.

> Alternatively, the “well_formed” function could return an
> indication of whether the item it determined to be well-formed
> was in fact a definite-length item or an indefinite-length item,
> and that would then be checked on the “if (it != mt)” line.

Which is exactly what is there, and what is explained better now with the above fix.

So I believe there is no problem in the pseudocode (which only has a comment changed in the above fix).

A couple of questions come up here:

* Is the pseudocode possibly too clever?

Maybe.  We even had one other misread of the pseudocode in https://github.com/cbor-wg/CBORbis/issues/148.

After seven years, I’m not sure that replacing the time-tested code from RFC 7049 by new code doesn’t incur too much risk.  
(In those seven years, we found we had to add one line, which checks against excluded two-byte forms of simple values.)

* Shouldn’t we allow indefinite strings as chunks in indefinite strings?

No.  An implementation that wants to put together indefinite strings from strings that are (possibly) indefinite can simply take out the brackets off the inner ones.  The actual use case for indefinite strings is “streaming”, where you just don’t know how long your string will be before you have to start sending it, called “chunking” in other contexts.  When you do that and have an indefinite string to send, it is very easy to take off the brackets (0x5f/0x7f and 0xff).

Having multiple ways to say the same thing can always lead to interoperability issues (and increases the cost of interoperability tests).

Worse, some applications or implementations will start to ascribe semantics to the presence or absence of redundant pairs of brackets.

Indefinite-length strings already add considerable complexity to some CBOR-consuming code; removing the ability to rely on only definit-length chunks being in there would add further complexity.

* Why doesn’t your own code check for this?

Touché.  In my backlog...

Grüße, Carsten

> On 2020-07-05, at 00:52, RFC Errata System <[email-masked]> wrote:
> 
> The following errata report has been submitted for RFC7049,
> "Concise Binary Object Representation (CBOR)".
> 
> --------------------------------------
> You may review the report below and at:
> https://www.rfc-editor.org/errata/eid6221
> 
> --------------------------------------
> Type: Technical
> Reported by: Stuart Cheshire <[email-masked]>
> 
> Section: Appendix C
> 
> Original Text
> -------------
>   well_formed_indefinite(mt, breakable) {
>     switch (mt) {
>       case 2: case 3:
>         while ((it = well_formed(true)) != -1)
>           if (it != mt)           // need finite embedded
>             fail();               //    of same type
>         break;
> 
> Corrected Text
> --------------
> Various possible fixes exist; however, none can be
> expressed briefly in just a few lines of replacement text.
> 
> Possibly the “well_formed” function could be changed
> to take an additional parameter indicating whether
> indefinite length items are allowed.
> 
> Alternatively, the “well_formed” function could return an
> indication of whether the item it determined to be well-formed
> was in fact a definite-length item or an indefinite-length item,
> and that would then be checked on the “if (it != mt)” line.
> 
> Notes
> -----
> Appendix C gives pseudocode for verifying whether a CBOR item is well-formed. However, it does not match the rules specified elsewhere in the RFC.
> 
> The normative text in the body of the RFC states:
> 
>>   Indefinite-length byte strings and text strings are actually a
>>   concatenation of zero or more definite-length byte or text strings
>>   ("chunks") that are together treated as one contiguous string.
> 
> The restrictive term “definite-length” is crucial there, and the pseudocode in Appendix C disregards this.
> 
> The pseudocode deems an indefinite-length byte/text string to be valid if it consists of a sequence of constituent items of the same type that are definite-length *or* indefinite-length.
> 
> It could be argued that the pseudocode is actually more sensible. Since an indefinite-length string item is the concatenation of zero or more well-formed string items, why shouldn’t it allow some of those well-formed string items to themselves be indefinite-length strings? There is no clear argument why not. If indefinite-length strings within other items are a useful concept in the first place, why wouldn’t they also be a useful concept within indefinite-length string items? Perhaps there is a library that outputs indefinite-length strings, and you want to use that library to output a string that is itself part of a larger indefinite-length string?
> 
> Indeed, a decoder applying Postel’s Robustness Principle (be liberal with what you accept) may choose to allow indefinite-length strings containing indefinite-length strings, nested arbitrarily deeply, since the intent, meaning, encoding and decoding of such items is clear and unambiguous.
> 
> However, such an implementation, applying the Robustness Principle, would accept input deemed illegal by the specification. Different implementations, some more liberal and some less, would decode the same input differently.
> 
> In the case where security policy is decided using one decoder implementation, and acting on the message is handled by another decoder implementation, this could result in security failures.
> 
> Possibly the normative text of the format specification could be changed to match the pseudocode, allowing any well-formed string of the right type (definite-length or indefinite-length) to be a constituent within an indefinite-length string.
> 
> Alternatively, if this is not desirable, it would be helpful for the specification text to explain, in unambiguous terms, why the designers chose to disallow indefinite-length strings to be used as constituents within an indefinite-length string. This would discourage creative implementers from feeling that it would be beneficial to be liberal and accept this input anyway, and would reduce the risk of inconsistent parsing by different implementations. In this case, the pseudocode should be corrected, to avoid implementers basing their code on that and getting incorrect implementations as a result.
> 
> Instructions:
> -------------
> This erratum is currently posted as "Reported". If necessary, please
> use "Reply All" to discuss whether it should be verified or
> rejected. When a decision is reached, the verifying party  
> can log in to change the status and edit the report, if necessary. 
> 
> --------------------------------------
> RFC7049 (draft-bormann-cbor-09)
> --------------------------------------
> Title               : Concise Binary Object Representation (CBOR)
> Publication Date    : October 2013
> Author(s)           : C. Bormann, P. Hoffman
> Category            : PROPOSED STANDARD
> Source              : IETF - NON WORKING GROUP
> Area                : N/A
> Stream              : IETF
> Verifying Party     : IESG

---

From: Jim Schaad <[email-masked]>
Date: Sat, 4 Jul 2020 19:40:33 -0700

> -----Original Message-----
> From: CBOR <[email-masked]> On Behalf Of Carsten Bormann
> Sent: Saturday, July 4, 2020 4:44 PM
> To: RFC Errata System <[email-masked]>
> Cc: [email-masked]; [email-masked]; Paul Hoffman
> <[email-masked]>; [email-masked]
> Subject: Re: [Cbor] [Technical Errata Reported] RFC7049 (6221)
> 
> Hi Stuart,
> 
> We had exactly that same discussion in https://github.com/cbor-
> wg/CBORbis/issues/96, and added https://github.com/cbor-
> wg/CBORbis/pull/101/files as a fix.
> 
> > Alternatively, the “well_formed” function could return an indication
> > of whether the item it determined to be well-formed was in fact a
> > definite-length item or an indefinite-length item, and that would then
> > be checked on the “if (it != mt)” line.
> 
> Maybe.  We even had one other misread of the pseudocode in
> https://github.com/cbor-wg/CBORbis/issues/148.
> 
> After seven years, I’m not sure that replacing the time-tested code from RFC
> 7049 by new code doesn’t incur too much risk.
> (In those seven years, we found we had to add one line, which checks against
> excluded two-byte forms of simple values.)
> 
> No.  An implementation that wants to put together indefinite strings from
> strings that are (possibly) indefinite can simply take out the brackets off the
> inner ones.  The actual use case for indefinite strings is “streaming”, where you
> just don’t know how long your string will be before you have to start sending it,
> called “chunking” in other contexts.  When you do that and have an indefinite
> string to send, it is very easy to take off the brackets (0x5f/0x7f and 0xff).
> 
> Having multiple ways to say the same thing can always lead to interoperability
> issues (and increases the cost of interoperability tests).
> 
> Worse, some applications or implementations will start to ascribe semantics to
> the presence or absence of redundant pairs of brackets.
> 
> Indefinite-length strings already add considerable complexity to some CBOR-
> consuming code; removing the ability to rely on only definit-length chunks
> being in there would add further complexity.

Even worse, the ability to have nested indefinite-length objects leads to stack overflow problems as it can just go on indefinitely.   Many implementations of ASN.1 which support this feature have had bugs reported against them.

Jim

> > The following errata report has been submitted for RFC7049, "Concise
> > Binary Object Representation (CBOR)".
> >
> > Various possible fixes exist; however, none can be expressed briefly
> > in just a few lines of replacement text.
> >
> > Possibly the “well_formed” function could be changed to take an
> > additional parameter indicating whether indefinite length items are
> > allowed.
> >
> > Alternatively, the “well_formed” function could return an indication
> > of whether the item it determined to be well-formed was in fact a
> > definite-length item or an indefinite-length item, and that would then
> > be checked on the “if (it != mt)” line.
> >
> > Notes
> > -----
> > Appendix C gives pseudocode for verifying whether a CBOR item is well-
> formed. However, it does not match the rules specified elsewhere in the RFC.
> >
> > The pseudocode deems an indefinite-length byte/text string to be valid if it
> consists of a sequence of constituent items of the same type that are definite-
> length *or* indefinite-length.
> >
> > It could be argued that the pseudocode is actually more sensible. Since an
> indefinite-length string item is the concatenation of zero or more well-formed
> string items, why shouldn’t it allow some of those well-formed string items to
> themselves be indefinite-length strings? There is no clear argument why not. If
> indefinite-length strings within other items are a useful concept in the first
> place, why wouldn’t they also be a useful concept within indefinite-length string
> items? Perhaps there is a library that outputs indefinite-length strings, and you
> want to use that library to output a string that is itself part of a larger
> indefinite-length string?
> >
> > Indeed, a decoder applying Postel’s Robustness Principle (be liberal with what
> you accept) may choose to allow indefinite-length strings containing indefinite-
> length strings, nested arbitrarily deeply, since the intent, meaning, encoding
> and decoding of such items is clear and unambiguous.
> >
> > However, such an implementation, applying the Robustness Principle, would
> accept input deemed illegal by the specification. Different implementations,
> some more liberal and some less, would decode the same input differently.
> >
> > In the case where security policy is decided using one decoder
> implementation, and acting on the message is handled by another decoder
> implementation, this could result in security failures.
> >
> > Possibly the normative text of the format specification could be changed to
> match the pseudocode, allowing any well-formed string of the right type
> (definite-length or indefinite-length) to be a constituent within an indefinite-
> length string.
> >
> > Alternatively, if this is not desirable, it would be helpful for the specification
> text to explain, in unambiguous terms, why the designers chose to disallow
> indefinite-length strings to be used as constituents within an indefinite-length
> string. This would discourage creative implementers from feeling that it would
> be beneficial to be liberal and accept this input anyway, and would reduce the
> risk of inconsistent parsing by different implementations. In this case, the
> pseudocode should be corrected, to avoid implementers basing their code on
> that and getting incorrect implementations as a result.
> >
> > Instructions:
> > -------------
> > use "Reply All" to discuss whether it should be verified or rejected.
> > When a decision is reached, the verifying party can log in to change
> > the status and edit the report, if necessary.
> >
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Stuart Cheshire <[email-masked]>
Date: Sun, 05 Jul 2020 14:51:51 -0700

> thank you for this errata report.

Thanks Carsten and Jim for your quick replies.

And I apologize for filing a mistaken erratum report. RFC Editor, if it is possible to simply delete this erratum report, please do so.

Stuart Cheshire

---

From: Stuart Cheshire <[email-masked]>
Date: Sun, 05 Jul 2020 15:51:49 -0700

> Are you aware of the 7049bis effort?

I am now. If you would like my feedback I can review it and send you comments. I realize it would not be appropriate to make any technical changes at this stage, but I may think of suggestions about minor wording changes to improve clarity. Is draft-ietf-cbor-7049bis-14 the latest version?

> (In those seven years, we found we had to add one line, which checks against excluded two-byte forms of simple values.)

Now that I understand it properly, I see how the pseudocode works, and I see why I was confused.

Without comments or a definition in RFC7049 of the well_formed function, I was left guessing. I guessed (wrongly) that it is defined to return the major type of the item consumed. The new explanatory text in draft-ietf-cbor-7049bis-14 makes it clear that it is not this simple.

Yes, the pseudocode is clever. Not too clever -- there is considerable merit in being able to make pseudocode that fits on one page of an RFC. I think a few minor tweaks can reduce misunderstandings, and still keep it fitting on a single page.

A minor textual suggestion. One of the function definitions below has a space before the opening parenthesis and one does not. I would suggest making them consistent.
well_formed (breakable = false)
well_formed_indefinite(mt, breakable)

The comments in the pseudocode use the terms “finite data item” and “finite-length chunk”, which are not used elsewhere in the RFC. Perhaps, to be consistent with the rest of the document, I suggest “definite-length item” and “definite-length chunk”.

One thing I would suggest to improve the clarity of the code would be not to overload the value zero to mean *both* that an item with major type zero was consumed (positive integer) *and* that an indefinite-length item was consumed (of any major type).

Perhaps well_formed_indefinite could return -1 when a "break" stop code is consumed, and -2 when an entire indefinite-length item is consumed.

Or maybe make well_formed_indefinite end with “return mt | 0x80” so that it *does* return the correct major type, but with the top bit set to show that it was an indefinite-length variant of that major type.

Also, the final comment “no break out” is a little confusing. What it really means is that this *is* the end of an indefinite-length item, so it really *does* break out of processing a complete indefinite-length item.

Maybe the comments at the end of well_formed and well_formed_indefinite (respectively) could be:

well_formed:
     return mt;                    // definite-length data item

well_formed_indefinite:
     return mt | 0x80;             // indefinite-length data item
or
     return -2;                    // indefinite-length data item

> Indefinite-length strings already add considerable complexity to some CBOR-consuming code; removing the ability to rely on only definit-length chunks being in there would add further complexity.

I agree with you 100% on this. The arguments you make, plus the stack usage point that Jim Schaad made, are all good.

However I didn’t find any explanation like this in draft-ietf-cbor-7049bis-14.

Given that the CBOR format could trivially support nested indefinite-length strings, there may be temptation for creative implementers to “improve” CBOR by allowing this. I can imagine a discussion between engineers debating whether to do this. Having clear text in the RFC stating that this was considered and rejected, and is considered unnecessary and a bad idea, and why, would help avoid those engineering debates ending with the wrong conclusion.

Stuart Cheshire

---

From: Jim Schaad <[email-masked]>
Date: Sun, 5 Jul 2020 17:18:37 -0700

We have not gone through the IETF wide Last Call - so any comments are welcome.

Jim

> From: Stuart Cheshire <[email-masked]>
> Sent: Sunday, July 5, 2020 3:52 PM
> To: Carsten Bormann <[email-masked]>; Jim Schaad <[email-masked]>
> Cc: Paul Hoffman <[email-masked]>; The IESG <[email-masked]>;
> [email-masked]
> Subject: Re: [Technical Errata Reported] RFC7049 (6221)
> 
> I am now. If you would like my feedback I can review it and send you
> comments. I realize it would not be appropriate to make any technical changes
> at this stage, but I may think of suggestions about minor wording changes to
> improve clarity. Is draft-ietf-cbor-7049bis-14 the latest version?
> 
> 
> Without comments or a definition in RFC7049 of the well_formed function, I
> was left guessing. I guessed (wrongly) that it is defined to return the major type
> of the item consumed. The new explanatory text in draft-ietf-cbor-7049bis-14
> makes it clear that it is not this simple.
> 
> Yes, the pseudocode is clever. Not too clever -- there is considerable merit in
> being able to make pseudocode that fits on one page of an RFC. I think a few
> minor tweaks can reduce misunderstandings, and still keep it fitting on a single
> page.
> 
> A minor textual suggestion. One of the function definitions below has a space
> before the opening parenthesis and one does not. I would suggest making them
> consistent.
> The comments in the pseudocode use the terms “finite data item” and “finite-
> length chunk”, which are not used elsewhere in the RFC. Perhaps, to be
> consistent with the rest of the document, I suggest “definite-length item” and
> “definite-length chunk”.
> 
> One thing I would suggest to improve the clarity of the code would be not to
> overload the value zero to mean *both* that an item with major type zero was
> consumed (positive integer) *and* that an indefinite-length item was
> consumed (of any major type).
> 
> Perhaps well_formed_indefinite could return -1 when a "break" stop code is
> consumed, and -2 when an entire indefinite-length item is consumed.
> 
> Or maybe make well_formed_indefinite end with “return mt | 0x80” so that it
> *does* return the correct major type, but with the top bit set to show that it
> was an indefinite-length variant of that major type.
> 
> Also, the final comment “no break out” is a little confusing. What it really
> means is that this *is* the end of an indefinite-length item, so it really *does*
> break out of processing a complete indefinite-length item.
> 
> > Having multiple ways to say the same thing can always lead to
> interoperability issues (and increases the cost of interoperability tests).
> >
> > Worse, some applications or implementations will start to ascribe semantics
> to the presence or absence of redundant pairs of brackets.
> >
> I agree with you 100% on this. The arguments you make, plus the stack usage
> point that Jim Schaad made, are all good.
> 
> Given that the CBOR format could trivially support nested indefinite-length
> strings, there may be temptation for creative implementers to “improve”
> CBOR by allowing this. I can imagine a discussion between engineers debating
> whether to do this. Having clear text in the RFC stating that this was considered
> and rejected, and is considered unnecessary and a bad idea, and why, would
> help avoid those engineering debates ending with the wrong conclusion.
> 
> Stuart Cheshire

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 6 Jul 2020 11:37:38 +0200

Hi Stuart,

(Trimming CC list)

Indeed, feedback is very welcome.

The repository is at https://github.com/cbor-wg/CBORbis, which is also where pull requests are being made that lead to future versions.  The current I-D version, for which publication has been requested, indeed is draft-ietf-cbor-7049bis-14

> well_formed_indefinite(mt, breakable)

Fixed.

> The comments in the pseudocode use the terms “finite data item” and “finite-length chunk”, which are not used elsewhere in the RFC. Perhaps, to be consistent with the rest of the document, I sugges…

Yes!  Fixed.

> Or maybe make well_formed_indefinite end with “return mt | 0x80” so that it *does* return the correct major type, but with the top bit set to show that it was an indefinite-length variant of that m…

I went for 99.
(Shades of FORTRAN…)

>     return -2;                    // indefinite-length data item

Fixed (with 99).

> However I didn’t find any explanation like this in draft-ietf-cbor-7049bis-14.

This is what I wrote to go into Section 3.2.3:

(Note that a decision has been made not to allow nesting
indefinite-length strings as chunks into indefinite-length strings.
This would require decoder implementations to keep a stack, or at
least a count, of nesting levels.  It is also unnecessary on the
encoder side, as the inner indefinite-length string would consist of
chunks, which can simply be put right into the outer indefinite-length
string.)

> Given that the CBOR format could trivially support nested indefinite-length strings, there may be temptation for creative implementers to “improve” CBOR by allowing this. I can imagine a discussion…

I agree that it is good to be explicit about these decisions.

I turned these fixes/additions into a pull request, which I hope to be turning into -15 together with any changes form the AD review.

https://github.com/cbor-wg/CBORbis/pull/203
https://cbor-wg.github.io/CBORbis/input-stuart/draft-ietf-cbor-7049bis.html
https://tools.ietf.org/rfcdiff?url1=https://tools.ietf.org/id/draft-ietf-cbor-7049bis.txt&url2=https://cbor-wg.github.io/CBORbis/input-stuart/draft-ietf-cbor-7049bis.txt

(The rfcdiff is less useful than expected because the xml2rfc processing in the I-D submission pipeline is different from that in the version of Martin Thomson’s I-D repo template we seem to be using.)

Grüße, Carsten

---

From: Barry Leiba <[email-masked]>
Date: Mon, 6 Jul 2020 12:42:26 -0400

> And I apologize for filing a mistaken erratum report. RFC Editor, if it is possible to simply delete this erratum report, please do so.

Alternatively, I can close it as "Held for Document Update".

Barry