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

[Orie Steele <[e-mail]>]

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.
});



> 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?


> > I reviewed the original registries established in:
> > https://www.rfc-editor.org/rfc/rfc7518.html#section-7
> >
> > I also reviewed the latest "kty" and "alg" registered in
> > https://datatracker.ietf.org/doc/html/rfc8778
> >
> > I'm going to stick to JOSE(ish) notation here, my goal is to get a
> > clear answer on
> > *"which values for `kty` and `alg` are relevant to kyber".*
> > See the latest editor's draft for additional details:
> > https://github.com/OR13/draft-steele-cose-kyber.
>
> Like with ECDH (but unlike with modern signatures), there can be
> multiple applicable alg's, so one can not subtype keys by using
> alg.
>
> 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?


The relevant algs are modeled after ECDH(-ES) ones. However, one can
> not use ECDH-ES ones, because ECDH-ES uses JWK/COSE_Key for the
> ephemeral value, which does not work with Kyber.
>
> And since Kyber internally uses SHA-3, one presumably wants the KDF
> to be based on SHA-3 too. However, neither concat-KDF (JOSE) nor HKDF
> (COSE) work with SHA-3 all too well.
>
> NIST SP 800-56Cr2 almost has a decent KDF based on SHA-3. Almost,
> because of two issues:
>
> - The space reserved for key block headers in default salt is one
>   byte too short. It reserves 4 bytes, but block headers are 5
>   bytes.
> - It does not outright say to set H_outputbits = L. Not only this
>   would make it faster, it would also make it easier to implement.
>
>
> Here is description of a bit tweaked NIST SP 800-56Cr2 KDF (from
> what I can tell, this is actually compliant with 800-56):
>
>
> - Assert desired output length L is positive.
>   (the upper limit it too big to care about.)
> - If not specified otherwise, salt is empty string.
> - Compute KMAC128 or KMAC256 (depending on security level), with:
>   + S being ASCII string "KDF".
>   + K being the salt
>   + X being concatenation of:
>     * 32-bit big-endian 1 (i.e., 0x00 0x00 0x00 0x01)
>     * The input key.
>     * Information structure.
>   + L being the desired output length in bits.
> - The KDF output is the KMAC output.
>
>
> KMAC128 is slightly more performant than KMAC256. However, the
> difference is so slight that it is probably good idea to always use
> KMAC256.
>
> The checks in steps 2 and 4 of 800-56 can never fail.
>
>
>
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,


>
> > 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.


>
> > 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?


>
> > 3. It is possible to define a key and NOT define any algorithms for it...
> > (see bls-key draft above).
>
> Seems to limit the usefulness, however...
>
>
I agree, but since the signature candidates are still in CFRG, it seems
nice they can move the key formats along independently...
... alg is optional after all ...


>
> > 4. OKP is reserved for Elliptic Curves only.
>
> This is incorrect. Both RFC 8037 (JOSE) and RFC 9053 (COSE) explicitly
> say otherwise.
>
>
[image: Screen Shot 2022-11-14 at 8.24.25 AM.png]

https://www.rfc-editor.org/rfc/rfc8037#section-2
<https://www.rfc-editor.org/rfc/rfc8037#section-2>

[image: Screen Shot 2022-11-14 at 8.36.02 AM.png]

https://www.rfc-editor.org/rfc/rfc9053.html#section-2.2

How is a reader supposed to interpret these sections together?

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

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

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.

@Cose Chairs Wg <[e-mail]> Is there a way to resolve this
ambiguity for future readers?


> > 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?


> > 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.


>
> > 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.

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?

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?

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?


> 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?

@Ilari Liusvaara <[e-mail]> Thank you for your comments!


>
> -Ilari
>
> _______________________________________________
> COSE mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/cose
>


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

<https://www.transmute.industries>