Subject: [COSE] Issue #51 - make "alg" field optional

From: "Jim Schaad" <[email-masked]>
Date: Wed, 3 Feb 2016 22:13:44 -0800

I have been trying to figure out a way forward on this issue that will make
all parties happy and I have not been successful.  I am therefore going to
open this up for discussion to see if it is possible as a group to come up
with a solution that will appeal to everybody.  I doubt that it is going to
be doable.

The request in the issue is to relax the current restriction where the alg
MUST be present in each message oriented object defined by COSE.  There is
current a requirement that the item be present and that, if possible, it
MUST be in the protected bucket of header items.  

This requirement is supported in several different security consideration by
discussions that the algorithm identifier needs to be included as part of
the authenticated data in order to protect against algorithm substation
attacks.  Different types of attacks that have been envisioned  that arise
from changing the hash of signatures (see discussion on the CFRG mailing
list), shorting the tag of an AEAD algorithm, and attacks changing the RSA
algorithm used from PSS or OAEP to v1.5. The first and third attacks have
been demonstrated or seen in the real world.  The middle case is, in my
mind, an extension of the current attacks where CBC tag checking is done
poorly and frequently allows for changes in encrypted text to be made.
(Currently CBC will correctly decrypt a little bit more often than 1 in 256
times with a modified text.)

