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

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sun, 12 Nov 2017 06:57:57 +0300

Dear Kenny and Alexey,

The review of draft-mcgrew-hash-sigs-08 has been posted to the CFRG mailing
list.

Best regards,
Stanislav

2017-10-30 1:15 GMT+08:00 Paterson, Kenny <[email-masked]>:

> Hi Stanislav,
>
> Two weeks would be just fine - thanks!
>
> Kenny
>
> On 29/10/2017 17:11, "Станислав Смышляев" <[email-masked]> wrote:
>
> >Dear Kenny,
> >
> >I'll be happy to do it. ‎Will it be appropriate, if it takes me two weeks?
> >
> >Kind regards,
> >Stanislav‎
> >‎
> >  Исходное сообщение
> >От: Paterson, Kenny
> >Отправлено: воскресенье, 29 октября 2017 г., 19:05
> >Кому: Stephen Farrell; Alexey Melnikov; [email-masked]
> >Тема: Re: [Crypto-panel] Request for review: draft-mcgrew-hash-sigs-08
> >
> >Thanks Stephen - much appreciated. We'll see what other volunteers we get.
> >We've another document coming up for the review panel right away, which
> >might be better suited to your interests.
> >
> >Cheers
> >
> >Kenny
> >
> >On 29/10/2017 14:39, "Crypto-panel on behalf of Stephen Farrell"
> ><[email-masked] on behalf of [email-masked]>
> >wrote:
> >
> >>
> >>Hiya,
> >>
> >>On 29/10/17 13: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?
> >>
> >>I'm willing to take a peek. But you may be better to
> >>put me at the end of the volunteer list - my only real
> >>knowledge here is what I learned from reviewing the
> >>xmss spec. But if you're stuck and/or think that's
> >>useful I could do it.
> >>
> >>S.
> >>
> >>
> >>>
> >>> Thank you,
> >>> Kenny and Alexey
> >>>
> >>> _______________________________________________
> >>> Crypto-panel mailing list
> >>> [email-masked]
> >>> https://www.irtf.org/mailman/listinfo/crypto-panel
> >>>
> >>
> >
> >_______________________________________________
> >Crypto-panel mailing list
> >[email-masked]
> >https://www.irtf.org/mailman/listinfo/crypto-panel
>
>

---

From: Alexey Melnikov <[email-masked]>
Date: Sun, 12 Nov 2017 12:14:08 +0800

On 12/11/2017 11:57, Stanislav V. Smyshlyaev wrote:
> Dear Kenny and Alexey,
> 
> The review of draft-mcgrew-hash-sigs-08 has been posted to the CFRG
> mailing list.

Thank you very much.

> Best regards,
> Stanislav
> 
> 2017-10-30 1:15 GMT+08:00 Paterson, Kenny <[email-masked]
> <mailto:[email-masked]>>:
> 
>     Hi Stanislav,
> 
>     On 29/10/2017 17:11, "Станислав Смышляев" <[email-masked]
>     <mailto:[email-masked]>> wrote:
> 
>     >Dear Kenny,
>     >
>     <mailto:[email-masked]>
>     ><[email-masked]
>     <mailto:[email-masked]> on behalf of
>     [email-masked] <mailto:[email-masked]>>
>     >wrote:
>     >
>     >>
>     >>Hiya,
>     >>
>     >>> <https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/
>     <https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/>> before
>     >>> [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/crypto-panel>
>     >>>
>     >>
>     >
>     >[email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/crypto-panel>
> 
> 
> 
>

---

From: Tibor Jager <[email-masked]>
Date: Thu, 16 Nov 2017 13:21:39 +0100

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"
> <[email-masked] on behalf of [email-masked]> 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,
>>>