Subject: Re: [COSE] draft-prorock-cose-post-quantum-signatures [Was: Re: Call for COSE Agenda Items for IETF 113 in Vienna]

From: Mike Jones <[email-masked]>
Date: Thu, 10 Mar 2022 01:52:23 +0000

Russ, I can't tell from your brief comment if you're supportive of non-polymorphic or polymorphic algorithm identifiers.  Can you expand on your remarks?

For the record, I also believe the polymorphic algorithm identifiers were a mistake.  OAuth, OpenID Connect, FIDO2, W3C WebAuthn, and I believe other systems, all count on being able to use a single algorithm identifier to fully specify the cryptographic computation.  Polymorphic algorithm identifiers break that invariant.  We should introduce no more of them.

That's why, for instance, https://www.rfc-editor.org/rfc/rfc8812 intentionally introduced the new algorithm identifier "ES256K" for "ECDSA using secp256k1 curve and SHA-256"; it requires the use of "ES256K" for signing with the secp256k1 curve so that a polymorphic algorithm identifier is never used with it.

                           -- Mike (writing as an individual)

From: COSE <[email-masked]> On Behalf Of Russ Housley
Sent: Wednesday, March 9, 2022 2:56 PM
To: Mike Prorock <[email-masked]>
Cc: Ilari Liusvaara <[email-masked]>; [email-masked]; Orie <[email-masked]>; Anders Rundgren <[email-masked]>
Subject: Re: [COSE] draft-prorock-cose-post-quantum-signatures [Was: Re: Call for COSE Agenda Items for IETF 113 in Vienna]

On Mar 8, 2022, at 2:36 PM, Mike Prorock <[email-masked]<mailto:[email-masked]>> wrote:

I believe most people (in retrospect) have rather come to the conclusion that polymorphic algorithms were a mistake.

+1 - that seems to be something that folks are finding out

Where the actual "kty" shakes out as we continue to improve the draft is yet to be seen.  "PQK" made sense at the time as this is dealing with post quantum keys and signatures - just as easily we could be looking at two key types, probably by family - e.g. one for lattice based, and one for hash based signatures, or could just as easily be "OKP" - we opened an issue to track that here:
https://github.com/mesur-io/post-quantum-signatures/issues/48
and will discuss on our next call.

This is exactly why we wanted the broader input from the COSE WG

https://www.rfc-editor.org/rfc/rfc8778.txt

Is there any reason to do things differently for other hash-based signatures?

Russ

---

From: Anders Rundgren <[email-masked]>
Date: Thu, 10 Mar 2022 07:15:01 +0100

Hi Guys,

May I as an implementer also comment on the idea of overloading the OKP identifier?

Actual code for a COSE public key decoder:

     // Throws an exception if there is no KTY label (=key object is completely malformed).
     int coseKty = publicKeyMap.getObject(COSE_KTY_LABEL).getInt();
     KeyTypes keyType = keyTypes.get(coseKty);
     if (keyType == null) {
         throw new GeneralSecurityException("Unrecognized key type: " + coseKty);
     }

I guess that most decoders do something like this since the parameters associated with each "kty" are quite different.

If you OTOH overload OKP, decoders would assume that they are going to process an x25519, x448, ed25519, or ed448 key and convert these to the platform's own representation.  Such code will fail and in a much less predictive way.  BTW, Oracle would never considering extending their existing interfaces for the mentioned algorithms; they would define new ones.   Some people suggested retrofitting the EC interfaces for ed25519 and friends but Oracle turned down this request since existing crypto providers would either have to be upgraded or just crash and that is not overly appealing.  Clean separation is more important than code reuse.  A key decoder/encoder is also a very small piece of code.

This is also a question about adoption. By using different identifiers, software can be upgraded without support by the platform vendors.  It took Oracle 5 years to introduce native support for Ed25519!

Cheers,
Anders

---

From: Mike Prorock <[email-masked]>
Date: Thu, 10 Mar 2022 05:27:18 -0500

Thanks Anders,
This implementation side is exactly why I set kty as a unique value first.
This work started when I was testing an implementation of Dilithium, and
then SPHINCS+ with some of our existing code and I wanted a clean way to
branch down a path to the new libs without adjusting our existing code that
switches on key types.  This was so that we could begin validating our
ability to handle post quantum algorithms once NIST finalizes, based on a
few customer requests.

