Re: [Cfrg] On the use of Montgomery form curves for key agreement
"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Fri, 05 September 2014 09:46 UTC
Return-Path: <Kenny.Paterson@rhul.ac.uk>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3B33A1A0645 for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 02:46:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
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 LwVjjyFXLoOb for <cfrg@ietfa.amsl.com>; Fri, 5 Sep 2014 02:46:28 -0700 (PDT)
Received: from emea01-db3-obe.outbound.protection.outlook.com (mail-db3lrp0076.outbound.protection.outlook.com [213.199.154.76]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EB96E1A0535 for <cfrg@irtf.org>; Fri, 5 Sep 2014 02:46:27 -0700 (PDT)
Received: from DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) by DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) with Microsoft SMTP Server (TLS) id 15.0.1015.19; Fri, 5 Sep 2014 09:46:25 +0000
Received: from DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) by DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) with mapi id 15.00.1015.018; Fri, 5 Sep 2014 09:46:25 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: Markulf Kohlweiss <markulf@microsoft.com>, Tanja Lange <tanja@hyperelliptic.org>, Brian LaMacchia <bal@microsoft.com>
Thread-Topic: [Cfrg] On the use of Montgomery form curves for key agreement
Thread-Index: Ac/GFKdVASv0pPTeROyHvj6EvV57FQAucr0AABmnhBAAAKhnAAAe8jSAABa/d5AAOgm1AA==
Date: Fri, 05 Sep 2014 09:46:25 +0000
Message-ID: <D02F3F88.2C657%kenny.paterson@rhul.ac.uk>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <20140902165340.17284.qmail@cr.yp.to> <d4322ec172d74aab83a1d17cf4dcf786@BL2PR03MB242.namprd03.prod.outlook.com> <20140903052704.GM8540@cph.win.tue.nl> <D02D245C.2C3CE%kenny.paterson@rhul.ac.uk> <C90F31503317124C8A9B59786EF212EA0338EF@AMSPRD3001MB017.064d.mgd.msft.net>
In-Reply-To: <C90F31503317124C8A9B59786EF212EA0338EF@AMSPRD3001MB017.064d.mgd.msft.net>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.4.3.140616
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [134.219.227.30]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 0325F6C77B
x-forefront-antispam-report: SFV:NSPM; SFS:(6009001)(53754006)(479174003)(199003)(51914003)(24454002)(189002)(13464003)(243025005)(51704005)(36756003)(101416001)(83322001)(93886004)(4396001)(54356999)(90102001)(81342001)(85306004)(81542001)(2421001)(95666004)(19580405001)(79102001)(31966008)(107046002)(105586002)(76482001)(106356001)(87936001)(66066001)(2656002)(76176999)(19273905006)(46102001)(74662001)(15975445006)(80022001)(64706001)(20776003)(19580395003)(85852003)(99396002)(15202345003)(77982001)(83072002)(86362001)(83506001)(1511001)(21056001)(74502001)(92726001)(74482001)(92566001)(50986999)(563064011); DIR:OUT; SFP:; SCL:1; SRVR:DBXPR03MB383; H:DBXPR03MB383.eurprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: text/plain; charset="euc-kr"
Content-ID: <20721CB6A4275E4DA61DBCD69F3DC66C@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/QcPGNygpyOoJLGtLDxCuPhTXHEw
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Cedric Fournet <fournet@microsoft.com>, Tibor Jager <tibor.jager@rub.de>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 05 Sep 2014 09:46:31 -0000
Markulf, Thanks for the reply. It's server-side reuse that is of concern here (that's where the heavy lifting is done). I now recall that our Crypto'13 paper [1] also uses a KEM abstraction and in Section 7 treats the case where the server has a static DH key; this is not exactly the same as ephemeral reuse, but I think it's close enough that the analysis should go through under the same assumption (PRF-ODH). The result would be that ephemeral reuse is OK in TLS, so long as the reused ephemeral value does not leak. Clearly, if a reused ephemeral value leaks, then all the related sessions are insecure; but it should be the case that all the other, unrelated sessions (using different ephemeral values) are still secure. However, I do not immediately see how a proof of this follows from any of our results in [1] (since we do not consider ephemeral compromise, and allow only non-adaptive corruption). There's still the question of what kind of forward security one can hope for in case of ephemeral reuse. This was not treated in our paper, but I think it should be achievable. It might be worth looking into the paper by Jager et al from Crypto'12 [2] to see how their analysis holds up under ephemeral reuse. I'm cc-ing Tibor Jager to see if he can shed any light on this. And of course, the analyses in [1] and [2] are only in the single ciphersuite setting, so the analysis is not complete (I thought I should say that before you pointed it out ;-) ). Cheers Kenny [1] http://eprint.iacr.org/2013/339.pdf [2] http://eprint.iacr.org/2011/219 On 04/09/2014 08:22, "Markulf Kohlweiss" <markulf@microsoft.com> wrote: >Hi all, > >Mostly in reply to Kenny's comments on provable security and miTLS. We >discussed this internally and have very partial results that should be >extended. > >The miTLS master-secret KEM does not distinguish between one-time use of >the KEM public key, and reuse. So the main proof (of a theorem that does >not model PFS) also holds for TLS-DHE in settings where server public >keys are reused. On the other hand the KEM abstraction does not allow for >client-side reuse of ephemeral values. In KEM terminology: Enc always >uses fresh randomness. > >What are you most concerned about client or server side reuse of >ephemeral secrets? > >How one would model PFS in such a time-based manner is fascinating. The >current, again rudimentary modelling of PFS in miTLS (you have to dig in >the appendix) only models signing key compromise, but not temporal >ephemeral secret compromise. > >Best, >Markulf > >PS. I added Cedric in CC to fact check what I am saying. In these subtle >issues the verification of the implementation may be more detailed than >the paper crypto proof. > >-----Original Message----- >From: Paterson, Kenny [mailto:Kenny.Paterson@rhul.ac.uk] >Sent: 03 September 2014 20:13 >To: Tanja Lange; Brian LaMacchia >Cc: cfrg@irtf.org >Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement > >Hi, > >On 03/09/2014 06:27, "Tanja Lange" <tanja@hyperelliptic.org> wrote: > >>Dear Brian, >>> Regarding the specific issue you raised concerning Microsoft¹s TLS >>>implementation, as you will recall Tanja first mentioned this issue to >>>me during dinner i >>> >>I actually made this statement in public in the Q&A after my talk when >>David McGrew asked about the ephemeral key case. > >This is indeed true as the minutes should show. But it was a topic of >some passionate discussion at the dinner later, IIRC. > >>> As for your suggestion regarding a blanket prohibition on reuse of >>>any ephemeral cryptographic keys across all IETF protocols, given the >>>current environment that does indeed seem like a good idea to me. I >>>guess what we¹d really want to do is have CFRG issue a BCP on this >>>point, if that¹s something the IRTF is allowed to do (I don¹t know the >>>answer to that process question). Perhaps CFRG can take that issue up >>>once the curve selection process has concluded. >>> >>What exactly do you think the security implications of key reuse are? >> >>Defining ephemeral in a time-based manner ist quite normal; the >>important thing to guarantee PFS is to delete the key afterwards, not >>whether it is used for 1 connection or 10 seconds (with potentially 0 >>connections). > >For what it's worth, ephemeral reuse invalidates all the formal security >analyses (in the provable security tradition) for key exchange protocols >that I know of. It certainly invalidates those proofs that I understand >for the TLS Handshake. Would be interesting if the miTLS guys could say >what it means for their TLS proofs from Crypto'14. > >My feeling is that this can be got around in the random oracle model for >protocols that hash the DH shared value and various other components by >using a suitable gap assumption or strong DH assumption. However, some >care would be needed in the analysis. Coming up with a standard model >proof for some specific protocol seems much harder because of the obvious >"correlation" between shared DH values that different parties would end >up with. Hashing with a random oracle of course destroys such relations. > >There's probably a nice research paper in this for someone - if it's not >already been done (indeed writing such a paper has been on my to do list >for some time - since long before this thread got started). > >Cheers > >Kenny > >> >>All the best >> Tanja >> >>_______________________________________________ >>Cfrg mailing list >>Cfrg@irtf.org >>http://www.irtf.org/mailman/listinfo/cfrg >
- [Cfrg] On the use of Montgomery form curves for k… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… D. J. Bernstein
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tony Arcieri
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Michael Hamburg
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Jim Schaad
- Re: [Cfrg] On the use of Montgomery form curves f… Markulf Kohlweiss
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Manuel Pégourié-Gonnard
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov