Subject: [Cose] Issue: Use arrays for some containers

From: "Jim Schaad" <[email-masked]>
Date: Tue, 21 Apr 2015 20:33:10 -0700

Questions:

1.  Should we use arrays or maps as top level containers for COSE?

2.  If we use arrays, should we always use nil elements to indicate absent
elements or use them only when ambiguity in parsing arises?

Discussion:

The first issue that I would like to look at is the question of using arrays
rather than maps at the top level.  For the purposes of this discussion, I
would like to assume that we are going to use integer as well as text keys
for maps where they occur.  I would also like to postpone the discussion of
using an integer vs a tag to identify the top level structures. 

There are some of the maps in the current JOSE specification which could be
changed to maps.  Not all of them can be changed, for example the protected
and unprotected header fields, since the contents in those cases will be
extremely fluid.  This works only for those structures which are both highly
predictable and unlikely to change in the future.

When I initially made the change from maps to arrays in my document, I was
assuming that there would be a significant space savings by doing so.  When
using integer values for the key of a map this expected space saving has not
been born out in practice.  This is, in part, due to a decision that I made
to put filler elements into the array to make the coding simpler.  There
would be no code to try and make a decision if elements are absent as to
what the next item would be.  For maps, this leads to an overhead of one
byte for all elements that are present in the map.  For arrays, this leads
to an overhead of one byte for all elements that are 'absent' in the array.

There is one argument that can be used against the use of arrays, that is
that one would be unable at a later date to easily add a new element to the
end of the array and expect people to process it.   This argument is only
true if the flattened version of the structures is kept.  If only the
arrayed version of signers and recipients is permitted then elements could
be added to the end of the array.  I am currently unable to come up with
something that I believe it would be reasonable to every want to add to a
top level structure that could not be better dealt with by adding it to the
set of protected and unprotected headers instead  In CMS the only time we
found we wanted to modify the top level structures it was when we were doing
the completely new paradigm of changing from EncryptedMessage to use
authenticated encryption algorithms.  This was dealt with by adding a
completely new structure rather than trying to modify the existing one.

The remaining argument for changing from maps to arrays is a question of
code implementations.  I believe, and it is mostly a belief, that the code
to evaluate the structures will be smaller when indexing arrays as opposed
to doing a map look up.  There is no significant change in the CBOR library
that would be needed.  The grammar will have both arrays and maps in it no
matter what decision is made on this topic. 

I made the decision in my document to use a nil filler when an array element
is absent.  It would, in theory, be possible to have the field omitted
entirely.  The issue that needs to be addressed for doing this is to make
sure that one does not end up with a sequence of values where it is not
possible to easily determine which of the optional elements is (or is not)
next.  Thus a grammar where you have an optional integer followed by an
integer can make parsing harder.  With some clever re-arranging of the
fields in the array along with occasional tagging or forced nil values it
should be possible to have omitted absent elements rather than always having
nil values for absent elements.  Doing this would likely lose the size gains
of code size, but potentially shrink the message size by a few extra bytes
in many cases. 

As an example, the current grammar for COSE_mac in my document is

COSE_mac = (

   protected : (bstr / nil),

   unprotected : (header_map / nil),

   payload : bstr,

   tag : bstr,

   ?recipients : ([+COSE_encrypt_a] / nil)

   ? COSE_encrypt

)

One of protected and unprotect would be required - so the nil on protected
could be removed as it would be followed by either a map or a bstr.  The nil
for unprotected could be removed as it would always be followed by a bstr.
Things are slightly more difficult if one wants to make the payload optional
as you have an optional bstr followed by a bstr.  This is a location where
the nil value would be required.  The optional nil on the recipients could
be removed as the count of elements in the group could be used to determine
if it is present.  Thus the group (removing flattening) could potentially be
encoded as

COSE_mac = (

   ? protected: bstr,

   ? unprotected: header_map,

   payload: (bstr / nil),

  tag: bstr,

   recipients: [+COSE_encrypt_a]

)

With only a single required nil value.

Jim

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 22 Apr 2015 07:08:08 -0700

On Apr 21, 2015, at 8:33 PM, Jim Schaad <[email-masked]> wrote:
> 2.  If we use arrays, should we always use nil elements to indicate absent elements or use them only when ambiguity in parsing arises?

1) Maps

2) But, if we do arrays, use null elements so that a decoder always gets the same number of elements.

For #1, unless every structure everywhere is an array, the encoder and decoder will need map interpretation. Given that, and given that maps have become a more natural way for programmers to think of bundles of information, choosing maps seems more likely to make COSE understandable. The programming cost is very low, and if using integers for the keys, the wire-size cost is also trivial.

