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

[Russ Housley <[e-mail]>]

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

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

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

> 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 :)

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

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

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.

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

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.

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

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. 

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


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

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.

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

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]

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

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'.
> 
> nit: no "and".

Fixed.

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

Yes.  Good Catch.

Russ