Subject: [Cbor] Canonical CBOR

From: Laurence Lundblade <[email-masked]>
Date: Wed, 30 May 2018 16:06:32 +0000

To be a bit direct here, canonical CBOR seems only about 2/3 baked to me. I have a couple of ideas on what to do about and may volunteer to write some text, but first I want to ask about use cases for it.  I’ve seen some described, but they really aren’t compelling to me.

I think the important question is this: has anyone actually implemented it and put it to use? 

One use case mentioned is to be able to reconstruct the encoded CBOR to verify a signature after decoding. If that is to be supported we should specify canonical encoding for every type in the RFC. Right now there is a good specification for some types (integers), but only suggestions for others (floating point). 

Another use case is that map sorting allows for fast detection of duplicate labels. I don’t know why duplicate detection is needed. If you can’t trust the sender and/or transport to not add duplicates, you can’t really trust them to not make other worse mistakes. 

But the real question is about implementations. If now one has implemented in the years that 7049 has been around it seems questionable.

Here’s a few ideas for what to do:

#1 Require all integers and lengths to always be in shortest form and always the same. Do the same for floating point, dates and as many other of the types defined in the spec as possible.  For a lot of data types, this is not that hard to implement and it eliminates a variability in the spec that seems unnecessary. Then you don’t have to define a canonical format for these types. They are always canonical.

#2 If not #1, then make a clear subsection of the document that sharply defines the canonical format for all data types that have multiple representations. This is specially called “Canonical CBOR” and anyone claiming to implement it, MUST implement all aspects of it.  We also highly recommended that every implementation use it.  Move this to section 3 so it is not in the recommendations for creating protocols. Leave the sorting order and use of definite lengths requirements out of this section because they are costly to implement.

#3 Rename section 4.9 to something like “recommendations for uniform CBOR” (or “invariant”, or “consistent” CBOR). This text is non-normative recommendations only. The sorting order can be part of this. 

Basically, the less work we leave to CBOR protocol designers, the better. It’ll be easier for protocol designers to do there work, they’ll get it right more often and there’ll be less interop problems.

Last, I think the names “Canonical Encoded CBOR” and “Strict CBOR Decoding” would be really helpful. 

LL

---

From: Jeffrey Yasskin <[email-masked]>
Date: Wed, 30 May 2018 11:12:38 -0700

Thanks for the prod to try to explain this better.

On Wed, May 30, 2018 at 9:06 AM Laurence Lundblade <
[email-masked]> wrote:

> To be a bit direct here, canonical CBOR seems only about 2/3 baked to me.
> I have a couple of ideas on what to do about and may volunteer to write
> some text, but first I want to ask about use cases for it.  I’ve seen some
> described, but they really aren’t compelling to me.
>

https://cs.chromium.org/chromium/src/components/cbor/cbor_reader.h only
parses (a subset of) CBOR matching the core canonicalization requirements.
https://fidoalliance.org/specs/fido-v2.0-id-20180227/fido-client-to-authenticator-protocol-v2.0-id-20180227.html#ctap2-canonical-cbor-encoding-form
requires non-canonical encodings to be rejected.

One use case mentioned is to be able to reconstruct the encoded CBOR to
> verify a signature after decoding. If that is to be supported we should
> specify canonical encoding for every type in the RFC. Right now there is a
> good specification for some types (integers), but only suggestions for
> others (floating point).
>

It's not obvious that verifying signatures is a good use for
canonicalization (even though I keep listing it as a possible use), but in
protocols that want to do it, the protocol is responsible to specify the
unique bytes that encode any semantic object that can appear in the
protocol. This is why https://cbor-wg.github.io/CBORbis/#rfc.section.4.9
defines "core canonicalization requirements" instead of "canonical CBOR".

Another use case is that map sorting allows for fast detection of duplicate
> labels. I don’t know why duplicate detection is needed. If you can’t trust
> the sender and/or transport to not add duplicates, you can’t really trust
> them to not make other worse mistakes.
>

We have to code expecting the sender to make any and all mistakes
(sometimes maliciously). If we don't prohibit duplicates, we have to
specify whether the first or last value "wins". If we do prohibit them,
then that's one bit of parser variation we don't need to worry about. All
the other possible mistakes are still on the table, of course. See also
https://tools.ietf.org/html/draft-thomson-postel-was-wrong-03.

Here’s a few ideas for what to do:
>
> #1 Require all integers and lengths to always be in shortest form and
> always the same. Do the same for floating point, dates and as many other of
> the types defined in the spec as possible.  For a lot of data types, this
> is not that hard to implement and it eliminates a variability in the spec
> that seems unnecessary. Then you don’t have to define a canonical format
> for these types. They are always canonical.
>

Carsten prefers this representation of floating point, but the folks
implementing FIDO hardware devices hate the idea of having to select
between floating-point formats based on an item's value.

There's some benefit in allowing integers to be in non-shortest form, in
that a serializer can put a long placeholder integer in the byte stream,
and then update it to its final value after writing some extra data.
Despite this tradeoff, I wouldn't personally object if CBOR itself always
required integers to be in shortest form. Since RFC7049 has been around for
a while, this would probably require a survey of implementations to see if
any actually take advantage of the flexibility.

#2 If not #1, then make a clear subsection of the document that sharply
> defines the canonical format for all data types that have multiple
> representations. This is specially called “Canonical CBOR” and anyone
> claiming to implement it, MUST implement all aspects of it.  We also highly
> recommended that every implementation use it.  Move this to section 3 so it
> is not in the recommendations for creating protocols. Leave the sorting
> order and use of definite lengths requirements out of this section because
> they are costly to implement.
>