Mike Prorock
mesur.io

---

From: Orie Steele <[email-masked]>
Date: Thu, 10 Mar 2022 07:57:58 -0600

seems like I should have replied here first... I agree with the comments.

If we think overloading will cause problems we should avoid it.

The problem with switching on key type alone is that there are key types
used for multiple signature algorithms.

I would recommend switching on kty + crv when present... but even then,
secp256k1 supports both ECDSA (ES256K) and Schnorr (unregistered, but I
once proposed SS256K at DIF -
https://github.com/decentralized-identity/SchnorrSecp256k1Signature2019)...
we also have the problem of normalize to lower s in ES256K... we
would probably need a new alg to signal that all ES256K signatures had been
normalized... so there is a future where a single public key
representation might verify many unique signature formats... without the
requirement to signal which one it was "meant for".

Our current approach with dilithium leaves us wishing `alg` were required
in all key formats... it's also a best practice not to use the same key
material for multiple algorithms... alg needs to be present to help
mitigate this, because otherwise any signature that verifies with the key
would be acceptable since the key representation does not signal an
intention.... depending on your perspective on security, you
might think this is a good thing.

All this to say, if you are only looking at `kty` you might have other
issues, at least with certain crv values that are registered today, we
should avoid making this problem worse.

OS

On Thu, Mar 10, 2022 at 4:27 AM Mike Prorock <[email-masked]> wrote:

> Thanks Anders,
> This implementation side is exactly why I set kty as a unique value
> first.  This work started when I was testing an implementation of
> Dilithium, and then SPHINCS+ with some of our existing code and I wanted a
> clean way to branch down a path to the new libs without adjusting our
> existing code that switches on key types.  This was so that we could begin
> validating our ability to handle post quantum algorithms once NIST
> finalizes, based on a few customer requests.
>
> Mike Prorock
> mesur.io
>

-- 
*ORIE STEELE*
Chief Technical Officer
www.transmute.industries

<https://www.transmute.industries>

---

From: Anders Rundgren <[email-masked]>
Date: Thu, 10 Mar 2022 16:56:55 +0100

Hi Orie,

TL;DR

This is my interpretation of how things presumably were intended to work:

Each "kty" represents a family of related key algorithms.

Each signature "alg" represents a specific signature algorithm that is compatible with exactly one "kty" family but not necessarily with all of its members.  For ECDH which is polymorphic things gets a little bit more fuzzy since it involves multiple "kty" families.

Since "kty" is a top-level item you should (IMO...) be free to define within reason :) whatever sub-level items that matches the algorithm specification.  The bottom line is that it must be easy to figure out which specific key- and signature-algorithms that were used, preferably supporting table-driven designs as well.

However, the existing "kty" definitions should (for not breaking existing software) be regarded as frozen even if EC keys indeed can be used both for ECDH and ECDSA (but the use-cases for that are few if any).

If there are strong arguments for not using the same key with multiple signature algorithms (assuming it is actually technically feasible as well), the most robust solution would be to define signature and key algorithms as pairs using the same identifier, but not under the same label since "alg" already is reserved for use in "kty"s.  You could also just say that "alg" in a "kty" is RECOMMENDED.  A problem here is that this scheme does not necessarily work at the crypto API level and then it becomes useless.  If this problem is for real, I would talk to the algorithms designers to get their view on this as well.  This is obviously history in the making :)

Cheers,
Anders