--Paul Hoffman

---

From: ⌘ Matt Miller <[email-masked]>
Date: Wed, 22 Apr 2015 08:36:02 -0600

> 1.  Should we use arrays or maps as top level containers for COSE?

I would prefer maps.  Since the space savings of arrays are
negligible, I'd rather have a model that lets me completely omit
things if I can.  As Paul said, COSE implementations will need to
support maps and arrays for other parts of the structure, so there's
no code savings in using arrays over maps.

> 
> 2.  If we use arrays, should we always use nil elements to
> indicate absent elements or use them only when ambiguity in parsing
> arises?
> 
> 

If arrays are used, then absent elements MUST be null.

- -- 
- - m&m

Matt Miller < [email-masked] >
Cisco Systems, Inc.

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 22 Apr 2015 17:38:06 +0200

So let’s recap the criteria here:
— representation size:  that’s generally a wash (Jim had a nice slide in Dallas), with a little benefit for arrays in a densely populated place and maps in more sparsely populated structures;
— extensibility: Maps are obviously way more extensible. Arrays make sense mostly where extensibility is hard to imagine (and not just as proof by lack of imagination) or where there is another place that can take that extension (e.g., unprotected headers);
— coding effort/size: a wash for higher level language environments (Java+). Arrays are nice for C-level programming in that the sequence in which you get the data is pre-determined, so there are no bugs caused by varying processing order or such.

Personally, I see some benefit for using arrays for small sets of data that mostly are present and come in well-defined sets (e.g., the top-level structures for sign, mac, encrypt, and maybe the equivalent embedded signature and encrypt structures).

Completely eliding absent array elements is likely to be brittle.  (There may be no need to make header maps absent, by the way, as an empty map is equivalent; an empty array also is a great representation of an empty recipient or signature set..)

In the end, we are trying to make the representation compact enough that bespoke formats (such as the one proposed as a strawman in Appendix C of draft-selander-ace-object-security-01) are no longer attractive.  (I’m not saying that that format would work or that its size must be matched exactly, but it’s an example of what people will come up with if we do COSE wrong.)

Grüße, Carsten

On 22 Apr 2015 at 16:38:07, ⌘ Matt Miller ([email-masked]) wrote:

- --  
- - m&m  

_______________________________________________  
Cose mailing list  
[email-masked]  
https://www.ietf.org/mailman/listinfo/cose

---

From: Derek Atkins <[email-masked]>
Date: Wed, 22 Apr 2015 12:13:41 -0400

Paul Hoffman <[email-masked]> writes:

>> 2.  If we use arrays, should we always use nil elements to indicate
>> absent elements or use them only when ambiguity in parsing arises?
>
> 1) Maps
>
> For #1, unless every structure everywhere is an array, the encoder and
> decoder will need map interpretation. Given that, and given that maps
> have become a more natural way for programmers to think of bundles of
> information, choosing maps seems more likely to make COSE
> understandable. The programming cost is very low, and if using
> integers for the keys, the wire-size cost is also trivial.

I agree with this.

I believe it would be less code to use maps.

I don't see the savings of using arrays; it doesn't really seem to
reduce space significantly, and it might add complexity.

> --Paul Hoffman

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: "Jim Schaad" <[email-masked]>
Date: Wed, 22 Apr 2015 11:51:44 -0700

> -----Original Message-----
> From: Cose [mailto:[email-masked]] On Behalf Of Derek Atkins
> Sent: Wednesday, April 22, 2015 9:14 AM
> To: Paul Hoffman
> Cc: cose
> Subject: Re: [Cose] Issue: Use arrays for some containers
> 

OK - I am open to novel ways to write code and would love to see something
more efficient that the algorithms that I would instinctively use.

For Arrays:

If (array.count < n) produce an error
If (array[0].type == type.bstr) then process this element
Else  if (array[0].type != type.nil) then produce an error.

For maps with loose enforcement:

Obj = map[key_name];
If (obj.type == type.bstr) then process this element
Else produce an error

For maps with strict enforcement:

Foreach (item in map)
   If (item.key.type != int) then ignore item
   Switch (item.key.value)
       Case "key_name":
          If (item.value.type != type.bstr) then produce an error
          Process element
          Break;

All of these look to me to be about the same size in terms of code.

Notice that I have included both a strict and a loose enforcement in my
examples.  These correspond to either saying that no elements other than the
defined set are present or any elements which I don't know are ignored.
JOSE is defined as using a loose enforcement.

