Re: [Cfrg] Review of draft-irtf-cfrg-xmss-hash-based-signatures-07

[Denis Butin <[e-mail]>]

Hi Kenny,

Many thanks for your efforts, much appreciated! We are now revising the 
document based your comments and will come up with a new version 
shortly.

Best,
Denis

On 2017-02-21 03:12, Paterson, Kenny wrote:
> Dear Authors,
> 
> Please find below my review of
> draft-irtf-cfrg-xmss-hash-based-signatures-07
> (https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signature
> s/).
> 
> Regards,
> 
> Kenny
> 
> ----
> 
> Review of draft-irtf-cfrg-xmss-hash-based-signatures-07
> 
> The draft is a mature, clear, and useful document. It is almost ready 
> for
> publication; only minor nits below.
> 
> p.1: "hash-based signatures withstand attacks using quantum computers"
> ---> ""hash-based signatures are believed to withstand attacks using
> quantum computers" or ""hash-based signatures can withstand attacks 
> using
> quantum computers"
> p.3: "from 2006 onwards" --> "from the mid 2000s onwards".
> p.3: "composed of" --> "composed from".
> p.4: "standardizing and introducing" --> "introducing and 
> standardizing"
> (depends to whom the introducing is being done here!).
> p.4: check for update to the text claiming that [BDH11] is the "latest
> stateful hash-based signature scheme".
> p.5: "Addition for XMSS"--> "Additionally, for XMSS:"
> p.6: "used implicitly" --> "omitted".
> p.7: "aside of" --> "aside from".
> p.7: "a n-byte value" --> "an n-byte value".
> p.7: setter methods?
> p.8: text beginning: "One type for the hashes ..." is not a grammatical
> sentence - it lacks verbs. You could insert "is used" in a couple of
> places.
> p.8: "The latter being" --> "The latter is".
> p.12: "hold" --> "held".
> p.13: here you introduce functions F and PRF for the first time, 
> referring
> to security requirements in Section 8 for some more details. I think 
> you
> should also include a forward reference here to Section 5 for specific
> instantiations.
> p.14: "end of this section" --> "section 3.1.7".
> p.16: the pseudocode for Algorithm 5 (WOTS_sign) has a loop in which 
> csum
> is increased by values w-1-msg[i]. Is it possible that csum could 
> overflow
> in an implementation, and what would be the consequences? Is a note 
> needed
> to explain the required bitsize of csum to avoid this?
> p.19: "If they match, the signature is valid." --> "If they match, the
> signature is declared valid.".
> p.19:  In Section 4.1.2, you introduce functions H and H_msg. Here you
> should refer to Section 5 for specific instantiations and Section 8 for
> security considerations.
> p.19: "2 * n" --> "2n" (for consistency).
> p.20: "The WOTS+ private keys MUST be generated as described in Section
> 3.1. To reduce the private key size, a cryptographic pseudorandom 
> method
> MAY be used as discussed at the end of this section." The "MUST" and 
> the
> "MAY" here initially seem incompatible. If you MUST do X, then you 
> cannot
> ever do Y which is different from X. But it turns out that Section 3.1
> also mentions the pseudorandom approach as an option, and refers to a
> later section, so the "MUST" and "MAY" are not strictly incompatible.
> However, it would be nice to find a way to address this small issue.
> p.23: In the pseudocode for Algorithm 10, we have "PK = root || SEED".
> Should OID be included here also? It's included in the byte structure 
> on
> page 24.
> p.24: You talk about the authentication path being h*n bytes and being 
> an
> array of h n-byte strings. Are the conversions clear? (Perhaps this is
> covered by notation introduced in Section 2?)
> p.25: "before the updated private key" --> "before the private key is
> updated". (This one is important: the current text could read as: 
> "output
> the signature first, then output the updated private key"!
> p.26: delete "just".
> p.32: again, should OID be part of the public key, PK_MT?
> p.39: "Finally, for the PRF no full-fledged HMAC is needed as the 
> message
> length is fixed." Here you could add "meaning that standard length
> extension attacks are not a concern here".
> p.39: "We use n-bytes for domain separation for consistency with the 
> SHA2
> implementations". This was a bit unclear to me. What domain separation? 
> Do
> you mean in the calls to the "toByte" function?
> p.43: Delete the text "Other signatures methods are out of scope....
> follow-up work." This is not a research paper!
> p.43: "The draft" --> "This note".
> p.44: "available on most platforms" does not seem to make sense - the 
> part
> about availability in crypto libraries does.
> p.44: "leads parameters that provides" --> "leads to parameters that
> provide".
> p.44: "less common" --> "less widely supported".
> p.44: "more assignments" --> "further assignments".
> p.44: "sufficient details" --> "sufficient detail".
> p.48: "message signature pair" --> "message, signature pair" ?
> p.48: "estimates when" --> "estimates for when".
> p.48: "A full security proof for the scheme described here can be found 
> in
> [HRS16]". Can you be more precise about which schemes are covered in
> [HRS16]? WOTS+, XMSS, or XMSS^MT (or all three?).
> p.48: "This proof shows that an attacker..." - this text may need to be
> modified, depending on which schemes you are talking about.
> p.49: "allows to prove that it is not enough for an adversary to break 
> the
> collision resistance of the underlying hash function". This feels like
> awkward phrasing. I don't think you've proved an impossibility result;
> rather I think you have proof of unforgeability under a different
> assumption than collision resistance. Is the assumption you need 
> strictly
> weaker than collision resistance? This text needs some reworking, I 
> think.
> How about "allows a proof of security under a weaker assumption than
> collision resistance"?
> p.49: "This can also be shown formally in the random oracle model." 
> What
> can? That the "above attack" is thwarted? If so, what positive security
> result do you then obtain? I think it's probably worth stating at this
> point.
> p.49: "The given bit security values...". I would suggest adding an 
> extra
> sentence here to say that while generic attacks are prevented by your
> choices of parameters, there could be quantum speed-ups for specific 
> hash
> functions (since we don't yet know the full power of quantum 
> algorithms).
> p.50: "relies on the security of a cryptographic hash function". This 
> is a
> bit vague. Can you be more specific about which security properties are
> relied upon, or maybe just say "relies on specific security properties 
> of
> cryptographic hash functions"?
> p.50: Section 8.3: same issue as above: there could be quantum 
> speed-ups
> for specific hash functions, but the text only covers generic
> attacks. Additional clarity would be beneficial here.
> p.52: I'm not sure what the style requirements on references are, but 
> it
> would be good to include stable URLs for things like [Huelsing13a].
> p.65: We should delete Appendix D in due course.