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, 5 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
>