I don't know which of the two enforcement models COSE should document if
maps are used.  If arrays are used then it is strict by default.  One
possibility is that we document both enforcement modes and allow
applications to decide.  My question on this has always been what are the
security implications of allowing for random elements to be included in the
structure which will never be processed by an app and are there any benefits
to having the random elements here rather than in the unprotected attribute
map.

Allowing for loose enforcement gives a possible upgrade path, one could put
in both a "signatures" and a "signatures2" item in the map and allow the
recipient to deal with the ones they can deal with.  Having both in the same
message would make me cringe in the world of IoT since that is possible just
making messages larger.  I am also not sure that I think this is a good way
to do versioning, a better way may be to update the structure type marker
instead and just have a new object if extensions to the base object are
really needed.

If this really does get rolled into the IoT world, then we are going to have
to live with the initial version being around for a long time based on the
lifespan of IoT hardware.   For the most part, I don't know how easy
firmware updates are going to be.

Jim

> 
> I don't see the savings of using arrays; it doesn't really seem to reduce
space
> significantly, and it might add complexity.
> 
> > --Paul Hoffman
> 
> -derek
> --

---

From: Derek Atkins <[email-masked]>
Date: Thu, 23 Apr 2015 10:57:47 -0400

> more efficient that the algorithms that I would instinctively use.

Okay, let me recind my statement here -- the formats do already use
Arrays in other contexts, so we wouldn't save code by being able to
elide all array-parsing code.

-derek

---

From: "Jim Schaad" <[email-masked]>
Date: Fri, 24 Apr 2015 18:24:00 -0700

Questions:

Arrays

Always have a field

**************************************

At this point, the majority of people who have expressed an opinion have
said that they prefer to use maps than arrays.  I have not yet seen an
argument that I could call a technical one rather than an 'emotional' one.
People are expressing a preference rather than an argument on what the
correct option is.  This applies to me as well.

After taking a long walk, I think I now understand why I prefer arrays to
maps.  I generally prefer to restrict the set of locations where arbitrary
things can be placed that might affect the security of the system.  By
allowing things in fewer places there are fewer ways that things can go
wrong.  This is not to say that things will go wrong, it is just expressing
a comfort level on my part.

On Wed I sent a message to the list and Derek, in which I outlined a policy
of either doing a strict or a lax enforcement of the fields in a map when
doing an evaluation.  I would appreciate it if people who think maps are
better can respond to this.

My personal preference is that if we do use maps, we all for applications to
specify if they want t use a strict or lax mode and would prefer that the
default is strict mode. 

Jim

---

From: Samuel Erdtman <[email-masked]>
Date: Sat, 25 Apr 2015 15:51:50 +0200

I initially felt strongly for using maps and not arrays, I think that was
mostly since it is so convenient in JavaScript but as keys in the map are
changed from string to integers some of the readability and simplicity
falls away. Initially I also thought that adding new element in an array
would be harder but I guess it would be more or less the same if I have a
map where I don´t address all elements compared to an array where I don´t
read the end.

With that said I´m still slightly more in favor of maps and if using arrays
I´m strongly in favor of having null for absent values. To me it seems
unnecessarily complex to analyse the type of an object based on previous
object.

Another reflection, for this protocol to get adoption implementors needs to
feel that it would be simple to use, and since my first reaction was to
intuitively prefer maps I think that using maps would benefit adoption.

Best Regards
//Samuel

---

From: Derek Atkins <[email-masked]>
Date: Mon, 27 Apr 2015 10:04:58 -0400

Samuel,

Samuel Erdtman <[email-masked]> writes:

> changed from string to integers some of the readability and simplicity falls
> away. Initially I also thought that adding new element in an array would be
> harder but I guess it would be more or less the same if I have a map where I
> don´t address all elements compared to an array where I don´t read the end.

Do you mean (User) Presentation Layer readability?  Or on-the-wire
readability?  Yes, the latter is definitely different with the
conversion to integers, but the former does not necessarily disappear.
The parser could have the mapping from string -> integer and be able to
"present" the strings to the user.

-derek

---

From: Samuel Erdtman <[email-masked]>
Date: Tue, 28 Apr 2015 06:45:11 +0200

Derek

see inline

On Mon, Apr 27, 2015 at 4:04 PM, Derek Atkins <[email-masked]> wrote:

> falls

Don´t think that I had thought about it in that detail. I completely agree
with you that it is possible to put a presentation layer on top of both
these scenario (map and array) so that one would see strings/labels when
writing code or looking at the bytes in wireshark (or similar), however
there will always be the case when you don´t have the tools available and
in those cases readability will be slightly easier with maps IMHO.

