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

From: Jim Schaad <[email-masked]>
Date: Sat, 2 Dec 2017 15:40:50 -0800

Looking at the CTAP description, it appears that it does not use the same one as the RFC in a really strange way.  It says that the 5/3 is to be ignored, but then does an ordering on the major type first.  I am not sure that this is actually self-consistent.

I agree that I do not want to try and do an encoding in order to decide things.  However, using the CTAP description I think that you might be able to do the sorting w/o needing to do the encoding  due to the fact that major types are all sorted together.  In fact it may be a really close to the memcmp version that I have suggested.  (I would need to do some really detailed futzing about how each of the different types is encoded to be sure one way or the other.  It might be that nested things from tags might mess that up.  Is a tagged uint sorted before a tagged sint if the second one has a shorter encoding?)

Jim

From: CBOR [mailto:[email-masked]] On Behalf Of Jeffrey Yasskin
Sent: Thursday, November 30, 2017 2:14 PM
To: Francesca Palombini <[email-masked]>
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cbor] [core] draft-ietf-cbor-7049bis - Change suggested Canonicalization

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 <https://cs.chromium.org/chromium/src/content/browser/webauth/cbor/cbor_values.h?l=27&rcl=9c334c65915ec312ae1e13c4da9285ee8c58735b> &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] <mailto:[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] <mailto:[email-masked]> ] On Behalf Of Carsten Bormann
> Sent: den 17 september 2017 20:08
> To: Jim Schaad <[email-masked] <mailto:[email-masked]> >
> Cc: [email-masked] <mailto:[email-masked]> ; [email-masked] <mailto:[email-masked]>  WG <[email-masked] <mailto:[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] <mailto:[email-masked]> 
> https://www.ietf.org/mailman/listinfo/core
_______________________________________________
CBOR mailing list
[email-masked] <mailto:[email-masked]> 
https://www.ietf.org/mailman/listinfo/cbor

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 3 Dec 2017 15:15:22 +0100

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

I looked at the spec referenced.

So they essentially add

		• If the major types are different, the one with the lower value in numerical order sorts earlier.

as a major sorting rule before the existing RFC 7049 canonicalization rules:

		• If two keys have different lengths, the shorter one sorts earlier;
		• If two keys have the same length, the one with the lower value in (byte-wise) lexical order sorts earlier.

This is different from simply going for byte-wise lexicographic (memcmp order(*)), which effectively would get us the first rule as the major sorting order already, but get rid of the length-based second rule (first rule in Section 3.9 of RFC 7049).

I’ve come to see the putting the length comparison rule early in 3.9 as a major regression.
One of the objectives when designing the CBOR serialization was not to repeat one big mistake that ASN.1 BER makes: to make overall lengths of complex composite items visible/important in the encoding of the next higher composite.
Here, we are doing just that.  D’oh.

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

Right.  So the change would be to mention two options for this, the old canonical, and the saner (memcmp order) canonical.  Now the next step is finding names for legacy canonical/saner canonical.  We then have to decide whether we turn this into a separate document, at Proposed Standard level, or believe that adding another suggestion to 3.9 is essentially a bug fix and can be done in the Standard level document.

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

Right.  So I think you are saying we get to fix this.

I’d like to understand why CTAP went for major type first, then legacy order.  Do you know when that was decided/who decided that?  Can we maybe even influence them to go for the simpler “saner” ordering?

Grüße, Carsten

(*) well, we wouldn’t define it as “memcmp order” because that would require a normative reference to some C standard plus defining the third parameter of the memcmp as the lower of the two lengths, which again exposes total lengths.
Instead, we would spell out “bytewise lexicographic order of the canonical encodings of the keys” in a few more words.
Note that this can be defined simply based on the first byte that differs in the byte sequence — there are no two different CBOR data items where one is a prefix of the other (CBOR is self-delimiting).

---

From: Jeffrey Yasskin <[email-masked]>
Date: Sat, 16 Dec 2017 01:04:47 +0000

Sorry for the belated response. I asked the owners of the CTAP spec your
questions in https://github.com/fido-alliance/fido-2-specs/issues/389,
which most of you can't read because it's a private repository, but I've
gotten permission to paste the answer here.

They felt they had to specify something because section 3.9 isn't normative.

