Subject: [COSE] Benjamin Kaduk's Discuss on draft-ietf-cose-hash-sig-07: (with DISCUSS and COMMENT)

From: Benjamin Kaduk via Datatracker <[email-masked]>
Date: Tue, 03 Dec 2019 09:41:01 -0800

Benjamin Kaduk has entered the following ballot position for
draft-ietf-cose-hash-sig-07: Discuss

When responding, please keep the subject line intact and reply to all
email addresses included in the To and CC lines. (Feel free to cut this
introductory paragraph, however.)

Please refer to https://www.ietf.org/iesg/statement/discuss-criteria.html
for more information about IESG DISCUSS and COMMENT positions.

The document, along with other ballot positions, can be found here:
https://datatracker.ietf.org/doc/draft-ietf-cose-hash-sig/

----------------------------------------------------------------------
DISCUSS:
----------------------------------------------------------------------

I do see the previous discussion in
https://mailarchive.ietf.org/arch/msg/cose/E6ApKPKlESQQSZwySJAVF1l27OE
but I am still unclear on where exactly we can represent the octet
string that is the HMS-LMS public key.  Do we not need to define a COSE
Key Type Parameter (i.e., label) that maps to the public key value?  For
reference, the examples in Appendix C.7.1 of RFC 8152 include key/value
pairs with the negative map labels from
https://www.iana.org/assignments/cose/cose.xhtml#key-type-parameters
corresponding to the key type in question.
Hopefully I'm just confused and missing where this is already done, but
marking as a Discuss point in case I'm not.  (The linked
cose-wg/Examples seem to be using a JSON structure to describe the input
to the example generation, with the "public" and "private" members of
the "key" that do not seem to correspond to anything that I can find at
https://www.iana.org/assignments/jose/jose.xhtml#web-key-parameters, and
which would in any case not directly apply to the *COSE* usage.)

----------------------------------------------------------------------
COMMENT:
----------------------------------------------------------------------

Related to the above Discuss, should we have an explicit statement that we do
not define a way to convey an HSS/LMS private key in a COSE_Key object?
(I think it is correct to not define such a thing, since conveying a
stateful private key is something of a non-sequitur.)

It's not entirely clear to me how much of RFC 8554 we need to duplicate
in order to give the reader an understanding of the signature structure
we're using.  A few times while reading Sections 2.x I had to
double-check that I was reading the right document :)

Section 1.1

   If large-scale quantum computers are ever built, these computers will
   be able to break many of the public-key cryptosystems currently in
   use.  A post-quantum cryptosystem [PQC] is a system that is secure
   against quantum computers that have more than a trivial number of
   quantum bits (qubits).  It is open to conjecture when it will be

(nit: they're also secure against quantum computers that do have a
trivial number of bits.  Yes, I know this is also true about classical
signature algorithms with sufficiently large keys, but the text here is
perhaps not making quite the point we want to make.)

   Since the HSS/LMS signature algorithm does not depend on the
   difficulty of discrete logarithm or factoring, the HSS/LMS signature
   algorithm is considered to be post-quantum secure.  The use of HSS/
   LMS hash-based signatures to protect software update distribution,
   perhaps using the format that is being specified by the IETF SUIT
   Working Group, will allow the deployment of software that implements
   new cryptosystems.

In light of the genart reviewer's comments, we could recast this as
"there is desire have HSS/LMS-based signatures available to protect
software update distribution, including from the IETF SUIT Working
Group" to place the focus on the desire, which is more easily fixed in
time, rather than the WG output, which will change with time.

Section 2.2

   Each tree in the hash-based signature algorithm specified in
   [HASHSIG] uses the Leighton-Micali Signature (LMS) system.  LMS
   systems have two parameters.  The first parameter is the height of
   the tree, h, which is the number of levels in the tree minus one.

