[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
Return-Path: <Kenny.Paterson@rhul.ac.uk>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D8299129595 for <cfrg@ietfa.amsl.com>; Mon, 20 Feb 2017 18:12:21 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.92
X-Spam-Level:
X-Spam-Status: No, score=-1.92 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H4=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=rhul.onmicrosoft.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id R-S6DVAHdfTz for <cfrg@ietfa.amsl.com>; Mon, 20 Feb 2017 18:12:18 -0800 (PST)
Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on0074.outbound.protection.outlook.com [104.47.1.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4AF2E129586 for <cfrg@irtf.org>; Mon, 20 Feb 2017 18:12:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rhul.onmicrosoft.com; s=selector1-rhul-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=e4wW8ONYGSlz26J8ioUS+XU9mmZa/W0G2FzLr9BeFqE=; b=WkRJo4yCVWpEH5wPchY4Q6lcJtVk4NyU2+Cd4VzTDE+I+bt5BnkI/c1+1iOMrg9Dfxh/nRQYyxzB9n+tRZhUih+E/MeNHkYLHTxDdbpEb2cXrc1SOn2U5a0HTQzPmfDoUlLWY94b2QBR/yinSb96fQ5AOVV/A1mZ+PSCjvXB3pA=
Received: from AM4PR0301MB1906.eurprd03.prod.outlook.com (10.168.2.156) by AM4PR0301MB1908.eurprd03.prod.outlook.com (10.168.3.8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.919.13; Tue, 21 Feb 2017 02:12:14 +0000
Received: from AM4PR0301MB1906.eurprd03.prod.outlook.com ([10.168.2.156]) by AM4PR0301MB1906.eurprd03.prod.outlook.com ([10.168.2.156]) with mapi id 15.01.0919.015; Tue, 21 Feb 2017 02:12:13 +0000
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
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.7.1.161129
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
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