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

From: Russ Housley <[email-masked]>
Date: Tue, 4 Sep 2018 16:55:15 -0400

Throughout the document, the terminology was changed to make it clear that this hs about HSS/LMS hash-based signatures.

Russ

> A new version of I-D, draft-ietf-lamps-cms-hash-sig-00.txt
> has been successfully submitted by Russ Housley and posted to the
> IETF repository.
> 
> Name:		draft-ietf-lamps-cms-hash-sig
> Revision:	00
> Title:		Use of the HSS/LMS Hash-based Signature Algorithm in the Cryptographic Message Syntax (CMS)
> Document date:	2018-08-31
> Group:		lamps
> Pages:		13
> URL:            https://www.ietf.org/internet-drafts/draft-ietf-lamps-cms-hash-sig-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-ietf-lamps-cms-hash-sig/
> Htmlized:       https://tools.ietf.org/html/draft-ietf-lamps-cms-hash-sig-00
> Htmlized:       https://datatracker.ietf.org/doc/html/draft-ietf-lamps-cms-hash-sig
> 
> 
> Abstract:
>   This document specifies the conventions for using the the HSS/LMS
>   hash-based signature algorithm with the Cryptographic Message Syntax
>   (CMS).  The HSS/LMS algorithm is one form of hash-based digital
>   signature; it is described in [HASHSIG].
> 
> 
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> The IETF Secretariat
>

---

From: Daniel Van Geest <[email-masked]>
Date: Sun, 23 Sep 2018 15:45:12 +0000

Hi Russ, some comments.

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.

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.

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?

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.
- in 2.1 signed_public_key is misspelled as sigend_public_key in one place.
- 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.

Thanks,
Daniel

[1] https://tools.ietf.org/html/draft-mcgrew-hash-sigs-13#section-4.5
[2] https://www.cs.princeton.edu/~mzhandry/docs/papers/QCol.pdf
[3] https://cr.yp.to/hash/collisioncost-20090823.pdf

On 2018-09-04, 10:55 PM, "Spasm on behalf of Russ Housley" <[email-masked] on behalf of [email-masked]> wrote:

    Russ

    > until the htmlized version and diff are available at tools.ietf.org.
    
    _______________________________________________
    Spasm mailing list
    [email-masked]
    https://www.ietf.org/mailman/listinfo/spasm

---

From: Russ Housley <[email-masked]>
Date: Sun, 23 Sep 2018 15:45:36 -0400

Daniel:

Thanks for the review.

> 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-3…

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,…

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, i…

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.

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

> or something to the same effect.

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

Russ