Re: [jose] [COSE] COSE and JOSE Keys for Kyber

[Ilari Liusvaara <[e-mail]>]

On Mon, Nov 14, 2022 at 09:21:28AM -0600, Orie Steele wrote:
> Thanks! Responses inline:
> 
> On Mon, Nov 14, 2022 at 5:47 AM Ilari Liusvaara <[e-mail]>
> wrote:
> 
> > On Sun, Nov 13, 2022 at 03:00:06PM -0600, Orie Steele wrote:
> > >
> > > Mike O. and I have been discussing the need to represent Kyber keys in
> > > JOSE and COSE, especially as we prepare to consider their use with
> > > HPKE.
> >
> > You do not need this for HPKE. Use the generic HPKE key representation
> > instead.
> >
> >
> Consider: https://github.com/dajiaji/hpke-js#base-mode
> 
> Especially this part:
> 
> const recipient = await suite.createRecipientContext({
>   recipientKey: rkp.privateKey, // rkp (CryptoKeyPair) is also
> acceptable.... here we might expect a COSE Key or JWK for Kyber.
>   enc: sender.enc, // this is opaque.
> });

In latest proposals for COSE-HPKE, there has been focus on reusing HPKE
registeries in order to not have to maintain duplicates. This requires
having generic key representation.

 
> > And being CFRG product, I doubt initial version will have pure Kyber
> > (instead being hybridized). And after Kyber is standardized, there might
> > be Kyber1024 (being part of CNSA 2.0) but no others.
> >
> > > Mike P. and I have previously shared a draft for presenting Dilithium,
> > > Falcon and Sphincs -
> > >
> > https://datatracker.ietf.org/doc/draft-ietf-cose-post-quantum-signatures/
> >
> > The kty assignments in that draft actually are problematic here, as both
> > Dilithium and Kyber are based on (M)LWE, but the keys are very much
> > incompatible.
> >
> >
> P-256 and P-384 are both kty:EC and not compatible...
> Ed25519 and Bls12381 are both kty: OKP and not compatible... What is your
> point?

One can do the same things with P-256 and P-384. And OKP is already a
grab bag of keys with the same keyshape (e.g., X25519 versus Ed25519).

However, in Dilithium versus Kyber, the properties assigned to "LWE" by
Dilithium are incompatible with Kyber.


> > There already is kty with the correct properties (OKP).
> >
> 
> [image: Screen Shot 2022-11-14 at 8.24.25 AM.png]
> https://www.rfc-editor.org/rfc/rfc8037#section-2
> 
> It seems like some people are interpreting the crv related MUST as being
> bound to Ed25519 and others are interpreting it as being bound to kty: OKP
> 
> @Cose Chairs Wg <[e-mail]> Can you help establish consensus
> regarding intention here? Which reading is intended by the working group?

Both RFC 8037 (JOSE) and RFC 9053 (COSE) are clear that the requirement
to have crv parameter is bound to the kty.

 
> >
> This is almost a suggestion for an `alg` value that would work with kyber.
> 
> Something like:
> 
> Kem-Kyber-1024+A256KW
> 
> This is the main question I am hoping to answer for Kyber, since kty, as
> better grounding in existing registry entries,

Ugh, I forgot that JOSE is very different here, and was only thinking
about COSE.

The way JOSE does things screws using alg for subtyping even worse than
COSE.

In JOSE, one presumably would model the thing after ECDH-ES, giving the
following alg's:

- KEM+SHA3KDF
- KEM+SHA3KDF+A128KW
- KEM+SHA3KDF+A192KW
- KEM+SHA3KDF+A256KW

(Where SHA3KDF is that bit profiled down NIST SP 800-56r2 KDF.)

And funkily enough, one gets the exact same algorithms in COSE! However,
in COSE it is possible to do without the KW variants (which is not an
option in JOSE).

The algorithms not being generic over KEMs would cause a nasty
combinatorial explosion.


