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

"Paterson, Kenny" <> Fri, 05 September 2014 09:46 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3B33A1A0645 for <>; Fri, 5 Sep 2014 02:46:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.902
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id LwVjjyFXLoOb for <>; Fri, 5 Sep 2014 02:46:28 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id EB96E1A0535 for <>; Fri, 5 Sep 2014 02:46:27 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1015.19; Fri, 5 Sep 2014 09:46:25 +0000
Received: from ([]) by ([]) with mapi id 15.00.1015.018; Fri, 5 Sep 2014 09:46:25 +0000
From: "Paterson, Kenny" <>
To: Markulf Kohlweiss <>, Tanja Lange <>, Brian LaMacchia <>
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: <>
References: <> <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: []
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;; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: text/plain; charset="euc-kr"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Cc: "" <>, Cedric Fournet <>, Tibor Jager <>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 05 Sep 2014 09:46:31 -0000


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

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 ;-) ).





On 04/09/2014 08:22, "Markulf Kohlweiss" <> 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
>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.
>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 []
>Sent: 03 September 2014 20:13
>To: Tanja Lange; Brian LaMacchia
>Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
>On 03/09/2014 06:27, "Tanja Lange" <> 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
>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).
>>All the best
>>	Tanja
>>Cfrg mailing list