I strongly suggest making it more clear that there are two (types of)
trees involved -- the HSS tree of Section 2.1, and a tree within a given
LMS signature (what's being discussed here).  Just using an unadorned
"the tree" is a recipe for confusion.

   The [HASHSIG] specification defines the value I as the private key
   identifier, and the same I value is used for all computations with
   the same LMS tree.  In addition, the [HASHSIG] specification defines

I think RFC 8554 uses I as the identifier for the key pair, not just the
private key, and it seems that in the COSE context we are more likely to
be referring to a public key than a private key.

Section 2.3

      n -  The number of bytes output by the hash function.  This
           specification supports only SHA-256 [SHS], with n=32.

      H -  A preimage-resistant hash function that accepts byte strings
           of any length, and returns an n-byte string.  This
           specification supports only SHA-256 [SHS].

Is supporting other n values basically just a matter of allocating from
a registry?  If so, we might want to tweak the wording a bit to leave
the possibility for such a generalization.

   The LM-OTS signature value can be summarized as the identifier of the
   LM-OTS variant, the random value, and a sequence of hash values (y[0]
   through y[p-1]) that correspond to the elements of the public key as
   described in Section 4.5 of [HASHSIG]:

nit: I'd consider a different wording than "correspond to"; the
correspondence is a bit hard to describe clearly, but "hash values that
include as input" (or similar) is IMO fairly clear.

Section 3

      o  The 'kty' field MUST be present, and it MUST be 'HSS-LMS'.

(Re. "MUST be present", I note that RFC 8152 already has """The element
"kty" is a required element in a COSE_Key map."""

      o  If the 'alg' field is present, and it MUST be 'HSS-LMS'.

nit: no "and".

Section 5

   To ensure that none of tree nodes are used to generate more than one
   signature, the signer maintains state across different invocations of
   the signing algorithm.  Section 12.2 of [HASHSIG] offers some
   practical implementation approaches around this statefulness.  In

There is no Section 12.2 in RFC 8554; is perhaps Section 9.2 the
intended one?

---

From: Russ Housley <[email-masked]>
Date: Wed, 4 Dec 2019 16:06:34 -0500

Ben:

I am trying to work with Jim Schaad on your DISCUSS comment.  He has done an implementation, so I'd like to get his insight.

Turning to your comments ...

I agree that we do not want to define such a structure.  I'm not sure where to say anything about it.

> double-check that I was reading the right document :)

I tried to achieve a balance.  I wanted to have enough to understand HSS, LMS, and LM-OTS.

> perhaps not making quite the point we want to make.)

I suggest:

   If large-scale quantum computers are ever built, these computers will
   have more than a trivial number of quantum bits (qubits) and they
   will be able to break many of the public-key cryptosystems currently
   in use.  A post-quantum cryptosystem [PQC] is a system that is secure
   against against such large-scale quantum computers.  It is open to
   conjecture when it will be feasible to build such computers; however,
   RSA [RFC8017], DSA [DSS], ECDSA [DSS], and EdDSA [RFC8032] are all
   vulnerable if large-scale quantum computers come to pass.

> time, rather than the WG output, which will change with time.

I suggest:

   Since the HSS/LMS signature algorithm does not depend on the
   difficulty of discrete logarithm or factoring, the HSS/LMS signature
   algorithm is considered to be post-quantum secure.  The use of HSS/
   LMS hash-based signatures to protect software update distribution
   will allow the deployment of future software that implements new
   cryptosystems.  By deploying HSS/LMS today, authentication and
   integrity protection of the future software can be provided, even if
   advances break current digital signature mechanisms.

> "the tree" is a recipe for confusion.

Perhaps an introduction sentence is enough:

   Subordinate LMS trees are placed in the the HSS structure discussed
   in Section 2.1.  Each tree in the hash-based signature algorithm
   specified in [HASHSIG] uses the Leighton-Micali Signature (LMS)
   system. 

> be referring to a public key than a private key.

Section 4.3 of RFC 8554 says that x, I, and q are taken from the private key, so I think this text is accurate.

