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

Russ Housley <housley@vigilsec.com> Wed, 04 December 2019 21:06 UTC

Return-Path: <housley@vigilsec.com>
X-Original-To: cose@ietfa.amsl.com
Delivered-To: cose@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BE15412004C for <cose@ietfa.amsl.com>; Wed, 4 Dec 2019 13:06:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 2Ljb0VaRIB7f for <cose@ietfa.amsl.com>; Wed, 4 Dec 2019 13:06:38 -0800 (PST)
Received: from mail.smeinc.net (mail.smeinc.net [209.135.209.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 17C3C1200A3 for <cose@ietf.org>; Wed, 4 Dec 2019 13:06:38 -0800 (PST)
Received: from localhost (localhost [127.0.0.1]) by mail.smeinc.net (Postfix) with ESMTP id 90403300B04 for <cose@ietf.org>; Wed, 4 Dec 2019 16:06:36 -0500 (EST)
X-Virus-Scanned: amavisd-new at mail.smeinc.net
Received: from mail.smeinc.net ([127.0.0.1]) by localhost (mail.smeinc.net [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id rJ-J_L-pqbZZ for <cose@ietf.org>; Wed, 4 Dec 2019 16:06:33 -0500 (EST)
Received: from a860b60074bd.fios-router.home (pool-108-51-198-163.washdc.fios.verizon.net [108.51.198.163]) by mail.smeinc.net (Postfix) with ESMTPSA id 871153005C5; Wed, 4 Dec 2019 16:06:33 -0500 (EST)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\))
From: Russ Housley <housley@vigilsec.com>
X-Priority: 1
In-Reply-To: <619FB9BA-BDEB-4E31-BC04-DF265F27E51D@vigilsec.com>
Date: Wed, 4 Dec 2019 16:06:34 -0500
Cc: Jim Schaad <jimsch@augustcellars.com>, IESG <iesg@ietf.org>, cose <cose@ietf.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <559B8753-15F1-4C18-A604-686FD0A96215@vigilsec.com>
References: <157539486101.24700.12161503456212968239.idtracker@ietfa.amsl.com> <619FB9BA-BDEB-4E31-BC04-DF265F27E51D@vigilsec.com>
To: Ben Kaduk <kaduk@mit.edu>
X-Mailer: Apple Mail (2.3445.104.11)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cose/3dhH5Eyc4T8PKWXLIp6hbZfnYHA>
Subject: Re: [COSE] Benjamin Kaduk's Discuss on draft-ietf-cose-hash-sig-07: (with DISCUSS and COMMENT)
X-BeenThere: cose@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: CBOR Object Signing and Encryption <cose.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/cose>, <mailto:cose-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cose/>
List-Post: <mailto:cose@ietf.org>
List-Help: <mailto:cose-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/cose>, <mailto:cose-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 04 Dec 2019 21:06:40 -0000

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