I have discussed this with the OSCoAP document
(https://datatracker.ietf.org/doc/draft-selander-ace-object-security)
writers and have suggested that the proper location to change this from a
MUST to a don't do this is in their document and that it be accompanied with
an appropriate external data structure that would include this field as part
of the authenticated data.   This would satisfy my very strong desire for
the item always be authenticated when possible, with the strong desire on
their part to not include the field in the structures that they are looking
at.  From my point of view, it also restricts the places where this would be
done to the subset of structures that they are using and would allow them to
address the fact that they requirements may be different, for example, when
looking at and Enveloped structures as oppose to an Encrypted structure.
The former may require the algorithm be present while the latter might not.

One of the main problems that I have with doing a general relaxation, even
with the type of text that is suggested in the issue, is that this does not
make the application explicitly define what the external data structure will
look like in the event it decides to omit the algorithm based on common use
rather than based on the specification itself.  Forcing this to be done by
the application specification makes this be a problem of the application and
it would be up to it to define the necessary external data structure at the
same time as it relaxes the requirement on the algorithm being present.

I am willing to add an appendix to discuss what an application needs to do
in order to have this relaxation, but strongly do not want to place this
change in the core text.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 4 Feb 2016 14:06:02 +0200

> MUST be in the protected bucket of header items.  

Thinking what I would think is proper, I would associate the algorithm
with the key. Either external key, or contained in protected members of
enveloped key.

Even putting the algorithm in protected members of the object itself
would not protect against all substitution attacks (I think Ed25519 vs.
Ed25519ph substitution for instance).

In any case, repeating already implicitly known algorithm is good source
of security bugs...

I haven't thought how much trouble that kind of architecture would cause
in COSE...

-Ilari

---

From: Mike Jones <[email-masked]>
Date: Thu, 4 Feb 2016 18:55:01 +0000

I am against making inclusion of the algorithm optional. Among other reasons, doing so would make support for crypto agility more problematic.

-- Mike
________________________________
From: Jim Schaad<mailto:[email-masked]>
Sent: ‎2/‎3/‎2016 10:16 PM
To: [email-masked]<mailto:[email-masked]>
Subject: [COSE] Issue #51 - make "alg" field optional

Jim

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

---

From: "Jim Schaad" <[email-masked]>
Date: Sat, 6 Feb 2016 18:28:24 -0800

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Thursday, February 04, 2016 4:06 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [COSE] Issue #51 - make "alg" field optional
> 
> > I have been trying to figure out a way forward on this issue that will
> > make all parties happy and I have not been successful.  I am therefore
> > going to open this up for discussion to see if it is possible as a
> > group to come up with a solution that will appeal to everybody.  I
> > doubt that it is going to be doable.
> >
> > The request in the issue is to relax the current restriction where the
> > alg MUST be present in each message oriented object defined by COSE.
> > There is current a requirement that the item be present and that, if
> > possible, it MUST be in the protected bucket of header items.
> 
> Thinking what I would think is proper, I would associate the algorithm with the
> key. Either external key, or contained in protected members of enveloped key.

For external keys, the current document follows the lead of JOSE and doesn’t require an algorithm identifier to be passed with keys.  This would be necessary for COSE in order to make an association of an algorithm and a key to exist.  I would also expect that there would need to be some language about binding one and only one algorithm to a key.

We do not have an ability to do something different than what we currently do for cases where a key is distributed in a message.  However, it is probably considered to be acceptable.

> 
> Even putting the algorithm in protected members of the object itself would not
> protect against all substitution attacks (I think Ed25519 vs.

I don't agree with this statement.  If the algorithm identifier is part of the string that is being signed and the application uses that identifier to determine what algorithm is being used to evaluate the validity of the signature, an attacker that changes the algorithm in the signed string would result in an invalid signature being received by the evaluation system.  This is, IMHO, the crux of preventing an algorithm substitution attack.  The ability to determine that the algorithm I use and the algorithm you use are the same.  (If you lie about it and sign the wrong algorithm identifier then that would be an undetectable error.)

In terms of Ed25519 and #d25519pH, I consider the fact that these are two different algorithms to be a distinction without a difference.  One can use the same software code to process these two different signatures and one will both produce and validate the same set of signatures.  It is really hard for me to therefore say that the signature algorithms are distinct.  What is distinct is how they are thought about for doing security proofs and how they would be implemented in an API sense.  

> 
> In any case, repeating already implicitly known algorithm is good source of
> security bugs...

I don't think that I would agree with this statement.  Making explicit what is implicit should not be an error unless you believe that people will like about what the algorithm is and refuse to fail if the explicit and implicit algorithm are different.

Jim

> 
> I haven't thought how much trouble that kind of architecture would cause in
> COSE...
> 
> 
> -Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 7 Feb 2016 15:07:54 +0200

On Sat, Feb 06, 2016 at 06:28:24PM -0800, Jim Schaad wrote:
> I don't agree with this statement.  If the algorithm identifier is
> part of the string that is being signed and the application uses that
> identifier to determine what algorithm is being used to evaluate the
> validity of the signature, an attacker that changes the algorithm in
> the signed string would result in an invalid signature being received
> by the evaluation system.

Get signature that is valid for both Ed25519 and Ed25519ph, including
the algorithm indications. The complexity of doing this is WAY below
breaking the curve or the hash.

> What is distinct is how they
> are thought about for doing security proofs and how they would be
> implemented in an API sense.  

The API for both should be the same. IMO, the sole reason Ed25519ph
exists is that some want to use bad legacy APIs in "exciting" way.

Actually, I should remove it from JOSE draft. My advice about it:
Don't use.

> > 
> > In any case, repeating already implicitly known algorithm is
> > good source of security bugs...
> 
> I don't think that I would agree with this statement.  Making
> explicit what is implicit should not be an error unless you
> believe that people will like about what the algorithm is and
> refuse to fail if the explicit and implicit algorithm are different.

Well, repeating information in multiple places is _legendary_
source of bugs all around, and when you got a security protocol,
some of those bugs become security bugs.

-Ilari

---

From: "Jim Schaad" <[email-masked]>
Date: Sun, 7 Feb 2016 16:33:17 -0800

> Sent: Sunday, February 07, 2016 5:08 AM
> Get signature that is valid for both Ed25519 and Ed25519ph, including the
> algorithm indications. The complexity of doing this is WAY below breaking the
> curve or the hash.

If this is a true statement, then you should be strenuously objecting to having the IRTF publish this pair of algorithms.  This says that these algorithms are so close to each other than having both is a severe problem that cannot be overcome.

While I understand that Ed25519(SHA512(M)) === Ed25519ph(M), Changing a byte in M, which is what would be required to change the algorithm indicator, is the same as needing to break the hash.  Could you layout what you think the attack is where this would not be the case?  (Does it need to be done on CFRG instead?) 

> The API for both should be the same. IMO, the sole reason Ed25519ph exists is
> that some want to use bad legacy APIs in "exciting" way.
> 

I would be happy with this change.

> 
> > >
> > > In any case, repeating already implicitly known algorithm is good
> > > source of security bugs...
> >
> > I don't think that I would agree with this statement.  Making explicit
> > what is implicit should not be an error unless you believe that people
> > will like about what the algorithm is and refuse to fail if the
> > explicit and implicit algorithm are different.
> 
> Well, repeating information in multiple places is _legendary_ source of bugs all
> around, and when you got a security protocol, some of those bugs become
> security bugs.

I hear what you are saying.  In this case I do not agree since I do not believe that the implicit algorithm is going to be generically there. 

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 8 Feb 2016 09:11:38 +0200

On Sun, Feb 07, 2016 at 04:33:17PM -0800, Jim Schaad wrote:
> If this is a true statement, then you should be strenuously objecting
> to having the IRTF publish this pair of algorithms.  This says that
> these algorithms are so close to each other than having both is a
> severe problem that cannot be overcome.

There actually is some stuff about this in security considerations.
Maybe it isn't clear enough.

> While I understand that Ed25519(SHA512(M)) === Ed25519ph(M),
> Changing a byte in M, which is what would be required to change
> the algorithm indicator, is the same as needing to break the hash.

Actually, for COSE case, it isn't even close to breaking the hash,
but however due to sig_struct internal structure, it actually seems
be close to breaking the curve.

To see example of where things go badly wrong, consider the following
signature format:

1 byte: 01=>Ed25519, 02=>Ed25519ph
levarint: Length of signed data.
octets: signed data

Then try message "ABCDEFGHJ71610" with Ed25519 to see things going
south.

-Ilari