Subject: [Cbor] Handling duplicate map keys

From: Jeffrey Yasskin <[email-masked]>
Date: Thu, 21 Nov 2019 20:52:07 +0800

Re https://github.com/cbor-wg/CBORbis/issues/63, we had a long discussion
today at IETF106 about what CBORbis should say about how protocols handle
the (invalid) situation in which a CBOR map contains two entries with the
same key.

Clearly basic-validating
<https://cbor-wg.github.io/CBORbis/draft-ietf-cbor-7049bis.html#basic-validity>
parsers will return an error. The disagreement comes from what if anything
to require from non-validating parsers. An interesting piece of background
information comes from CVE-2013-4787
<https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2013-4787> and the ZIP
format: A ZIP central directory can have a single filename multiple times
(with no mention of this possibility in the specification
<https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT>). The Android
signature checker (in Java) checked the last occurrence, while the package
loader (in C) used the first. It takes two mistakes for that kind of
vulnerability to happen: 1) The implementer has to parse the format twice
with two different parsers instead of parsing once and operating over that
parse result twice. 2) The format has to fail to say how to deal with
invalid input. We have control over (2).

CBORbis currently says:

"A CBOR-based protocol MUST define what to do when a receiving application
> does see multiple identical keys in a map. The resulting rule in the
> protocol MUST respect the CBOR data model: it cannot prescribe a specific
> handling of the entries with the identical keys, except that it might have
> a rule that having identical keys in a map indicates a malformed map and
> that the decoder has to stop with an error. Duplicate keys are also
> prohibited by CBOR decoders that enforce validity (Section 5.4)."

A) Leaving this alone is one of the possibilities.

B) CBOR itself could say that a protocol implementation with a
non-validating decoder MUST use the *first* entry with a particular key and
discard the rest. (Note that this works even with a streaming decoder,
since it's a requirement at the protocol level.) This would ban three kinds
of implementations:
1) Ones that build up a native map from the full content of the CBOR map,
and unconditionally overwrite any existing entry with the next entry read
from the CBOR map. These can be fixed by checking whether an entry with the
key is already present before writing to it. Some native map APIs might not
be able to do this without a redundant lookup.
2) Ones that initialize a native structure with default values (as opposed
to "missing") and then overwrite those values with the entries read from
the CBOR map. These can be fixed by adding a "missing" value to all the
native structure fields, which might increase the storage needed.
3) Ones that perform some real-world action as they stream each CBOR map
entry and never store the entries at all. I don't see a way to get those to
ignore duplicates. I also worry about the real-world effect of performing
one of those actions twice if it was important to use a map instead of an
array.

C) CBOR could require protocols to use the *last* entry with a given key.
This requires any implementation to scan to the end of a map before using
any of the content, so it's probably a bad idea. It is potentially easier
to implement in a decoder that builds up a native map of the content.

D) CBOR could allow protocols to leave the behavior of duplicate keys
unspecified if they explicitly declare that the fields are not
security-sensitive.

I prefer B and then D. What do other people think?

Jeffrey

---

From: Laurence Lundblade <[email-masked]>
Date: Sat, 23 Nov 2019 09:59:52 +0800

Here’s a rough proposed text:

The protocol designer should make a choice for maps as to whether duplicates are allowed or not, particularly as to whether duplicates would cause security or functionality problems.

The protocol designer should only require duplicate detection when necessary as it can have the following implications:
Some generic decoders do not support duplicate detection because the underlying facilities in their programming environment to represent maps can’t detect duplicates
Some generic decoders do not support duplicate detection because it requires more code and is not required
It requires more resources to implement: 1) memory to store all the keys in the map, 2) more code, 3) more CPU time, as much as O(n^2). This is particularly an issue with big maps in constrained environments.
It is suggested that protocol designers require duplicate detection only no the particular maps for which there is an issue.

Decoders will typically fall into one of these categories:
Full duplicate detection
Pass all items up to caller, allowing the caller to implement duplicate detection or not
No duplicate detection
A generic decoder should identify which it is. Some may support more than one, selectable by configuration.

Here’s why.

I see no value in take first or take last over duplicate detection. In all three all, the keys encountered must be recorded and processed. If the map is large this will take a lot of memory. In all cases there is some extra code and CPU. CPU time is worse than O(n), perhaps O(n^2). It doesn’t matter if the use case is streaming or not. It is the memory, code and CPU time that matter.  (Take last can only be implemented by decoding the whole map, as it is only after decoding the whole map that it can know it has encountered the last; in a way you cannot do the last for a streaming decoder).

This is a guess — I don’t think map libraries that don’t support duplicate detection commonly support  take first. I suspect some do take first, some do take last and some do take random. To me that makes any mention of take first or take last in the specification not very valuable especially as it doesn’t have much memory, CPU or code advantage over duplicate detection.

LL

---

From: Jeffrey Yasskin <[email-masked]>
Date: Sat, 23 Nov 2019 17:11:22 +0800

On Sat, Nov 23, 2019 at 10:00 AM Laurence Lundblade <[email-masked]>
wrote:

> The protocol designer should make a choice for maps as to whether
> duplicates are allowed or not, particularly as to whether duplicates would
> cause security or functionality problems.
>
> The protocol designer should only require duplicate detection when
> necessary as it can have the following implications:
>
>    - Some generic decoders do not support duplicate detection because the
>    underlying facilities in their programming environment to represent maps
>    can’t detect duplicates
>    - Some generic decoders do not support duplicate detection because it
>    requires more code and is not required
>
>
>    - It requires more resources to implement: 1) memory to store all the
>    keys in the map, 2) more code, 3) more CPU time, as much as O(n^2). This is
>    particularly an issue with big maps in constrained environments.
>
> It is suggested that protocol designers require duplicate detection only
> no the particular maps for which there is an issue.
>
>    - Full duplicate detection
>    - Pass all items up to caller, allowing the caller to implement
>    duplicate detection or not
>    - No duplicate detection
>
I don't think generic decoders are relevant here. Protocol implementations
often accumulate their input into a data structure even if they use a
streaming decoder to read the input. Any such protocol can detect
duplicates (of the keys it uses at all) for at most the cost of an extra
bit per field.

Here’s why.
>
> I see no value in take first or take last over duplicate detection. In all
> three all, the keys encountered must be recorded and processed. If the map
> is large this will take a lot of memory. In all cases there is some extra
> code and CPU. CPU time is worse than O(n), perhaps O(n^2). It doesn’t
> matter if the use case is streaming or not. It is the memory, code and CPU
> time that matter.  (Take last can only be implemented by decoding the whole
> map, as it is only after decoding the whole map that it can know it has
> encountered the last; in a way you cannot do the last for a streaming
> decoder).
>
> This is a guess — I don’t think map libraries that don’t support duplicate
> detection commonly support  take first. I suspect some do take first, some
> do take last and some do take random. To me that makes any mention of take
> first or take last in the specification not very valuable especially as it
> doesn’t have much memory, CPU or code advantage over duplicate detection.
>

I think you make a good point that if a protocol is going to specify "take
first", it can probably specify "error on duplicate key" for the same cost.
That might imply some much simpler text:

"Protocols based on CBOR SHOULD fail with an error if a map contains a
> duplicate key, except that if the key isn't used at all, they MAY ignore it
> instead. Protocols that do not reject duplicate keys MUST (?) document why
> the cost of rejecting duplicates is too high and why accepting them will
> not lead to security vulnerabilities. An array might be a better choice for
> such protocols."

Do we have any concrete examples of protocols or formats built on CBOR that
don't store anything while parsing their input? One of those might provide
a good example of a protocol that shouldn't reject duplicates.

Jeffrey

---

From: Laurence Lundblade <[email-masked]>
Date: Sat, 23 Nov 2019 07:21:49 -0800

> On Nov 23, 2019, at 1:11 AM, Jeffrey Yasskin <[email-masked]> wrote:
> 
> On Sat, Nov 23, 2019 at 10:00 AM Laurence Lundblade <[email-masked] <mailto:[email-masked]>> wrote:
> It requires more resources to implement: 1) memory to store all the keys in the map, 2) more code, 3) more CPU time, as much as O(n^2).. This is particularly an issue with big maps in constrained environments.
> I don't think generic decoders are relevant here. Protocol implementations often accumulate their input into a data structure even if they use a streaming decoder to read the input. Any such protocol can detect duplicates (of the keys it uses at all) for at most the cost of an extra bit per field.

My intention was that “pass all items up” covers your case. 

My QCBOR + t_cose implementations work exactly as you describe to implement dup detection in COSE header parameters. It’s the data structures that hold the COSE header params that are used to detect the duplicates, not the generic decoder (QCBOR).  This seems like a good way to handle this problem for lots of use cases. 

> I think you make a good point that if a protocol is going to specify "take first", it can probably specify "error on duplicate key" for the same cost. That might imply some much simpler text:
> 
> "Protocols based on CBOR SHOULD fail with an error if a map contains a duplicate key, except that if the key isn't used at all, they MAY ignore it instead. Protocols that do not reject duplicate keys MUST (?) document why the cost of rejecting duplicates is too high and why accepting them will not lead to security vulnerabilities. An array might be a better choice for such protocols.”

