Re: [Crypto-panel] Request for review: draft-mcgrew-hash-sigs-08

Tibor Jager <tibor.jager@upb.de> Thu, 16 November 2017 12:21 UTC

Return-Path: <tibor.jager@upb.de>
X-Original-To: crypto-panel@ietfa.amsl.com
Delivered-To: crypto-panel@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 028CB12947E; Thu, 16 Nov 2017 04:21:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_MED=-2.3] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=uni-paderborn.de
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 1tK-dRdmgivQ; Thu, 16 Nov 2017 04:21:44 -0800 (PST)
Received: from mail.uni-paderborn.de (mail.uni-paderborn.de [131.234.142.9]) (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 145EB129476; Thu, 16 Nov 2017 04:21:43 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=uni-paderborn.de; s=20170601; h=Content-Transfer-Encoding:Content-Type: In-Reply-To:MIME-Version:Date:Message-ID:From:Cc:References:To:Subject:Sender :Reply-To:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id:List-Help: List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=4IRtF3tKH1nqGtfK/oaxi0S5+v2z9Pg0dIlrpin3TAU=; b=f0H+rctKQ39O0TYlZTrNY55NL8 /Yj9CTXUPAGgFO0a1hNjZlvN0sk7Pf2IG50GkJompWl2v3UDfxNEOSpjI8kVxRub6o1YVB93saQMs onjVhtZWSqZUyxab3ido5sOs4i9CS88a+8TRAJW9Al29Yq1x88EiDKQNFvP+EtiWTdvE=;
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
References: <59F5D882.30707@isode.com> <f57bc54a-b4a4-5b1d-f15e-f5dab4d06033@upb.de> <D61CA75A.A2E11%kenny.paterson@rhul.ac.uk>
Cc: "crypto-panel@irtf.org" <crypto-panel@irtf.org>, cfrg@irtf.org, mcgrew@cisco.com
From: Tibor Jager <tibor.jager@upb.de>
Message-ID: <83851479-b427-c7d5-798f-03a791c5d5be@upb.de>
Date: Thu, 16 Nov 2017 13:21:39 +0100
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:45.0) Gecko/20100101 Thunderbird/45.8.0
MIME-Version: 1.0
In-Reply-To: <D61CA75A.A2E11%kenny.paterson@rhul.ac.uk>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
X-IMT-Spam-Score: 0.0 ()
X-PMX-Version: 6.3.3.2656215, Antispam-Engine: 2.7.2.2107409, Antispam-Data: 2017.11.16.120316, AntiVirus-Engine: 5.43.0, AntiVirus-Data: 2017.11.16.5430001
X-IMT-Authenticated-Sender: uid=tjager,ou=People,o=upb,c=de
Archived-At: <https://mailarchive.ietf.org/arch/msg/crypto-panel/IB1hjyf9nq4GIwSNTRf7ffQfvEI>
Subject: Re: [Crypto-panel] Request for review: draft-mcgrew-hash-sigs-08
X-BeenThere: crypto-panel@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: <crypto-panel.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/crypto-panel>, <mailto:crypto-panel-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/crypto-panel/>
List-Post: <mailto:crypto-panel@irtf.org>
List-Help: <mailto:crypto-panel-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/crypto-panel>, <mailto:crypto-panel-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Nov 2017 12:21:49 -0000

Dear all,

Please find my review of draft-mcgrew-hash-sigs-08 below.

Cheers,
Tibor


Summary:
The proposal is very carefully written and complete. I like very much
that it provides helpful overview sections, good examples and is
*extremely* clear.

There are no major comments or concerns, but a few minor comments and
recommendations. Among the points listed below, I consider a
generalization of the discussion of race conditions that may lead to
multiple signatures signed with the same state as the most important one.

I've also checked the pseudocodes, but just by reading and not
implementing them, so I may have missed something there.



Minor comments:

p.2:
The "small private key" holds only if the keys are generated using the
procedure from Appendix A (or any other pseudorandom function). I
suggest to replace:

"The characteristics of these signature systems are small private and
public keys and fast signature generation and verification, but large
signatures and moderatley slow key generation (in comparison with RSA
and ECDSA)."
->
"The characteristics of these signature systems are small public keys
and fast signature generation and verification, but large signatures and
moderatley slow key generation (in comparison with RSA and ECDSA).
Private keys can be made very small by appropriate key generation, as
described in Appendix A."


p.2:
I suggest to clarify by replacing:

"A One-Time Signature (OTS) system can be used to sign one message
securely, but cannot securely sign more than one"
->
"A One-Time Signature (OTS) system can be used to sign one message
securely, but will become insecure if more than one is signed with the
same public/secret key pair."

p.4
"When B is a byte and i is an integer, then B >> i denotes the logical
right-shift operation."
->
"When B is a byte and i is an integer, then B >> i denotes the logical
right-shift operation by i positions."

p.6/7: At first reading, I found r and q redundant. Only later in the
document their different purpose became clear.

p.8: The Winternitz coefficient w is a member of the set {1,2,4,8}.
Later in the spec, only terms of the form 2^w-1 become relevant. I
understand that this probably the notation from the paper, but it seems
a bit weird to consider constant w-th powers of 2, instead of integer
constants directly. One could (slightly) simplify this by letting w be a
member of the set {1,3,15,255} and later work with w instead of 2^w-1.
One could then easily even consider other values for w. Also
{1,4,16,256} would appear a bit more natural.

p.15:
"size of the hash function"
->
"output length of the hash function"

p.16, Algorithm 5:
Is step 3 of this algorithm really necessary? If yes, an explaining
remark would be helpful. It seems to me that this instruction is not
necessary.

p.18/19:
Algorithm 6a, step 3: "compute the candidate the LMS root value Tc ...
using algorithm 6b"
The caption of Algorithm 6b uses a different wording: "compute an LMS
Public Key Candidate".
I suggest to replace in algorithm 6a, step 3:
"compute the candidate the LMS root value Tc ... using algorithm 6b"
->
"compute the candidate the LMS Public Key Candidate Tc ... using
algorithm 6b"
to unify notation and improve clarity.

p.20: A developer may wonder for which choices of N it should implement
the scheme from Section 5, and when the scheme from Section 6 becomes
more reasonable. I understand that this is difficult to say in general,
but at least some recommendations or hints, e.g. in form of table with
some example calculations of key size, computational difficulty of
signing, etc., would clearly be helpful to assist this decision.

p.31/32: I got the impression that the root of the problem does not
become very clear here. The draft discusses volatile memory etc., but I
think that more generally *any* race condition that can result in re-use
of individual OTS keys is problematic. One could also point out that
this makes it difficult to parallelize the generation of signatures, in
particular with modern multi-core operating CPUs in mind. This could be
explained more clearly here.


Typos:
p.2: "moderatley"
p.2: "incorporate" -> "incorporated"
p.11: "priva key" -> "private key"






On 30/10/2017 10:54, Paterson, Kenny wrote:
> Thanks Tibor, that would be great.
> 
> On 30/10/2017 08:17, "Crypto-panel on behalf of Tibor Jager"
> <crypto-panel-bounces@irtf.org on behalf of tibor.jager@upb.de>; wrote:
> 
>> Hi Alexey and Kenny,
>>
>> I can have a look at this, too.
>>
>> Cheers,
>> Tibor
>>
>> On 29/10/2017 14:32, Alexey Melnikov wrote:
>>> Dear Crypto Panel,
>>>
>>> CFRG Chairs would like to request review of
>>> <https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/> before
>>> forwarding it to IRSG for final review and approval.
>>>
>>> Can we have some volunteer(s) please?
>>>
>>> Thank you,
>>> Kenny and Alexey
>>>
>>> _______________________________________________
>>> Crypto-panel mailing list
>>> Crypto-panel@irtf.org
>>> https://www.irtf.org/mailman/listinfo/crypto-panel
>>>
>>
>> _______________________________________________
>> Crypto-panel mailing list
>> Crypto-panel@irtf.org
>> https://www.irtf.org/mailman/listinfo/crypto-panel
>