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

[Benjamin Kaduk <[e-mail]>]

Hi Russ,

On Wed, Dec 04, 2019 at 04:06:34PM -0500, Russ Housley wrote:
> 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.

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

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

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

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

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

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

A nice solution; thanks!

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

It seems to be, yes.

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

Thanks for all the updates!

-Ben