Subject: [Cfrg] Review of Dragonfly PAKE

From: Trevor Perrin <[email-masked]>
Date: Tue, 10 Dec 2013 14:30:48 -0800

Dear CFRG (cc: TLS),

Here's a review of the Dragonfly Password-Authenticated Key Exchange (PAKE) from
draft-irtf-cfrg-dragonfly-02 [CFRGDRAFT].

Overview
----
The Dragonfly PAKE is built on SPEKE with an "obfuscation" applied to
the exchange of Diffie-Hellman values.  The obfuscation lacks formal
analysis and serves no obvious purpose, but may be an attempt to avoid
the SPEKE patent [IPSEC].  Dragonfly has security weaknesses due to
use of a variable-time algorithm to map a password to an EC point
[STRUIK], and lack of "augmented" PAKE properties.

Obfuscating the SPEKE DH exchange
----
SPEKE is an old and well-known PAKE [JABLON].  In SPEKE each party
uses a shared password to derive a Diffie-Hellman generator.  The
generator is then used for a Diffie-Hellman exchange.

SPEKE is patented until 2017 [SPEKEPATENT].  Alternatives without
current patents incude [DH-EKE] and [J-PAKE].  Alternatives with
royalty-free terms include [SRP] and [AUGPAKE].

Dragonfly uses the SPEKE approach but obfuscates the exchange of DH
values.  In particular, given:

  g : DH generator (calculated by hashing the password)
  a : Alice's DH private key

In SPEKE, Alice sends g^a.

In Dragonfly, Alice generates a mask m, and sends (a+m, g^-m).  Bob
uses these values and g to reconstruct g^a.  [ g^a = g^(a+m) * g^-m ]

This obfuscation adds computation and bandwidth costs.  It's not clear
whether it adds any security benefit.  It's not clear how Dragonfly's
security relates to SPEKE; whether the SPEKE security proof from
[MACKENZIE] still applies; or whether another security proof could be
created.

The Dragonfly author argues that the SPEKE patent only covers use of a
"password-based parameter" with a "known technique of unauthenticated
key distribution" [IPSEC], and thus does not apply to Dragonfly.

It's not obvious that this is true.  Particularly given expiry of the
Lucent EKE/DH-EKE patents [LUCENT], the Dragonfly IPR situation seems
less clear than some alternatives.

Sidechannel attack on mapping password to EC point
----
Mapping a password onto a Diffie-Hellman generator is easy for
Diffie-Hellman with safe primes, which are typically used with SPEKE.
For ECDH, the naive "try-and-increment" algorithm for mapping to a
point leaks timing information about its input ([BONEH], [ICART]).

Nonetheless, this algorithm might be acceptable provided its input is
fixed for a given password.  Unfortunately, Dragonfly recommends
mixing nonces with the password prior to "hunting-and-pecking".  This
enables a timing attack:

 * The attacker initiates many protocol runs, recording the time taken
by the server to produce each Commit message.  (Alternatively, the
attacker passively observes many protocol runs.)

 * Afterwards, for each offline password guess, the attacker predicts
how long the "hunting-and-pecking" algorithm would have taken for each
run.

 * For a successful guess, the predictions will be correlated with
recorded times.

Dragonfly attempts to reduce this timing leak by performing the
"hunting-and-pecking" loop a fixed number of times (at least 40 is
recommended).  Yet within each loop are conditional branches and
Legendre symbol / square-root algorithms, which are hard to implement
efficiently in constant time ([STRUIK], [ICART], [FIPS186-4]).

This attack is easily avoided by omitting nonces from the input to the
"hunting-and-pecking" loop.  However, variants of the attack may be
possible (e.g. using salt to attack the client).  Difficulties of this
sort are why PAKE schemes often avoid the EC setting.

Non-augmented protocol
-----
Unlike [SRP] and [AUGPAKE], Dragonfly is a "balanced" PAKE, not an
"augmented" one.  This means that a Dragonfly server stores values
that can be used directly to authenticate to that server.  In
contrast, an SRP or AugPAKE server stores verifiers which would have
to be attacked by password-cracking.

Conclusions
------------
The Dragonfly approach seems inferior to existing PAKE schemes due to:
 * Lack of formal security proofs or extensive cryptanalysis
 * An unclear IPR situation compared to alternatives
 * High computation cost due to "hunting-and-pecking" and "DH obfuscation"
 * Side-channel risks due to "hunting-and-pecking"
 * Non-augmented properties

