Subject: [Cfrg] DDH, GapDH and Static DH [was RE: On Strong DH]

From: Dan Brown <[email-masked]>
Date: Wed, 7 May 2014 14:56:37 +0000

More theoretical discussion below that factors into whether to use more
conventional curves like P256, Brainpool, and Curve25519, or something more
radical, like Cheon-secure, and GapDH-friendly.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Watson Ladd
> My slides mentioned a reduction to the DDH. 

[DB] Nit on the direction of reductions. I think you meant a reduction of
DDH to TLS, not TLS to DDH.

A reductionist security proof for TLS-DH{E} handshake must assume something
about the PRF in addition to the DH group.

I think that abstracted hashed DH key agreement component can be proved
secure assuming a hard DDH, as you suggesting in a previous email, but also
with an additional assumption KDF/PRF.  I presume that this is actually a
well-known result, and probably implicit of some of the recent security
proof papers on TLS, which cover much more complicated TLS details and
security models.

Although a weak DDH is known to result in an attacked on hashed key
agreement schemes, a hard DDH can help in security proofs and to provide of
margin of error resisting a single point of failure in the PRF (or helping
in more esoteric security models like session state reveals). 

In an earlier email, I suggested using a weak DDH group: this would be
useful if the GapDH security proofs are somehow much better than DDH-base
proofs.  Hence it is a subject for further research.

> It's actually a reduction to what 
> has been called the strong DH assumption in some papers and books, namely

[DB] Good, but what is your reduction that other can verify?  A refereed
publication would be a bonus.

I think a recent IACR eprint by Maurer uses GapDH, among other things, to
prove the security of TLS-DHE.

> that calculating g^(ab) given g^a, g^b, and g is hard even when you can
check if
> your answer is correct. (It's this last subtlety that I forgot about)

[DB] That's what I thought was the GapDH: solving the CDH with the help of a
DDH oracle (even if the DDH oracle is only imaginary). 

That's why I recently suggested using a group in which the DDH oracle can be
made feasible.  Else, what's the use of a GapDH based security reduction
without any kind of DDH oracle?

Even with a DDH-oracle available, a GapDH proof seems weird to me.   If the
adversary can use the DDH-oracle, how can the reducer extract the
adversary's use of the DDH-oracle. That's another reason to label this a
long-term research topic.

Also, deliberately having a weak DDH undermines the security proof relying
on DDH, so there is a tension between GapDH and DDH.

> 
> This is not the strong DH assumption as defined in the paper of Cheon!

[DB] In an earlier paper, Rob Gallant and I called this the static DH
problem.  I suggest keeping with this precedent term "static".

Cheon generalized the attack to depend on n+1, instead of just n-1, so
Cheon's static DH attack supersedes ours.

Cheon applied the attack to pairings group (as did Rob earlier).

> That strong DH assumption is used in pairing based cryptography, and
assumes
> g^(ab) is hard to compute given an an oracle that calculates it unless you
feed
> the oracle g^b. Usually this is called the q-SDH, or l-SDH, where l or q
is the
> number of oracle queries allowed. It generally shows up in the context of
pairing
> based cryptography.

[DB] Other contexts where static DH is relevant:

- re-used static DH keys for key agreement
	- certain usually there's an extra layer of protection, e.g. a
one-way KDF or PRF, so
	- so the benefit of a hard static DHP is mainly for 
		- security proofs and 
		- margins of error (i.e. so PRF is not a single point of
failure),
- signatureless authentication with a DH style static key (similar to above)
- blinded services, e.g. blind signatures and password hardening, well this
is esoteric
- generic services, e.g. a hardware module stores a static DH key, for one
of the services above, but cannot bother with the complexity and variety of
KDFs: ANSI KDF, NIST KDF, TLS PRF, etc., well this is an implementation
convenience only.

Anyway, the main benefit of a hard static DHP (aka Cheon secure) is not for
TLS-ECDHE, but for having a multi-purpose curve.  

That said, there's that IACR eprint which uses the Strong PRF-ODH assumption
in a security proof for TLS-DHE.  As I said before, the Strong PRF-ODH
collapses into the static DH if the PRF collapses into the identity.  If
this is more than just an artefact of the proof technique, and due to some
characteristic of TLS, then maybe static DHP is more important to TLS-DHE
than I thought.  Or, maybe there's something in their security model, like a
corrupt client whose session state can be replayed.  I don't know.

The other point I was trying to make in my presentation, is that if we are
to speculate that secret attacks exist, e.g. against P256, then one strategy
to avoid the secret attack is to infer that secret attacks are most likely
to be similar to known attacks.  For example, Bernstein used this argument
to reason that the small coefficient size in Curve25519 is not a concern,
because no known attacks depend on coefficient size.  The flip side of this
argument is that we should try, if possible, to avoid secret attacks similar
to known attacks.  The Cheon attack is a known attack, and a secret attack
similar to it might depend on the same features in the factorization of n-1
and n+1.  

> 
> Strong DH (not the q-version), like CDH, is commonly believed as hard as
discrete
> log. Anyone with papers showing otherwise, please let us know. I don't
know of
> a reduction to CDH, although Gap DH, stronger than Strong DH, appears
true.
[DB] Since you asked, I have a theoretical result on the issue, in Theorem 3
in

http://eprint.iacr.org/2007/435

(These may be couple layers more theoretical than CFRG, sorry.)

---

From: Watson Ladd <[email-masked]>
Date: Wed, 7 May 2014 15:33:26 -0700

On Wed, May 7, 2014 at 7:56 AM, Dan Brown <[email-masked]> wrote:

> about the PRF in addition to the DH group.

In the case of DHE, you don't get to check your answers at all (the
ephemeral key changes), so it becomes CDH in the ROM, and DDH in the
standard model if no PRF is used. However, there isn't any reason not
to use a PRF.

In the case of DH (no E) you need a PRF to avoid the Cheon attack,
hence PRF-ODH. Now replace the PRF with a random oracle. Do that and
you see that the PRF-ODH is equivalent to the CDH with an answer
checking oracle. (This isn't Gap DH, because you can check your answer
for one g^a, that is the server's g^a, not all possible (g, g^a, g^b,
g^(ab)). The argument is as follows: a random oracle only reveals
equality of queried inputs, so you get to solve the CDH with an oracle
telling you if you got the right answer.

So yes, there is a PRF assumption, but it's the usual random oracle
one if you like the ROM. If you don't like the ROM you wind up with
something funny (PRF-ODH), but again, we don't know of any way to
solve the funny problem faster than taking a discrete log.

> similar to it might depend on the same features in the factorization of n-1

No, that isn't what DJB said. What he did is point out that all known
attacks on Curve25519 were hard. Secondly, the Cheon attack isn't an
"attack" on the DL, CDH, DDH, or even Gap DH assumptions, which most
key agreement protocols reduce to. Thirdly, it's a generic attack: we
know exactly how strong those are against DDH, CDH, and DL.

Any attack on ECC will require fundamentally new ideas. I'm not
convinced we can say anything meaningful about what those ideas will
look like, and I can't imagine this being a strong reason to require
new curves to satisfy anything more than the usual criteria. I think
we're going to have to agree to disagree on this one.

Sincerely,
Watson Ladd

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

---

From: Dan Brown <[email-masked]>
Date: Thu, 8 May 2014 14:26:32 +0000

Retracting my own terminology suggestion, adding more credit to Boneh et
al., and clarifying some things.

> From: Cfrg [mailto:[email-masked]] On Behalf Of Dan Brown
> Sent: Wednesday, May 07, 2014 10:57 AM
> 
> 
problem.  I
> suggest keeping with this precedent term "static".

[DB]  l retract this suggestion for two reasons:

1. Boneh defined the term q-strong DHP before our work, so q-strong has
precedent,
2. what we called the static DHP is different from the q -Strong DHP, as
explained below.

Our "static DHP" was to reproduce the raw static DH operation without the
private key.

Gallant and I described an algorithm that used a static DHP oracle to find
the corresponding private key, i.e. discrete log.

Informally, we showed: static_DHP => DLP.

We presented this both as attack when static_DHP oracles were exposed in
protocols, and as argument for the hardness of the static_DHP in other
cases.

One variant q-strong DHP can be expressed as the problem (static_DHP =>
DLP/other), as defined by Boneh et al (where the other can be some different
related task).

Boneh et al proved the strong DHP to be hard in the generic group model, but
only with n^(1/3) cost (including queries).

Our algorithm is the same as Cheon's when n-1 has a suitable factorization,
which is most of the time.  Cheon extended this to n+1.

A philosophical difficulty with our formulation the static DHP is that an
efficient algorithm exists to solve it, i.e. just using the private key.
This is like collision existing in SHA-3.  To get around this, one can take
Rogaway's approach as in the paper "Formalizing Human Ignorance ...", or use
the terminology of constructive v existential.  E.g. finding collisions in
SHA3 is existentially easy, because collisions exist, but constructively
hard, because the only known constructions are costly, i.e. use Floyd's
cycle finding algorithm.  Ditto for static DHP, existentially easy, but
constructively hard.

Anyway, the passive security of static DH-based requires the static DHP to
be hard: this is a necessary condition, regardless of any hashing of the
shared secret.

The active security of static DH-based does *not* require the strong DHP to
be hard, but many static DH-based schemes can be proved secure if the strong
DHP is hard.  I.e. it is a sufficient condition, but not a necessary
condition.  As such, it could be deemed as a nice-to-have.

There is a tension between these two aspects, but it may be possible to tune
the group parameters to get the best of both.