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

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Tue, 21 February 2017 02:12 UTC

From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: "draft-irtf-cfrg-xmss-hash-based-signatures@ietf.org" <draft-irtf-cfrg-xmss-hash-based-signatures@ietf.org>
Thread-Topic: Review of draft-irtf-cfrg-xmss-hash-based-signatures-07
Thread-Index: AQHSi+fq7bZUKu69YEqbWcQECptCAA==
Date: Tue, 21 Feb 2017 02:12:13 +0000
Message-ID: <D4D152DC.88C79%kenny.paterson@rhul.ac.uk>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/14.7.1.161129
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: [153.224.139.152]
x-microsoft-exchange-diagnostics: 1; AM4PR0301MB1908; 7:aoS90lQ3BiIHIgNktV/3H40/1wm9W4bLTeJsVdTn22kdrI8mim6O8eeCh9cAV2zx5pGDGOAGlmK8hmvAYgJNeKDsqIS9dKc2SQ9HCXFf0O1PMjt/1LgiepOpZ96/cGPIre0VA2/x6a864upFeo7f/949y1MCM6E9pgah4bFOEWZACbr3/x8/saY7P+eqfolekxuOcA2gufKnRQdScv3MYZN9Q3wttyzv+RpmeKbtE2BDKlzLh7RNjxa0LMlU0VkrEQ87BGBsg7WQ4d88AZnEmhyf/VxxSwOqpE7MCq2cT05isj+F9Jfjm/YODUGsOserRrVrU+UTiwU7xrN42Wj4nA==
x-forefront-antispam-report: SFV:SKI; SCL:-1SFV:NSPM; SFS:(10009020)(6009001)(7916002)(39450400003)(199003)(189002)(7736002)(106116001)(92566002)(2900100001)(66066001)(54356999)(97736004)(101416001)(230783001)(2501003)(36756003)(3280700002)(50986999)(8676002)(189998001)(54906002)(6512007)(122556002)(305945005)(81166006)(4001350100001)(81156014)(99286003)(6306002)(4326007)(53936002)(2351001)(25786008)(86362001)(38730400002)(6916009)(110136004)(42882006)(3660700001)(68736007)(77096006)(106356001)(6486002)(3846002)(6116002)(105586002)(5640700003)(5660300001)(74482002)(2906002)(102836003)(8936002)(6436002)(83506001)(6506006); DIR:OUT; SFP:1101; SCL:1; SRVR:AM4PR0301MB1908; H:AM4PR0301MB1906.eurprd03.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
x-ms-office365-filtering-correlation-id: 17fa0581-52c0-49d9-fdc3-08d459ff0d23
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001); SRVR:AM4PR0301MB1908;
x-microsoft-antispam-prvs: <AM4PR0301MB19087D1BC4265E5F6AEFB1B5BC510@AM4PR0301MB1908.eurprd03.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(120809045254105)(192374486261705);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040375)(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001)(6041248)(20161123558025)(20161123560025)(20161123564025)(20161123562025)(20161123555025)(6072148); SRVR:AM4PR0301MB1908; BCL:0; PCL:0; RULEID:; SRVR:AM4PR0301MB1908;
x-forefront-prvs: 0225B0D5BC
received-spf: None (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <056BBFAC91FF8049B13697D884C1941F@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-originalarrivaltime: 21 Feb 2017 02:12:13.7347 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM4PR0301MB1908
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/X7LpPDDoKGtiKV91jcddHzti-P4>
Cc: Andreas Huelsing <andreas@huelsing.net>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] Review of draft-irtf-cfrg-xmss-hash-based-signatures-07
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 21 Feb 2017 02:12:22 -0000

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.

[Cfrg] Review of draft-irtf-cfrg-xmss-hash-based-… Paterson, Kenny
Re: [Cfrg] Review of draft-irtf-cfrg-xmss-hash-ba… Denis Butin