[Cfrg] Comments on draft-mcgrew-hashsigs-13

Philip Lafrance <Philip.Lafrance@isara.com> Wed, 12 December 2018 16:01 UTC

Return-Path: <Philip.Lafrance@isara.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id DF1AE130E3E for <cfrg@ietfa.amsl.com>; Wed, 12 Dec 2018 08:01:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id Rl2nPpRejwIb for <cfrg@ietfa.amsl.com>; Wed, 12 Dec 2018 08:01:23 -0800 (PST)
Received: from esa1.isaracorp.com (esa1.isaracorp.com []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7E906130E86 for <cfrg@irtf.org>; Wed, 12 Dec 2018 08:01:16 -0800 (PST)
Received: from unknown (HELO V0501WEXGPR01.isaracorp.com) ([]) by ip1.isaracorp.com with ESMTP; 12 Dec 2018 16:01:15 +0000
Received: from V0501WEXGPR01.isaracorp.com ( by V0501WEXGPR01.isaracorp.com ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.1466.3; Wed, 12 Dec 2018 11:01:12 -0500
Received: from V0501WEXGPR01.isaracorp.com ([fe80::d802:5aec:db34:beba]) by V0501WEXGPR01.isaracorp.com ([fe80::d802:5aec:db34:beba%7]) with mapi id 15.01.1466.012; Wed, 12 Dec 2018 11:01:12 -0500
From: Philip Lafrance <Philip.Lafrance@isara.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Comments on draft-mcgrew-hashsigs-13
Thread-Index: AQHUkjPn2jcNKIT4Fkq3y88XUjFLGQ==
Date: Wed, 12 Dec 2018 16:01:12 +0000
Message-ID: <F575A3E8-B3AA-4EA6-8DAB-E87C46B45809@isara.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
x-originating-ip: []
Content-Type: multipart/related; boundary="_004_F575A3E8B3AA4EA68DABE87C46B45809isaracom_"; type="multipart/alternative"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/w7SSDSBH15C3enbVdAxT_w4VfFQ>
Subject: [Cfrg] Comments on draft-mcgrew-hashsigs-13
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 12 Dec 2018 16:03:23 -0000

Greetings all,

My colleagues and I had some comments on draft-mcgrew-hashsigs-13 we wanted to share with you.

1) Section 6, top of page 28

      “pub[i] is the current LMS public key of the i-th level (which

      includes the identifier I as well as the root node value K),”

The notation “K” is used in LM-OTS, not in LMS (as per Algorithm 1), and so K should be replaced with T[1]. Although, we might then want to use different notation for the i-th LMS root node: T_i[1], T^i[1], Ti[1], whatever floats your boat. Also, typecodes for LMS and LM-OTS are included in pub[i] along with I and T[1], is this worth including in the above text?

2) Section 6.1 (HSS) Key Generation

 “To generate an HSS private and public key pair, new LMS private and

   public keys are generated for prv[i] and pub[i] for i=0, ... , L-1…”

Initial HSS key gen requires only the generation of the single tree on the topmost level. I’d say that generating L LMS key-pairs at the time of initial (global) key generation is more of an optimization than a requirement. Such as if you want to cache LMS keys at the onset or something. Considering the text that follows:

“The public key of the HSS scheme consists of the number of levels L,

   followed by pub[0], the public key of the top level”

maybe we can clarify this discussion?

3) Algorithm 7: Generating an HSS keypair

This is along the same vein as my above comment. Step 2. of Algorithm 7 is the following:

      2. sign each child key pair with the private key of its parent:

        i  = 0

            while (i < L-1) {

              sig[i] = lms_signature( pub[i+1], priv[i] )

                  i = i + 1


The 3rd and final step of the algorithm is just to return u32str(L)||pub[0]. The text at the top of the page says, “These key pairs, and their identifiers, MUST be generated independently.” And so pub[0] is independent of all other LMS public keys; i.e., doesn’t need them to be generated first. Further, the sig[i] are not used in the algorithm at all, nor is their purpose mentioned. The text immediately following Alg 7 clearly states that Step 2. isn’t necessary, but I think the presentation here is needlessly complicated.

Thanks to Mark Paruzel and Szilard Balla!

Warm regards, and happy holidays to all.
Philip Lafrance


Philip Lafrance | Standards Manager
Mobile: +1.226.750.2439

www.isara.com<https://www.isara.com/> · 560 Westmount Road North, Waterloo, Ontario N2L 0A9 CANADA