Subject: [Cbor] Review: draft-bormann-cbor-packed-00 & SUIT

From: Brendan Moran <[email-masked]>
Date: Tue, 28 Jul 2020 15:24:48 +0000

I think that packed CBOR is a feature that’s very much needed. In fact, there’s a similar feature in SUIT. I’d rather get rid of SUIT’s deduplication system and use packed CBOR instead, but the timing may not work out.

I’d like to reiterate some of things that were said in the discussion during the cbor meeting, and add some additional points.

The current encoding of #6.6([]) is not friendly to stream processing, nor to pull parsers. It is easier for this style of parser to have a dictionary first, followed by the rump. We could arrange to resolve this by replacing the rump in its entirety with a shared object reference, and encoding the actual rump as a shared object. This allows a pull parser to directly jump to the dictionary. If the “rump” is placed as the last shared object, a stream processor can use this abstraction to ensure that the rump is encountered only once the dictionary is received. So, this “concern” may be a no-op and may just require an implementation hint for addressing pull parsers.

SUIT has some peculiar requirements that might be relevant to the design of packed CBOR:

1. SUIT manifests would absolutely benefit from a mechanism to compress CBOR sequences. SUIT’s basic building block is arrays that are effectively multi-maps. Some of these multi-maps contain similar sequences of objects. It would be beneficial to be able to deduplicate the identical parts.

2. SUIT would benefit from nested packed CBOR items. SUIT features elements that can be detached from each other in much the same way as COSE supports detached payloads. A SUIT envelope contains a manifest and zero or more severable (detached) elements. It would be preferable for packing to work like this: any element or sequence that appears at least once in the manifest and two or more times in the union of manifest and severable elements, should be placed in the dictionary for the manifest. Any element or sequence that appears two or more times in a severable element, but not in the manifest, should be placed in the severable element’s dictionary.

I believe that a suit-specific cbor packer could achieve this mechanism if nested packed CBOR data items were supported. SUIT does not appear to require more than a

3. I suspect that SUIT would also benefit from domain-specific pre-shared dictionaries. I’d like to see some way of defining canonical dictionary merging: Are dictionaries concatenated? In which order are they concatenated? How should a domain-specific pre-shared dictionary be included in a signed context? By digest?

Best Regards,
Brendan
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 28 Jul 2020 10:18:51 -0700

From: CBOR <[email-masked]> On Behalf Of Brendan Moran
Sent: Tuesday, July 28, 2020 8:25 AM
To: [email-masked]
Subject: [Cbor] Review: draft-bormann-cbor-packed-00 & SUIT

 

[Brendan] One of the questions that I have is the order of compressing and applying security operations.  If you are using a pull parser do you think it is going to be easier (we can talk about more secure later) to do the hashing on the compressed or uncompressed version.  This could be an even harder question to ask with the use of an external dictionary.  There is one potential benefit w/ COSE in that the hash of the dictionary could be included as external data.

Jim

Best Regards,

Brendan

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 28 Jul 2020 23:13:57 +0200

> On 2020-07-28, at 19:18, Jim Schaad <[email-masked]> wrote:
> 
> [Brendan] One of the questions that I have is the order of compressing and applying security operations.  If you are using a pull parser do you think it is going to be easier (we can talk about more secure later) to do the hashing on the compressed or uncompressed version.  

Whoa.  We normally hash byte strings.
So are you proposing that, say, a compressed version is received, it is uncompressed, re-serialized in deterministic encoding, and then hashed?

> This could be an even harder question to ask with the use of an external dictionary.  There is one potential benefit w/ COSE in that the hash of the dictionary could be included as external data.

There are two aspects here:
— how do we make sure the external dictionary cannot be surreptitiously exchanged by an attacker
— how do we make sure there is an unambiguous way to integrate the external dictionary/-ies into the prefix and sharing tables?

I have a design for the latter that I still need to write up.

For the former, a COSE hash algorithm + the hash would do; the dictionary would be hashed as an encoded CBOR data item.  There is a question whether there should be a way to put in a (compact!) identifier for the dictionary as well, so the hash in the external data isn’t a trapdoor function.