This isn't sufficient to call the result "canonical", because a protocol
may define multiple ways to represent something. For example, in Carsten's
idea of an automatic JSON->CBOR converter, the result of converting
"deadbeef" could be either a text string or the byte string h'75E69D6DE79F'
wrapped in tag 22.

Also, if a map can be sorted in two different ways, neither is canonical.

#3 Rename section 4.9 to something like “recommendations for uniform CBOR”
> (or “invariant”, or “consistent” CBOR). This text is non-normative
> recommendations only. The sorting order can be part of this.

Basically, the less work we leave to CBOR protocol designers, the better.
> It’ll be easier for protocol designers to do there work, they’ll get it
> right more often and there’ll be less interop problems.
>
>

Yep, https://cbor-wg.github.io/CBORbis/#strict-mode isn't clear that
"Strict Mode" applies only to decoders. It's also not precise enough to
write just "use strict mode" in the definition of a decoder and be sure
you'll get the same results from all decoders.
<https://www.ietf.org/mailman/listinfo/cbor>

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 30 May 2018 21:10:46 +0200

Hi Laurence,

thank you for bringing this subject up again.

In 2013, we knew what we were up to when we wrote the original section 3.9 of RFC 7049.
Essentially, canonicalization (14n) is a mine field where the only way to win is to not play.

However, we got a few things right, I think:

(1) we acknowledged that c14n is to a certain extent application-specific.  So the RFC gives some guidance, but does not define a single hard and fast set of rules.

(2) the serialization provides little intrinsic incentive for gratuitous variation.  Apart from definite vs. indefinite lengths (which is an example of something that depends on application requirements), the obvious rule to use the shortest of several possible encodings is natural and easy to implement.  [One design alternative, to only ever allow the shortest encoding, is problematic for some other applications.]  Implementations already do this naturally (except sometimes for floating point — implementers of serialization layers often know little about floating point and are rightfully scared by it.  That’s why we have the example code in the appendix… and it is easy to do exhaustive testing at least for binary16!).

We also got one thing extremely wrong:

(A) the canonical ordering for keys based on lengths first, then byte-wise lexicographical order, is violating the principle of least surprise and poses some performance disadvantages.  This probably should be fixed to pure byte-wise lexicographical order.  Applications that already have decided to use the existing map order guidance can do that by invoking (1) above.

So what are the use cases?  Signing information expressed at the data model level is often given as one, but it is not very convincing.  What I consider much more interesting is to be able to do byte-wise comparison of instances to establish a certain degree of data model level equality/inequality.  This is really useful for testing and for matching information in a database.

Several of the 50 implementations of CBOR listed at cbor.io do some form of c14n, sometimes as an add-on.  (E.g., for cbor-ruby, there is a separate gem cbor-canonical that provides canonical encoding.  There is no decode checker — you check by canonical-encoding again and then doing a bytewise comparison.)  I never got around to collecting feature lists for the implementations on cbor.io, so I don’t know how many of them do canonical.

We discussed c14n in some detail at IETF 101.
Please search for “c14n” in:
https://datatracker.ietf.org/meeting/101/materials/minutes-101-cbor-00
and read up to “implementation matrix”.

While we didn’t make a final determination at the meeting, it seems to me that the best way forward is to keep c14n at the “proposed standard” level, by splitting it out to a separate document, while the rest of CBOR goes to Internet Standard.  This also reflects the lower levels of implementation experience we have with c14n, and the desire to fix the map order.

> #1 Require all integers and lengths to always be in shortest form and always the same.

We already do this for c14n.  (Do you mean to always require this?  Not so sure about that.)

> Do the same for floating point,

(But only weakly so for floating point.)

> dates and as many other of the types defined in the spec as possible.  

These often have way more application semantics than you can handle in a generic canonicalizer.
Try canonicalizing URIs, Regexps, etc.  Do you canonicalize RFC 3339 dates to UTC?
I think we have to be open about the limitations of what can be done here.

> For a lot of data types, this is not that hard to implement and it eliminates a variability in the spec that seems unnecessary. Then you don’t have to define a canonical format for these types. They are always canonical.

I sure like that approach.

> #2 If not #1, then make a clear subsection of the document that sharply defines the canonical format for all data types that have multiple representations. This is specially called “Canonical CBOR” and anyone claiming to implement it, MUST implement all aspects of it.  We also highly recommended that every implementation use it.  Move this to section 3 so it is not in the recommendations for creating protocols.

That would be the separate document proposed above?

> Leave the sorting order and use of definite lengths requirements out of this section because they are costly to implement.

Er, now you lost me.

> #3 Rename section 4.9 to something like “recommendations for uniform CBOR” (or “invariant”, or “consistent” CBOR). This text is non-normative recommendations only. The sorting order can be part of…

“Consistent CBOR” sounds good to me.  (As a name for the new version with the fixed map sorting order…)

> Basically, the less work we leave to CBOR protocol designers, the better. It’ll be easier for protocol designers to do there work, they’ll get it right more often and there’ll be less interop probl…

I can’t argue with that.  Prematurely nailing down details can also be very costly, though.

> Last, I think the names “Canonical Encoded CBOR” and “Strict CBOR Decoding” would be really helpful. 

With what semantics?

Grüße, Carsten