I think I’d invert it and say that protocols that require duplicate detection for security reasons should describe that requirement in security considerations so the implementor gets a good solid hint that they need to worry about it.

There is lot of text implying that duplicates are bad, but I think it would be worth being explicit.

You are an idiot if you design a protocol that considers duplicate input valid or necessary. Duplicate map keys are always an error in CBOR and will not work with many generic decoders.

> 
> Do we have any concrete examples of protocols or formats built on CBOR that don't store anything while parsing their input? One of those might provide a good example of a protocol that shouldn't reject duplicates.

Duplicates will / must only occur in error situations. It is always right to reject encoded CBOR that has duplicates.

The main thing is that when duplicates have security implications for the protocol, that must be called out and the implementor told to do something about them. 

To say it more in prose: They should either use a generic CBOR decoder that errors out on duplicates, or a CBOR decoder that passes duplicates up so the protocol implementation on top of CBOR can do the detection. What they must not do is use a decoder that does take first, take last or randomly takes one of the occurrences.

LL

---

From: Laurence Lundblade <[email-masked]>
Date: Sat, 23 Nov 2019 09:11:23 -0800

> On Nov 23, 2019, at 7:21 AM, Laurence Lundblade <[email-masked]> wrote:
> 

To be really explicit (for my brain too), it is never right for normal behavior of a CBOR protocol to rely on take first. It is *always* right to error out when duplicates are detected.

LL

---

From: Jeffrey Yasskin <[email-masked]>
Date: Sun, 24 Nov 2019 02:48:56 -0800

Comments inline:

On Sat, Nov 23, 2019 at 7:21 AM Laurence Lundblade <[email-masked]>
wrote:

>>    - Some generic decoders do not support duplicate detection because
>>    the underlying facilities in their programming environment to represent
>>    maps can’t detect duplicates
>>    keys in the map, 2) more code, 3) more CPU time, as much as O(n^2).. This
>>    is particularly an issue with big maps in constrained environments.
>>
> My QCBOR + t_cose implementations work exactly as you describe to
> implement dup detection in COSE header parameters. It’s the data structures
> that hold the COSE header params that are used to detect the duplicates,
> not the generic decoder (QCBOR).  This seems like a good way to handle this
> problem for lots of use cases.
>

Yep, that's the model I'm thinking of. I'm clearly struggling to put it
into understandable spec language.

>> such protocols.”
> I think I’d invert it and say that protocols that require duplicate
> detection for security reasons should describe that requirement in security
> considerations so the implementor gets a good solid hint that they need to
> worry about it.
>

There's an interesting difference of approach here. It's plausible to say
that protocol designers should pick the secure design only when they
realize their design has security implications, but I prefer to say that
they should pick the secure design unless they think about it and realize
the design doesn't have security implications. I think the second will get
us noticeably more security in a world where designers don't have time to
think about every aspect of every piece of their design.

There is lot of text implying that duplicates are bad, but I think it would
> be worth being explicit.
>
> You are an idiot if you design a protocol that considers duplicate input
> valid or necessary. Duplicate map keys are always an error in CBOR and will
> not work with many generic decoders.
>
>
I wouldn't say "idiot", just "wrong". The spec already says you "MUST NOT"
do this, but I'm not opposed to making that statement more direct.

Thanks,
Jeffrey

---

From: Laurence Lundblade <[email-masked]>
Date: Sun, 24 Nov 2019 10:21:44 -0800

> On Nov 24, 2019, at 2:48 AM, Jeffrey Yasskin <[email-masked]> wrote:
> 
> There's an interesting difference of approach here. It's plausible to say that protocol designers should pick the secure design only when they realize their design has security implications, but I prefer to say that they should pick the secure design unless they think about it and realize the design doesn't have security implications. I think the second will get us noticeably more security in a world where designers don't have time to think about every aspect of every piece of their design.

I don’t know how many generic decoders exist that really can’t do or support duplicate detection. I also don’t know how many use cases there are that can’t afford duplicate detection. If there are few of both, then making no duplicate detection the exception that needs to be called out seems right.

I have been thinking about CWT and EAT as examples. Maybe EAT should say that duplicate detection should be required unless a profile of EAT says it is not, the secure choice. For the most part EAT will be processed on servers where there is clearly no resource issue. The only issue would be the implementation  environment (Java, PHP, Python…).

