Subject: Re: [Cfrg] Slides for interim meeting

From: Dan Brown <[email-masked]>
Date: Mon, 5 May 2014 15:04:59 +0000

Hi Watson,

Can you elaborate on your last slide item "Reduction to DDH"?

I've been trying to catch up with reading the papers about TLS, but was 
further motived by your comment.  So far, I have scanned a couple papers for 
such a reduction, without clear success.  I have probably just not looked at 
the right paper yet.

The paper

http://eprint.iacr.org/2014/020

seems to use GapDH instead of DDH to prove the security of TLS-DHE. Obviously, 
that does not contradict your reduction, because security can be proved under 
a variety of assumptions, which is good.  Also, it does not contradict your 
point that Strong DH is irrelevant to the TLS-DHE, because it uses the GapDH.

The paper

http://eprint.iacr.org/2013/367

seems to use the DDH and Strong PRF-ODH assumption (and a couple other 
non-group related assumptions) to prove the security of Server-Only TLS-DHE.

Interestingly, the Strong PRF-ODH kind of reduces to the Strong DDH if the PRF 
reduces to PRF(X,m) = X.

To that end, using a group in which the strong DDH is hard (which requires the 
Strong DH to be hard), might somehow boost the effectiveness of this proof. 
It seems vaguely relevant, in a way I've not yet fully understood.

But perhaps this reliance of the proof on assumptions like PRF-ODH has be 
overcome by further research.  Another reason for my question.

Anyway, despite this paper, I'd agree that with the intuition that TLS-DHE 
does not require the Strong (aka Static) DH to be hard.  Nor does it need the 
DDH to be hard. Unless, the PRF and record layer break down, etc., or the 
session state (shared secret) leaks, etc.

Best regards,

Dan

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
> Sent: Monday, April 28, 2014 8:25 PM
> To: [email-masked]
> Subject: [Cfrg] Slides for interim meeting
>
> Dear all,
> My slides are attached.
> Sincerely,
> Watson Ladd

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 May 2014 08:40:01 -0700

> such a reduction, without clear success.  I have probably just not looked at

So I'm ignoring everything that TLS actually does, and focusing on a
protocol I understand, namely Diffie-Hellman where we have known
public keys.

The attacker sees a bunch of (g^a, g^b, H(g^(ab)), and can feed in an
h to get (g^a, H(h^a)). If H is a random oracle, then for the attacker
to distinguish (g^c, g^d, H(g^(cd)), where he hasn't seen one of c or
d before, from (g^c, g^d, X), reduces to CDH: they have to compute
g^(cd) to get the answer out of the random oracle, and knowing
H(whatever) is (almost) absolutely useless. (Apply usual quadratic
loss to abort in case of H(whatevers) equaling each other)

In the standard model I think you get DDH instead. Either way, the
Cheon attack is completely inhibited unless a preimage attack on the
hash function exists.

Most key exchanges look like this: MQV hashes the shared element, HMQV
hashes the shared element, TLS hashes the shared element. The need to
do other things in the case of TLS then reduce to DDH is because of
technicalities in the TLS protocol, according to
http://eprint.iacr.org/2013/367.pdf.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin