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

["Paterson, Kenny" <[e-mail]>]

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" <[e-mail]> 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:[e-mail]]
>Sent: 03 September 2014 20:13
>To: Tanja Lange; Brian LaMacchia
>Cc: [e-mail]
>Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
>
>Hi,
>
>On 03/09/2014 06:27, "Tanja Lange" <[e-mail]> 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
>>[e-mail]
>>http://www.irtf.org/mailman/listinfo/cfrg
>