Grüße, Carsten

---

From: Jim Schaad <[email-masked]>
Date: Tue, 28 Jul 2020 16:17:59 -0700

> -----Original Message-----
> From: Carsten Bormann <[email-masked]>
> Sent: Tuesday, July 28, 2020 2:14 PM
> To: Jim Schaad <[email-masked]>
> Cc: Brendan Moran <[email-masked]>; [email-masked]
> Subject: Re: [Cbor] Review: draft-bormann-cbor-packed-00 & SUIT
> 
> 
> > [Brendan] One of the questions that I have is the order of compressing and
> applying security operations.  If you are using a pull parser do you think it is
> going to be easier (we can talk about more secure later) to do the hashing on
> the compressed or uncompressed version.
> 
> So are you proposing that, say, a compressed version is received, it is
> uncompressed, re-serialized in deterministic encoding, and then hashed?

Both yes and no.  I was thinking that the only thing that was going to need to be re-encoded would be prefixes so that strings are fully there and have the correct value.  For doing things like substructure substitution, I was just replacing the tag with that substructure and passing in the data of that substructure as I was doing the decoding.  This has the advantage that an entity can sign a single representation, the uncompressed version and it can later be compressed, with some restrictions around maps, and both versions would verify.  With attention to doing maps, that is you are the both signing and compressing, you could get "optimal" compression while still having a signature that works on both versions.

> 
> > This could be an even harder question to ask with the use of an external
> dictionary.  There is one potential benefit w/ COSE in that the hash of the
> dictionary could be included as external data.
> 
> — how do we make sure the external dictionary cannot be surreptitiously
> exchanged by an attacker — how do we make sure there is an unambiguous
> way to integrate the external dictionary/-ies into the prefix and sharing tables?
> 
> For the former, a COSE hash algorithm + the hash would do; the dictionary
> would be hashed as an encoded CBOR data item.  There is a question whether
> there should be a way to put in a (compact!) identifier for the dictionary as
> well, so the hash in the external data isn’t a trapdoor function.

Part of this includes the question of how you are going to identify the dictionaries so that you get the right one if there are multiple possibilities.  The hash would be something that can be unique but would need to be validated by the decoder.

Jim

---

From: Brendan Moran <[email-masked]>
Date: Wed, 29 Jul 2020 12:37:09 +0000

On 29 Jul 2020, at 00:17, Jim Schaad <[email-masked]<mailto:[email-masked]>> wrote:

-----Original Message-----
From: Carsten Bormann <[email-masked]<mailto:[email-masked]>>
Sent: Tuesday, July 28, 2020 2:14 PM
To: Jim Schaad <[email-masked]<mailto:[email-masked]>>
Cc: Brendan Moran <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Subject: Re: [Cbor] Review: draft-bormann-cbor-packed-00 & SUIT

On 2020-07-28, at 19:18, Jim Schaad <[email-masked]<mailto:[email-masked]>> wrote:

My intent was to verify first, then unpack. This is because the unpacked structure never exists, in its entirety, in memory. If you have to unpack straight into the digest algorithm in order to verify, you introduce a TOCTOU problem. If you verify first, you at least have a static, verified object.

The problem with this approach is dictionary selection. We need some way to hint a dictionary identifier if it’s not obvious. This could be a tag, an element in the Tag 6 array, some kind of OOB signal, or something else.

exchanged by an attacker

This requires some sort of security mechanism. Using a COSE feature that includes additional data is not ideal in SUIT because we support COSE_Sign, COSE_Sign1, COSE_MAC, or COSE_MAC0, or any combination thereof. This would mean that a COSE feature that includes extra data would be duplicated for as many COSE objects as are included. Of course, that’s not particularly relevant if the list of COSE objects is also using packed CBOR, so maybe it’s fine.

Including a dictionary reference as AAD seems fine to me. In the SUIT case, I think I would make it more explicit because we need to identify which external dictionary to digest.

— how do we make sure there is an unambiguous
way to integrate the external dictionary/-ies into the prefix and sharing tables?

We need to (logically) concatenate the dictionaries together. The question is: which order?

From a pull parser perspective, I think I would suggest a stack-based model:
- Each dictionary is an element in a singly linked list.
- When you encounter a new dictionary, you push it onto the head of the list
- When you finish a rump element, you pop the dictionary associated with it from the head of the list.
- When you find a dictionary reference in the rump, you traverse the dictionary list, starting at the most recent.
- When you find a dictionary reference in a dictionary element, you traverse the dictionary list, starting at the current dictionary.

This has several advantages:
- It’s compatible with including a packed CBOR object inside a packed CBOR object without rewriting any references.
- The data model for dictionary traversal is fairly simple

It has several disadvantages:
- References have inconsistent meanings (Tag 6 (1) doesn’t mean the same dictionary entry everywhere. It points to different dictionaries in different places)
- The stack model requires some kind of allocation strategy to keep track of the dictionaries.
- The compressor has to be aware of the dictionaries of packed CBOR objects it traverses in order to pack anything that appears within an already packed CBOR object.

However, this may be naive as well. It implies that there is only a list of dictionaries that applies at any point, rather than a tree. This is probably accurate when looking at nested packed objects. It might be more of a problem with external dictionaries.

The requirement for a hash depends on context. Where it is required, the question is whether it’s explicit or implicit. Now, what’s really interesting here is that it could be packed too. Effectively, what I mean here is that it’s legitimate to use packed CBOR to compress a COSE object. If we use an external dictionary to compress the COSE object, it seems plausible to add in a dictionary value for the hash & hash algorithm used to represent a second, non-COSE external dictionary.

I think that external dictionaries *outside* an authentication object probably don’t require authentication, since the authentication object itself will naturally verify these data. However, any external dictionary represented *inside* an authentication object MUST also be authenticated.

I can provide a worked-up example if that makes it clearer.

Brendan

Jim

Grüße, Carsten

_______________________________________________
CBOR mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/cbor

---

From: Michael Richardson <[email-masked]>
Date: Wed, 29 Jul 2020 13:53:36 -0400

{please note that this converation is incomprehensible unless you render the
HTML, so the archives are be useless. I feel that this thread should be in
the SUIT WG too, but I won't CC because catching up will be hard}

Brendan Moran <[email-masked]> wrote:
    > My intent was to verify first, then unpack. This is because the
    > unpacked structure never exists, in its entirety, in memory. If you
    > have to unpack straight into the digest algorithm in order to verify,
    > you introduce a TOCTOU problem. If you verify first, you at least have
    > a static, verified object.

I agree.  I would write the encoder "sign the packed structure"
(so decoder we verify first, then unpack...)

I like this because it means:
a) a third party can verify the signature without having the dictionaries.
   Clearly it can't audit the contents without the external dictionar(y/ies).

b) at this point in the specification I'm unclear if multiple passes of the
   unpacked content is required.  But, if we did want to permit such
   self-referential things, the decoder could wind up decoding infinite
   things.  Such a thing ight be a desireable feature!
   We could accomodate such a thing if with sign the packed structure,
   because the decoder would know it's authentic before it tried to
   expand.

    > dictionary could be included as external data.

i.e. it could go into the protected bucket.

    > The problem with this approach is dictionary selection. We need some
    > way to hint a dictionary identifier if it’s not obvious. This could be
    > a tag, an element in the Tag 6 array, some kind of OOB signal, or
    > something else.

I think it needs to be in the tag 6 array.

    cabo> There are two aspects here:
    cabo> — how do we make sure the external dictionary cannot be surreptitiously
    cabo> exchanged by an attacker

    > This requires some sort of security mechanism. Using a COSE feature
    > that includes additional data is not ideal in SUIT because we support
    > COSE_Sign, COSE_Sign1, COSE_MAC, or COSE_MAC0, or any combination
    > thereof. This would mean that a COSE feature that includes extra data
    > would be duplicated for as many COSE objects as are included. Of
    > course, that’s not particularly relevant if the list of COSE objects is
    > also using packed CBOR, so maybe it’s fine.

    > Including a dictionary reference as AAD seems fine to me. In the SUIT
    > case, I think I would make it more explicit because we need to identify
    > which external dictionary to digest.

    cabo> — how do we make sure there is an unambiguous
    cabo> way to integrate the external dictionary/-ies into the prefix and sharing tables?

    > - When you find a dictionary reference in the rump, you traverse the
    > dictionary list, starting at the most recent.

    > - When you find a dictionary reference in a dictionary element, you
    > traverse the dictionary list, starting at the current dictionary.

Implying that dictionaries can be created that are self-referential, and can
blow up to infinite data streams :-)

Unless you mean that dictionaries should be sorted so that they always (can only)
reference forward, and you can start at the current location in the current
dictionary.

    > - It’s compatible with including a packed CBOR object inside a packed
    > CBOR object without rewriting any references.

I agree.

    > - References have inconsistent meanings (Tag 6 (1) doesn’t mean the
    > same dictionary entry everywhere. It points to different dictionaries
    > in different places)

    > track of the dictionaries.

It's a stack of pointers.  It can point at the in-band dictionary which can
be processed by a pull-parser.  Or at an out-of-band dictionary which is
probably in "ROM" in some convenient format (probably CBOR map)

    > - The compressor has to be aware of the dictionaries of packed CBOR
    > objects it traverses in order to pack anything that appears within an
    > already packed CBOR object.

In the SUIT case, the compressor is "cloud" :-)

    > However, this may be naive as well. It implies that there is only a
    > list of dictionaries that applies at any point, rather than a
    > tree. This is probably accurate when looking at nested packed
    > objects. It might be more of a problem with external dictionaries.

    > I think that external dictionaries *outside* an authentication object
    > probably don’t require authentication, since the authentication object
    > itself will naturally verify these data. However, any external
    > dictionary represented *inside* an authentication object MUST also be
    > authenticated.

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

---

From: Brendan Moran <[email-masked]>
Date: Wed, 29 Jul 2020 22:45:45 +0000

> On 29 Jul 2020, at 18:53, Michael Richardson <[email-masked]> wrote:
>
>

The original specification prohibits loops, but leaves the implementation up to the reader.

> I think it needs to be in the tag 6 array.

Possibly, but this opens the question of where it goes. Maybe it needs to be explicitly included. Suppose that we use a special case:

Tag 6([rump, Tag 6(dictionary-id)]).

The context of the second Tag 6 (normally, there would be an array there) makes it clear that this is an external reference dictionary. We could specify a reference digest in the tag as well:

Tag 6([rump, Tag 6([digest-alg, digest-bytes, dictionary-id])])

I’m not sure this is the right approach, but I like that it keeps Tag 6 information in Tag 6

> blow up to infinite data streams :-)

As above, the original specification prohibits loops, but leaves the implementation up to the reader.

> reference forward, and you can start at the current location in the current

Possibly, but I’m not sure that’s universally advantageous. Remember that we want high reference frequency items to be at the start. Suppose that I have the prefixes [“https://“, “www.”, “files.”, “domain.com”]. Clearly, I want to be able to compose these in one of two ways:

https://www.domain.com
https://files.domain.com

Only these two prefixes will appear in my object, the others will not, which renders their compression less important. I would expect something like:

[[Tag 225(simple(0)), Tag 226(simple(0), Tag 227(“www.”), Tag 227(“files”), “https://“], “domain.com"]

Note that the sorting is the opposite of what’s implied.

But what if “https://" is used extensively? Then we need to change our sort order so that it can be referenced with Tag 6().

I think we need to be very clear about what’s allowed because otherwise, there will be a lot of varied implementations with varied limitations.

> probably in "ROM" in some convenient format (probably CBOR map)

Indeed. Not too bad, I think.

> In the SUIT case, the compressor is "cloud" :-)

Yup. Let’s not make things hard for constrained nodes because it’s easier for unconstrained ones.