> >
> > > First, let's start with what we have today:
> > >
> > > - https://www.iana.org/assignments/cose/cose.xhtml
> > > - https://www.iana.org/assignments/jose/jose.xhtml
> > >
> > > { kty: RSA, alg: PS384 / RSAES-OAEP w/ SHA-256}
> > > { kty: RSA, alg: RS384 / RSAES-OAEP w/ SHA-256}
> > > { kty: EC2, crv: P-256, alg: ES256 / ECDH-ES+A256KW }
> > > { kty: OKP, crv: Ed25519, alg: EdDSA } -
> > > https://www.rfc-editor.org/rfc/rfc8037#section-2
> > > { kty: OKP, crv: Bls12381G1, alg: ??? } ...
> > >
> > https://datatracker.ietf.org/doc/html/draft-ietf-cose-bls-key-representations-01#section-2.1.3
> > > { kty: HSS-LMS, alg: HSS-LMS }
> > > { kty: WalnutDSA, alg: WalnutDSA }
> > >
> > > Observations:
> > >
> > > 1. Although `alg` is optional... It looks especially needed in some
> > > cases (RSA), and especially not needed in others (HSS-LMS, WalnutDSA)
> >
> > Sometimes there is only one sensible algorithm for given key (e.g.,
> > Ed25519 keys) sometimes there are multiple (e.g., RSA).
> >
> >
> This observation is correct, but still at the time of key generation, the
> party generating the key should declare its purpose,
> otherwise I might use a key for a million signatures and then suddenly
> start using it for encryption...
> that's the kind of security issue we are welcoming when we make `alg`
> optional in a key representation...
> It is also a reflection of the uneasy feeling we get when we see a new key
> defined with no supported algs.

There is key_ops/use for this. 

However, there is asymmetry between signature keys and encryption keys.
For signature keys, it very much makes sense to lock down the alg.
However, for encryption keys, it might not be possible to lock down the
alg. Then one is left to only saying some key is encryption-only key.

And in context of symmetric keys, it is even worse: In generic
implementation, key subtyping being optional causes quite a mess.


> > > 2. We appear to have slowly started to encode "Purpose" in the key
> > > type (HSS-LMS / WalnutDSA) , which suggests that we are commiting to
> > > keeping `alg` optional forever, and also acknowledging that it is best
> > > to use a key for a single purpose.
> >
> > These are kinds of keys where only signing makes sense, and the
> > keyshapes are different from anything else (first is stateful,
> > the second has decomposed parameters).
> >
> I agree about the stateful part, perhaps that allows us to ignore the
> precedent set by putting the word "stateful signature" in a `kty` value?
> 
> Should the word "kem" be in all kem enabled kty?

The point was, these are not encoding purpose, these are different kty's
because of technical reasons.

 
> >
> > > 4. OKP is reserved for Elliptic Curves only.
> >
> > This is incorrect. Both RFC 8037 (JOSE) and RFC 9053 (COSE) explicitly
> > say otherwise.
> >
> >
> 
> https://www.rfc-editor.org/rfc/rfc8037#section-2
> <https://www.rfc-editor.org/rfc/rfc8037#section-2>
> 
> https://www.rfc-editor.org/rfc/rfc9053.html#section-2.2
> 
> How is a reader supposed to interpret these sections together?

https://www.rfc-editor.org/rfc/rfc9053.html#section-7.2 is more relevant
than section 2.2. It says the following about OKP keys:

"For public keys, it is REQUIRED that "crv" and "x" be present in the
structure. For private keys, it is REQUIRED that "crv" and "d" be
present in the structure."

REQUIRED, SHALL and MUST are all synonyms.

 
> Where does it say you can use kty:OKP for lattices, hashes, curves and
> whatever comes next ?

Both RFC 8037 and RFC 9053 say this about OKP:

"Do not assume that keys using this type are elliptic curves."


> I agree that OKP should not be bound to curves, I disagree (strongly) that
> there is consensus or clarity on this matter.

The intent of the previous statement in RFC 8037 is very explictly that
OKP is not bound to curves.

 
> If the working group / list is saying that it is valid to represent non
> elliptic curves with OKP, that is a revelation I would like to see
> formalized.

That was certainly the intent from the very beginning.
 
 
> > > 5. IANA Registries exist for Elliptic Curves but no other "families"
> > > such as lattices, stateful hash based schemes, or stateless hash based
> > > schemes... based on HSS-LMS not attempting to fix this, it seems we
> > > are ok not establishing new IANA registries for lattice or hash types.
> >
> > Lattices and hashes are very complicated things, far exceeding what IANA
> > registry is useful for.
> >
> >
> I take this as a request NOT to establish an IANA registry for lattices or
> hash based systems, that would mirror the registries for curves.
> 
> Is there consensus on the lists that we should not ask IANA to maintain
> registries for lattices?

