[Cbor] Handling duplicate map keys

[Jeffrey Yasskin <[e-mail]>]

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