On 2022-03-10 14:57, Orie Steele wrote:
> The problem with switching on key type alone is that there are key types used for multiple signature algorithms.
> 
> I would recommend switching on kty + crv when present... but even then, secp256k1 supports both ECDSA (ES256K) and Schnorr (unregistered, but I once proposed SS256K at DIF - https://github.com/decentralized-identity/SchnorrSecp256k1Signature2019 <https://github.com/decentralized-identity/SchnorrSecp256k1Signature2019>)... we also have the problem of normalize to lower s in ES256K... we would probably need a new alg to signal that all ES256K signatures had been normalized... so there is a future where a single public key representation might verify many unique signature formats... without the requirement to signal which one it was "meant for".
> 
> Our current approach with dilithium leaves us wishing `alg` were required in all key formats... it's also a best practice not to use the same key material for multiple algorithms... alg needs to be present to help mitigate this, because otherwise any signature that verifies with the key would be acceptable since the key representation does not signal an intention.... depending on your perspective on security, you might think this is a good thing.
> 
> All this to say, if you are only looking at `kty` you might have other issues, at least with certain crv values that are registered today, we should avoid making this problem worse.
> 
> OS
> 
> 
> On Thu, Mar 10, 2022 at 4:27 AM Mike Prorock <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     Thanks Anders,
>     This implementation side is exactly why I set kty as a unique value first.  This work started when I was testing an implementation of Dilithium, and then SPHINCS+ with some of our existing code and I wanted a clean way to branch down a path to the new libs without adjusting our existing code that switches on key types.  This was so that we could begin validating our ability to handle post quantum algorithms once NIST finalizes, based on a few customer requests.
> 
>     Mike Prorock
>     mesur.io <http://mesur.io>
> 
> 
> 
> -- 
> *ORIE STEELE*
> Chief Technical Officer
> www.transmute.industries
>

---

From: Mike Prorock <[email-masked]>
Date: Thu, 10 Mar 2022 12:06:29 -0500

Anders,
That read closely matches my interpretation as well, and is part of why i
suggested that we might want one new 'kty' for post quantum, or perhaps two
in this case (breaking things apart by family of algorithms) - 1) for
lattice based algorithms, possibly 'PQL', and 2) for hash based approaches,
perhaps 'PQH'
This way the kty is additionally informational in that we are indicating
that the algorithms are post quantum in nature, and then the specific
family of post quantum approach that is being followed.  This could be very
beneficial with something like SPHINCS+ where then the 'alg' can break out
as required for:
SPHINCS+-SHAKE256-[PARAMETERS]
SPHINCS+-SHA-256-[PARAMETERS]
SPHINCS+-Haraka-[PARAMETERS]

Mike Prorock
CTO, Founder
https://mesur.io/

On Thu, Mar 10, 2022 at 10:56 AM Anders Rundgren <
[email-masked]> wrote:

> Each signature "alg" represents a specific signature algorithm that is
> compatible with exactly one "kty" family but not necessarily with all of
> its members.  For ECDH which is polymorphic things gets a little bit more
> fuzzy since it involves multiple "kty" families.
>
> Since "kty" is a top-level item you should (IMO...) be free to define
> within reason :) whatever sub-level items that matches the algorithm
> specification.  The bottom line is that it must be easy to figure out which
> specific key- and signature-algorithms that were used, preferably
> supporting table-driven designs as well.
>
> However, the existing "kty" definitions should (for not breaking existing
> software) be regarded as frozen even if EC keys indeed can be used both for
> ECDH and ECDSA (but the use-cases for that are few if any).
>
> If there are strong arguments for not using the same key with multiple
> signature algorithms (assuming it is actually technically feasible as
> well), the most robust solution would be to define signature and key
> algorithms as pairs using the same identifier, but not under the same label
> since "alg" already is reserved for use in "kty"s.  You could also just say
> that "alg" in a "kty" is RECOMMENDED.  A problem here is that this scheme
> does not necessarily work at the crypto API level and then it becomes
> useless.  If this problem is for real, I would talk to the algorithms
> designers to get their view on this as well.  This is obviously history in
> the making :)
>
> Cheers,
> Anders
>
>
> https://github.com/decentralized-identity/SchnorrSecp256k1Signature2019 <
> https://github.com/decentralized-identity/SchnorrSecp256k1Signature2019>)...
> > Our current approach with dilithium leaves us wishing `alg` were
> required in all key formats... it's also a best practice not to use the
> same key material for multiple algorithms... alg needs to be present to
> help mitigate this, because otherwise any signature that verifies with the
> key would be acceptable since the key representation does not signal an

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 10 Mar 2022 19:59:49 +0200

> Each "kty" represents a family of related key algorithms.

No, each "kty" represents a key format. Each key format may or may not
have multiple key types.

For example, OKP is the key format with octet string private and public
keys. It explicitly has nothing to more to do with elliptic curves than
that initial key types all happened to be based on elliptic cuves.