To address your point, I suggest:

   The [HASHSIG] specification defines the value I as the private key
   identifier, and the same I value is used for all computations with
   the same LMS tree.  The value I is also available in the public key.
   In addition, the [HASHSIG] specification defines the value T[i] as
   the m-byte string associated with the ith node in the LMS tree, where
   and the nodes are indexed from 1 to 2^(h+1)-1.  Thus, T[1] is the
   m-byte string associated with the root of the LMS tree.

> the possibility for such a generalization.

Good point.  I suggest:

   n -  The number of bytes output by the hash function.  For
        SHA-256 [SHS], n=32.

   H -  A preimage-resistant hash function that accepts byte strings
        of any length, and returns an n-byte string.

> include as input" (or similar) is IMO fairly clear.

I suggest:

   The LM-OTS signature value can be summarized as the identifier of the
   LM-OTS variant, the random value, and a sequence of hash values (y[0]
   through y[p-1]) as described in Section 4.5 of [HASHSIG]:

      u32str(otstype) || C || y[0] || ... || y[p-1]

> "kty" is a required element in a COSE_Key map."""

Yes, but the check is still needed.  I suggest:

      o  The 'kty' field MUST be 'HSS-LMS'.

>     o  If the 'alg' field is present, and it MUST be 'HSS-LMS'.

Fixed.

> There is no Section 12.2 in RFC 8554; is perhaps Section 9.2 the

Yes.  Good Catch.

Russ

---

From: Russ Housley <[email-masked]>
Date: Wed, 4 Dec 2019 17:50:33 -0500

I suggest:

6.3.  COSE Key Type Parameters Registry Entry

  The new entry in the "COSE Key Type Parameters" registry [IANA] has
  the following columns:

     Key Type:  TBD  (Value to be assigned above by IANA)

     Name:  pub

     Label:  TBD (Value to be assigned by IANA)

     CBOR Type:  bstr

     Description:  Public key for HSS/LMS hash-based digital signature

     Reference:  This document (Number to be assigned by RFC Editor)

Russ

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 4 Dec 2019 14:52:29 -0800

>      Reference:  This document (Number to be assigned by RFC Editor)

That's basically what I had in mind; thanks!
(We could perhaps number the different TBDs but this case is not too
complicated...)

-Ben

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 5 Dec 2019 14:18:06 -0800

Hi Russ,

> I am trying to work with Jim Schaad on your DISCUSS comment.  He has done an implementation, so I'd like to get his insight.

As it happens, I had had the same thought, so I expect he had the answer at
hand for you :)

> I agree that we do not want to define such a structure.  I'm not sure where to say anything about it.

The best place I can see is in Section 5 (Operational Considerations), as
something like "Because of the need to maintain state across invocations of
the signing algorithm, a COSE Key Type Parameter for encoding the private
key (and its state) is deliberately not defined; serializing the state for
conveyance presents too great a risk of state reuse to justify any
potential benefit from doing so."

> I tried to achieve a balance.  I wanted to have enough to understand HSS, LMS, and LM-OTS.

Understood, and I'm deferring to you on judging the balance.

>    vulnerable if large-scale quantum computers come to pass.

A nice solution; thanks!

>    specified in [HASHSIG] uses the Leighton-Micali Signature (LMS)

It seems to be, yes.

> > There is no Section 12.2 in RFC 8554; is perhaps Section 9.2 the

Thanks for all the updates!

-Ben

---

From: Russ Housley <[email-masked]>
Date: Fri, 6 Dec 2019 12:26:58 -0500

Ben:

Trimming to the one unresolved comment...

I suggest:

   A COSE Key Type Parameter for encoding the HSS/LMS private key and
   the state about which tree nodes have been used is deliberately not
   defined.  It was not defined to avoid creating the ability to save
   the private key and state, generate one or more signatures, and then
   restore the private key and state.  Such a restoration operation
   provides disastrous opportunities for tree node reuse.

Russ

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 10 Dec 2019 18:06:32 -0800

Hi Russ,

>    provides disastrous opportunities for tree node reuse.

That works for me; thanks!

-Ben