Re: [Cfrg] I-D Action: draft-irtf-cfrg-xmss-hash-based-signatures-06.txt

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Sat, 23 July 2016 19:14 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 B650712B006 for <cfrg@ietfa.amsl.com>; Sat, 23 Jul 2016 12:14:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-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 oloaytcRyOX6 for <cfrg@ietfa.amsl.com>; Sat, 23 Jul 2016 12:14:51 -0700 (PDT)
Received: from EUR01-VE1-obe.outbound.protection.outlook.com (mail-ve1eur01on0045.outbound.protection.outlook.com [104.47.1.45]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BA0CF12D607 for <cfrg@irtf.org>; Sat, 23 Jul 2016 12:14:50 -0700 (PDT)
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=xRP3q+CjTRvB14RxLDMEHm4dVpaAIxyOZEHRZTDi2yA=; b=xqVVsW0YfCLrJwN/qyE6hZn4dlZQAJ+fjpFvzfcrNUl/vUo9US3zlp6HMCYINP7ks9GYyteRdGIHhyz+qzI9w83ESnkvsviXpL3AuHBqv9yMd/tije/CVy/JBLxPe/WJUWFYmo6f0nYGUlz51tDQGIXdY4iJdqkKKZKbfvR65AU=
Received: from VI1PR03MB1822.eurprd03.prod.outlook.com (10.166.42.148) by VI1PR03MB1822.eurprd03.prod.outlook.com (10.166.42.148) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.544.10; Sat, 23 Jul 2016 19:14:46 +0000
Received: from VI1PR03MB1822.eurprd03.prod.outlook.com ([10.166.42.148]) by VI1PR03MB1822.eurprd03.prod.outlook.com ([10.166.42.148]) with mapi id 15.01.0544.018; Sat, 23 Jul 2016 19:14:46 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: Phillip Hallam-Baker <phill@hallambaker.com>
Thread-Topic: [Cfrg] I-D Action: draft-irtf-cfrg-xmss-hash-based-signatures-06.txt
Thread-Index: AQHR15UYqNPamwit8kua06Zbbm7UcKALfSwAgBrD+ICAADlwAIAAAzRG
Date: Sat, 23 Jul 2016 19:14:46 +0000
Message-ID: <C6F5FDF9-6A09-4ECB-AAF5-985BF06F0F83@rhul.ac.uk>
References: <20160706144508.25995.18605.idtracker@ietfa.amsl.com> <577D1B6E.1020506@huelsing.net> <D3B93AC9.7187E%kenny.paterson@rhul.ac.uk>, <994C5976EA09B556.08963792-86E6-4CE4-95FB-23F0F6046EC0@mail.outlook.com>
In-Reply-To: <994C5976EA09B556.08963792-86E6-4CE4-95FB-23F0F6046EC0@mail.outlook.com>
Accept-Language: en-GB, en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
x-originating-ip: [78.146.50.187]
x-ms-office365-filtering-correlation-id: 2901e91a-7749-4ac0-1cac-08d3b32d9c02
x-microsoft-exchange-diagnostics: 1; VI1PR03MB1822; 6:fo9kJLj2S3hskzYe5YwU+Nq/5a+8Dw713Uz0oSIK15YcZn/H8C1ooBIQspjc+DgKD9W5+vgVRX0rvRvjXof5y3ntp7KY3yLP+/rz4M22vAhoQjNFUPX5qH2rb2tLx8TzsJ13cp0u/b6Ay/92xymdJwIQigViAEQdOQ8aIDeizKvxcD2/CTmIGpXYF1mYhJbo2mPUVV4YGcuwikc6ufxcGurD95W3lDuy/ol861UskMdJt1XozOinLF7ISnRxnBrx+M0ll6RJOhOMOqpnWwP2sW5KqKXDUWeA1XpOMpu2B2o=; 5:1/utI0KeKPx1CxcSkgQUoZB1zHRNJKn6jqhi1xE+OnNP8JE9AEuMGhImx8d/Qmtpu2gTrOoFqM80pocbj2faYq/yqsNOP1Gv/NaI8jisgMjSDHKLDHbXKW8j3gENvG9BTC5l7d0KDUqzQ3v7W7a3vA==; 24:ygAj2FF+3byzPO2KdFBFzovGKN/xnNFMdQGCTn9CwH+JqbMe3o6ACdtBNfafWvgUpYLJcbkzFzzCm5ApzIK76ZmN4c49dj01KhEuiCN/CrA=; 7:SkwJfXWSa6iXXZEsqywDa3Ouf3UinRrSLCsq6XmxnNHfOfGZZ1gGRsN/BF+9XGMKhz1PdeJmLWponq9leWy0z4OGztsq6Q4nHbra+5DdWnthDei6+9jotOQXaU3GGC6vpA0tgLaytrS+5HGhr++7ggMm1wo+WZ0a9FwtfNNUaHuTdZo1A8RXrLlyvAkQO7LbfwzHfbPRpcPlEpT3DsLb2zJxdSYIe7I9lYFc6vpjJpvOQajYIvnpgPOYt2hx6iB6
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:VI1PR03MB1822;
x-microsoft-antispam-prvs: <VI1PR03MB18221B6A421B068F4B105146BC0B0@VI1PR03MB1822.eurprd03.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(120809045254105)(192374486261705)(100405760836317);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001); SRVR:VI1PR03MB1822; BCL:0; PCL:0; RULEID:; SRVR:VI1PR03MB1822;
x-forefront-prvs: 0012E6D357
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(7916002)(199003)(377454003)(24454002)(377424004)(189002)(19580405001)(82746002)(19617315012)(106116001)(106356001)(68196006)(50986999)(33656002)(16236675004)(66066001)(19580395003)(76176999)(54356999)(230783001)(87936001)(86362001)(83716003)(105586002)(93886004)(101416001)(11100500001)(7846002)(2906002)(4326007)(7736002)(189998001)(81166006)(81156014)(7906003)(97736004)(110136002)(8936002)(92566002)(68736007)(10400500002)(8676002)(36756003)(1680700002)(102836003)(586003)(3846002)(6116002)(122556002)(74482002)(77096005)(16601075003)(15975445007)(5002640100001)(3660700001)(2900100001)(2950100001)(3280700002)(104396002); DIR:OUT; SFP:1101; SCL:1; SRVR:VI1PR03MB1822; H:VI1PR03MB1822.eurprd03.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
received-spf: None (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_C6F5FDF96A094ECBAAF5985BF06F0F83rhulacuk_"
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Jul 2016 19:14:46.0215 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR03MB1822
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/hNj3BXlVi3e34jAQrzOE7lFLIVI>
Resent-From: alias-bounces@ietf.org
Resent-To: <>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-xmss-hash-based-signatures-06.txt
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: Sat, 23 Jul 2016 19:14:54 -0000

Hi Phillip,

We're confident *given our current understanding of the power of quantum algorithms*. Since that research field is still relatively young, it might be over-stating things to say that the community is "very confident" for the long-term (and, yes, I know about the lower bounds that have been proven for quantum algorithms for problems like generic search and collision finding, but that does not rule out advances in quantum algorithms targeting specific hash functions).

Your other point regarding state is well made.

Cheers,

Kenny

On 23 Jul 2016, at 20:03, Phillip Hallam-Baker <phill@hallambaker.com<mailto:phill@hallambaker.com>> wrote:

I think the text gets the position wrong.

We are in fact very confident that Hash signatures are secure against QC. We have no current attack on symmetric crypto that gives us concern on that score.

BUT, where we have a big question mark is on the 'use once' aspect of hash signatures. The systems depend either on absolutely on not screwing up and signing more than once or on the security of some 'stateless' hack which may or may not be secure. So there is a big big question as far as systems integration goes and on robustness of the system as a whole.

Get Outlook for iOS<https://aka.ms/o0ukef>




On Sat, Jul 23, 2016 at 10:35 AM -0400, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk<mailto:Kenny.Paterson@rhul.ac.uk>> wrote:


Dear Andreas,

Thanks for pushing the new version.

Stephen and I had a chat at IETF 96 this week. His original suggestion for
text to be added was this [1]:

"All quantum-resistant algorithms documented by CFRG are today
considered ready for experimentation and further engineering
development (e.g. to establish the impact of performance and sizes
on IETF protocols) but CFRG has consensus that we are not yet
sufficiently confident to the point where we would want the security
or privacy of a significant part of the Internet to be dependent on
any set of those algorithms. In future, as things mature, CFRG
intends to publish updated guidance on this topic."

Personally, I think this is too strong for hash-based signatures: although
we have no deployment experience (that I know of), we do have fairly
strong confidence in the security of hash-based signatures against quantum
computers, given the current state of the art of research in quantum
algorithms. I'd suggest instead that some text like this should be
included:


"All quantum-resistant algorithms documented by CFRG are today
considered ready for experimentation and further engineering
development (e.g. to establish the impact of performance and sizes
on IETF protocols). However, at the time of writing, we do not have
significant deployment experience with such algorithms.
CFRG consensus is that we are confident in the security of the
signature schemes described in this document against

quantum computers, given the current state of the research
community's knowledge about quantum algorithms. Indeed, we are
confident that the security of a significant part of the Internet
could be made dependent on the signature schemes defined in this
document."

I realise that's a pretty strong statement that is the opposite of what
Stephen suggested *for these signature schemes*.

So let's discuss a bit more, and see if there is consensus from CFRG for
the statement I've made here. Happy also to receive suggestions for
alternative, better-worded statements.

Cheers,


Kenny

[1] https://www.ietf.org/mail-archive/web/cfrg/current/msg08315.html

On 06/07/2016 15:53, "Cfrg on behalf of A. Huelsing"
 wrote:

>Hi,
>
>we pushed a new version that further simplifies the addresses due to a
>comment we received off-list. It is a minor change that simplifies
>implementation of addresses as u_int32 array. We did not take any action
>regarding Stephens comment, yet. For this we want to get more feedback
>on what we should do.
>
>Andreas
>
>
>
>On 07/06/16 16:45, internet-drafts@ietf.org<mailto:internet-drafts@ietf.org> wrote:
>> A New Internet-Draft is available from the on-line Internet-Drafts
>>directories.
>> This draft is a work item of the Crypto Forum of the IETF.
>>
>>         Title           : XMSS: Extended Hash-Based Signatures
>>         Authors         : Andreas Huelsing
>>                           Denis Butin
>>                           Stefan-Lukas Gazdag
>>                           Aziz Mohaisen
>>      Filename        : draft-irtf-cfrg-xmss-hash-based-signatures-06.txt
>>      Pages           : 66
>>      Date            : 2016-07-06
>>
>> Abstract:
>>    This note describes the eXtended Merkle Signature Scheme (XMSS), a
>>    hash-based digital signature system.  It follows existing
>>    descriptions in scientific literature.  The note specifies the WOTS+
>>    one-time signature scheme, a single-tree (XMSS) and a multi-tree
>>    variant (XMSS^MT) of XMSS.  Both variants use WOTS+ as a main
>>    building block.  XMSS provides cryptographic digital signatures
>>    without relying on the conjectured hardness of mathematical problems.
>>    Instead, it is proven that it only relies on the properties of
>>    cryptographic hash functions.  XMSS provides strong security
>>    guarantees and is even secure when the collision resistance of the
>>    underlying hash function is broken.  It is suitable for compact
>>    implementations, relatively simple to implement, and naturally
>>    resists side-channel attacks.  Unlike most other signature systems,
>>    hash-based signatures withstand attacks using quantum computers.
>>
>>
>> The IETF datatracker status page for this draft is:
>>
>>https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatur
>>es/
>>
>> There's also a htmlized version available at:
>>
>>https://tools.ietf.org/html/draft-irtf-cfrg-xmss-hash-based-signatures-06
>>
>> A diff from the previous version is available at:
>>
>>https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-xmss-hash-based-signatu
>>res-06
>>
>>
>> Please note that it may take a couple of minutes from the time of
>>submission
>> until the htmlized version and diff are available at tools.ietf.org<http://tools.ietf.org>.
>>
>> Internet-Drafts are also available by anonymous FTP at:
>> ftp://ftp.ietf.org/internet-drafts/
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org<mailto:Cfrg@irtf.org>
>> https://www.irtf.org/mailman/listinfo/cfrg
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org<mailto:Cfrg@irtf.org>
>https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org<mailto:Cfrg@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg