Subject: [Cfrg] Reduction and pseudoreduction of static DHP to TLS-DH

From: Dan Brown <[email-masked]>
Date: Wed, 7 May 2014 19:06:38 +0000

Suppose adversary A can attack TLS-(EC)DH (or a semi-static TLS-DHE being
proposed to TLS 1.3). To be concrete, suppose that A interacts via TLS with
a server (or client) who possesses a static DH private key s, and thereby
computes some key derived from s, e.g. TLS-PRF(s, other public info), such
as past and future TLS master secrets from the server with other honest
parties (not A).  We also consider a stronger version of A, we can call A+,
that is able to compute the actual server key s using this information.

For the reduction, we use A+ to build an adversary B that can solve the
static DHP.

Recall that B is given an oracle O that returns g^st for any input g^t,
which is part of the definition of the static DHP.

So, B implements whatever version of TLS that A+ attacks, except instead of
using the actual key s, B calls its oracle O whenever TLS would use the
static private key s.

At the end of the day, A+ returns s, and thus B wins its static DHP
challenge.

To address the weaker adversary A, we use a pseudoreduction.

As an intermediate step, we a formal reduction: we build an adversary B-
that solves the static DHP given the help of a second oracle O+ that can
invert the TLS-PRF to find s.  

Adversary B- works just like B, except when A returns TLS-PRF(s,public
data), B- now applies its second oracle O+ to compute s.

Now we apply intuition: how can the oracle O+, which inverts TLS-PRF help at
all to solve the static DHP, which is defined purely in terms of a group?

In other words, any such B- really ought to work without needing to use O+,
so ought to solve static DHP.

So, the formal reduction for TLS-PRF-inverter-assisted static DHP can be
deemed as a pseudoreduction for plain old static DHP.

If the static DHP is hard, then it seems like static modes of TLS have a
security.  This is a kind of security proof.

Note, that TLS uses s in a way other than as static DHP, then the reductions
above fail.

Cheon's attack is a known attack against the static DHP, and sets an upper
bound for how hard the static DHP is in a group.

If we want to have the most benefit from the reduction and pseudoreduction
I've outlined above, then we should choose a group whose threshold against
static DHP could be as high as possible.

Just to be clear, we cannot reverse this reduction to apply Cheon's attack
against TLS-DH, because we do not know of any way to invert TLS-PRF.  

But if we value reductions, then why not choose a group in which static DHP
appears harder?  The point of reduction is to better than just avoid known
attacks, but to try to avoid unknown attacks.

Sure, it's may well possible to reduce to more complicated problems, oracle
DH, gap-hashed-DH, that combine properties of the group and hash, but this
brings the assumptions closer to what one is trying to prove.

Well, I hope that was clear enough.  I am sorry if I was unclear before,
because I did not really spell out the reductions above, even to myself.

Best regards,

Daniel Brown

Research In Motion Limited