I was just saying that I consider the matter to be too complicated for
registry to be useful.

 
> > > 6. Walnut encodes parameters as separate values in the key type, but not
> > > the algorithm name... similar to RSA... which seems like a step backwards
> > > to me.
> >
> > What if the two do not agree?
> >
> >
> Exactly.
> 
> It would be better to keep your parameters embedded in the `alg`, similar
> to how "ECDH-ES+A256KW" implies "Concat KDF".
> 
> Imagine seeing something like this:
> 
> kty: EC
> crv: P-256
> alg: ES256 // alg for signing
> kdf: "Concat-KDF" // parameter for key agreement
> 
> I'm not sure if this kind of parameter issue will exist for 1 or more PQC
> algorithms, and I would like to avoid accidentally creating unsafe
> registries.

I was thinking more about the following kind of scenario:

message alg: foo-1+bar
key crv: foo-2

What happens if implementation forgets to check for this? In JOSE, there
have been really bad CVEs from implementations failing to check alg is
actually compatible with the key.

JOSE has that kind of thing with ECDSA, but fortunately in that case
nothing bad happens.

 
> >
> > > Here is a proposal for Kyber keys that aligns with the previous proposals
> > > and drafts for post quantum signatures:
> > >
> > > { kty: LWE, alg: CRYDI5 }
> > > { kty: LWE, alg: CRYDI3 }
> > > { kty: LWE, alg: CRYDI2 }
> > >
> > > { kty: NTRU, alg: FALCON1024 }
> > > { kty: NTRU, alg: FALCON512 }
> > >
> > > { kty: HASH, alg: SPHINCS+-SHAKE-256s-robust }
> > >
> > > { kty: LWE, alg: Kyber-1024 }
> > > { kty: LWE, alg: Kyber-768 }
> > > { kty: LWE, alg: Kyber-512 }
> > >
> > > Please focus your comments on establishing consensus for relevant values
> > > for `kty` and `alg`.
> >
> > This will not work.
> >
> > Kyber can not be subtyped on alg, because it also requires KDF (like
> > ECDH). And this impiles it can not have the same kty as Dilitihium,
> > which subtypes on alg.
> >
> >
> Why do you say this? ECDH-ES+A256KW implies "Concat KDF"... You can't
> do "ECDH-ES+A256KW"
> from P-256 to P-384 either.... but both have the same kty: EC.

The thing that makes impossible to do "ECDH-ES+A256KW" from P-256 to
P-384 is ECDH-ES auto-adapting the source key type.

 
> We are talking about "key formats here...." we are not talking about JWS /
> JWE Header parameters.
> 
> Are you suggesting that when a kyber key is created it's allowed to be used
> with any `alg` forever, based only on the header parameters of a ciphertext?

I am suggesting that is an option. Seems like this would also be needed
to use the same key for single-recipient and multi-recipient encryption
in JOSE.

 
> Is it a good idea for kyber keys to distribute 1 billion decryptions
> uniformly across all registered kdf in HPKE, based only on the header
> parameters of a ciphertext?

The COSE-HPKE proposals explictly allow that sort of thing.

Assuming there are no bad kdfs in HPKE, that is sound thing to do. What
is less sound is also allowing the same keys to be used both with HPKE
and JOSE/COSE.


> Is it better to announce the kdf that is supported by kyber at the time the
> key is generated, similar to what is done for ECDH-ES+A256KW over P-256
> today?

JOSE and COSE are different here. JOSE only supports Concat-KDF-SHA256.
However, COSE supports HKDF-SHA-256 and HKDF-SHA-512.

 
> 
> > Seriously, "LWE", "NTRU" and "HASH" are not "families of algorithms",
> > those are underlying problems. The families in this care are Dilithium,
> > Falcon, Sphincs+ and Kyber themselves.
> >
> >
> I am going to infer this counter-proposal from what you have said:
> 
> { kty: Dilithium, alg: CRYDI5 }
> { kty: Dilithium, alg: CRYDI3 }
> { kty: Dilithium, alg: CRYDI2 }
> 
> { kty: Falcon, alg: FALCON1024 }
> { kty: Falcon, alg: FALCON512 }
> 
> { kty: SPHINCS, alg: SPHINCS+-SHAKE-256s-robust }
> 
> { kty: Kyber, alg: Kem-Kyber-1024+A256KW }
> { kty: Kyber, alg: Kem-Kyber-768+A256KW }
> { kty: Kyber, alg: Kem-Kyber-512+A256KW }
> 
> Does this counter proposal capture the `alg` and `kty` values that you
> believe are relevant to Kyber key representations?

Using alg values like that in Kyber causes a nasty combinatorial
explosition.

It would also seem to pretty much preclude using the same key for
both single-recipient and multi-recipient encryption in JOSE (since
key wrap is not suitable for bulk encryption and JOSE does not have
triple-layer option from COSE).



-Ilari