> absent
> >     My personal preference is that if we do use maps, we all for
> applications
> >     to

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 28 Apr 2015 06:40:11 -0700

From: Cose [mailto:[email-masked]] On Behalf Of Samuel Erdtman
Sent: Monday, April 27, 2015 9:45 PM
To: Derek Atkins
Cc: Jim Schaad; cose
Subject: Re: [Cose] Issue: Use arrays for some containers

Derek

see inline

Samuel,

 

Don´t think that I had thought about it in that detail. I completely agree with you that it is possible to put a presentation layer on top of both these scenario (map and array) so that one would see strings/labels when writing code or looking at the bytes in wireshark (or similar), however there will always be the case when you don´t have the tools available and in those cases readability will be slightly easier with maps IMHO.

I think that you are going to be disappointed in terms of readability.  Remember that we are using integer key names for the most part so you are not going to get any useful hints.  You are going to see something like

{ 1:{2:3, 4:h’xXXXXXXXXX’}, 5:h’XXXXXXXXXXXX’, 6:[{7:h’XXXXXX’}]}

I don’t think that this is going to make life any easier if you don’t remember what all of the indexes are vs where things are in an array.

Jim

-derek

---

From: Derek Atkins <[email-masked]>
Date: Tue, 28 Apr 2015 11:26:36 -0400

"Jim Schaad" <[email-masked]> writes:

> I think that you are going to be disappointed in terms of readability. 
> Remember that we are using integer key names for the most part so you are not
> going to get any useful hints.  You are going to see something like
>
> I don’t think that this is going to make life any easier if you don’t remember
> what all of the indexes are vs where things are in an array.

Sure, the "on the wire" format would absolutely be integers.  Howeve I
can certainly see a translator (e.g. wireshark) that would provide a
"presentation" of strings by translating the "known integer tags" back
to their string "representations" by using the registry values:

 { foo:{bar:baz, quux:h’xXXXXXXXXX’}, biz:h’XXXXXXXXXXXX’, buz:[{boz:h’XXXXXX’}]}

-derek

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 28 Apr 2015 13:40:19 -0700

> From: Derek Atkins [mailto:[email-masked]]
> Sent: Tuesday, April 28, 2015 8:27 AM
> To: Jim Schaad
> Cc: 'Samuel Erdtman'; 'Derek Atkins'; 'cose'
> > Remember that we are using integer key names for the most part so you
> > are not going to get any useful hints.  You are going to see something
> > like
> >
> > I don’t think that this is going to make life any easier if you don’t
> > remember what all of the indexes are vs where things are in an array.
> 
> Sure, the "on the wire" format would absolutely be integers.  Howeve I can
> certainly see a translator (e.g. wireshark) that would provide a "presentation"
> of strings by translating the "known integer tags" back to their string
> "representations" by using the registry values:
> 

Sure - but at that point the difference between array and map is marginal.  On can decorate the array just as easily as one decorates the map.

Jim

---

From: Derek Atkins <[email-masked]>
Date: Wed, 29 Apr 2015 10:30:24 -0400

[snip]
> Sure - but at that point the difference between array and map is
> marginal.  On can decorate the array just as easily as one decorates
> the map.

Probably true; I feel that maps map easier to the decoration, but I've
never implemented it so couldn't tell you how much more work it would be
to decorate an array.

-derek

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 29 Apr 2015 17:09:04 +0200

> never implemented it so couldn't tell you how much more work it would be

Actually, we thought about this a bit when designing CDDL:
That's why you can give a name to array members.
A CDDL-based pretty-printer could use that information to print even
prettier.

I probably should mention that I'm a bit uneasy about the current
thread.  Applying hard-earned design taste is good.  However, there are
cold hard numbers to look at, as well.  Jim has generated some of them.
 I'd sure like to see numbers for applications such as
draft-selander-ace-object-security that contrast the choices here.  (As
I said, my hunch is that arrays are right for the outer structure, but
numbers! numbers!)  We are doing this for the people who truncate the
CCM authenticator from 16 to 8 bytes because they can't afford more...

Grüße, Carsten

---

From: Derek Atkins <[email-masked]>
Date: Thu, 30 Apr 2015 10:53:58 -0400

Hi,

Carsten Bormann <[email-masked]> writes:

>        However, there are

I agree, I'd like to see more numbers.  From what Jim presented in
Dallas I didn't see any significant gains from one choice over the
other.  Maybe I misinterpreted?

In my use case it's going to be a Digital Signature object that matters
most to me.

-derek