Trevor

[CFRGDRAFT] http://tools.ietf.org/html/draft-irtf-cfrg-dragonfly-02
[IPSEC] http://www.ietf.org/mail-archive/web/ipsec/current/msg06323.html
[STRUIK]
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03259.html
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03489.html
  http://www.ietf.org/mail-archive/web/cfrg/current/msg03527.html
[JABLON]
  http://www.jablon.org/jab96.pdf
  http://www.jablon.org/jab97.pdf
[SPEKEPATENT]
  https://www.google.com/patents/US6226383
  https://www.google.com/patents/US6792533
[DH-EKE]
  http://www.cs.columbia.edu/~smb/papers/neke.ps
  http://eprint.iacr.org/2000/014.pdf
[J-PAKE] http://eprint.iacr.org/2010/190.pdf
[SRP]
  http://tools.ietf.org/html/rfc5054
  http://srp.stanford.edu/design.html
[AUGPAKE] https://eprint.iacr.org/2010/334.pdf
[MACKENZIE] https://eprint.iacr.org/2001/057.pdf
[LUCENT] http://www.ietf.org/mail-archive/web/tls/current/msg08191.html
[BONEH] http://cseweb.ucsd.edu/~hovav/dist/sigs.pdf
[ICART] http://www.iacr.org/archive/crypto2009/56770300/56770300.pdf
[FIPS186-4] http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

---

From: "Dan Harkins" <[email-masked]>
Date: Tue, 10 Dec 2013 17:35:51 -0800 (PST)

Hi Trevor,

On Tue, December 10, 2013 2:30 pm, Trevor Perrin wrote:
> the exchange of Diffie-Hellman values.

  I disagree with this over-simplification.

>                                                             The
obfuscation
lacks formal
> [STRUIK], and lack of "augmented" PAKE properties.

  What is a "weakness" from the point of view of an augmented PAKE
scheme is a benefit from the point of view of a balanced PAKE scheme.
Augmented PAKE schemes bind the password to a single domain
parameter set while balanced PAKE schemes allow for the domain
parameter set to be negotiated. This allows, for example, a domain
parameter set to be agreed upon that provides commensurate
security to the rest of the cipher suite with which it can be used.

  It makes little sense to negotiate a 256-bit or even a 128-bit
