Re: [Cbor] Handling duplicate map keys

[Jim Schaad <[e-mail]>]

 

 

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

 

Comments inline:

 

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

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

 

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

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.

 

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. 

 

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

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

 

[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

 

 

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