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

From: Jim Schaad <[email-masked]>
Date: Sun, 17 Sep 2017 08:43:11 -0700

I had to stop and wait before responding because of frustration.

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.

> -----Original Message-----
> From: Carsten Bormann [mailto:[email-masked]]
> Sent: Saturday, September 16, 2017 2:08 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: draft-ietf-cbor-7049bis - Change suggested Canonicalization
> 
> Hi Jim,
> 
> On Sep 16, 2017, at 22:59, Jim Schaad <[email-masked]> wrote:
> >
> > I have never been happy with the suggested canonicalization steps for
> > dealing with maps in this document.  I would like to suggest that the
> > following algorithm be used in its stead.
> >
> >
> > * Key/value pairs are sorted from lowest value to highest.  Sorting is
> > performed on the bytes of the representation of the key and value data
> > items.  The sorting algorithm is:
> >
> > 1.  For every key value pair, encode the key and encode the value and
> > form a single byte stream by concatenating the key and value encoded
> values.
> 
> 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.

> 
> > 2.  Sort the resulting byte arrays in (byte-wise) lexical order.  This
> > is the standard memcmp sorting order.
> 
> (The reference to memcmp works because one key cannot be a prefix of
> another key.)
> 
> > This has the following benefits.
> >
> > 1.  The algorithm used to sort the byte streams is the expected one
> > for most people.
> 
> Right.
> 
> > 2.  In the event that a key occurs multiple times, there is still a
> > canonical ordering for the map which is reproducible.
> 
> I don’t think there is a need for a canonical encoding of things that aren’t
> canonicalizable data in the first place.
> 
> 
> 
> 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.

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

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

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.

jim

> Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 17 Sep 2017 20:07:44 +0200

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 co…

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

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

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

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

> 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 wron…

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