cipher or a hash algorithm with a 256-bit or 512-bit digest size
when the domain parameter set is fixed to a 1024-bit FFC group.
What makes sense is to allow for negotiation of a 4096-bit FFC
group or a 256-bit ECC group along with your AES-GCM-128
with key derivation using HMAC-256.

  Of course, you may disagree (in fact, I'll bet money on it). But
I hope you do not feel that your opinion is the only valid one. I
respect your opinion on the matter, I just don't know why you
fail to respect the opinion of anyone who has a different evaluation
of that cost-benefit equation.

  A balanced PAKE scheme in addition to the existing augmented
PAKE scheme offers choice. You want to restrict and prohibit
choice.

> royalty-free terms include [SRP] and [AUGPAKE].

  AugPAKE has particularly nasty terms as the license explicitly
states that the "royalty-free" license does not cover all the claims
in the patent yet it does not spell out exactly which ones are or
are not covered. If your legal council advises you accept such a
license I'd advise you get new legal council.

> [MACKENZIE] still applies; or whether another security proof could be

  Apparently much is not clear to you. I will tell you that I do not believe
that sending (a+m, g^-m) with a password-derived g has any security
benefits over sending g^a with a password-derived g. Does that clear
anything up?

> It's not obvious that this is true.

  That is truly a content-free statement, especially given the subject matter
(IPR). The reference you give goes to some lengths to explain the rationale
behind that statement. Sadly your response does not address any points
made in that reference, and, in fact, contributes nothing. Maybe this too is
not clear to you so let me give a brief attempt to make it more obvious:

  - if you replace the password-derived generator from SPEKE with the
     generator from the domain parameter set what do you have? You have
     the Diffie-Hellman key exchange, a "known technique of unauthenticated
     key distribution."

  - if you replace the password-derived generator from dragonfly with
     the generator from the domain parameter set what do you have? Well,
     whatever it is it is certainly not a "known technique of unauthenticated
     key distribution." I had never seen this technique of unauthenticated
     key distribution. If you have, please provide me with a reference from
     before 2007 or so.

>                                                      Particularly given
expiry of the
> less clear than some alternatives.

  The existence of "alternatives" is really irrelevant to the subject of
your email-- a review of dragonfly. Yes there are numerous ways to skin
a cat. So what?

> mixing nonces with the password prior to "hunting-and-pecking".  This

  This has been discussed on both the TLS and CFRG lists already.

> how long the "hunting-and-pecking" algorithm would have taken for each

  Except that the amount of time is hidden by a constant number of
loops through the hunting-and-pecking loop. Given that randomness
replaces the base once PE is obtained, it makes it all the more difficult
for the attacker to use any recorded time from a run of the protocol
or to make any prediction on the amount of time it would take.

>  * For a successful guess, the predictions will be correlated with

  Which given the additional randomness will not correlate in a
way that allows the attacker to reduce the size of the pool from
which the password was chosen.

> efficiently in constant time ([STRUIK], [ICART], [FIPS186-4]).

  It also adds randomness into the loop once PE is found, which
will be with probability 1 - (q/2p)^n, after n loops (where q is the
order of the domain parameter set and p is the prime).

  And that's why it continues to loop through a fixed number of times,
in order to hide the number of times it took to find the solution.

> sort are why PAKE schemes often avoid the EC setting.

  The current "hunting-and-pecking" text in draft-ietf-tls-pwd is
the result of a discussion with numerous people on a long thread on
the TLS list from an earlier version of the draft. Given that you have
obviously spent a considerable amount of time scouring through
numerous email lists that should be known to you. I'm not really sure
why you have waited until now to comment on it but I'm glad you have,
so let me ask:

  - what change would you like to see in the text and why? And,

  - if I accommodated your change would you support this draft?

> to be attacked by password-cracking.

  This is well-known and mentioned in the Security Considerations.
As mentioned above, the benefit to this cost is that the domain
parameter set is not fixed to a password. And, as I mentioned, while
you may not view that benefit as outweighing the cost, your opinion
is not the ultimate truth on the subject, other people may evaluate
that equation differently and just because they do does not mean
they're wrong.

  As I mentioned above, having a balanced PAKE protocol (dragonfly)
as well as an augmented PAKE protocol (SRP) allows for freedom of
choice. What you are advocating for is less choice, and in fact,
restricting everyone to what you would choose. That is a somewhat
arrogant position.

  I'm also not sure why you have become a cheerleader for AugPAKE,
especially given your previous statements about: 1) how nobody
wants any PAKE solution in TLS; 2) that we have SRP and that can
address the few people (in your mind) who want it; and, 3) how you
would be against any additional PAKE scheme in TLS. It's especially
bizarre given that AugPAKE offers nothing on top of what SRP already
offers.

> Conclusions

  It is extremely clear; it's not patented. Would you would like me to give
you a "royalty-free" license to use an unpatented protocol? Would you like
it to include all of the claims in a patent that does not exist or would you
be OK with it if it excluded some claims in a patent that does not exist?

>  * Non-augmented properties

  Aside from the last one, which is your personal preference which has
really no bearing on the personal preferences of anyone else, what would
you like to see change in the draft?

  regards,

  Dan.

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 10 Dec 2013 17:54:32 -0800

> [MACKENZIE] still applies; or whether another security proof could be
Note Bena: The proof does not address resistance to offline attack,
and uses an assumption that
isn't know to be equivalent to anything.

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 11 Dec 2013 11:50:47 -0800

> with key derivation using HMAC-256.

It makes little sense to use a 1024-bit FFC group in any circumstances
because (pardon me, Kevin) - fuck the NSA.

Having server-side password-data be flexible to different DH groups
seems of little value.  For a typical password auth performed over an
existing encrypted session, the PAKE DH group is already decoupled
from the session's DH group.

I prefer the security benefit of an augmented PAKE.

> PAKE scheme offers choice. You want to restrict and prohibit

I think augmented PAKEs are preferable.  But if you really want a
balanced PAKE, there are many better than Dragonfly (e.g. DH-EKE,
SPAKE2, J-PAKE).

> license I'd advise you get new legal council.

The AugPAKE IPR declaration is not a license, it's a declaration that
the AugPAKE patent holders will make a royalty-free license available
*if* the IETF adopts AugPAKE on the standard track.

I hope the AugPAKE inventors have seen enough IETF incompetence to
rethink tying AugPAKE's future to the IETF.  I would certainly prefer
a royalty-free license without such restrictions.

But I see no basis for questioning the honesty of the AugPAKE IPR declaration.

> benefits over sending g^a with a password-derived g. Does that clear

