Re: [Cfrg] On the use of Montgomery form curves for key agreement

Markulf Kohlweiss <markulf@microsoft.com> Thu, 04 September 2014 07:23 UTC

Return-Path: <markulf@microsoft.com>
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 C5D321A1F70 for <cfrg@ietfa.amsl.com>; Thu, 4 Sep 2014 00:23:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.602
X-Spam-Level:
X-Spam-Status: No, score=-2.602 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, 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 nC6XyKaZHCj1 for <cfrg@ietfa.amsl.com>; Thu, 4 Sep 2014 00:23:14 -0700 (PDT)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2lp0236.outbound.protection.outlook.com [207.46.163.236]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 84EED1A001A for <cfrg@irtf.org>; Thu, 4 Sep 2014 00:23:14 -0700 (PDT)
Received: from BY2PR03CA073.namprd03.prod.outlook.com (10.141.249.46) by CH1PR03MB622.namprd03.prod.outlook.com (10.255.156.169) with Microsoft SMTP Server (TLS) id 15.0.1019.16; Thu, 4 Sep 2014 07:23:12 +0000
Received: from BN1AFFO11FD044.protection.gbl (2a01:111:f400:7c10::184) by BY2PR03CA073.outlook.office365.com (2a01:111:e400:2c5d::46) with Microsoft SMTP Server (TLS) id 15.0.1019.16 via Frontend Transport; Thu, 4 Sep 2014 07:23:12 +0000
Received: from mail.microsoft.com (131.107.125.37) by BN1AFFO11FD044.mail.protection.outlook.com (10.58.52.191) with Microsoft SMTP Server (TLS) id 15.0.1010.11 via Frontend Transport; Thu, 4 Sep 2014 07:23:12 +0000
Received: from 064-smtp-out.microsoft.com (141.251.33.15) by TK5EX14HUBC105.redmond.corp.microsoft.com (157.54.80.48) with Microsoft SMTP Server (TLS) id 14.3.195.2; Thu, 4 Sep 2014 07:22:34 +0000
Received: from AMSPRD3001MB017.064d.mgd.msft.net ([169.254.8.57]) by AMSPRD3001HT002.064d.mgd.msft.net ([141.251.33.15]) with mapi id 14.16.0466.000; Thu, 4 Sep 2014 07:22:33 +0000
From: Markulf Kohlweiss <markulf@microsoft.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, 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/d5A=
Date: Thu, 4 Sep 2014 07:22:33 +0000
Message-ID: <C90F31503317124C8A9B59786EF212EA0338EF@AMSPRD3001MB017.064d.mgd.msft.net>
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>
In-Reply-To: <D02D245C.2C3CE%kenny.paterson@rhul.ac.uk>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [86.31.191.28]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-EOPAttributedMessage: 0
X-Forefront-Antispam-Report: CIP:131.107.125.37; CTRY:US; IPV:CAL; IPV:NLI; IPV:NLI; EFV:NLI; SFV:NSPM; SFS:(6009001)(438002)(53754006)(479174003)(189002)(199003)(24454002)(51704005)(13464003)(80022001)(81342001)(66066001)(50466002)(64706001)(20776003)(47776003)(2421001)(86146001)(2656002)(15202345003)(85306004)(93886004)(46102001)(76482001)(15975445006)(77982001)(1511001)(55846006)(77096002)(79102001)(83072002)(84676001)(92726001)(86612001)(85852003)(86362001)(69596002)(68736004)(90102001)(19580405001)(19580395003)(83322001)(6806004)(44976005)(31966008)(23756003)(92566001)(99396002)(50986999)(16796002)(81542001)(33656002)(26826002)(74502001)(95666004)(76176999)(107046002)(87936001)(97736001)(74662001)(106466001)(81156004)(4396001)(21056001)(54356999); DIR:OUT; SFP:; SCL:1; SRVR:CH1PR03MB622; H:mail.microsoft.com; FPR:; MLV:ovrnspm; PTR:InfoDomainNonexistent; MX:1; A:1; LANG:en;
X-Microsoft-Antispam: BCL:0;PCL:0;RULEID:;UriScan:;
X-O365ENT-EOP-Header: Message processed by - O365_ENT: Allow from ranges (Engineering ONLY)
X-Forefront-PRVS: 0324C2C0E2
Received-SPF: Pass (protection.outlook.com: domain of microsoft.com designates 131.107.125.37 as permitted sender) receiver=protection.outlook.com; client-ip=131.107.125.37; helo=mail.microsoft.com;
Authentication-Results: spf=pass (sender IP is 131.107.125.37) smtp.mailfrom=markulf@microsoft.com;
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/CP1Log0rpXQbq3iP8JG0L1XWkpI
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Cedric Fournet <fournet@microsoft.com>
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: Thu, 04 Sep 2014 07:23:17 -0000

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