Re: [lamps] New Version Notification for draft-ietf-lamps-cms-hash-sig-00.txt

[Russ Housley <[e-mail]>]

Daniel:

Thanks for the review.

> 1. Regarding the recommendation that SHA-256 be used to compute the message digest.
> The LM-OTS signature generation prepends a random string (plus other metadata) to the message before hashing it [1]:
>        Q = H(I || u32str(q) || u16str(D_MESG) || C || message)
> This reduces the chances of being able to find collisions, effectively changing the problem to finding a second preimage.  A second preimage can be found in O(2^(n/2)) queries with Grover's algorithm.  For SHA-256 this is O(2^128), which is sufficiently secure.
> 
> But by using SHA-256 to compute the message digest in CMS, and passing that digest to HSS to be (randomized-hashed and) signed, this removes the advantage given by the randomized hash.  An attacker could look for collisions on the CMS pre-hash instead of the HSS randomized hash.  A quantum computer can find collisions in O(2^(n/3)) queries[2], or O(2^85.3) for SHA-256, which is probably not sufficiently secure.  That said, there are arguments[3] that the hardware cost for the algorithm in [2] is greater than the query cost.  This argument makes certain assumptions on hardware limitations, and I don't think it precludes the possibility of a quantum algorithm with the same query complexity as [2] but with better hardware costs.
> 
> So anyways, for this draft you might want to consider that a SHA-256 message digest within CMS might provide insufficient security against a quantum collision attack and recommend SHA-512 (or SHA-384) instead.

Thanks for the careful review.  Does anyone have a preference for a way forward here?

> 2. The draft's ASN.1 module defines the HSS public key (pk-HSS-LMS-HashSig), but the rest of the draft makes no mention of HSS public key algorithm identifier or properties (parameters, key usage, public key encoding).  Is this something that should be specified in this draft?  In another draft?  My employer has seen interest in HSS (and XMSS) for root certificates and code signing certificates so I was going to write and propose a draft for HSS/XMSS in X.509 certificates to support those use cases.  If the public key is well defined in the CMS draft I can reference it, or I can take on the definition.

Yes, the ASN.1 does include the object identifier for the public key.  I'll be glad to add as section to the body of the Internet-Draft about it.

> 3. It had been suggested by Panos in this draft's call to add to the recharter that it be expanded to include other hash-based signatures like XMSS.  Since that was not included in the recharter, is it off the table?

NO.  At the time, no one else spoke in support of the work.  We need to hear that people want to do the work, that people want to review the work, and that people are interested in deploying.  When we look for new work items in the future, speak up.

> 4. Nits:
> - Several places in Section 3 id-alg-hss-lms-hashsig is referred to as an algorithm identifier, but it is an object identifier.

An ASN.1  AlgorithmIdentifier is an OBJECT IDENTIFIER with OPTIONAL parameters.  In this case, the parameters are always absent, so I think that both names are accurate.

> - in 2.1 signed_public_key is misspelled as sigend_public_key in one place.

Will fix.

> - draft-mcgrew-hash-sigs-13 defines Nspk = L-1 where L is the number of levels, and then an HSS signature as:
>    u32str(Nspk) || signed_pub_key[0] || ... || signed_pub_key[Nspk-1] || sig[Nspk]
> The CMS draft isn't consistent with that, so this:
> 	   The elements of the HSS signature value for a tree with Nspk levels
> 	   can be summarized as:
> 
> 	      u32str(Nspk) ||
> 	      signed_public_key[1] ||
> 	      signed_public_key[2] ||
> 	         ...
> 	      sigend_public_key[Nspk-1] ||
> 	      signed_public_key[Nspk] ||
> 	      lms_signature_on_message
> should be:
> 	   The elements of the HSS signature value for a tree with L levels
> 	   can be summarized as:
> 
> 	      u32str(L-1) ||
> 	      signed_public_key[0] ||
> 	      signed_public_key[1] ||
> 	         ...
> 	      signed_public_key[L-2] ||
> 	      lms_signature_on_message
> or something to the same effect.

Oops.  I seem to have missed a change along the way.  I will check alignment.

Russ