Document: draft-mcgrew-hash-sigs-08
Reviewer: Stanislav Smyshlyaev
Review Date: 2017-11-11
Summary: Minor revision needed

The hash-based signature scheme described in the I-D provides message
authentication algorithms that remain secure after introduction of
effective full-scale quantum computers. This scheme is based on the Merkle
tree scheme and employs specific variant of Winternitz one-time signature.
The scheme requires a small set of fixed domain parameters and can be
easily adopted for the use with national-specific cryptographic primitives.
A particularly important feature of the scheme is the fact that each
invocation of a fixed hash function H outputs a unique byte string (except
a negligible of identifiers collision).

The proposed scheme was proven to be existentially unforgeable under
adaptive chosen message attack (GMR-secure) in random oracle model when
using second preimage resistant hash function ([F17]). It seems also not to
be vulnerable against so called duplicate signature key selection attack
(which is out of GMR-security definition and was firstly introduced in
[BM99] since an attacker who wants to create his own key pair which can be
used for successful verification of a target signature has to find a second
preimage of a used hash function. The current version of the document
lacks, however, comments on the post-quantum security. It would be great if
such a comment appears.

Since the proposed signature scheme is stateful, it is extremely important
to manage its states in a secure way. The I-D proposes helpful technical
implementation notes that cover synchronization issues when storing key in
non-volatile memory.

The document is very important, well-written and fully defines the proposed
algorithms. I particularly like that there are very helpful sections that
give an overview of the design rationale.

There is a number of concerns, that should be addressed before the
publication. Once the comments are resolved, I think that the document can
be published.


Formulae and algorithms to be checked for correctness:
The second paragraph of Section 4.2 states that length of LM-OTS signature
equals np, while it seems to be equal to 4 + n(p+1)
The description of the algorithm 6 lacks parsing of parameter otstype
The description of the algorithm 6b supposes that otssigtype is set
directly after q, while the informal description in Section 5.4 states that
otssigtype follows after the OTS value

Other comments:

Throughout the text: consider replacing 'signature system' with a commonly
used 'signature scheme'

Chapter 1:

"moderatley" -> "moderately"

Chapter 2:

"A message/signature pair are valid"  -> "... is valid"

"the signature and message pair are not valid" -> "... is not valid"

Section 3.1:

"a four byte string S " -> "a four-byte string S"

Section 3.1.1:

The i^th element in an array A is denoted as A[i] -> the i-th element...

The same change should be done throughout the text to avoid confusion with
powers of i.

Section 3.2:

"I - a 16 byte identi­fier" -> "I - a 16-byte identifier"

"i = a value between 0 and 264" -> "i - a value between 0 and 264"

Function H is used in the definition of par­ameter i, but that function is
not yet defin­ed at that point.

"a two byte identifier "  -> "a two-byte identifier"

Chapter 4:

"a diversification parameter q (which is used as part of the security
string, as listed in Section 3.2" - ")" should be added

Section 4.1:

Definitions of n, w, p, ls and H: last three definifons end with ".", while
the first two do not.

The definition or re­ference should be gi­ven for the notion of Winte­rnitz
coefficient. Also the same should be done with the not­ions Winternitz
tree, Winternitz  chain and LMS tree.

Section 4.2:

"Here SHA256 denotes the NIST standard hash function [FIPS180]." - since
SHA-256 is defined together with SHA-1, SHA-384 etc., it seems better to
say something like "Here SHA256 denotes the SHA-256 hash function, defined
in NIST standard [FIPS180]."

Section 4.5:

"A checksum is used to ensure that any forgery attempt that manipulates the
elements of an existing signature will be detected." - the sentence is too
general and seem to not add any real information to the reader. In my
opinion, it would be better to say explicitly about the vulnerability that
appears if we do not use the checksum.

Section 4.7:

"Signature Typecode Type ," -> "Signature Typecode Type,"

Chapter 5:

There is "Leight­on Micali Signatures", but in the introduction this notion
was men­tioned as "Leighton-M­icali Signatures". Al­so, the abbreviation
LMS was already given in Section 1.

Section 5.1:

"h : the height (number of levels - 1) in the tree, and" - 1) "of" instead
of "in", 2) it seems that "and" should be omitted.

There are two sentences about possible usage of different hash functions -
I'd prefer to seem them combined in a one, they look quite confusing in the
current version.

Consider adding in the end of Section 5.1 a paragraph, which explicitly
defines the sizes of private key, public key and signature in terms of the
used parameters. It can be useful for a reader, who first opens the
document and wants to understand the overall properties of the scheme.

Section 5.4:

Line 3 “an LM-OTS signature, and” - it seems that “and” should be omitted.

Section 5.4.1:

It seems strange that the section for "LMS Signature Verification" has the
number "5.5" and the "LMS Signature Generation" has "5.4.1" - maybe use
"5.6" and "5.5" instead?

Section 5.5:

It seems more reasonable to use "Algorithm 6a" instead of "Algorithm 6"

Chapter 6:

In the first paragraph a general description is given for HSS with 2
levels, and in the I-D it is defined for up to 8 levels. It seems more
helpful to modify the first paragraph for the case of arbitrary number of
levels, not only for two.

Chapter 8:

"Other hash functions may be used in future specifications; all the ones
that we will be likely to support (SHA-512/256 and the various SHA-3
hashes) would work well with a 16 byte I value." - mentioning SHA-256 here
among "other hash functions" looks confusing, given the whole I-D defines
schemes for SHA-256.

Chapter 12:

"an attacker who does not know the private key associated with a public key
can find a message and signature that are valid with that public key" -
maybe "a new message" or "a message which is different from all previously
signed ones".

There is a very helpful text about formatted inputs of a hash - I'd
recommend to add a subtitle before it (use 12.1 before "The format of the
inputs to...").

"pseuddorandom" -> "pseudorandom"

"This can be shown (in [Fluhrer17]) ..." -> "This is shown (in [Fluhrer17])
..."

Section 12.1

"It is essential for security that the application ensure" -> "ensures"

"until the data has been to the underlying hardware" - maybe add "stored"
or "written" after "has been"?

In your IETF 97 slides there was a slide with "Anti-Copying Token in
Private Key Files" (slide 19 in https://datatracker.ietf.org/
meeting/97/materials/slides-97-cfrg-hash-based-signatures-
update-and-batch-message-signing/) - won't it be helpful to add those
recommendation in Chapter 12 also?

Chapter 12:
"where HSS need only perform one" -> "needs only to perform one"
"HSS is somewhat simpler" - this looks quite vague and uncertain - maybe it
would be better to get rid of this phrase?..

References:

"Buchmann, J., Dahmen, E., and . Andreas Hulsing," - remove "." before
"Andreas"

Appendix A:

"however any other cryptographical secure method of generating private keys
would also be safe." - formally, this is not true: if the previously
mentioned formula is used with, say, 254 instead of 255, it would be
generally "cryptographically secure", but won't be very good for the
considered case.
Maybe just get rid of this (quite vague) sentence at all?

"cryptographical secure method" -> " cryptographically secure method"


[BM99]: Blake-Wilson S., Menezes A., "Unknown key-share attacks on the
station-to-station (STS) protocol", Lect. Notes Comput. Sci., 1560, 1999,
156?170.

[F17]: Fluhrer S., "Further analysis of a proposed hash-based signature
standard", EPrint IACR Archieve, http://eprint.iacr.org/2017/553.pdf.