EATs might be decoded on constrained devices sometimes, but that is rare. In that case a profile can relax the requirement.

EATs are always signed so duplicates would only come from bad implementations. There are plenty of ways that am implementation can go wrong other than duplicating keys that are completely undetectable.

> I wouldn't say "idiot", just "wrong". The spec already says you "MUST NOT" do this, but I'm not opposed to making that statement more direct.

Pardon my wording. Certainly, I do not want that as normative text.

---

From: Mike Jones <[email-masked]>
Date: Sun, 24 Nov 2019 22:10:57 +0000

I advocate wording that says you MUST NOT create protocols or specifications that count on any behavior for duplicate map keys other than rejecting the input.  Anything else opens up a Pandora’s Box of non-interoperability.

                                                       -- Mike

From: CBOR <[email-masked]> On Behalf Of Laurence Lundblade
Sent: Sunday, November 24, 2019 10:22 AM
To: Jeffrey Yasskin <[email-masked]>
Cc: Jeffrey Yasskin <jyasskin=[email-masked]>; [email-masked]
Subject: [EXTERNAL] Re: [Cbor] Handling duplicate map keys

On Nov 24, 2019, at 2:48 AM, Jeffrey Yasskin <[email-masked]<mailto:[email-masked]>> wrote:

Thanks,
Jeffrey

---

From: Jim Schaad <[email-masked]>
Date: Sun, 24 Nov 2019 20:35:44 -0800

From: CBOR <[email-masked]> On Behalf Of Jeffrey Yasskin
Sent: Sunday, November 24, 2019 2:49 AM
To: Laurence Lundblade <[email-masked]>
Cc: Jeffrey Yasskin <jyasskin=[email-masked]>; Jeffrey Yasskin <[email-masked]>; [email-masked]
Subject: Re: [Cbor] Handling duplicate map keys

Comments inline:

On Sat, Nov 23, 2019 at 7:21 AM Laurence Lundblade <[email-masked] <mailto:[email-masked]> > wrote:

On Nov 23, 2019, at 1:11 AM, Jeffrey Yasskin <[email-masked] <mailto:[email-masked]> > wrote:

On Sat, Nov 23, 2019 at 10:00 AM Laurence Lundblade <[email-masked] <mailto:[email-masked]> > wrote:

*	Some generic decoders do not support duplicate detection because the underlying facilities in their programming environment to represent maps can’t detect duplicates
*	Some generic decoders do not support duplicate detection because it requires more code and is not required

*	It requires more resources to implement: 1) memory to store all the keys in the map, 2) more code, 3) more CPU time, as much as O(n^2).. This is particularly an issue with big maps in constrained environments.

*	Full duplicate detection
*	Pass all items up to caller, allowing the caller to implement duplicate detection or not
*	No duplicate detection

Yep, that's the model I'm thinking of. I'm clearly struggling to put it into understandable spec language. 

[JLS]  It also gets fun in some other ways.  It might not matter for the protocol I am designing, because I always reflect back the input that I use to the client application.  That means it does not matter what the duplicate behavior is right up to the point in time where I decide that I am going to apply COSE to it.  I now have multiple potential behaviors that are required for the application

Jim

Thanks,
Jeffrey

---

From: Michael Richardson <[email-masked]>
Date: Mon, 25 Nov 2019 09:02:30 +0100

> My intention was that “pass all items up” covers your case.

python, ruby, lua, java, etc. dictionaries can not "pass all items up"
The reason why JSON is so successful is because it maps into native
dictionaries (maps) trivially.

In order to pass things up, a different structure will be necessary,
at which point many developers and protocol designers will see no value in
CBOR over a bespoke binary encoding.

It is this refusal to define a specific algorithm for dealing with duplicates
that is leading to security issues.  It's not the duplicates themselves that
is the problem, it is the ambiguity.

I am less afraid to declare an answer and make some decoders non-compliant.
I think that they will get fixed.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Laurence Lundblade <[email-masked]>
Date: Mon, 25 Nov 2019 17:36:28 -0800

Hi Michael

> On Nov 25, 2019, at 12:02 AM, Michael Richardson <[email-masked]> wrote:
> 
> 

Yes, they fall into one of the other two categories:
- They do duplicate checking and return an error
- They return no error and are either take first, take last or take random

> I think that they will get fixed.

I would hope fix them means that they will error out when a duplicate is detected.

It probably doesn’t cost any more than take first and is the more clear, clean and secure thing to do IMO.

Seems like it will be easier to get agreement on that behavior than take first. Also, there will always be some implementations that error out. We can’t get them all to do take first.

LL