Yes.  You added a gimmick to SPEKE, hoping to avoid its IPR.

> made in that reference, and, in fact, contributes nothing.

That thread develops your theory about how the SPEKE patent only
applies to a "known technique of unauthenticated key distribution",
and how your gimmick transforms DH into something unknown, thus
avoiding it.

I'm not qualified to assess this argument, but it seems dubious.  The
primary innovation in SPEKE is mapping a password to a DH base point,
which is used in Dragonfly.  Adding innovations onto an existing
patented work does not free you from the earlier patent.

Perhaps I'm wrong.  But the patent situation in the rest of the PAKE
world seems much clearer.  The last Lucent EKE patent expired a few
months ago.  As that was from the inventors of the PAKE concept, it
cast a bit of a pall over the whole area.  But now that's gone.

I'm particularly leery of the SPEKE patents, as the patent holder used
to aggressively pursue licensing.

So while I support steering clear of difficult IPR, I think there are
easier ways of doing it.

> Maybe this too is

To me, it looks like Diffie-Hellman with a silly gimmick.

> or to make any prediction on the amount of time it would take.

Except that sidechannel attacks use statistics, so injecting noise
just increases the number of measurements required.

Modern crypto practice is to prefer constant-time algorithms when
remote timing attacks are possible, as in this case.

> numerous email lists that should be known to you.

Yes, I see people like Rene Struik recommended not mixing the nonces
in multiple times [1,2].

Even Kevin Igoe - a fount of bad advice, generally - mentioned this
once, before agreeing that just looping a shit-ton of times was an
"elegant change" [3,4].

> I'm not really sure

I won't support this draft even with the gratuitous sidechannel problem fixed.

I think it's a bad PAKE and there are many better ones (DH-EKE,
SPAKE2, J-PAKE, SRP, AugPAKE, and probably others).

> bizarre given that AugPAKE offers nothing on top of what SRP already

1 and 2 are true.  I don't understand why CFRG is reviewing this, or
why the TLS WG is considering TLS-PWD.

According to chair Kevin Igoe, Dragonfly "fills a real need" [5].
Perhaps he can explain.

(I'm not a cheerleader for AugPAKE.  It's one of many protocols that
are better than Dragonfly).

> be OK with it if it excluded some claims in a patent that does not exist?

I'd prefer to use PAKEs which steer clear of the SPEKE approach entirely.

> you like to see change in the draft?

I don't support this draft.  I think it's a bad PAKE and there are better ones.

Trevor

[1] http://www.ietf.org/mail-archive/web/cfrg/current/msg03489.html
[2] http://www.ietf.org/mail-archive/web/cfrg/current/msg03527.html
[3] http://www.ietf.org/mail-archive/web/cfrg/current/msg03258.html
[4] http://www.ietf.org/mail-archive/web/cfrg/current/msg03262.html
[5] http://www.ietf.org/mail-archive/web/cfrg/current/msg03383.html

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 11 Dec 2013 14:07:09 -0800 (PST)

> On Tue, Dec 10, 2013 at 5:35 PM, Dan Harkins <[email-masked]> wrote:
[snip]
> because (pardon me, Kevin) - fuck the NSA.

  That certainly is a fashionable pose to strike these days!

  But I brought up binding a 1024-bit FFC to a password because that's
what an RFC with your name on it does. So it makes sense to replace
"the NSA" in your sentence with "Trevor Perrin".

  Dan.

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 11 Dec 2013 14:34:22 -0800

On Wed, Dec 11, 2013 at 2:07 PM, Dan Harkins <[email-masked]> wrote:
> what an RFC with your name on it does.

RFC 5054 has a range of DH groups.  I would've preferred not to
include the lower-strength ones.

Care to respond to any other points, or can we assume Dragonfly is
debunked at this point?

Trevor

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 11 Dec 2013 15:04:01 -0800 (PST)

> Care to respond to any other points, or can we assume Dragonfly is

  Your post was a series of personal opinions that were caveated with
things like "I'm not qualified to assess this argument" and "Perhaps I'm
wrong." You restated your preference favoring augmented PAKEs for the
umpteenth time-- "I prefer the security benefit of augmented PAKE"--
and for the umpteenth plus one time-- "I think augmented PAKEs
are preferable." And you called dragonfly "gimmicky" and "a bad PAKE".

  I already responded to the points you raised originally. You replied with
a bunch of opinions. I'll just let those stand.

  Debunked? Ha ha. You sure think highly of yourself.

  Dan.