Re: [Cbor] Handling duplicate map keys

[Jeffrey Yasskin <[e-mail]>]

Comments inline:

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

> On Nov 23, 2019, at 1:11 AM, Jeffrey Yasskin <[e-mail]>
> wrote:
>
> On Sat, Nov 23, 2019 at 10:00 AM Laurence Lundblade <[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.

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