They wanted to "allow for a simple comparison using unbounded memcmp", and
they wanted to guarantee that "an overflow would never occur with this
encoding."

They hadn't realized that CBOR is self-delimiting, which answers the second
concern.

CTAP happens to only use integers and text strings as map keys, which the
author convinced me makes the CTAP rule equivalent to the pure
lexicographic ordering. That'll make it a backward-compatible change to
switch to the lexicographic ordering if they ever do add more complex keys,
but it seems unlikely that they'll need more complex keys.

For Jim, yes, [30] (81 18 1E) comes before [-1] (81 20) in the pure
lexicographic order, but after in the major-then-length-then-lexicographic
order.

Jeffrey

On Sun, Dec 3, 2017 at 6:15 AM Carsten Bormann <[email-masked]> wrote:

> > 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.)
>
>                 • If two keys have the same length, the one with the lower
> value in (byte-wise) lexical order sorts earlier.
>
> This is different from simply going for byte-wise lexicographic (memcmp
> order(*)), which effectively would get us the first rule as the major
> sorting order already, but get rid of the length-based second rule (first
> rule in Section 3.9 of RFC 7049).
>
> One of the objectives when designing the CBOR serialization was not to
> repeat one big mistake that ASN.1 BER makes: to make overall lengths of
> complex composite items visible/important in the encoding of the next
> higher composite.
> > 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.
>
> Right.  So the change would be to mention two options for this, the old
> canonical, and the saner (memcmp order) canonical.  Now the next step is
> finding names for legacy canonical/saner canonical.  We then have to decide
> whether we turn this into a separate document, at Proposed Standard level,
> or believe that adding another suggestion to 3.9 is essentially a bug fix
> and can be done in the Standard level document.
>
> > 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.
>
> I’d like to understand why CTAP went for major type first, then legacy
> order.  Do you know when that was decided/who decided that?  Can we maybe
> even influence them to go for the simpler “saner” ordering?
>
> Grüße, Carsten
>
> (*) well, we wouldn’t define it as “memcmp order” because that would
> require a normative reference to some C standard plus defining the third
> parameter of the memcmp as the lower of the two lengths, which again
> exposes total lengths.
> Instead, we would spell out “bytewise lexicographic order of the canonical
> encodings of the keys” in a few more words.
> Note that this can be defined simply based on the first byte that differs
> in the byte sequence — there are no two different CBOR data items where one
> is a prefix of the other (CBOR is self-delimiting).
>
>

---

From: Jim Schaad <[email-masked]>
Date: Fri, 15 Dec 2017 18:25:31 -0800

From: CBOR [mailto:[email-masked]] On Behalf Of Jeffrey Yasskin
Sent: Friday, December 15, 2017 5:05 PM
To: Carsten Bormann <[email-masked]>
Cc: Jeffrey Yasskin <[email-masked]>; [email-masked]
Subject: Re: [Cbor] [core] draft-ietf-cbor-7049bis - Change suggested Canonicalization

Sorry for the belated response. I asked the owners of the CTAP spec your questions in https://github.com/fido-alliance/fido-2-specs/issues/389, which most of you can't read because it's a private repository, but I've gotten permission to paste the answer here.

They wanted to "allow for a simple comparison using unbounded memcmp", and they wanted to guarantee that "an overflow would never occur with this encoding."

They hadn't realized that CBOR is self-delimiting, which answers the second concern.

CTAP happens to only use integers and text strings as map keys, which the author convinced me makes the CTAP rule equivalent to the pure lexicographic ordering. That'll make it a backward-compatible change to switch to the lexicographic ordering if they ever do add more complex keys, but it seems unlikely that they'll need more complex keys.

For Jim, yes, [30] (81 18 1E) comes before [-1] (81 20) in the pure lexicographic order, but after in the major-then-length-then-lexicographic order.

[JLS] Yes, but the major-length-lexicographic order does match what the byte-by-byte ordering would be.  So if we change to that it means that they would not need to do a heavy re-write if they add new items.

Jim

Jeffrey

On Sun, Dec 3, 2017 at 6:15 AM Carsten Bormann <[email-masked] <mailto:[email-masked]> > wrote:

So they essentially add

Grüße, Carsten

---

