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

Denis Butin <> Tue, 21 February 2017 11:49 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 701571298CA; Tue, 21 Feb 2017 03:49:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id vHoGXE46m2rb; Tue, 21 Feb 2017 03:49:53 -0800 (PST)
Received: from ( []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id D1C501298C1; Tue, 21 Feb 2017 03:49:51 -0800 (PST)
Received: from ( []) by (8.14.4/8.14.4/HRZ/PMX) with ESMTP id v1LBnYr0012452; Tue, 21 Feb 2017 12:49:34 +0100 (envelope-from
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by (Postfix) with ESMTPSA id 9D9DA23A52; Tue, 21 Feb 2017 12:49:34 +0100 (CET)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII; format=flowed
Content-Transfer-Encoding: 7bit
Date: Tue, 21 Feb 2017 12:49:34 +0100
From: Denis Butin <>
To: "Paterson, Kenny" <>
Organization: TU Darmstadt
In-Reply-To: <>
References: <>
Message-ID: <>
User-Agent: Roundcube Webmail/1.1.5
X-PMX-TU: seen v1.2 by, Antispam-Engine:, Antispam-Data: 2017.2.21.113616
X-PMX-RELAY: outgoing
Archived-At: <>
Cc: Andreas Huelsing <>,,, Stefan Gazdag <>
Subject: Re: [Cfrg] Review of draft-irtf-cfrg-xmss-hash-based-signatures-07
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 21 Feb 2017 11:49:55 -0000

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 


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
> (
> 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.