Subject: Re: [Cbor] [core] draft-ietf-cbor-7049bis - Change suggested Canonicalization

From: Jeffrey Yasskin <[email-masked]>
Date: Thu, 30 Nov 2017 22:14:22 +0000

Belatedly, I've discovered a user of "canonical" CBOR who's proposing a
different map order than the RFC suggests:
https://fidoalliance.org/specs/fido-v2.0-rd-20170927/fido-client-to-authenticator-protocol-v2.0-rd-20170927.html#message-encoding.
(Note that this isn't a final standard yet and may change.)

This is justified by the RFC saying that "Those protocols are free to
define what they mean by a canonical format and what encoders and decoders
are expected to do.  This section lists some suggestions for such
protocols." That is (as Jim said), the RFC doesn't specify "canonical"
CBOR: it just provides an option for higher-level protocols to do so.

The use of a different order in CTAP is going to either force its
implementers to write custom CBOR encoders and decoders or require the
generic encoders to take a configuration option for the map order. If the
generic encoders take an option, then it stops being an issue for CBORbis
to suggest a different order.

---

On the question of *which* order, it may be instructive to look at the
current Chromium implementation:
https://cs.chromium.org/chromium/src/content/browser/webauth/cbor/cbor_values.h?l=27&rcl=9c334c65915ec312ae1e13c4da9285ee8c58735b

We currently have serializations and deserializations create a C++
datastructure representing the CBOR value, and maps are represented by a
std::map<> whose comparator implements the canonical order. This is not as
high-performance as it could be, but it does allow the encoder to guarantee
that its output is well-formed without relying on its caller to maintain
any invariants. However, once we add support for more than just string
keys, having the comparison check the keys' serializations' lengths first
looks like it's going to make us allocate space for the serializations
inside the comparator. i.e. O(log N) allocations for a tree lookup instead
of just O(log N) comparisons. There are ways around this, but they appear
to involve having each CBORValue object cache its serialization, which
isn't pretty either.

An ordering that doesn't compare the length first (e.g. Jim's memcmp
suggestion) seems like it'll be more amenable to optimizations.

Jeffrey

On Thu, Oct 5, 2017 at 4:20 AM Francesca Palombini <
[email-masked]> wrote:

> Hi,
>
> (chair-hat on) I would really like to hear the opinion of the working
> group on this one.
> Please make sure you read through the mail thread and express your
> thoughts.
>
> Thanks,
> Francesca
>
> > -----Original Message-----
> > From: core [mailto:[email-masked]] On Behalf Of Carsten Bormann
> > Sent: den 17 september 2017 20:08
> > To: Jim Schaad <[email-masked]>
> > Cc: [email-masked]; [email-masked] WG <[email-masked]>
> > Subject: Re: [core] draft-ietf-cbor-7049bis - Change suggested
> > Canonicalization
> >
> > Hi Jim,
> >
> > I do share your frustration a bit, because I do believe the canonical
> map key
> > sorting order is one of the very few things we didn’t quite get right
> about RFC
> > 7049.  The question about fixing this really is procedurally, can we fix
> it, and
> > what is the impact on people who are now using the old order.
> >
> > > I complained that this was not a good sorting order before RFC 7049 was
> > published, so this is not a new issue.  I wish that I could find the
> mails from
> > the time as my memory was that you said we could discuss it on the next
> > version which is what I am trying to do.
> >
> > I must admit I don’t remember that discussion (it would have been more
> > than four years in the past) and my mail program apparently doesn’t
> either.
> >
> > (My mail program does remember errata report 4409 from July 2015, where
> > you did propose another sorting order.)
> >
> > >> Why do you think the values need to be in there, too?
> > >> Map keys must be different, so the value never can have an effect,
> > >
> > > That is from below - where you could have multiple duplicate keys.  It
> is
> > very possible people will do this even if it is not a valid encoding.
> >
> > The reason why 7049 does not outright make emitting duplicate keys a
> > conformance issue is that, in a streaming implementation, it is hard to
> check
> > for duplicate keys.  That argument does not apply to an implementation
> that
> > has to sort map member keys to achieve a canonical encoding.  So, while
> > creating canonical encoding, the implementation can also check for key
> > duplication and raise an error if that happens.
> >
> > >> Now, if it were mid-2013, I would just agree with you, change the
> > >> draft, and ask the WG (at the time appsawg) whether there are any
> > further comments.
> > >
> > > Given that you did not agree with me at the time when I raised this
> issue, I
> > would disagree with this statement.
> >
> > Well, I probably should have said “knowing what I know now” (i.e., the
> > degree of POLS violation that the current rules pose) I would agree with
> you.
> > (At the time, the definition we now have in RFC 7049 appeared to be
> > expedient.)
> >
> > >> Unfortunately, CBOR has been out there, we are on the way to an
> > >> Internet STD, and the current canonicalization is what’s implemented
> > >> (at least in a couple of places).  If we change this, we have to take
> > >> canonicalization out from the STD and put it into a separate
> specification.
> > >> We could decide to do this, but I’m not sure that this helps.  (We’ll
> > >> also have the CER vs. DER situation again.)
> > >
> > > I do not believe that changing this would in any way stop the
> advancement
> > to STD.
> >
> > Now that (i.e., just going ahead and changing things here) is an
> interesting
> > thought.
> >
> > One problem with that is that in the IETF, the IESG is the gating
> function, and
> > it is sufficient for a single member of the IESG to disagree with this
> thought to
> > hold up the process.
> >
> > > This section is completely non-normative there is not a single
> normative
> > statement in the entire section. Nor is the set of rules complete given
> that
> > there are two paragraphs at the end which have additional rules that
> "might"
> > need to be added.  Making this one change would not alter the fact that
> it is
> > non-normative and incomplete.
> >
> > Filling in those blanks might be another argument for going ahead and
> > writing a separate document about canonicalized CBOR instead.
> >
> > > There is a possible multiple encoding issue that may come, but that is
> > already implicit in the text of this section.  The current text reads
> "Those
> > protocols are free to define what they mean by a canonical format and
> what
> > encoders and decoders are expected to do." Which means that multiple
> > encodings are already not only possible but probably.  I think that we
> can get
> > this fixed now and go forward with an obsoleted suggested
> canonicalization
> > and be fine.
> > >
> > > The suggested algorithm is far easier to understand, easier to get
> right and
> > also has some advantages where one can do the canonicalization without
> > having to do the encoding first.
> > >
> > > int CompareNodes(node1, node2)
> > >   if node1.majorMode != node2.majorMode then return node1.majorMode
> > - node2.majorMode;
> > >   if node1.majorMode has a length field and node1.length !=
> node2.length
> > then return node1.length - node2.length;
> > >   return compare node1 and node2 values - this is major mode dependent.
> > >
> > > With the current method, you need to do a lot more work to try and get
> > things in the correct order if you have any mixing of major modes, which
> is
> > now very common place despite the statement that this is probably a bad
> > practice.
> >
> > Indeed, this is one thing we have learned since 2013: There are quite
> good
> > reasons for mixing major types in the keys of a single map.
> >
> > > If you have to emit all of the keys, sort them and then remember the
> > original order to emit the values, it is harder than concatenating the
> entire
> > thing and then emitting the values after doing the sort.  You are going
> to
> > need to keep some type of more complex structure - and thus more code- to
> > do the emission in the generic case.  Yes for a small fixed set of keys
> this is
> > not necessary but I do not believe that is where a good canonicalization
> > routine is going to be needed.
> >
> > Here is my implementation of a pre-canonicalizer for maps from the cbor-
> > canonical gem (the type “Hash” in Ruby is an order-preserving map, so we
> > can do all this entirely at the data model level):
> >
> >       def cbor_pre_canonicalize
> >         Hash[collect {|k, v|
> >                       k = k.cbor_pre_canonicalize
> >                       v = v.cbor_pre_canonicalize
> >                       cc = k.to_cbor # already canonical
> >                       [cc.size, cc, k, v]}.sort.collect{|s, cc, k, v|
> [k, v]}]
> >       end
> >
> > A sorting rule that is entirely based on (byte-wise) lexical ordering
> would
> > enable pre-sorting on types — there often would be no need to generate
> the
> > entire key encoding for sorting.  But then, you have to generate them
> > anyway, so the additional overhead is mostly a matter of memory
> > allocation/copying.
> >
> > Here is an (untested) implementation of what I think you are proposing:
> >
> >       def cbor_pre_canonicalize
> >         Hash[collect {|k, v|
> >                       k = k.cbor_pre_canonicalize
> >                       v = v.cbor_pre_canonicalize
> >                       cc = k.to_cbor # already canonical
> >                       [cc, k, v]}.sort.collect{|cc, k, v| [k, v]}]
> >       end
> >
> > I.e., the size of the key encoding is removed from the list of things to
> sort for.
> >
> > > I strongly urge that this change be done even if it might hurt
> backwards
> > compatibility and the sooner we make the decision to do it the better as
> it
> > reduces the number of people who will do it wrong.
> >
> > Now whether we should do this or not is a good question for the CBOR WG
> > to look at.
> >
> > (I’ve added the WG back to the recipient list.)
> >
> > Grüße, Carsten
> >
> >
> > _______________________________________________
> > core mailing list
> > [email-masked]
> > https://www.ietf.org/mailman/listinfo/core
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor
>