From: Jeffrey Yasskin <[email-masked]>
Date: Fri, 22 Dec 2017 22:13:52 +0000

> Right.  So I think you are saying we get to fix this.

I've tried to implement this in https://github.com/cbor-wg/CBORbis/pull/9.
I defined a core set of rules so that other specs can use them by
reference, gave several examples of protocols that will need to extend the
rules, and defined a second set of rules that match the canonical order
that RFC7049 suggested.

Do folks like this direction?

I don't have a strong opinion about which document should hold the
canonicalization rules. Can we ask the IESG which they'd prefer?

Jeffrey

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 22 Dec 2017 23:23:32 +0100

Hi Jeffrey,

quick reactions after a first skim:

I’m not sure the direction should be to open this up; I think the recommendations should become more narrow as we learn about the practical issues.

We could write a separate document on the preferred c14n so we can keep this out of the main document.

I don’t think we necessarily want to encourage cross-over between int and float, so I think the “shortest float” rule should be applied independent of whether that cross-over is desired.

Why keep the “shortest int” rule less well defined for protocols that use bignums?  It should apply there as well, i.e., use bignums only for integers too large for the major type 0/1 formats.

Grüße, Carsten

> On Dec 22, 2017, at 23:13, Jeffrey Yasskin <[email-masked]> wrote:
> 
> I've tried to implement this in https://github.com/cbor-wg/CBORbis/pull/9. I defined a core set of rules so that other specs can use them by reference, gave several examples of protocols that will need to extend the rules, and defined a second set of rules that match the canonical order that RFC7049 suggested.
> 
> I don't have a strong opinion about which document should hold the canonicalization rules. Can we ask the IESG which they'd prefer?
> 
> Jeffrey

---

From: Jeffrey Yasskin <[email-masked]>
Date: Fri, 22 Dec 2017 23:56:29 +0000

I don't think https://github.com/cbor-wg/CBORbis/pull/9 allows anything
that RFC7049 didn't, which is the meaning I get from "open this up".

We *could* move this (all of section 3?) to a separate document, but I
haven't seen anyone say that we need to. A downside of moving section 3 to
another RFC is that it'll make it harder to find. Someone authoritative
(Francesca?) should just make this call so that we can stop angsting about
it.

I'm generally happy to change exactly which examples demonstrate that
protocol designers need to think about canonicalization even if they start
from the core canonicalization requirements. I'd appreciate a concrete
statement of which examples to use though.

Once we add floating values, the type of a field matters in defining its
canonicalization. A float64 field only needs to canonicalize NaN. A
float16/float32/float64 field needs to canonicalize to either the smallest
or largest type. An int/float field needs to again canonicalize toward or
away from int. A bigint field needs to prefer either a fixed-length (useful
for cryptographic signatures) or the shortest representation. A
decfrac/bigfloat/number field has an even more complex problem. I don't
personally have enough examples of existing canonicalized CBOR-based
protocols to make any confident recommendations here. If the list gives me
some, along with the field experience that justifies them, I'm happy to
write them down in my patch.

Jeffrey

On Fri, Dec 22, 2017 at 2:23 PM Carsten Bormann <[email-masked]> wrote:

> I’m not sure the direction should be to open this up; I think the
> recommendations should become more narrow as we learn about the practical
> issues.
>
> I don’t think we necessarily want to encourage cross-over between int and
> float, so I think the “shortest float” rule should be applied independent
> of whether that cross-over is desired.
>
> Why keep the “shortest int” rule less well defined for protocols that use
> bignums?  It should apply there as well, i.e., use bignums only for
> integers too large for the major type 0/1 formats.
>
> Grüße, Carsten
>
>
> > > Belatedly, I've discovered a user of "canonical" CBOR who's proposing
> a different map order than the RFC suggests:
> >                 • If the major types are different, the one with the
> lower value in numerical order sorts earlier.
> >
> >                 • If two keys have the same length, the one with the
> lower value in (byte-wise) lexical order sorts earlier.
> >
> > I've tried to implement this in
> https://github.com/cbor-wg/CBORbis/pull/9. I defined a core set of rules
> so that other specs can use them by reference, gave several examples of
> protocols that will need to extend the rules, and defined a second set of
> rules that match the canonical order that RFC7049 suggested.
> >