> Each signature "alg" represents a specific signature algorithm that
> is compatible with exactly one "kty" family but not necessarily with
> all of its members.  For ECDH which is polymorphic things gets a
> little bit more fuzzy since it involves multiple "kty" families.

Each alg is compatible with key types it is compatible with. That might
include some key types of some key format (happens especially with OKP)
or it might include entiere key formats (happens especially with EC2),
or both at once.

That might turn out to be bit problematic if, e.g., some joker defines
some coordinate-swapped Edwards curve as EC2. Those things work just
fine for ECDH. Attempting to perform ECDSA technically works, but breaks
ECDSA specification.

> specification.  The bottom line is that it must be easy to figure out
> which specific key- and signature-algorithms that were used,
> preferably supporting table-driven designs as well.

It goes the other way around: Once one has a new key type, one goes to
see if it has existing key format, or if one should define a new key
format for it.

> However, the existing "kty" definitions should (for not breaking
> existing software) be regarded as frozen even if EC keys indeed can
> be used both for ECDH and ECDSA (but the use-cases for that are few
> if any).

Not being able to introduce new key types would for example imply that
new elliptic curves can not be added.

> algorithms as pairs using the same identifier, but not under the same
> label since "alg" already is reserved for use in "kty"s.  You could
> also just say that "alg" in a "kty" is RECOMMENDED.  A problem here
> is that this scheme does not necessarily work at the crypto API level
> and then it becomes useless.  If this problem is for real, I would
> talk to the algorithms designers to get their view on this as well. 
> This is obviously history in the making :)

In general,  using the same key with multiple signature algoritihms is
not cryptographically kosher. In fact, RSA-PKCS#1v1.5 is one of the rare
exceptions (it has encoded message level indication of hash algorithm
used).

It depends on algorithm if trying to use mismatching key and algorithm
is guranteed to blow up as implementation is faced trying to do the
impossible (e.g., trying to mismatch dilithium2 and dilithium3),  or if
it is just omittable implementation checks that prevent some
key/algorithm pair from working (e.g. trying to mismatch ES384 and
P-256 curve).

However, there is no "key says what alg this actually is" alg value in
COSE and JOSE. However, in current HTTP signatures work, there is such
value (omitted alg means exactly that).

-Ilari

---

From: Rafael Misoczki <[email-masked]>
Date: Thu, 10 Mar 2022 15:20:43 -0500

I'm not quite familiar with kty's and OKP's yet (sorry, I hope to ramp up
soon) but from a pure crypto perspective, here are my two cents:

History has shown that anytime we left room for ambiguity in terms of the
primitive being used, we saw some sort of downgrade attacks in the wild.
See for example this attack
<https://www.youtube.com/watch?v=CiH6iqjWpt8&t=1428s> where AES-GCM is
replaced by the weaker AES-CBC, thus being exploited as an efficient
padding oracle.

For PQC, things are even trickier because most of them employ several
cryptographic building blocks. The choice for these building blocks has
critical security implications, so I won't consider them "equivalent".  For
example, SPHINCS+ using SHA256 or the more efficient Haraka are secure but
I won't be so sure if some other (second pre-image vulnerable) hash
function is plugged in.

Again, I'm not very familiar with all the nuances for the kty's design but
being as specific as possible may have some security benefits.

On Thu, Mar 10, 2022 at 1:00 PM Ilari Liusvaara <[email-masked]>
wrote:

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 11 Mar 2022 17:51:54 +0200

> being as specific as possible may have some security benefits.

Yes, in general, using one key with multiple algorithms is crypto-
graphically unsound. Safety would have to be evaluated at case-by-case
basis. That is a reason for any cryptographic key material to state what
algorithm it is intended to be used with. However, Taking this to the
logical conclusion would lead to the ultimate algorithm overload.

And I think that any "hash" function that fails 2nd preimage resistance
is utterly worthless (similarly to any key exchange that fails OW-CONF
security). Fortunately that seems to be extremely rare. I think the last
time any "serious" hash function has failed that way was SNEFRU (1990).
However, even just failing collision resistance is a cause for grave
concern.

And with parametrizing asymmetric primitives, some primitives use
parameters like hash functions in public key derivation. So what
public key goes with what private key depends on hash function. And
this might not change lengths of the fields, so it is possible for
an implementation to try use wrong one.

-Ilari